Используя сборку C/Intel, какой самый быстрый способ проверить, содержит ли 128-байтовый блок памяти все нули?

Ответ 1

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

cmp    qword ptr [rax],      0x0       0.171s
jnz    0x14000222                     42.426s

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

cmp    qword ptr [rax+0x40], 0x0       0.156s
jnz    0x14000222                      2.550s

Те 42,4 + 2,5 секунды, которые были учтены инструкциями JNZ, действительно являются остановкой, вызванной предыдущей загрузкой из памяти... процессор сидит без дела в течение 45 секунд за время, когда вы профилировали программу... ожидая DRAM.

Вы можете спросить, что такое вторая точка доступа на полпути. Ну, вы получаете доступ к 128-байтам, а кэш-строки - 64-байтные, CPU начал предвыборную для вас, как только он прочитал первые 64-байтные... но вы не сделали достаточной работы с первыми 64-байтами полностью перекрывают латентность перехода в память.

Ширина памяти Ivy Bridge очень высока (это зависит от вашей системы, но я догадываюсь о 10 ГБ/сек). Ваш блок памяти составляет 4 ГБ, вы можете пропустить его менее чем за 1 секунду, если вы получите доступ к нему последовательно, и пусть данные предварительной выборки CPU будут впереди вас.

Я предполагаю, что вы пресекаете prefetcher данных CPU, обращаясь к 128-байтовым блокам непересекающимся образом.

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

Другое дело - TLB misses. Это дорого, особенно в 64-битной системе. Вместо использования страниц 4 КБ рассмотрите возможность использования 2 МБ huge pages. См. Эту ссылку для поддержки Windows для них: Поддержка больших страниц (Windows)

Если вы должны получить доступ к данным 4 ГБ несколько случайным образом, но заранее знаете последовательность значений m7 (ваш индекс), вы можете pipeline выборку памяти явно перед вашим использованием (ей нужно чтобы было несколько 100 циклов ЦП раньше, когда вы будете использовать его для повышения эффективности). См

• _mm_prefetch
• использование "_mm_prefetch (...)"
• MM_PREFETCH

Вот некоторые ссылки, которые могут быть полезны в общем случае для оптимизации памяти

Что каждый программист должен знать о памяти Ульриха Дреппера

http://www.akkadia.org/drepper/cpumemory.pdf

Архитектура машины: все, что ваш язык программирования никогда не говорил вам, Herb Sutter

http://www.gotw.ca/publications/concurrency-ddj.htm

http://nwcpp.org/static/talks/2007/Machine_Architecture_-_NWCPP.pdf

http://video.google.com/videoplay?docid=-4714369049736584770#

Ответ 2

Извините за ответ, у меня недостаточно репутации для комментариев.
Что произойдет, если вы используете следующее в качестве теста?

if( (psz[0]  | psz[1]  | psz[2]  | psz[3]  |
     psz[4]  | psz[5]  | psz[6]  | psz[7]  |
     psz[8]  | psz[9]  | psz[10] | psz[11] |
     psz[12] | psz[13] | psz[14] | psz[15] ) == 0) continue;

К сожалению, у меня нет 64-битной системы, на которой ее компилировать, и я не знаком с тем, что именно делает компилятор с кодом c, но мне кажется, что двоичный файл или будет быстрее, чем индивидуальный == сравнения. Я также не знаю, что такое встроенные функции Intel, но может быть возможно оптимизировать вышеуказанный код аналогично тому, что вы уже сделали.
Надеюсь, мой ответ поможет. Mmarss

Ответ 3

В 98% 128-байтовых блоков все ноль, вы усредняете менее одного ненулевого байта на страницу 4K. С массивом, который разрежен, попробовали ли вы хранить его как разреженный массив? Вы сэкономите огромные объемы памяти и сопутствующие задержки кэширования; Я не удивлюсь, если обычная std:: map окажется быстрее.

Ответ 4

Рассматривали ли вы инструкции Intel по сканированию строк? Они имеют очень высокую скорость передачи данных, и процессор знает, что доступ к данным последователен.

     mov      rdi, <blockaddress>
     cld
     xor      rax, rax
     mov      rcx, 128/8
     repe     scasq
     jne      ...

Это не поможет проблемы с отсутствием данных в кеше. Вы можете исправить это, используя инструкцию Intel prefetch, если вы знаете, какой фрагмент вы хотите рассмотреть заранее. См. http://software.intel.com/en-us/articles/use-software-data-prefetch-on-32-bit-intel-architecture

