Стресс-тест на отсутствие кеша: потрясающие результаты … есть объяснения?
Чтобы получить реальную производительность современного компьютера относительно пропусков кэша (как «распределяются» данные в памяти), я провел простой тест, в котором выделяю 500 МБ ОЗУ, а затем выполняю постоянное количество операций чтения и Я выполняю этот тест с увеличением смещения байтов. Наконец, я обертываю конец буфера 1000 МБ, когда достигаю его.
Я весьма удивлен результатами. Похоже, что существует барьер стоимости около 32 байтов, а еще один около 32 КБ. Я полагаю, это как-то связано с загрузкой кэша L1 / L2 / L3 или размером страницы виртуальной памяти? Что меня больше всего поразило, так это то, что кешируется всего около 16 абсолютно разных областей памяти. Это очень низко !!! Любые объяснения (ОС, оборудование)?
Вот результаты на 3 разных компьютерах, от самого быстрого до самого дешевого, за которым следует мой простой тестовый код (использует только стандартные библиотеки).
16 ГБ ОЗУ для быстрой рабочей станции HP (тест в 32-битной Windows):
time=0.364000 byteIncrement=4 numReadLocations=262144000 numReads=262144000
time=0.231000 byteIncrement=8 numReadLocations=131072000 numReads=262144000
time=0.339000 byteIncrement=16 numReadLocations=65536000 numReads=262144000
time=0.567000 byteIncrement=32 numReadLocations=32768000 numReads=262144000
time=1.177000 byteIncrement=64 numReadLocations=16384000 numReads=262144000
time=1.806000 byteIncrement=128 numReadLocations=8192000 numReads=262144000
time=2.293000 byteIncrement=256 numReadLocations=4096000 numReads=262144000
time=2.464000 byteIncrement=512 numReadLocations=2048000 numReads=262144000
time=2.621000 byteIncrement=1024 numReadLocations=1024000 numReads=262144000
time=2.775000 byteIncrement=2048 numReadLocations=512000 numReads=262144000
time=2.908000 byteIncrement=4096 numReadLocations=256000 numReads=262144000
time=3.007000 byteIncrement=8192 numReadLocations=128000 numReads=262144000
time=3.183000 byteIncrement=16384 numReadLocations=64000 numReads=262144000
time=3.758000 byteIncrement=32768 numReadLocations=32000 numReads=262144000
time=4.287000 byteIncrement=65536 numReadLocations=16000 numReads=262144000
time=6.366000 byteIncrement=131072 numReadLocations=8000 numReads=262144000
time=6.124000 byteIncrement=262144 numReadLocations=4000 numReads=262144000
time=5.295000 byteIncrement=524288 numReadLocations=2000 numReads=262144000
time=5.540000 byteIncrement=1048576 numReadLocations=1000 numReads=262144000
time=5.844000 byteIncrement=2097152 numReadLocations=500 numReads=262144000
time=5.785000 byteIncrement=4194304 numReadLocations=250 numReads=262144000
time=5.714000 byteIncrement=8388608 numReadLocations=125 numReads=262144000
time=5.825000 byteIncrement=16777216 numReadLocations=62 numReads=262144000
time=5.759000 byteIncrement=33554432 numReadLocations=31 numReads=262144000
time=2.222000 byteIncrement=67108864 numReadLocations=15 numReads=262144000
time=0.471000 byteIncrement=134217728 numReadLocations=7 numReads=262144000
time=0.377000 byteIncrement=268435456 numReadLocations=3 numReads=262144000
time=0.166000 byteIncrement=536870912 numReadLocations=1 numReads=262144000
4 ГБ ОЗУ MacBookPro 2010 (тест в 32-битной Windows):
time=0.476000 byteIncrement=4 numReadLocations=262144000 numReads=262144000
time=0.357000 byteIncrement=8 numReadLocations=131072000 numReads=262144000
time=0.634000 byteIncrement=16 numReadLocations=65536000 numReads=262144000
time=1.173000 byteIncrement=32 numReadLocations=32768000 numReads=262144000
time=2.360000 byteIncrement=64 numReadLocations=16384000 numReads=262144000
time=3.469000 byteIncrement=128 numReadLocations=8192000 numReads=262144000
time=3.990000 byteIncrement=256 numReadLocations=4096000 numReads=262144000
time=3.549000 byteIncrement=512 numReadLocations=2048000 numReads=262144000
time=3.758000 byteIncrement=1024 numReadLocations=1024000 numReads=262144000
time=3.867000 byteIncrement=2048 numReadLocations=512000 numReads=262144000
time=4.275000 byteIncrement=4096 numReadLocations=256000 numReads=262144000
time=4.310000 byteIncrement=8192 numReadLocations=128000 numReads=262144000
time=4.584000 byteIncrement=16384 numReadLocations=64000 numReads=262144000
time=5.144000 byteIncrement=32768 numReadLocations=32000 numReads=262144000
time=6.100000 byteIncrement=65536 numReadLocations=16000 numReads=262144000
time=8.111000 byteIncrement=131072 numReadLocations=8000 numReads=262144000
time=6.256000 byteIncrement=262144 numReadLocations=4000 numReads=262144000
time=6.311000 byteIncrement=524288 numReadLocations=2000 numReads=262144000
time=6.416000 byteIncrement=1048576 numReadLocations=1000 numReads=262144000
time=6.635000 byteIncrement=2097152 numReadLocations=500 numReads=262144000
time=6.530000 byteIncrement=4194304 numReadLocations=250 numReads=262144000
time=6.544000 byteIncrement=8388608 numReadLocations=125 numReads=262144000
time=6.545000 byteIncrement=16777216 numReadLocations=62 numReads=262144000
time=5.272000 byteIncrement=33554432 numReadLocations=31 numReads=262144000
time=1.524000 byteIncrement=67108864 numReadLocations=15 numReads=262144000
time=0.538000 byteIncrement=134217728 numReadLocations=7 numReads=262144000
time=0.508000 byteIncrement=268435456 numReadLocations=3 numReads=262144000
time=0.817000 byteIncrement=536870912 numReadLocations=1 numReads=262144000
4Гб оперативной памяти дешевого Acer «семейный компьютер»:
time=0.732000 byteIncrement=4 numReadLocations=262144000 numReads=262144000
time=0.549000 byteIncrement=8 numReadLocations=131072000 numReads=262144000
time=0.765000 byteIncrement=16 numReadLocations=65536000 numReads=262144000
time=1.196000 byteIncrement=32 numReadLocations=32768000 numReads=262144000
time=2.318000 byteIncrement=64 numReadLocations=16384000 numReads=262144000
time=2.483000 byteIncrement=128 numReadLocations=8192000 numReads=262144000
time=2.760000 byteIncrement=256 numReadLocations=4096000 numReads=262144000
time=3.194000 byteIncrement=512 numReadLocations=2048000 numReads=262144000
time=3.369000 byteIncrement=1024 numReadLocations=1024000 numReads=262144000
time=3.720000 byteIncrement=2048 numReadLocations=512000 numReads=262144000
time=4.842000 byteIncrement=4096 numReadLocations=256000 numReads=262144000
time=5.797000 byteIncrement=8192 numReadLocations=128000 numReads=262144000
time=9.865000 byteIncrement=16384 numReadLocations=64000 numReads=262144000
time=19.273000 byteIncrement=32768 numReadLocations=32000 numReads=262144000
time=19.282000 byteIncrement=65536 numReadLocations=16000 numReads=262144000
time=19.606000 byteIncrement=131072 numReadLocations=8000 numReads=262144000
time=20.242000 byteIncrement=262144 numReadLocations=4000 numReads=262144000
time=20.956000 byteIncrement=524288 numReadLocations=2000 numReads=262144000
time=22.627000 byteIncrement=1048576 numReadLocations=1000 numReads=262144000
time=24.336000 byteIncrement=2097152 numReadLocations=500 numReads=262144000
time=24.403000 byteIncrement=4194304 numReadLocations=250 numReads=262144000
time=23.060000 byteIncrement=8388608 numReadLocations=125 numReads=262144000
time=20.553000 byteIncrement=16777216 numReadLocations=62 numReads=262144000
time=14.460000 byteIncrement=33554432 numReadLocations=31 numReads=262144000
time=1.752000 byteIncrement=67108864 numReadLocations=15 numReads=262144000
time=0.963000 byteIncrement=134217728 numReadLocations=7 numReads=262144000
time=0.687000 byteIncrement=268435456 numReadLocations=3 numReads=262144000
time=0.453000 byteIncrement=536870912 numReadLocations=1 numReads=262144000
Код:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MEMBLOCSIZE ((2<<20)*500)//1000MB
int readMemory( int* data, int* dataEnd, int numReads, int incrementPerRead ) {
int accum = 0;
int* ptr = data;
while(true) {
accum += *ptr;
if( numReads-- == 0)
return accum;
ptr += incrementPerRead;
if( ptr >= dataEnd )
ptr = data;
}
}
int main()
{
int* data = (int*)malloc(MEMBLOCSIZE);
int* dataEnd = data+(MEMBLOCSIZE / sizeof(int));
int numReads = (MEMBLOCSIZE / sizeof(int));
int dummyTotal = 0;
int increment = 1;
for( int loop = 0; loop < 28; ++loop ) {
int startTime = clock();
dummyTotal += readMemory(data, dataEnd, numReads, increment);
int endTime = clock();
double deltaTime = double(endTime-startTime)/double(CLOCKS_PER_SEC);
printf("time=%f byteIncrement=%d numReadLocations=%d numReads=%d\n",
deltaTime, increment*sizeof(int), MEMBLOCSIZE/(increment*sizeof(int)), numReads);
increment *= 2;
}
//Use dummyTotal: make sure the optimizer is not removing my code...
return dummyTotal == 666 ? 1: 0;
}
Основываясь на некоторых комментариях, я изменил свой тест, чтобы использовать только 250 МБ ОЗУ и делать 16 последовательных чтений для каждого «чтения» в случае, если он активирует предварительную выборку. Он по-прежнему имеет аналогичные результаты, однако это тот случай, когда последние тесты, считывающие несколько удаленных местоположений, имеют лучшую производительность (2 секунды вместо 5), так что, вероятно, предварительная выборка не была активирована при начальном тесте.
#define MEMBLOCSIZE 262144000//250MB
int readMemory( int* data, int* dataEnd, int numReads, int incrementPerRead ) {
int accum = 0;
int* ptr = data;
while(true) {
accum += *ptr;
if( numReads-- == 0)
return accum;
//Do 16 consecutive reads
for( int i = 1; i < 17; ++i )
accum += *(ptr+i);
ptr += incrementPerRead;
if( ptr >= dataEnd+17 )
ptr = data;
}
}
Результаты этого обновленного теста для MacBookPro 2010:
time=0.691000 byteIncrement=4 numReadLocations=65536000 numReads=65536000
time=0.620000 byteIncrement=8 numReadLocations=32768000 numReads=65536000
time=0.715000 byteIncrement=16 numReadLocations=16384000 numReads=65536000
time=0.827000 byteIncrement=32 numReadLocations=8192000 numReads=65536000
time=0.917000 byteIncrement=64 numReadLocations=4096000 numReads=65536000
time=1.440000 byteIncrement=128 numReadLocations=2048000 numReads=65536000
time=2.646000 byteIncrement=256 numReadLocations=1024000 numReads=65536000
time=3.720000 byteIncrement=512 numReadLocations=512000 numReads=65536000
time=3.854000 byteIncrement=1024 numReadLocations=256000 numReads=65536000
time=4.673000 byteIncrement=2048 numReadLocations=128000 numReads=65536000
time=4.729000 byteIncrement=4096 numReadLocations=64000 numReads=65536000
time=4.784000 byteIncrement=8192 numReadLocations=32000 numReads=65536000
time=5.021000 byteIncrement=16384 numReadLocations=16000 numReads=65536000
time=5.022000 byteIncrement=32768 numReadLocations=8000 numReads=65536000
time=4.871000 byteIncrement=65536 numReadLocations=4000 numReads=65536000
time=5.163000 byteIncrement=131072 numReadLocations=2000 numReads=65536000
time=5.276000 byteIncrement=262144 numReadLocations=1000 numReads=65536000
time=4.699000 byteIncrement=524288 numReadLocations=500 numReads=65536000
time=1.997000 byteIncrement=1048576 numReadLocations=250 numReads=65536000
time=2.118000 byteIncrement=2097152 numReadLocations=125 numReads=65536000
time=2.071000 byteIncrement=4194304 numReadLocations=62 numReads=65536000
time=2.036000 byteIncrement=8388608 numReadLocations=31 numReads=65536000
time=1.923000 byteIncrement=16777216 numReadLocations=15 numReads=65536000
time=1.084000 byteIncrement=33554432 numReadLocations=7 numReads=65536000
time=0.607000 byteIncrement=67108864 numReadLocations=3 numReads=65536000
time=0.622000 byteIncrement=134217728 numReadLocations=1 numReads=65536000
Решение
Обратите внимание, что большинство из приведенного ниже, как и любые сделанные вами выводы, носит умозрительный характер. Сравнительный анализ памяти очень сложен, и сравнительно наивный сравнительный анализ, как вы это делали, редко дает много определенной информации о производительности реальной программы.
Основной «ценовой барьер», как вы его называете в 32 КБ, наверное больше на 64киБ (или комбинация обоих). Поскольку вы не инициализируете память, Windows будет загружать ноль страниц по мере их чтения. Гранулярность выделения составляет 64 КБ, и страницы всегда «готовы» (и предварительно выбираются, если вы отображаете карту памяти) в этом размере, даже если только одна из страниц в диапазоне 64 КБ перемещена в ваш рабочий набор. Это то, что я обнаружил, экспериментируя с отображением памяти.
Ваш рабочий процесс, установленный Windows, по умолчанию смехотворно мал, поэтому, перебирая этот блок памяти, вы будете постоянно сталкиваться с ошибками страниц. Некоторые из них дешевле, они меняют только флаг в дескрипторе страницы, другие (при 64 КБ) стоят дороже, вытягивая 16 новых страниц из нулевого пула (или, в худшем случае, если пул пуст, обнуляют страницы). Это может очень хорошо объяснить один из «барьеров стоимости», которые вы видите.
Как вы правильно заметили, еще один ценовой барьер — ассоциативность кэша. Разные адреса с большей степенью смещения двух используют одни и те же записи кэша. Учитывая «нездоровые» смещения, можно вызывать повторное удаление одних и тех же строк кэша снова и снова. Это одна из двух основных причин, почему выравнивание хорошо, но чрезмерное выравнивание плохо (другая причина — отсутствие локальности данных).
Барьер стоимости в 32 байта удивителен, во всяком случае, можно представить, что он составляет 64 байта (пересечение строк кэша в вашей тестовой архитектуре). Предварительная выборка должна по большей части устранять этот вид срыва, но предварительная выборка обычно активируется только (если вы явно не намекаете на это) после второй строки кэша промах с заданным шагом.
Это вполне приемлемо для «реальных» программ, которые либо читают только одно местоположение и другое, либо последовательно перебирают большие объемы данных. С другой стороны, это может легко дать запутанные результаты при выполнении искусственных измерений. Это также может быть возможным объяснением того, почему вы видите ценовой барьер в 32 КБ. Если предварительная выборка не работает, то это будет момент, когда вы исчерпаете кэш L1 на типичном x86.
Другие решения
Других решений пока нет …