Пример использования процессорного кэша

задачу отключения процессорного кэша :)))

умножение двух матриц

root@murr:/tmp # cat zzz.c 
#define _GNU_SOURCE        
#include <stdio.h>         
#include <stdlib.h>        
#include <sys/mman.h>      
#include <sys/time.h>      
#include <sched.h>         
#include <assert.h>        

#define ARRAY_SIZE 1048576*100

unsigned long mcd(unsigned long a, unsigned long b)
{                                                  
        while (a != 0 && b != 0) {                 
                if (a > b) a %= b;                 
                else b %= a;                       
        }                                          
        return a + b;                              
}                                                  

void add(char *a, char *b, unsigned long num, unsigned long sf)
{
        int i = 0;

        assert(mcd(num, sf) == 1);

        do {
                a[i] += b[i];
                i = (i + sf) % num;
        } while (i != 0);
}

int main(int argc, char *argv[])
{
        char *a, *b;
        int rc;
        unsigned long sf;
        struct timeval tv1, tv2;
        cpu_set_t cpusetp;

        assert(argc == 2);
        sf = atoi(argv[1]);

        CPU_ZERO(&cpusetp);
        CPU_SET(0, &cpusetp);

        a = (char *)malloc(ARRAY_SIZE);
        assert(a != (char *)NULL);
        b = (char *)malloc(ARRAY_SIZE);
        assert(b != (char *)NULL);

        rc = mlockall(MCL_CURRENT | MCL_FUTURE);
        assert(rc == 0);
        rc = gettimeofday(&tv1, NULL);
        assert(rc == 0);
        rc = sched_setscheduler(0, SCHED_RR, &(const struct sched_param){ .sched_priority = 1 });
        assert(rc == 0);
        rc = sched_setaffinity(0, sizeof(cpusetp), &cpusetp);
        assert(rc == 0);

        add(a, b, ARRAY_SIZE, sf);

        rc = gettimeofday(&tv2, NULL);
        assert(rc == 0);
        rc = munlockall();
        assert(rc == 0);

        free(a);
        free(b);

        printf("~%d ms\n", (int)(tv2.tv_sec - tv1.tv_sec));

        return 0;
}
root@murr:/tmp # gcc zzz.c -O3
root@murr:/tmp # ./a.out 1
~1 ms
root@murr:/tmp # ./a.out 1
~1 ms
root@murr:/tmp # ./a.out 1
~1 ms
root@murr:/tmp # ./a.out 33
~2 ms
root@murr:/tmp # ./a.out 33
~2 ms
root@murr:/tmp # ./a.out 131
~4 ms
root@murr:/tmp # ./a.out 131
~4 ms

s/ms/s/

проще выключить кеш в bios-е и оценить всю глубину разницы с и без :)

// wbr

> проще выключить кеш в bios-е и оценить всю глубину разницы с и без :)

Я такой биос в последний раз видел в 2003 году.

> проще выключить кеш в bios-е и оценить всю глубину разницы с и без :)

вопрос был не в этом -- человеку хочется увидеть вариант cache-friendly программы, которая работает в 2 раза быстрее враждебной кэшу.

можно попробовать складывать матрицы по столбцам

кстати, самому интересно стало.

$ bash test4.c 8 1234567 10
start:
BAD

real 0m1.406s
user 0m1.236s
sys 0m0.104s
start:
GOOD

real 0m18.600s
user 0m17.625s
sys 0m0.096s


Что интересно, в 10 раз быстрее работает то, что я думал будет работать медленнее. Тестировалось на стоящем без дела селероне 1500 gcc (GCC) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)

щас запощщу тест

#usage: bash test4.c 8 1234567 10

echo -e "#define I $1 \n#define J $2 \n#define K $3 \n" > tmp1.c
echo '

#include <stdio.h>
#include <stdlib.h>


inline void bad( int a[I][J], int b[I][J], int c[I][J] )
{
    puts("BAD"); int i,j,k;
    for( k=0; k<K; k++ ) 
        for( j=0; j<J; j++)
    	    for( i=0; i<I; i++) 
		c[i][j]=a[i][j]+b[i][j];
}
inline void good( int a[I][J], int b[I][J], int c[I][J] )
{
    puts("GOOD"); int i,j,k;
    for( k=0; k<K; k++ ) 
        for( i=0; i<I; i++) 
    	    for( j=0; j<J; j++)
		c[i][j]=a[i][j]+b[i][j];
}
int main(int argc, char** argv)
{
    void* a = malloc(sizeof(int)*I*J); if( !a ) return 2;
    void* b = malloc(sizeof(int)*I*J); if( !b ) return 3;
    void* c = malloc(sizeof(int)*I*J); if( !c ) return 4;
    puts("start:");

#ifdef BAD
        bad(a,b,c);
#else
	good(a,b,c);
#endif
    return 0;
}

'>>tmp1.c

gcc -O3 -Wall -DBAD tmp1.c -o tmp-bad  && time ./tmp-bad
gcc -O3 -Wall       tmp1.c -o tmp-good && time ./tmp-good

> gcc -O3 -Wall -DBAD tmp1.c -o tmp-bad && time ./tmp-bad > gcc -O3 -Wall tmp1.c -o tmp-good && time ./tmp-good

Оптимизатор гцц все портит. У меня в этом тесте одинаково, а с O2 выигрывает GOOD в полтора раза.

А на умножении матриц: с O2 хороший лучше в 1.5 раза, с O3 - в 10 о_О

>проще выключить кеш в bios-е и оценить всю глубину разницы с и без :)

А что, есть BIOS'ы которые отрубают L1 кеш?

Вообще-то, постановка prefetch(...) вполне может считаться тем самым 2-м cache-friendly способом.