[РЕДАКТИРОВАТЬ, чтобы запрограммировать промежуточные икоты, указанные в комментариях)

Ответ 5

Спасибо за отличные советы, полученные до сих пор.

Я чувствовал уверенность в том, что "мега" или "подход" Mmarss повысят производительность, поскольку он породил меньше инструкций на языке ассемблера. Однако, когда я запускал свою тестовую программу, мне потребовалось 163 секунды против 150 секунд для моих оригинальных неуклюжих && решение и 145 секунд для моего оригинального неуклюжего решения Intel instrinsics (эти два описаны в моем первоначальном посте).

Для полноты, вот код C, который я использовал для подхода "мега или":

if ((psz[0]  | psz[1]  | psz[2]  | psz[3]
|    psz[4]  | psz[5]  | psz[6]  | psz[7]
|    psz[8]  | psz[9]  | psz[10] | psz[11]
|    psz[12] | psz[13] | psz[14] | psz[15]) == 0) continue;

Узел VTune был:

mov    rax, qword ptr [rcx+0x78]    0.155s
or     rax, qword ptr [rcx+0x70]   80.972s
or     rax, qword ptr [rcx+0x68]    1.292s
or     rax, qword ptr [rcx+0x60]    0.311s
or     rax, qword ptr [rcx+0x58]    0.249s
or     rax, qword ptr [rcx+0x50]    1.229s
or     rax, qword ptr [rcx+0x48]    0.187s
or     rax, qword ptr [rcx+0x40]    0.233s
or     rax, qword ptr [rcx+0x38]    0.218s
or     rax, qword ptr [rcx+0x30]    1.742s
or     rax, qword ptr [rcx+0x28]    0.529s
or     rax, qword ptr [rcx+0x20]    0.233s
or     rax, qword ptr [rcx+0x18]    0.187s
or     rax, qword ptr [rcx+0x10]    1.244s
or     rax, qword ptr [rcx+0x8]     0.155s
or     rax, qword ptr [rcx]         0.124s
jz     0x1400070b9                  0.342s

Затем я попытался перевести идею "мега или" в Intel instrinsics с помощью:

__m128i tt7;
// ...
tt7 = _mm_or_si128(_mm_or_si128(_mm_or_si128(psz[0], psz[1]),
      _mm_or_si128(psz[2], psz[3])),
      _mm_or_si128(_mm_or_si128(psz[4], psz[5]),
      _mm_or_si128(psz[6], psz[7])));
if ( (tt7.m128i_i64[0] | tt7.m128i_i64[1]) == 0) continue;

хотя и тот, который оказался медленнее, заняв 155 секунд. Его сборка VTune была:

movdqa xmm2, xmmword ptr [rax]         0.047s
movdqa xmm0, xmmword ptr [rax+0x20]   75.461s
movdqa xmm1, xmmword ptr [rax+0x40]    2.567s
por    xmm0, xmmword ptr [rax+0x30]    1.867s
por    xmm2, xmmword ptr [rax+0x10]    0.078s
por    xmm1, xmmword ptr [rax+0x50]    0.047s
por    xmm2, xmm0                      0.684s
movdqa xmm0, xmmword ptr [rax+0x60]    0.093s
por    xmm0, xmmword ptr [rax+0x70]    1.214s
por    xmm1, xmm0                      0.420s
por    xmm2, xmm1                      0.109s
movdqa xmmword ptr tt7$[rsp], xmm2     0.140s
mov    rax, qword ptr [rsp+0x28]       0.233s
or     rax, qword ptr [rsp+0x20]       1.027s
jz     0x1400070e2                     0.498s

Подход Intel instrinsics выше довольно груб. Предложения по его улучшению приветствуются.

Это еще раз показывает, насколько важно измерять. Почти каждый раз, когда я догадывался, что будет быстрее, я ошибся. Тем не менее, пока вы тщательно оцениваете каждое изменение, вы не можете ухудшаться, оно может только улучшиться. Хотя я прошёл назад (как указано выше) чаще, чем вперед, за последнюю неделю мне удалось сократить время работы небольшой тестовой программы с 221 секунды до 145. Учитывая, что реальная программа будет работать для месяцев, что позволит сэкономить дни.

Ответ 6

Предложение: выровняйте массив до 128B, поэтому пространственный предварительный выборщик всегда хочет заполнить правильную строку кеша, чтобы сделать пару строк кэша 128B. Руководство по оптимизации Intel, стр. 2-30 (стр. 60 из PDF), описывающее Sandybridge/Ivybridge:

