Сколько стоит мисс L1 Cache?
Редактировать: В справочных целях (если кто-то сталкивается с этим вопросом), Игорь Островский написал отличный пост о промахах кэша. В нем обсуждаются несколько разных вопросов и приведены примеры номеров. Конец Править
Я сделал некоторое тестирование <long story goes here> и мне интересно, если разница в производительности из-за промахов кэша памяти. Следующий код демонстрирует проблему и сводит ее к критической части синхронизации. В следующем коде есть несколько циклов, которые посещают память в случайном порядке, а затем в порядке возрастания адресов.
Я запустил его на машине с XP (скомпилированной с VS2005: cl /O2) и на Linux-машине (gcc –Os). Оба произвели одинаковое время. Эти времена в миллисекундах. Я считаю, что все циклы работают и не оптимизированы (в противном случае он будет запущен "мгновенно").
*** Тестирование 20000 узлов Общее время заказа: 888.822899 Общее случайное время: 2155.846268
Имеют ли эти цифры смысл? Разница в основном из-за пропусков кэша L1 или что-то еще происходит? Имеется 20 000^2 обращений к памяти, и если каждый из них был с ошибкой в кэше, то это примерно 3,2 наносекунды за промах. Машина с XP (P4), которую я тестировал, имеет частоту 3,2 ГГц, и я подозреваю (но не знаю), что она имеет 32 КБ L1 кеша и 512 КБ L2. Я предполагаю, что с 20 000 записей (80 КБ) не будет значительного количества пропусков L2. Так что это будет (3.2*10^9 cycles/second) * 3.2*10^-9 seconds/miss) = 10.1 cycles/miss, Это кажется высоким для меня. Может быть, нет, или, может быть, моя математика плохая. Я попытался измерить ошибки кэша с помощью VTune, но получил BSOD. И теперь я не могу заставить его подключиться к серверу лицензий (grrrr).
typedef struct stItem
{
long lData;
//char acPad[20];
} LIST_NODE;
#if defined( WIN32 )
void StartTimer( LONGLONG *pt1 )
{
QueryPerformanceCounter( (LARGE_INTEGER*)pt1 );
}
void StopTimer( LONGLONG t1, double *pdMS )
{
LONGLONG t2, llFreq;
QueryPerformanceCounter( (LARGE_INTEGER*)&t2 );
QueryPerformanceFrequency( (LARGE_INTEGER*)&llFreq );
*pdMS = ((double)( t2 - t1 ) / (double)llFreq) * 1000.0;
}
#else
// doesn't need 64-bit integer in this case
void StartTimer( LONGLONG *pt1 )
{
// Just use clock(), this test doesn't need higher resolution
*pt1 = clock();
}
void StopTimer( LONGLONG t1, double *pdMS )
{
LONGLONG t2 = clock();
*pdMS = (double)( t2 - t1 ) / ( CLOCKS_PER_SEC / 1000 );
}
#endif
long longrand()
{
#if defined( WIN32 )
// Stupid cheesy way to make sure it is not just a 16-bit rand value
return ( rand() << 16 ) | rand();
#else
return rand();
#endif
}
// get random value in the given range
int randint( int m, int n )
{
int ret = longrand() % ( n - m + 1 );
return ret + m;
}
// I think I got this out of Programming Pearls (Bentley).
void ShuffleArray
(
long *plShuffle, // (O) return array of "randomly" ordered integers
long lNumItems // (I) length of array
)
{
long i;
long j;
long t;
for ( i = 0; i < lNumItems; i++ )
plShuffle[i] = i;
for ( i = 0; i < lNumItems; i++ )
{
j = randint( i, lNumItems - 1 );
t = plShuffle[i];
plShuffle[i] = plShuffle[j];
plShuffle[j] = t;
}
}
int main( int argc, char* argv[] )
{
long *plDataValues;
LIST_NODE *pstNodes;
long lNumItems = 20000;
long i, j;
LONGLONG t1; // for timing
double dms;
if ( argc > 1 && atoi(argv[1]) > 0 )
lNumItems = atoi( argv[1] );
printf( "\n\n*** Testing %u nodes\n", lNumItems );
srand( (unsigned int)time( 0 ));
// allocate the nodes as one single chunk of memory
pstNodes = (LIST_NODE*)malloc( lNumItems * sizeof( LIST_NODE ));
assert( pstNodes != NULL );
// Create an array that gives the access order for the nodes
plDataValues = (long*)malloc( lNumItems * sizeof( long ));
assert( plDataValues != NULL );
// Access the data in order
for ( i = 0; i < lNumItems; i++ )
plDataValues[i] = i;
StartTimer( &t1 );
// Loop through and access the memory a bunch of times
for ( j = 0; j < lNumItems; j++ )
{
for ( i = 0; i < lNumItems; i++ )
{
pstNodes[plDataValues[i]].lData = i * j;
}
}
StopTimer( t1, &dms );
printf( "Total Ordered Time: %f\n", dms );
// now access the array positions in a "random" order
ShuffleArray( plDataValues, lNumItems );
StartTimer( &t1 );
for ( j = 0; j < lNumItems; j++ )
{
for ( i = 0; i < lNumItems; i++ )
{
pstNodes[plDataValues[i]].lData = i * j;
}
}
StopTimer( t1, &dms );
printf( "Total Random Time: %f\n", dms );
}
8 ответов
Хотя я не могу предложить ответ на вопрос о том, имеют ли числа смысл (я не очень хорошо разбираюсь в задержках кеша, но для записи ~10 циклов кэш L1 пропускает звуки о правильном), я могу предложить вам Cachegrind как инструмент, который поможет вам увидеть разницу в производительности кеша между двумя вашими тестами.
Cachegrind - это инструмент Valgrind (фреймворк, обеспечивающий всегда приятную проверку), который профилирует кэш и попадания / пропадания веток. Это даст вам представление о том, сколько попаданий / пропусков кэша вы фактически получаете в своей программе.
Вот попытка дать представление об относительной стоимости промахов кэша по аналогии с выпечкой шоколадного печенья...
Ваши руки - ваши регистры. Чтобы положить шоколадные чипсы в тесто, вам понадобится 1 секунда.
Кухонный счетчик - ваш кэш L1, в двенадцать раз медленнее регистров. Требуется 12 x 1 = 12 секунд, чтобы подойти к прилавку, взять пакет с грецкими орехами и вылить его в руку.
Холодильник - это ваш кеш L2, в четыре раза медленнее, чем L1. Требуется 4 x 12 = 48 секунд, чтобы дойти до холодильника, открыть его, убрать остатки прошлой ночи с пути, вынуть коробку яиц, открыть коробку, положить 3 яйца на прилавок и положить коробку обратно в холодильник.
Шкаф - ваш кэш L3, в три раза медленнее, чем L2. Требуется 3 x 48 = 2 минуты и 24 секунды, чтобы сделать три шага к шкафу, наклониться, открыть дверь, повернуть вокруг, чтобы найти олово для выпечки, извлечь его из шкафа, открыть его, копать, чтобы найти разрыхлитель положи его на стойку и подмести беспорядок, который ты пролил на пол.
А основная память? Это магазин на углу, в 5 раз медленнее, чем L3. Требуется 5 x 2:24 = 12 минут, чтобы найти свой кошелек, надеть обувь и пиджак, броситься вниз по улице, взять литр молока, броситься домой, снять обувь и пиджак и вернуться на кухню.
Обратите внимание, что все эти обращения имеют постоянную сложность - O(1) - но различия между ними могут оказать огромное влияние на производительность. Оптимизация исключительно для сложности big-O - это все равно, что решить, добавлять ли шоколадные чипсы в тесто 1 за раз или 10 за раз, но забыть поместить их в свой список покупок.
Мораль этой истории: организуйте доступ к своей памяти так, чтобы ЦПУ приходилось ходить за продуктами как можно реже.
Числа были взяты из сообщения в блоге CPU Cache Flushing Fallacy, в котором указано, что для конкретного процессора Intel 2012-го года верно следующее:
- доступ к регистру = 4 инструкции за цикл
- L1 латентность = 3 цикла (12 х регистров)
- Задержка L2 = 12 циклов (4 x L1, 48 x регистр)
- Задержка L3 = 38 циклов (3 x L2, 12 x L1, 144 x регистр)
- Задержка DRAM = 65 нс = 195 циклов на процессоре 3 ГГц (5 x L3, 15 x L2, 60 x L1, 720 x регистр)
Галерея Processor Cache Effects также хорошо читает эту тему.
3,2 нс для пропуска кэша L1 вполне правдоподобно. Для сравнения, на одном конкретном современном многоядерном процессоре PowerPC промах L1 составляет около 40 циклов - для некоторых ядер он немного больше, чем для других, в зависимости от того, как далеко они находятся от кэша L2 (да, действительно). Промах L2 составляет не менее 600 циклов.
Кэш - это все в производительности; Процессоры теперь намного быстрее, чем память, так что вы фактически оптимизируете для шины памяти вместо ядра.
Ну, да, похоже, это будет в основном промах L1.
10 циклов при пропадании кэша L1 звучат довольно разумно, вероятно, с низкой стороны.
Чтение из ОЗУ будет занимать порядка 100 с или может быть даже 1000 с (я слишком устал, чтобы пытаться делать математику прямо сейчас;)) циклов, так что это все еще огромная победа над этим.
Если вы планируете использовать cachegrind, обратите внимание, что это симулятор попадания / пропуска кэша. Это не всегда будет точно. Например: если вы обращаетесь к некоторой ячейке памяти, скажем, 0x1234 в цикле 1000 раз, cachegrind всегда будет показывать вам, что была только одна ошибка кэша (первый доступ), даже если у вас есть что-то вроде:
clflush 0x1234 в вашем цикле.
На x86 это вызовет все 1000 пропусков кэша.
Некоторые цифры для P4 с частотой 3,4 ГГц из серии Lavalys Everest:
- L1 dcache составляет 8 КБ (кешлайн 64 байта)
- L2 512K
- Задержка выборки L1 составляет 2 цикла
- Задержка получения L2 примерно вдвое больше, чем вы видите: 20 циклов
Больше здесь: http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt
(время ожидания смотрите внизу страницы)
Трудно сказать что-либо наверняка без большого количества тестирования, но по моему опыту, такая разница определенно может быть отнесена к кэш-памяти L1 и / или L2 ЦП, особенно в сценарии с произвольным доступом. Вероятно, вы могли бы сделать это еще хуже, если бы каждый доступ был на некотором минимальном расстоянии от последнего.
Самое простое, что нужно сделать - это сделать масштабную фотографию целевого процессора и физически измерить расстояние между ядром и кэшем 1-го уровня. Умножьте это расстояние на расстояние, которое электроны могут перемещать в секунду в меди. Затем выясните, сколько тактов вы можете иметь за одно и то же время. Это минимальное количество циклов ЦП, которое вы тратите на промах L1.
Вы также можете рассчитать минимальную стоимость извлечения данных из ОЗУ с точки зрения количества циклов ЦП, потраченных таким же образом. Вы можете быть удивлены.
Обратите внимание, что то, что вы видите здесь, определенно связано с промахами кэша (будь то L1 или оба L1 и L2), потому что обычно кэш извлекает данные из одной и той же строки кэша, как только вы обращаетесь к чему-либо в этой строке, требующей меньше поездок в оперативную память
Однако то, что вы, вероятно, также видите, это то, что ОЗУ (даже если оно называется оперативной памятью) все еще предпочитает линейный доступ к памяти.