Подтвердить что ты не робот

Почему скорость memcpy() резко падает каждые 4 КБ?

Я протестировал скорость memcpy(), заметив, что скорость резко падает при я * 4KB. Результат следующий: ось Y - это скорость (МБ/секунда), а ось Х - размер буфера для memcpy(), увеличиваясь с 1 КБ до 2 МБ. На рисунках 2 и 3 представлены детали 1KB-150KB и 1KB-32KB.

Окружающая среда:

Процессор: Intel (R) Xeon (R) CPU E5620 @2,40 ГГц

ОС: 2.6.35-22-общий # 33-Ubuntu

Флаги компилятора GCC: -O3 -msse4 -DINTEL_SSE4 -Wall -std = c99

Graphs of memcpy speed showing troughs every 4k

Я предполагаю, что это должно быть связано с кэшами, но я не могу найти причину из следующих небезопасных случаев, связанных с кешем:

Так как ухудшение производительности этих двух случаев вызвано недружественными циклами, которые считывают разбросанные байты в кеш, теряя остальную часть пространства кэша.

Вот мой код:

void memcpy_speed(unsigned long buf_size, unsigned long iters){
    struct timeval start,  end;
    unsigned char * pbuff_1;
    unsigned char * pbuff_2;

    pbuff_1 = malloc(buf_size);
    pbuff_2 = malloc(buf_size);

    gettimeofday(&start, NULL);
    for(int i = 0; i < iters; ++i){
        memcpy(pbuff_2, pbuff_1, buf_size);
    }   
    gettimeofday(&end, NULL);
    printf("%5.3f\n", ((buf_size*iters)/(1.024*1.024))/((end.tv_sec - \
    start.tv_sec)*1000*1000+(end.tv_usec - start.tv_usec)));
    free(pbuff_1);
    free(pbuff_2);
}

UPDATE

Учитывая предложения от @usr, @ChrisW и @Leeor, я уточнил тест более точно, и приведенный ниже график показывает результаты. Размер буфера составляет от 26 КБ до 38 КБ, и я тестировал его каждый другой 64B (26 КБ, 26 КБ + 64 Б, 26 КБ + 128 Б,......, 38 КБ). Каждый тест проходит 100 000 раз за 0.15 секунды. Интересно то, что падение происходит не только на границе 4 КБ, но и выходит в 4 * я + 2 КБ с гораздо меньшей амплитудой падения.

More graphs showing performance drops

PS

@Leeor предложила способ заполнить капли, добавив 2-килобайтовый макет-буфер между pbuff_1 и pbuff_2. Это работает, но я не уверен в объяснении Лиора.

enter image description here

4b9b3361

ОТВЕТЫ

Ответ 1

Память обычно организована на 4 тыс. страниц (хотя там также поддерживаются более крупные размеры). Виртуальное адресное пространство, которое видит ваша программа, может быть смежным, но это не обязательно в физической памяти. OS, которая поддерживает сопоставление виртуальных и физических адресов (на карте страниц), обычно пытается сохранить вместе физические страницы, но это не всегда возможно, и они могут быть разбиты (особенно при длительном использовании, когда они могут быть заменены иногда).

Когда ваш поток памяти пересекает границу страницы 4k, CPU необходимо остановить и перейти к новому переводу - если он уже просмотрел страницу, он может быть кэширован в TLB, а доступ оптимизирован как самый быстрый, но если это первый доступ (или если у вас слишком много страниц для TLB, на которые нужно удержаться), CPU должен будет остановить доступ к памяти и начать прохождение страницы через записи карты страниц - это относительно долго, как каждый уровень на самом деле является памятью, которая читается сама по себе (на виртуальных машинах она еще больше, так как каждому уровню может потребоваться полный перерыв на хосте).

У вашей функции memcpy может возникнуть другая проблема - при первом распределении памяти ОС просто создаст страницы в pagemap, но помечает их как неактивные и немодифицированные из-за внутренних оптимизаций. Первый доступ может не только вызывать прохождение страницы, но, возможно, также помогает сообщать ОС, что страница будет использоваться (и хранится для страниц целевого буфера), что приведет к дорогостоящему переходу на какой-либо обработчик ОС.

Чтобы устранить этот шум, выделите буферы один раз, выполните несколько повторений копии и рассчитайте время амортизации. Это, с другой стороны, даст вам "теплую" производительность (т.е. После прогревания кешей), поэтому вы увидите, что размеры кеша отражаются на ваших графиках. Если вы хотите получить "холодный" эффект, не страдая от задержек подкачки, вам может понадобиться очистить кеши между итерацией (просто убедитесь, что вы не успели это сделать)