Профилированный предварительный набор: этот prefetcher стремится завершить каждую строку кэша, извлеченную в кэш L2, с помощью пара-линия, которая завершает его до 128-байтового выровненного фрагмента.

Когда ваш массив выравнивается только до 64B, чтение 128B может касаться двух пар строк кэша, что приводит к пространственному предборнику L2, чтобы выдать больше загрузок для данных, которые, вероятно, никогда не будут использоваться.

Ваш ответ имеет правильную идею: ИЛИ блок вместе с векторами, затем проверьте, что для all-zero. Использование одной ветки, вероятно, лучше, чем разветвление на каждые 8 ​​байтов.

Но ваша стратегия тестирования вектора сосет: не храните его, а затем скалярную нагрузку + ИЛИ обе половины. Это идеальный прецедент для SSE4 PTEST, который позволяет нам избегать обычного pcmpeqb / pmovmskb:

ptest   xmm0,xmm0      ; 2 uops, and Agner Fog lists it as 1c latency for SnB/IvB, but this is probably bogus.  2c is more likely
jz    vector_is_all_zero
; 3 uops, but shorter latency and smaller code-size than pmovmskb

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

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

Итак, я мог бы сделать:

allzero_128B(const char *buf)
{
    const __m128i *buf128 = (const __m128i*)buf;  // dereferencing produces 128b aligned-load instructions

    __m128i or0 = _mm_or_si128(buf[0], buf[2]);
    __m128i or2 = _mm_or_si128(buf[1], buf[3]);
    __m128i first64 = _mm_or_si128(or0, or2);
    // A chain of load + 3 OR instructions would be fewer fused-domain uops
    //  than load+or, load+or, or(xmm,xmm).  But resolving the branch faster is probably the most important thing.

    if (_mm_testz_si128(first64, first64)
        return 0;

    __m128i or4 = _mm_or_si128(buf[4], buf[6]);
    __m128i or6 = _mm_or_si128(buf[5], buf[7]);
    __m128i first64 = _mm_or_si128(or4, or6);


}

В IvyBrige нет ничего, что можно выиграть от использования 256b AVX op. Vector-FP 256b VORPS ymm выполняет в два раза больше работы на каждый, но работает только на port5. (POR xmm работает на p015). 256b нагрузки выполняются как две 128b половинки, но они все еще только 1 uop.

Я не вижу способа использовать один CMPEQPS для проверки 256b-вектора для all-zero. +0.0 сравнивается с -0.0, поэтому 1-бит в позиции знакового бита будет оставаться необнаруженным в сравнении с нулем. Я не думаю, что любой из предикатов CMPPS также помогает, поскольку ни один из них не реализует сравнения, которые обрабатывают -0.0, отличные от +0.0. (См. инструкции SIMD для сравнения равенства с плавающей запятой (с NaN == NaN) для получения дополнительной информации о FP-равенстве).

; First 32B arrives in L1D (and load buffers) on cycle n
vmovaps  ymm0,   [rdi+64]              ; ready on cycle n+1  (256b loads take 2 cycles)
vorps    ymm0,   ymm0, [rdi+96]        ; ready on cycle n+3  (the load uop is executing on cycles n+1 and n+2)
vextractf128 xmm1, ymm0, 1           ; 2c latency on IvB, 3c on Haswell
                                     ; xmm1 ready on cycle n+5
vpor     xmm0,   xmm0, xmm1          ; ready on n+6 (should be no bypass delay for a shuffle (vextractf128) -> integer booleans)
vptest   xmm0,   xmm0
jz   second_cacheline_all_zero

Нет, это не лучше

; First 32B of the cache-line arrives in L1D on cycle n (IvB has a 32B data path from L2->L1)
vmovaps  xmm0,   [rdi+64]              ; result ready on cycle n
vmovaps  xmm1,   [rdi+64 + 16]         ; result ready on cycle n  (data should be forwarded to outstanding load buffers, I think?)
vpor     xmm0,   xmm0, [rdi+64 + 32]   ; ready on cycle n+1
vpor     xmm1,   xmm1, [rdi+64 + 48]   ; ready on cycle n+1, assuming the load uops get their data the cycle after the first pair.
vpor     xmm0,   xmm1                  ; ready on cycle n+2
vptest   xmm0,   xmm0
jz   second_cacheline_all_zero

С AVX2 операторы 256b будут иметь смысл, включая VPTEST ymm, ymm.