Какова стоимость пропуска кэша L1?
Edit: для справочных целей (если кто-то наткнется на этот вопрос), Игорь Островский написал Великий пост о кэш-промахов. Он обсуждает несколько различных вопросов и показывает примеры номеров. Редактирование
Я сделал некоторые испытания <long story goes here> и мне интересно, если разница в производительности из-за памяти кэша. Следующий код демонстрирует проблему и сводит ее к критической части синхронизации. Следующий код имеет пару циклов, которые посещают память в случайном порядке, а затем в порядке возрастания адреса.
Я запустил его на машине XP (скомпилированной с VS2005: cl /O2) и на Linux box (GCC –Os). Оба произвели подобные времена. Это время в миллисекундах. Я считаю, что все циклы работают и не оптимизированные (в противном случае он будет работать "мгновенно").
*** Testing 20000 nodes Total Ordered Time: 888.822899 Total Random Time: 2155.846268
имеют ли эти цифры смысл? Разница в первую очередь из-за промахов кэша L1 или что-то еще происходит на что же еще? Есть 20 000^2 доступа к памяти, и если бы каждый из них был промахом кэша, это составляет около 3,2 наносекунды за промах. Машина XP (P4), на которой я тестировал, составляет 3,2 ГГц, и я подозреваю (но не знаю), что у нее есть кэш 32KB L1 и 512KB L2. С 20 000 записей (80KB), я предполагаю, что нет значительного количества пропусков 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( "nn*** Testing %u nodesn", 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: %fn", 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: %fn", dms );
}
8 ответов:
хотя я не могу предложить ответ на вопрос, Имеют ли цифры смысл (я не очень хорошо разбираюсь в задержках кэша, но для записи ~10 циклов L1 кэш пропускает звуки примерно правильно), я могу предложить вам Cachegrind как инструмент, который поможет вам увидеть различия в производительности кэша между вашими 2 тестами.
Cachegrind-это инструмент Valgrind (фреймворк, который питает всегда прекрасный memcheck), который профилирует кэш и ветви хитов/промахов. Это даст вам идея о том, сколько кэш-хитов/промахов вы на самом деле получаете в своей программе.
вот попытка дать представление об относительной стоимости промахов кэша по аналогии с выпечкой шоколадного печенья...
ваши руки-это ваши регистры. это займет у вас 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) -- но различия между ними могут иметь огромный влияние на производительность. Оптимизация исключительно для большой сложности - это как решить, добавлять ли шоколадные чипсы в тесто 1 за раз или 10 за раз, но забыть положить их в свой список покупок.
мораль истории: организовать доступ к памяти, так что процессор должен идти за продуктами, как редко, насколько это возможно.
номера были взяты из ошибка промывки кэша процессора сообщение в блоге, которое указывает, что для конкретного процессора Intel 2012 года верно следующее:
- Регистрация доступа = 4 Инструкции за цикл
- задержка L1 = 3 цикла (12 x регистр)
- задержка L2 = 12 циклов (4 x L1, 48 x регистр)
- задержка L3 = 38 циклов (3 x L2, 12 x L1, 144 x регистр)
- драма задержка = 65 НС = 195 циклов на процессоре 3 ГГц (5 x L3, 15 x L2, 60 x L1, 720 x регистр)
The Галерея эффектов кэша процессора также делает хорошее чтение на эту тему.
3.2 НС, для кэш-памяти L1 пропустите полностью правдоподобный. Для сравнения, на одном конкретном современном многоядерном процессоре PowerPC промах L1 составляет около 40 циклы -- немного дольше для некоторых ядер, чем другие, в зависимости от того, как далеко они находятся от кэша L2 (да действительно). Промах L2-это по крайней мере600 циклы.
кэш-это все в производительности; процессоры теперь намного быстрее, чем память, что вы действительно почти оптимизируете для шины памяти вместо ядра.
Ну да, похоже, что это будет в основном промахи кэша L1.
10 циклов для промаха кэша L1 действительно звучит разумно, вероятно, немного на низкой стороне.
чтение из ОЗУ будет принимать порядка 100s или может быть даже 1000s (я слишком устал, чтобы пытаться делать математику прямо сейчас ;)) циклов, поэтому его все еще огромная победа над этим.
Если вы планируете использовать cachegrind, обратите внимание, что это только симулятор попадания/пропуска кэша. Это не всегда будет точно. Например: если вы получаете доступ к некоторому местоположению памяти, скажем 0x1234 в цикле 1000 раз, cachegrind всегда покажет вам, что был только один промах кэша (первый доступ), даже если у вас есть что-то вроде:
clflush 0x1234 в цикле.
на x86, это вызовет все 1000 промахов кэша.
некоторые числа для 3,4 ГГц P4 от запуска Lavalys Everest:
- L1 dcache составляет 8K (cacheline 64 байта)
- L2 составляет 512 КБ
- L1 задержка выборки составляет 2 цикла
- L2 fetch latency примерно в два раза больше, чем вы видите: 20 циклов
подробнее здесь: http://www.freeweb.hu/instlatx64/GenuineIntel0000F25_P4_Gallatin_MemLatX86.txt
(для задержек смотрите в нижней части страницы)
трудно сказать что-нибудь наверняка без гораздо большего тестирования, но по моему опыту, что масштаб разницы определенно может быть отнесен к кешу CPU L1 и/или L2, особенно в сценарии с рандомизированным доступом. Вероятно, вы могли бы сделать это еще хуже, гарантируя, что каждый доступ находится хотя бы на некотором минимальном расстоянии от последнего.
проще всего сделать масштабированную фотографию целевого процессора и физически измерить расстояние между ядром и кэшем уровня 1. Умножьте это расстояние на расстояние, на которое электроны могут перемещаться в секунду в меди. Затем выясните, сколько тактов вы можете иметь в то же время. Это минимальное количество циклов процессора, которое вы потратите на пропуск кэша L1.
вы также можете разработать минимальную стоимость извлечения данных из ОЗУ с точки зрения количества ЦП циклы потрачены впустую таким же образом. Вы можете быть удивлены.
обратите внимание, что то, что вы видите здесь, определенно имеет какое-то отношение к кэш-промахам (будь то L1 или оба L1 и L2), потому что обычно кэш будет извлекать данные в одной и той же строке кэша, как только вы получите доступ к чему-либо в этой строке кэша, требующей меньше поездок в ОЗУ.
однако то, что вы, вероятно, также видите, - это тот факт, что RAM (даже если он вызывает оперативную память) по-прежнему предпочитает линейный доступ к памяти.