Shaos wrote:Еще я написал текстовую программку чтобы выяснить какого размера должна быть таблица байтов, чтобы при обращении к ней по индексу не было бы потерь на копирование из памяти в кеш данных - и у меня получилось, наращивая размер таблицы от 2^1 и далее 2^2, 2^3 и т.д., что до 2^14 индексирование случайным индексом идет абсолютно одинаковое время, а вот далее - скорость обращения падает в 2 и более раз...
Текст программки под спойлером и мои результаты с 64-битного дебиян-линуха на амд64 ниже:
lutest.cCode: Select all
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
#define N INT_MAX
#define T char
#define M 0xFF
int main(int argc, char **argv)
{
int i,j,k,l,n,m;
unsigned int s;
time_t t1,t2;
T *a;
if(argc<2) n = 22;
else n = atoi(argv[1]);
if(n==0) return -1;
for(l=1;l<=n;l++)
{
k = 1<<l;
m = k - 1;
a = (T*)malloc(k*sizeof(T));
if(a==NULL) return -2;
srand(time(NULL));
for(i=0;i<k;i++) a[i]=rand()+(rand()<<15);
i = s = 0;
t1 = time(NULL);
for(j=0;j<N;j++)
{
s += ((unsigned)a[i])&M;
i = (i+j+j+s)&m;
}
t2 = time(NULL);
printf("%8.8X 2^%i * %i -> %is\n",s,l,N,(int)(t2-t1));
free(a);
}
return 0;
}
Code: Select all
FFFFFF68 2^1 * 2147483647 -> 5s
AAAAAA18 2^2 * 2147483647 -> 6s
BFFFFFC2 2^3 * 2147483647 -> 5s
0000004B 2^4 * 2147483647 -> 6s
5C87B6EE 2^5 * 2147483647 -> 5s
DB6DB6B0 2^6 * 2147483647 -> 6s
1ED7E6C8 2^7 * 2147483647 -> 5s
CB4F4C26 2^8 * 2147483647 -> 6s
7E567055 2^9 * 2147483647 -> 6s
E721A4D4 2^10 * 2147483647 -> 5s
594CD3B9 2^11 * 2147483647 -> 6s
EC14A96A 2^12 * 2147483647 -> 6s
6551305A 2^13 * 2147483647 -> 5s
7C903FFD 2^14 * 2147483647 -> 6s
64DE1F79 2^15 * 2147483647 -> 15s
AFB68EBD 2^16 * 2147483647 -> 17s
CE4B0F09 2^17 * 2147483647 -> 18s
902C7F06 2^18 * 2147483647 -> 19s
AB68549C 2^19 * 2147483647 -> 28s
D0ECA61B 2^20 * 2147483647 -> 34s
A5FF4DB7 2^21 * 2147483647 -> 73s
CA388996 2^22 * 2147483647 -> 160s
Если у кого есть желание может попробовать на своём компьютере (собирать
gcc -O2 lutest.c -o lutest запускать без параметров) и запостить результаты сюда
P.S. Да, похоже так и есть - у AMD процессоров размер L1 кеша данных 16кб (у меня семейство Bulldozer с микроархитектурой Steamroller):
https://www.extremetech.com/extreme/188776-how-l1-and-l2-cpu-caches-work-and-why-theyre-an-essential-part-of-modern-chips
AMD64-CacheChart.png
L1 имеет задержку на доступ 3-4 такта, а L2 - уже 19 тактов (у Steamroller-a), поэтому массивы больше 16кб имеют в среднем в 5 раз более худшие времена доступа если лезть в них действительно случайным образом. Вот инфа про мою 4-коровую (+ 8 графических коров, которые в линухе не юзаются) конфигурацию AMD-проца:
http://www.cpu-world.com/CPUs/Bulldozer/AMD-A10-Series%20A10-7850K.html (там правда написано
4 x 16 KB 4-way set associative data caches, т.е. их четыре - видимо один и тот же массив больше 16кб не может быть аккуратно порезан на разные кеши)
P.P.S. Intel Core i5 вроде как имеет 6 x 32KB 8-way дата кэш - там наверное результаты моей программки сдвинуться и до 2^15...
P.P.P.S. Так и есть - проверил на Intel Core Duo с WinXP в Cigwin:
IntelCoreDuo.gif
P.P.P.P.S. Откопал свой чёрный
G4 Cube и как ни странно он живой
Я его "потерял" при переезде из Нью-Йорка в 2017, а вот сейчас "нашёл" когда коробки для очередного переезда перепаковывал
Вот его результаты, подтверждающие информацию, что процессор PowerPC G4 имеет L1 кеш данных размером 32кб:
Code: Select all
shaos@g4cube:~/Sources/tests$ ./lutest
FFFFFF9A 2^1 * 2147483647 -> 26s
71C71C0C 2^2 * 2147483647 -> 25s
C30C3108 2^3 * 2147483647 -> 28s
1642C9D6 2^4 * 2147483647 -> 30s
1C71C59A 2^5 * 2147483647 -> 30s
A98EF52C 2^6 * 2147483647 -> 30s
30201446 2^7 * 2147483647 -> 30s
3658AAB7 2^8 * 2147483647 -> 30s
0F83DFB4 2^9 * 2147483647 -> 30s
124C7633 2^10 * 2147483647 -> 30s
3A5A0095 2^11 * 2147483647 -> 33s
66C9001B 2^12 * 2147483647 -> 30s
27B43966 2^13 * 2147483647 -> 30s
9ED6807C 2^14 * 2147483647 -> 30s
886A5016 2^15 * 2147483647 -> 31s
BB4554A4 2^16 * 2147483647 -> 64s
CDBA02EA 2^17 * 2147483647 -> 83s
B15AC01C 2^18 * 2147483647 -> 101s
EF4C360E 2^19 * 2147483647 -> 180s
C11A763B 2^20 * 2147483647 -> 388s
AA959D8B 2^21 * 2147483647 -> 582s
B72B2E0A 2^22 * 2147483647 -> 703s
Так же можно видеть, что копирование байтов из L1 кеша данных в G4 медленнее в 5-6 раз чем у AMD или Intel (разница частоты процессоров - как раз те самые 6 раз)
You do not have the required permissions to view the files attached to this post.