ИЗМЕНИТЬ

Перечитайте вопрос, и вы, кажется, делаете правильное измерение. Проблема с моим объяснением заключается в том, что после 4k*i она должна постепенно увеличиваться, так как на каждой такой каплей вы платите штраф снова, но затем должны наслаждаться бесплатной поездкой до следующих 4k. Это не объясняет, почему есть такие "всплески", и после них скорость возвращается к норме.

Я думаю, что вы столкнулись с подобной проблемой с критическим вопросом шага, связанным с вашим вопросом, - когда ваш размер буфера - хороший раунд 4k, оба буфера будут выравниваться с одними и теми же наборами в кеше и трэш друг друга. Ваш L1 - 32k, поэтому сначала это не похоже на проблему, но при условии, что данные L1 имеют 8 способов, это на самом деле обход вокруг 4k для одних и тех же наборов, и у вас есть 2 * 4k блоки с одинаковым выравниванием (предполагая, что распределение было сделано смежно), поэтому они перекрываются на одних и тех же наборах. Достаточно того, что LRU работает не так, как вы ожидаете, и у вас будут конфликты.

Чтобы проверить это, я попытался malloc фиктивный буфер между pbuff_1 и pbuff_2, сделайте его 2k большим и надеемся, что он сломает выравнивание.

EDIT2:

Хорошо, так как это работает, пора разработать немного. Предположим, вы назначили два массива 4k в диапазонах 0x1000-0x1fff и 0x2000-0x2fff. set 0 в вашем L1 будет содержать строки в 0x1000 и 0x2000, набор 1 будет содержать 0x1040 и 0x2040 и т.д. При этих размерах у вас еще нет проблем с ударом, все они могут сосуществовать без переполнения ассоциативности кеша. Тем не менее, каждый раз, когда вы выполняете итерацию, у вас есть загрузка и хранилище, доступ к одному набору - я предполагаю, что это может привести к конфликту в HW. Хуже того, вам понадобится несколько итераций для копирования одной строки, что означает, что у вас есть загруженность 8 нагрузок + 8 магазинов (меньше, если вы векторизовать, но все же много), все направлены на тот же самый плохой набор, я довольно уверен, что там есть куча коллизий.

Я также вижу, что руководство по оптимизации Intel может что-то сказать об этом (см. 3.6.8.2):

4-Кбайтное сглаживание памяти происходит, когда код обращается к двум различным памяти с 4-килобайтным смещением между ними. 4-Кбайт ситуация с псевдонимом может проявляться в режиме копирования памяти, где адреса исходного буфера и буфер назначения сохраняют постоянное смещение, а постоянное смещение оказывается кратным приращение байта от одной итерации к следующей.

...

нагрузки должны ждать, пока магазины не будут уволены, прежде чем они смогут Продолжать. Например, при смещении 16 нагрузка следующей итерации равна 4-килобайтный алиасированный текущий итерационный магазин, поэтому цикл должен ждать пока операция хранилища не завершится, делая весь цикл сериализованная. Количество времени, необходимого для ожидания, уменьшается с увеличением смещение до смещения 96 разрешает проблему (поскольку нет ожидающих магазины к моменту загрузки с тем же адресом).

Ответ 2

Я ожидаю, потому что:

  • Когда размер блока составляет 4 Кбайт, тогда malloc выделяет новые страницы из O/S.
  • Если размер блока не равен 4 Кбайт, то malloc выделяет диапазон из его (уже выделенной) кучи.
  • Когда страницы выделены из O/S, тогда они "холодны": прикосновение к ним в первый раз очень дорого.

Я предполагаю, что если вы сделаете одиночный memcpy до первого gettimeofday, тогда это будет "нагревать" выделенную память, и вы не увидите эту проблему. Вместо того, чтобы делать первоначальную memcpy, даже писать один байт на каждую выделенную страницу 4 КБ может быть достаточно, чтобы предварительно разогревать страницу.

Обычно, когда мне нужен тест производительности, такой как ваш, я его кодирую как:

// Run in once to pre-warm the cache
runTest();
// Repeat 
startTimer();
for (int i = count; i; --i)
  runTest();
stopTimer();

// use a larger count if the duration is less than a few seconds
// repeat test 3 times to ensure that results are consistent

Ответ 3

Поскольку вы повторяетесь много раз, я думаю, что аргументы о не отображаемых страницах не имеют значения. На мой взгляд, то, что вы видите, - это эффект аппаратного префедера, который не желает пересекать границу страницы, чтобы не вызывать (потенциально ненужные) ошибки страницы.