Почему мой кеш 8M L3 не дает никаких преимуществ для массивов размером более 1 МБ?

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

Почему векторизация цикла не повышает производительность

Мой код использует memset для записи в буфер (или буферы) снова и снова и измеряет скорость. Он также сохраняет адрес каждого буфера для печати в конце. Здесь перечисление:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define SIZE_KB {8, 16, 24, 28, 32, 36, 40, 48, 64, 128, 256, 384, 512, 768, 1024, 1025, 2048, 4096, 8192, 16384, 200000}
#define TESTMEM 10000000000 // Approximate, in bytes
#define BUFFERS 1

double timer(void)
{
    struct timeval ts;
    double ans;

    gettimeofday(&ts, NULL);
    ans = ts.tv_sec + ts.tv_usec*1.0e-6;

    return ans;
}

int main(int argc, char **argv)
{
    double *x[BUFFERS];
    double t1, t2;
    int kbsizes[] = SIZE_KB;
    double bandwidth[sizeof(kbsizes)/sizeof(int)];
    int iterations[sizeof(kbsizes)/sizeof(int)];
    double *address[sizeof(kbsizes)/sizeof(int)][BUFFERS];
    int i, j, k;

    for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
        iterations[k] = TESTMEM/(kbsizes[k]*1024);

    for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
    {
        // Allocate
        for (j = 0; j < BUFFERS; j++)
        {
            x[j] = (double *) malloc(kbsizes[k]*1024);
            address[k][j] = x[j];
            memset(x[j], 0, kbsizes[k]*1024);
        }

        // Measure
        t1 = timer();
        for (i = 0; i < iterations[k]; i++)
        {
            for (j = 0; j < BUFFERS; j++)
                memset(x[j], 0xff, kbsizes[k]*1024);
        }
        t2 = timer();
        bandwidth[k] = (BUFFERS*kbsizes[k]*iterations[k])/1024.0/1024.0/(t2-t1);

        // Free
        for (j = 0; j < BUFFERS; j++)
            free(x[j]);
    }

    printf("TESTMEM = %ld\n", TESTMEM);
    printf("BUFFERS = %d\n", BUFFERS);
    printf("Size (kB)\tBandwidth (GB/s)\tIterations\tAddresses\n");
    for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
    {
        printf("%7d\t\t%.2f\t\t\t%d\t\t%x", kbsizes[k], bandwidth[k], iterations[k], address[k][0]);
        for (j = 1; j < BUFFERS; j++)
            printf(", %x", address[k][j]);
        printf("\n");
    }

    return 0;
}

И результаты (с BUFFERS = 1):

TESTMEM = 10000000000
BUFFERS = 1
Size (kB)   Bandwidth (GB/s)    Iterations  Addresses
      8     52.79               1220703     90b010
     16     56.48               610351      90b010
     24     57.01               406901      90b010
     28     57.13               348772      90b010
     32     45.40               305175      90b010
     36     38.11               271267      90b010
     40     38.02               244140      90b010
     48     38.12               203450      90b010
     64     37.51               152587      90b010
    128     36.89               76293       90b010
    256     35.58               38146       d760f010
    384     31.01               25431       d75ef010
    512     26.79               19073       d75cf010
    768     26.20               12715       d758f010
   1024     26.20               9536        d754f010
   1025     18.30               9527        90b010
   2048     18.29               4768        d744f010
   4096     18.29               2384        d724f010
   8192     18.31               1192        d6e4f010
  16384     18.31               596         d664f010
 200000     18.32               48          cb2ff010

Я могу легко увидеть эффект 32K L1-кеша и 256K L2-кеша. Я не понимаю, почему производительность падает внезапно после того, как размер буфера memset превышает 1M. Мой кеш L3 должен быть 8M. Это случается так внезапно, но не сужается вообще, как при превышении размера кеша L1 и L2.

