С помощью сборки C/Intel, какой самый быстрый способ проверить, содержит ли 128-байтовый блок памяти все нули?
Продолжая свой первый вопрос, я пытаюсь оптимизировать горячую точку памяти, найденную через VTune, для профилирования 64-битной программы на Си.
В частности, я хотел бы найти самый быстрый способ проверить, содержит ли 128-байтовый блок памяти все нули. Вы можете принять любое желаемое выравнивание памяти для блока памяти; Я использовал 64-байтовое выравнивание.
Я использую ПК с процессором Intel Ivy Bridge Core i7 3770 с 32 ГБ памяти и бесплатной версией компилятора Microsoft vs2010 C.
Моя первая попытка была:
const char* bytevecM; // 4 GB block of memory, 64-byte aligned
size_t* psz; // size_t is 64-bits
// ...
// "m7 & 0xffffff80" selects the 128 byte block to test for all zeros
psz = (size_t*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (psz[0] == 0 && psz[1] == 0
&& psz[2] == 0 && psz[3] == 0
&& psz[4] == 0 && psz[5] == 0
&& psz[6] == 0 && psz[7] == 0
&& psz[8] == 0 && psz[9] == 0
&& psz[10] == 0 && psz[11] == 0
&& psz[12] == 0 && psz[13] == 0
&& psz[14] == 0 && psz[15] == 0) continue;
// ...
Профилирование VTune соответствующей сборки следует:
cmp qword ptr [rax], 0x0 0.171s
jnz 0x14000222 42.426s
cmp qword ptr [rax+0x8], 0x0 0.498s
jnz 0x14000222 0.358s
cmp qword ptr [rax+0x10], 0x0 0.124s
jnz 0x14000222 0.031s
cmp qword ptr [rax+0x18], 0x0 0.171s
jnz 0x14000222 0.031s
cmp qword ptr [rax+0x20], 0x0 0.233s
jnz 0x14000222 0.560s
cmp qword ptr [rax+0x28], 0x0 0.498s
jnz 0x14000222 0.358s
cmp qword ptr [rax+0x30], 0x0 0.140s
jnz 0x14000222
cmp qword ptr [rax+0x38], 0x0 0.124s
jnz 0x14000222
cmp qword ptr [rax+0x40], 0x0 0.156s
jnz 0x14000222 2.550s
cmp qword ptr [rax+0x48], 0x0 0.109s
jnz 0x14000222 0.124s
cmp qword ptr [rax+0x50], 0x0 0.078s
jnz 0x14000222 0.016s
cmp qword ptr [rax+0x58], 0x0 0.078s
jnz 0x14000222 0.062s
cmp qword ptr [rax+0x60], 0x0 0.093s
jnz 0x14000222 0.467s
cmp qword ptr [rax+0x68], 0x0 0.047s
jnz 0x14000222 0.016s
cmp qword ptr [rax+0x70], 0x0 0.109s
jnz 0x14000222 0.047s
cmp qword ptr [rax+0x78], 0x0 0.093s
jnz 0x14000222 0.016s
Я смог улучшить это с помощью встроенных функций Intel:
const char* bytevecM; // 4 GB block of memory
__m128i* psz; // __m128i is 128-bits
__m128i one = _mm_set1_epi32(0xffffffff); // all bits one
// ...
psz = (__m128i*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (_mm_testz_si128(psz[0], one) && _mm_testz_si128(psz[1], one)
&& _mm_testz_si128(psz[2], one) && _mm_testz_si128(psz[3], one)
&& _mm_testz_si128(psz[4], one) && _mm_testz_si128(psz[5], one)
&& _mm_testz_si128(psz[6], one) && _mm_testz_si128(psz[7], one)) continue;
// ...
Профилирование VTune соответствующей сборки следует:
movdqa xmm0, xmmword ptr [rax] 0.218s
ptest xmm0, xmm2 35.425s
jnz 0x14000ddd 0.700s
movdqa xmm0, xmmword ptr [rax+0x10] 0.124s
ptest xmm0, xmm2 0.078s
jnz 0x14000ddd 0.218s
movdqa xmm0, xmmword ptr [rax+0x20] 0.155s
ptest xmm0, xmm2 0.498s
jnz 0x14000ddd 0.296s
movdqa xmm0, xmmword ptr [rax+0x30] 0.187s
ptest xmm0, xmm2 0.031s
jnz 0x14000ddd
movdqa xmm0, xmmword ptr [rax+0x40] 0.093s
ptest xmm0, xmm2 2.162s
jnz 0x14000ddd 0.280s
movdqa xmm0, xmmword ptr [rax+0x50] 0.109s
ptest xmm0, xmm2 0.031s
jnz 0x14000ddd 0.124s
movdqa xmm0, xmmword ptr [rax+0x60] 0.109s
ptest xmm0, xmm2 0.404s
jnz 0x14000ddd 0.124s
movdqa xmm0, xmmword ptr [rax+0x70] 0.093s
ptest xmm0, xmm2 0.078s
jnz 0x14000ddd 0.016s
Как видите, инструкций по сборке меньше, и эта версия оказалась более быстрой в тестах синхронизации.
Поскольку я довольно слаб в области инструкций Intel SSE/AVX, я приветствую советы о том, как их можно было бы лучше использовать для ускорения этого кода.
Хотя я искал сотни доступных инстинктов, возможно, я упустил идеальные. В частности, я не смог эффективно использовать _mm_cmpeq_epi64(); Я искал "не равную" версию этой сущности (которая, кажется, лучше подходит для этой проблемы), но выдохлась. Хотя приведенный ниже код "работает":
if (_mm_testz_si128(_mm_andnot_si128(_mm_cmpeq_epi64(psz[7], _mm_andnot_si128(_mm_cmpeq_epi64(psz[6], _mm_andnot_si128(_mm_cmpeq_epi64(psz[5], _mm_andnot_si128(_mm_cmpeq_epi64(psz[4], _mm_andnot_si128(_mm_cmpeq_epi64(psz[3], _mm_andnot_si128(_mm_cmpeq_epi64(psz[2], _mm_andnot_si128(_mm_cmpeq_epi64(psz[1], _mm_andnot_si128(_mm_cmpeq_epi64(psz[0], zero), one)), one)), one)), one)), one)), one)), one)), one), one)) continue;
он не читается на границе и (что неудивительно) оказался намного медленнее, чем две версии, приведенные выше. Я уверен, что должен быть более элегантный способ использования _mm_cmpeq_epi64 (), и приветствую совет о том, как этого добиться.
В дополнение к использованию встроенных функций из C, приветствуются также решения этой проблемы на языке ассемблера Intel.
6 ответов
Основная проблема, как отмечали другие, заключается в том, что проверяемые 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-байтные, процессор начал предварительную выборку для вас, как только он прочитал первые 64-байтовые... но вы не сделали достаточно работы с первыми 64-байтовыми полностью перекрывают задержку перехода в память.
Пропускная способность памяти Ivy Bridge очень высока (это зависит от вашей системы, но я предполагаю более 10 ГБ / с). Ваш блок памяти составляет 4 ГБ, вы должны быть в состоянии сжать его менее чем за 1 секунду, если вы обращаетесь к нему последовательно и позволяете процессору предварительно выбирать данные.
Я предполагаю, что вы мешаете предварительному извлечению данных процессора, обращаясь к 128-байтовым блокам несмежным способом.
Измените ваш шаблон доступа, чтобы быть последовательным, и вы будете удивлены, насколько быстрее он работает. Затем вы можете позаботиться о следующем уровне оптимизации, который будет гарантировать, что предсказание ветвления работает хорошо.
Еще одна вещь, чтобы рассмотреть это TLB misses, Это дорого, особенно в 64-битной системе. Вместо того, чтобы использовать страницы 4 КБ, рассмотрите возможность использования 2 МБ huge pages, См. Эту ссылку для поддержки Windows для этих: Поддержка больших страниц (Windows)
Если вам нужен случайный доступ к данным 4 ГБ, но вы заранее знаете последовательность m7 значения (ваш индекс), то вы можете pipeline память извлекается явно перед вашим использованием (она должна быть на несколько 100 циклов процессора раньше, чем вы будете использовать ее, чтобы быть эффективной). Увидеть
Вот некоторые ссылки, которые могут быть полезны в целом по теме оптимизации памяти
Что каждый программист должен знать о памяти Ульриха Дреппера
http://www.akkadia.org/drepper/cpumemory.pdf
Архитектура машины: вещи, которые ваш язык программирования никогда не говорил вам, Херб Саттер
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
Извините за ответ, мне не хватает репутации для комментариев.
Что произойдет, если вы используете следующее в качестве теста?
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
При том, что 98% из 128-байтовых блоков равны нулю, вы усредняете менее одного ненулевого байта на страницу 4K. Вы пытались сохранить массив как разреженный массив? Вы сэкономите огромные объемы памяти и связанные с этим задержки кэширования; Я не удивлюсь, если простая std::map получится быстрее.
Рассматривали ли вы инструкции по сканированию строк Intel? Они, как правило, имеют очень высокие скорости передачи данных, и процессор знает, что доступ к данным является последовательным.
mov rdi, <blockaddress>
cld
xor rax, rax
mov rcx, 128/8
repe scasq
jne ...
Это не поможет решить проблему отсутствия ваших данных в кеше. Вы можете исправить это, используя инструкцию Intel по предварительной выборке, если знаете, какой блок вы хотите рассмотреть заранее. См. http://software.intel.com/en-us/articles/use-software-data-prefetch-on-32-bit-intel-architecture
[РЕДАКТИРОВАТЬ, чтобы закодировать, чтобы объединить незначительные отклонения, указанные в комментариях]
Спасибо за отличные советы, полученные до сих пор.
Я был уверен, что подход Mmarss "мега или" улучшит производительность, потому что он генерирует меньше инструкций на языке ассемблера. Тем не менее, когда я запустил свою тестовую программу, мне потребовалось 163 секунды против 150 секунд для моего исходного неуклюжего решения && и 145 секунд для моего исходного неуклюжего решения Intel для встроенных функций (эти два описаны в моем первоначальном посте).
Для полноты вот код 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 Instinsics с помощью:
__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. Учитывая, что настоящая программа будет работать в течение месяцев, которые спасут дни.
Предложение: выровняйте ваш массив по 128B, так что пространственный предварительный выборщик всегда захочет заполнить правильную строку кэша, чтобы создать пару строк кэша 128B. Руководство по оптимизации Intel, стр. 2-30 (стр. 60 в PDF), описывающее Sandybridge / Ivybridge:
Spatial Prefetcher: этот предварительный сборщик стремится завершить каждую строку кэша, извлеченную в кэш L2, с парной строкой, которая завершает его до 128-байтового выровненного фрагмента.
Если ваш массив выровнен только до 64B, чтение 128B может коснуться двух пар строк кэша, что приведет к пространственному предварительному извлечению L2, чтобы выгрузить больше данных, которые вы, вероятно, никогда не будете использовать.
Ваш ответ имеет правильную идею: ИЛИ блок вместе с векторами, затем проверьте это на все ноль. Использование одной ветви, вероятно, лучше, чем ветвление отдельно на каждые 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
Обычно ветки предсказывают хорошо, и задержка для генерации входных данных их флагов не важна. Но в этом случае основным узким местом являются ошибочные прогнозы отрасли. Так что, вероятно, стоит потратить больше мопов (при необходимости), чтобы уменьшить задержку.
Я не уверен, лучше ли тестировать первую строку кэша перед загрузкой второй строки кэша, если вы обнаружите ненулевой байт без потери второго кэша. Пространственный prefetcher не может загрузить вторую строку кеша мгновенно, поэтому, вероятно, попробуйте ранний выход перед загрузкой второй строки кеша 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 ops. Vector-FP 256b VORPS ymm выполняет вдвое больше работы за моп, но работает только на порту 5. (POR xmm работает на p015). 256b нагрузки выполняются как две половинки 128b, но они все еще только 1 моп.
Я не вижу способа использовать один CMPEQPS для проверки вектора 256b на ноль. +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.