Мой процессор - Intel i7 3700. Детали кеша L3 из /sys/devices/system/cpu/cpu 0/cache:

level = 3
coherency_line_size = 64
number_of_sets = 8192
physical_line_partition = 1
shared_cpu_list = 0-7
shared_cpu_map = ff
size = 8192K
type = Unified
ways_of_associativity = 16

Я думал, что попробую использовать несколько буферов - вызовите memset на 2 буфера по 1M каждый и посмотрите, не снизится ли производительность. С BUFFERS = 2 я получаю:

TESTMEM = 10000000000
BUFFERS = 2
Size (kB)   Bandwidth (GB/s)    Iterations  Addresses
      8     54.15               1220703     e59010, e5b020
     16     51.52               610351      e59010, e5d020
     24     38.94               406901      e59010, e5f020
     28     38.53               348772      e59010, e60020
     32     38.31               305175      e59010, e61020
     36     38.29               271267      e59010, e62020
     40     38.29               244140      e59010, e63020
     48     37.46               203450      e59010, e65020
     64     36.93               152587      e59010, e69020
    128     35.67               76293       e59010, 63769010
    256     27.21               38146       63724010, 636e3010
    384     26.26               25431       63704010, 636a3010
    512     26.19               19073       636e4010, 63663010
    768     26.20               12715       636a4010, 635e3010
   1024     26.16               9536        63664010, 63563010
   1025     18.29               9527        e59010, f59420
   2048     18.23               4768        63564010, 63363010
   4096     18.27               2384        63364010, 62f63010
   8192     18.29               1192        62f64010, 62763010
  16384     18.31               596         62764010, 61763010
 200000     18.31               48          57414010, 4b0c3010

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

Я компилирую с -O3. Это не имеет большого значения (за исключением, возможно, разворачивания петель над буфферами). Я пробовал с -O0, и это то же самое, за исключением скоростей L1. Версия gcc - 4.9.1.

Подводя итог, у меня есть вопрос из двух частей:

  • Почему мой 8-мегабайтный L3-кеш не дает каких-либо преимуществ для блоков с памятью больше 1 М?
  • Почему падение производительности настолько неожиданное?

EDIT:

Как было предложено Gabriel Southern, я запустил свой код с помощью perf, используя BUFFERS = 1 с одним размером буфера за раз. Это была полная команда:

perf stat -e dTLB-loads,dTLB-load-misses,dTLB-stores,dTLB-store-misses -r 100 ./a.out 2> perfout.txt

-r означает, что perf будет запускать a.out 100 раз и возвращать среднюю статистику.

Вывод perf, с #define SIZE_KB {1024}:

 Performance counter stats for './a.out' (100 runs):

         1,508,798 dTLB-loads                                                    ( +-  0.02% )
                 0 dTLB-load-misses          #    0.00% of all dTLB cache hits 
       625,967,550 dTLB-stores                                                   ( +-  0.00% )
             1,503 dTLB-store-misses                                             ( +-  0.79% )

       0.360471583 seconds time elapsed                                          ( +-  0.79% )

и #define SIZE_KB {1025}:

 Performance counter stats for './a.out' (100 runs):

         1,670,402 dTLB-loads                                                    ( +-  0.09% )
                 0 dTLB-load-misses          #    0.00% of all dTLB cache hits 
       626,099,850 dTLB-stores                                                   ( +-  0.00% )
             2,115 dTLB-store-misses                                             ( +-  2.19% )

       0.503913416 seconds time elapsed                                          ( +-  0.06% )

Таким образом, похоже, что больше нет пропусков TLB с буфером 1025K. Однако с этим буфером размера программа выполняет около 9500 вызовов memset, поэтому она по-прежнему меньше 1 промаха за вызов memset.

Ответы

Ответ 1

Краткий ответ:

Ваша версия memset начинает использовать невременные магазины при инициализации области памяти размером более 1 МБ. В результате ЦП не хранит эти строки в своем кеше, даже если ваш кеш-память L3 больше 1 МБ. Следовательно, производительность ограничена доступной пропускной способностью памяти в системе для значений буфера более 1 МБ.

Детали:

Справочная информация:

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

Некоторые из тестируемых нами систем использовали Arch Linux с последней версией glibc, в то время как другие использовали Ubuntu 10.04, которая использует более старую версию eglibc. Я смог воспроизвести поведение, описанное в вопросе, при использовании статически связанного двоичного файла при тестировании с несколькими разными архитектурами процессора. Поведение, на которое я сосредоточился, было существенным различием во времени выполнения, когда SIZE_KB был 1024 и когда он был 1025. Разница в производительности объясняется изменением кода, выполняемого для медленных и быстрых версий.

Код сборки

Я использовал perf record и perf annotate для сбора трассировки кода выполняемой сборки, чтобы узнать, что такое путь к горячим кодам. Код отображается ниже, используя следующий формат:

percentage time executing instruction | address | instruction.

Я скопировал горячий цикл из более короткой версии, которая пропускает большую часть адреса, и имеет линию, соединяющую конец цикла и заголовок цикла.

Для версии, скомпилированной в Arch Linux, горячий цикл был (для размеров 1024 и 1025):

  2.35 │a0:┌─+movdqa %xmm8,(%rcx)
 54.90 │   │  movdqa %xmm8,0x10(%rcx)
 32.85 │   │  movdqa %xmm8,0x20(%rcx)
  1.73 │   │  movdqa %xmm8,0x30(%rcx)
  8.11 │   │  add    $0x40,%rcx      
  0.03 │   │  cmp    %rcx,%rdx       
       │   └──jne    a0

Для двоичного файла Ubuntu 10.04 горячий цикл при работе с размером 1024 был:

       │a00:┌─+lea    -0x80(%r8),%r8
  0.01 │    │  cmp    $0x80,%r8     
  5.33 │    │  movdqa %xmm0,(%rdi)  
  4.67 │    │  movdqa %xmm0,0x10(%rdi)
  6.69 │    │  movdqa %xmm0,0x20(%rdi)
 31.23 │    │  movdqa %xmm0,0x30(%rdi)
 18.35 │    │  movdqa %xmm0,0x40(%rdi)
  0.27 │    │  movdqa %xmm0,0x50(%rdi)
  3.24 │    │  movdqa %xmm0,0x60(%rdi)
 16.36 │    │  movdqa %xmm0,0x70(%rdi)
 13.76 │    │  lea    0x80(%rdi),%rdi 
       │    └──jge    a00

Для версии Ubuntu 10.04, работающей с размером буфера 1025, горячий цикл:

       │a60:┌─+lea    -0x80(%r8),%r8  
  0.15 │    │  cmp    $0x80,%r8       
  1.36 │    │  movntd %xmm0,(%rdi)    
  0.24 │    │  movntd %xmm0,0x10(%rdi)
  1.49 │    │  movntd %xmm0,0x20(%rdi)
 44.89 │    │  movntd %xmm0,0x30(%rdi)
  5.46 │    │  movntd %xmm0,0x40(%rdi)
  0.02 │    │  movntd %xmm0,0x50(%rdi)
  0.74 │    │  movntd %xmm0,0x60(%rdi)
 40.14 │    │  movntd %xmm0,0x70(%rdi)
  5.50 │    │  lea    0x80(%rdi),%rdi 
       │    └──jge    a60

Ключевое отличие здесь в том, что более медленная версия использовала команды movntd, в то время как более быстрые версии использовали инструкции movdqa. В руководстве Intel Software Developers написано следующее о невременных хранилищах:

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

Таким образом, это объясняет поведение, при котором использование memset со значениями, превышающими 1 МБ, не вписывается в кеш. Следующий вопрос заключается в том, почему существует разница между системой Ubuntu 10.04 и системой Arch Linux, и почему 1 МБ выбран как точка отсечки. Чтобы исследовать этот вопрос, я посмотрел исходный код glibc:

Исходный код для memset

Глядя на glibc git repo at sysdeps/x86_64/memset.S, первая фиксация, которую я нашел интересной, была b2b671b677d92429a3d41bf451668f476aa267ed

Описание фиксации:

Быстрее memset на x64

Эта реализация ускоряет memset несколькими способами. Во-первых, избегайте дорогой расчетный прыжок. Во-вторых, используется тот факт, что аргументы memset в большинстве случаев выровнены с 8 байтами.

Результаты тестов: kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_result27_04_13.tar.bz2

И веб-сайт на который ссылается, имеет некоторые интересные профилирующие данные.

diff коммита показывает, что код для memset упрощается, а не временные хранилища удаляются. Это соответствует тому, что показывает профилированный код из Arch Linux.

Посмотрев на старый код, я увидел, что выбор того, следует ли использовать невременные магазины, использовать значение, описанное как The largest cache size

L(byte32sse2_pre):

    mov    __x86_shared_cache_size(%rip),%r9d  # The largest cache size
    cmp    %r9,%r8
    ja     L(sse2_nt_move_pre)

Код для расчета: sysdeps/x86_64/cacheinfo.c

Хотя похоже, что существует код для вычисления фактического общего размера кеша, значение по умолчанию также 1 MB:

long int __x86_64_shared_cache_size attribute_hidden = 1024 * 1024;

Поэтому я подозреваю, что используется либо значение по умолчанию, но может быть и другая причина, по которой код выбирает 1 МБ в качестве точки отсечки.

В любом случае общий ответ на ваш вопрос заключается в том, что версия memset в вашей системе использует невременные хранилища при установке области памяти размером более 1 МБ.

Ответ 2

Учитывая разбор Габриэля сгенерированного кода сборки, я думаю, что это действительно проблема [Edit: его ответ был отредактирован, теперь он выглядит как основная причина, поэтому мы согласны):

Обратите внимание, что movnt - это хранилище потоковой передачи, которое может иметь (в зависимости от точной микро-архитектурной реализации) несколько воздействий:

  • Имеет слабую упорядочивающую семантику (что позволяет ей быть быстрее).
  • Улучшена латентность, если она перезаписывает полную строку (нет необходимости извлекать предыдущие данные и слияние).
  • Имеет не временный намек, делая его неприступным.

# 1 и # 2 могут улучшить латентность и пропускную способность этих операций, если они связаны с памятью, но # 3 в основном заставляет их быть привязанными к памяти, даже если они могут вписаться в некоторый уровень кеша. Это, вероятно, превосходит преимущества, так как латентность памяти /BW значительно хуже для начала.

Итак, ваша реализация библиотеки memset, вероятно, использует неправильный порог для переключения в версию потоковых хранилищ (я думаю, она не мешает проверять размер вашего LLC, но при условии, что 1M - резидент памяти, довольно странно). Я предлагаю попробовать альтернативные библиотеки или отключить способность компилятора их генерировать (если он поддерживается).

Ответ 3

Ваш бенчмарк записывает только в память, никогда не читает, используя memset, который, вероятно, продуман, чтобы не читать что-либо из кэша в память. Вполне возможно, что с помощью этого кода, в котором вы используете только половину возможностей кэш-памяти, просто нет увеличения производительности по сравнению с необработанной памятью. Тот факт, что запись в сырую память довольно близка к скорости L2, может быть намеком. Если L2 работает со скоростью 26 ГБ/с, основная память - 18 ГБ/с, что вы действительно можете ожидать для кеша L3?

Вы измеряете пропускную способность, а не латентность. Я бы попробовал тест, в котором вы фактически используете силу кеша L3, предоставляя данные с меньшей задержкой, чем основная память.