Ответ 1
Ответ на заголовок вопроса
Теперь, когда вы разместили полный код: вызов count2(a,N) выведен из цикла в main. Время работы по-прежнему очень незначительно увеличивается с количеством циклов (например, 1<<18), но все, что делает цикл, это одиночный add. Компилятор оптимизирует его, чтобы больше походить на этот источник:
uint64_t hoisted_count = count2(a,N);
for (uint64_t i=0; i < ((uint64_t)1<<18); i++) {
n += hoisted_count; // doesn't optimize to a multiply
}
Не существует конфликта регистров: %rax содержит результат инструкции asm, заключенный в строку count2. Затем он используется как исходный операнд в крошечном цикле, который умножает его на n на повторное добавление.
(см. asm в Godbolt Compiler Explorer, и обратите внимание на все предупреждения компилятора об арифметике на void* s: clang отказывается скомпилируйте свой код):
## the for() loop in main, when using count2()
.L23:
addq %rax, %r12
subq $1, %rdx
jne .L23
%rdx здесь счетчик циклов, а %r12 - это аккумулятор, который содержит n. IDK, почему gcc не оптимизирует его при умножении на постоянное время.
Предположительно, версия, которая была в 260 тыс. раз медленнее, не смогла вытащить весь count2 из цикла. С точки зрения gcc, версия inline asm намного проще: оператор asm рассматривается как чистая функция его входов, и gcc даже не знает ничего об этом, касаясь памяти. Версия C затрагивает кучу памяти, и гораздо сложнее доказать, что ее можно поднять.
Использование clobber "memory" в выражении asm не позволяло ему подниматься, когда я проверял godbolt. Вы можете указать из наличия или отсутствия цели ветвления в main перед векторным блоком.
Но в любом случае время выполнения будет выглядеть как n + rep_count vs. n * rep_count.
Оператор asm не использует привязку "memory" clobber или любые входы памяти, чтобы сообщить gcc, что он считывает память, на которую указывают указатели на вход. Возможны некорректные оптимизации. будучи выведенным из цикла, который модифицировал элементы массива. (См. Раздел раздел Clobbers в руководстве на примере использования ввода в память немого анонимного struct вместо обложки "memory" clobber. К сожалению, я не думаю, что это можно использовать, когда блок памяти не имеет постоянного времени компиляции.)
Я думаю, что -fno-inline предотвращает подъем, потому что функция не помечена __attribute__((const)) или немного слабее __attribute__((pure)), чтобы указать отсутствие побочных эффектов. После встраивания оптимизатор может видеть, что для оператора asm.
count0 не оптимизируется ни к чему хорошему, потому что gcc и clang не могут автоинъекционировать циклы, где число итераций неизвестно в начале. то есть они сосут на таких вещах, как strlen или memchr, или поисковые петли вообще, даже если им говорят, что они безопасны для доступа к памяти за пределами точки, в которой цикл поиска выходит раньше (например, используя char buf[static 512] как функция arg).
Оптимизация для вашего кода asm:
Как я прокомментировал вопрос, использование xor reg, 0xFFFF/jnz глупо по сравнению с cmp reg, 0xFFFF/jnz, потому что cmp/jcc может с помощью макросов встраивать uop. cmp reg, mem/jne также может сглаживаться с помощью макросов, поэтому скалярная версия, которая выполняет загрузку /xor/branch, использует 3x для каждого сравнения. (Разумеется, Sandybridge может только скомпенсировать загрузку, если он не использует режим индексированной адресации. Кроме того, SnB может только скомпенсировать только одну пару на блок декодирования, но вы, вероятно, получите первый cmp/jcc и ветвь цикла к макро-предохранителю.) В любом случае, xor - плохая идея. Лучше всего xor прямо перед tzcnt, поскольку сохранение в этом цикле более важно, чем размер кода или общий объем.
Ваша скалярная петля - это 9 скомпилированных доменов, которые слишком много для выдачи на одной итерации за 2 такта. (SnB - это 4-х широкий конвейер, и для крошечных циклов он может фактически поддерживать это.)
Отступы в коде в первой версии вопроса с count += __builtin_ctz на том же уровне, что и if, заставляют меня думать, что вы считали блоки рассогласования, а не просто находили первый.
К сожалению, код asm, который я написал для первой версии этого ответа, не решает ту же проблему, что и обновленный и понятный код OP. См. Старую версию этого ответа для SSE2 asm, которая подсчитывает байты 0xFF с использованием pcmpeqb/paddb и psadbw для горизонтальной суммы, чтобы избежать обхода.
Получение ускорения с помощью SSE2 (или AVX):
Ветвление на результат a pcmpeq занимает гораздо больше, чем разветвление на cmp. Если наш массив поиска велик, мы можем использовать цикл, который проверяет сразу несколько векторов, а затем выясняет, какой из байтов имел наш хит после выхода из цикла.
Эта оптимизация применяется и к AVX2.
Здесь моя попытка, используя GNU C inline asm с синтаксисом -masm=intel. (Intrinsics может дать лучшие результаты, особенно при встраивании, потому что компилятор понимает intrinsics и поэтому может делать постоянное распространение через них и т.д. OTOH, вы можете часто бить компилятор рукописным asm, если понимаете сделку -offs и микроархитектуры, на которую вы нацеливаете. Кроме того, если вы можете смело сделать некоторые предположения, но вы не можете легко передать их компилятору.)
#include <stdint.h>
#include <immintrin.h>
// compile with -masm=intel
// len must be a multiple of 32 (TODO: cleanup loop)
// buf should be 16B-aligned for best performance
size_t find_first_zero_bit_avx1(const char *bitmap, size_t len) {
// return size_t not uint64_t. This same code works in 32bit mode, and in the x32 ABI where pointers are 32bit
__m128i pattern, vtmp1, vtmp2;
const char *result_pos;
int tmpi;
const char *bitmap_start = bitmap;
asm ( // modifies the bitmap pointer, but we're inside a wrapper function
"vpcmpeqw %[pat], %[pat],%[pat]\n\t" // all-ones
".p2align 4\n\t" // force 16B loop alignment, for the benefit of CPUs without a loop buffer
//IACA_START // See the godbolt link for the macro definition
".Lcount_loop%=:\n\t"
// " movdqu %[v1], [ %[p] ]\n\t"
// " pcmpeqb %[v1], %[pat]\n\t" // for AVX: fold the load into vpcmpeqb, making sure to still use a one-register addressing mode so it can micro-fuse
// " movdqu %[v2], [ %[p] + 16 ]\n\t"
// " pcmpeqb %[v2], %[pat]\n\t"
" vpcmpeqb %[v1], %[pat], [ %[p] ]\n\t" // Actually use AVX, to get a big speedup over the OP scalar code on his SnB CPU
" vpcmpeqb %[v2], %[pat], [ %[p] + 16 ]\n\t"
" vpand %[v2], %[v2], %[v1]\n\t" // combine the two results from this iteration
" vpmovmskb %k[result], %[v2]\n\t"
" cmp %k[result], 0xFFFF\n\t" // k modifier: eax instead of rax
" jne .Lfound%=\n\t"
" add %[p], 32\n\t"
" cmp %[p], %[endp]\n\t" // this is only 2 uops after the previous cmp/jcc. We could re-arrange the loop and put the branches farther apart if needed. (e.g. start with a vpcmpeqb outside the loop, so each iteration actually sets up for the next)
" jb .Lcount_loop%=\n\t"
//IACA_END
// any necessary code for the not-found case, e.g. bitmap = endp
" mov %[result], %[endp]\n\t"
" jmp .Lend%=\n\t"
".Lfound%=:\n\t" // we have to figure out which vector the first non-match was in, based on v1 and (v2&v1)
// We could just search the bytes over again, but we don't have to.
// we could also check v1 first and branch, instead of checking both and using a branchless check.
" xor %k[result], 0xFFFF\n\t"
" tzcnt %k[result], %k[result]\n\t" // runs as bsf on older CPUs: same result for non-zero inputs, but different flags. Faster than bsf on AMD
" add %k[result], 16\n\t" // result = byte count in case v1 is all-ones. In that case, v2&v1 = v2
" vpmovmskb %k[tmp], %[v1]\n\t"
" xor %k[tmp], 0xFFFF\n\t"
" bsf %k[tmp], %k[tmp]\n\t" // bsf sets ZF if its *input* was zero. tzcnt flag results are based on its output. For AMD, it would be faster to use more insns (or a branchy strategy) and avoid bsf, but Intel has fast bsf.
" cmovnz %k[result], %k[tmp]\n\t" // if there was a non-match in v1, use it instead of tzcnt(v2)+16
" add %[result], %[p]\n\t" // If we needed to force 64bit, we could use %q[p]. But size_t should be 32bit in the x32 ABI, where pointers are 32bit. This is one advantage to using size_t over uint64_t
".Lend%=:\n\t"
: [result] "=&a" (result_pos), // force compiler to pic eax/rax to save a couple bytes of code-size from the special cmp eax, imm32 and xor eax,imm32 encodings
[p] "+&r" (bitmap),
// throw-away outputs to let the compiler allocate registers. All early-clobbered so they aren't put in the same reg as an input
[tmp] "=&r" (tmpi),
[pat] "=&x" (pattern),
[v1] "=&x" (vtmp1), [v2] "=&x" (vtmp2)
: [endp] "r" (bitmap+len)
// doesn't compile: len isn't a compile-time constant
// , "m" ( ({ struct { char x[len]; } *dummy = (typeof(dummy))bitmap ; *dummy; }) ) // tell the compiler *which* memory is an input.
: "memory" // we read from data pointed to by bitmap, but bitmap[0..len] isn't an input, only the pointer.
);
return result_pos - bitmap_start;
}
Этот фактически компилирует и собирает в asm, который выглядит так, как я ожидал, но я не тестировал его. Обратите внимание, что он оставляет все распределение регистров компилятору, поэтому он более дружественный к inlining. Даже без инкрустации он не заставляет использовать регистр с сохранением вызова, который должен быть сохранен/восстановлен (например, использование ограничения "b").
Не сделано: скалярный код для обработки последнего куска данных под-32B.
статический перфорированный анализ для процессоров Intel SnB-семейства на основе Agner Fog guide/tables. См. Также x86 теги wiki. Я предполагаю, что мы не являемся узким местом по пропускной способности кеша, поэтому этот анализ применяется только тогда, когда данные горячие в кэше L2, или, может быть, только кеш L1 достаточно быстро.
Этот цикл может выходить из интерфейсного интерфейса на одной итерации (два вектора) на 2 такта, потому что он имеет 7 плавных доменов. (Внешние проблемы в группах по 4). (Вероятно, на самом деле это 8 uops, если две пары cmp/jcc декодируются в одном блоке. Haswell и более поздние могут выполнять два макро-слияния на группу декодирования, но предыдущие процессоры могут только сначала скомпилировать макрос. цикл, так что ранняя ветвь находится дальше от ветки p < endp.)
Все эти утипы с объединенными доменами включают в себя ALU uop, поэтому узкое место будет на портах выполнения ALU. Хасуэлл добавил четвертый блок ALU, который может обрабатывать простые не-векторные операционные системы, включая ветки, поэтому может запускать этот цикл на одной итерации на 2 такта (16B за такт). Ваш i5-2550k (упомянутый в комментариях) является процессором SnB.
Я использовал IACA для подсчета количества оборотов на порт, поскольку для этого требуется много времени. IACA тупой и думает, что существует какая-то зависимость между итерациями, отличная от счетчика циклов, поэтому мне пришлось использовать -no_interiteration:
g++ -masm=intel -Wall -Wextra -O3 -mtune=haswell find-first-zero-bit.cpp -c -DIACA_MARKS
iaca -64 -arch IVB -no_interiteration find-first-zero-bit.o
Intel(R) Architecture Code Analyzer Version - 2.1
Analyzed File - find-first-zero-bit.o
Binary Format - 64Bit
Architecture - SNB
Analysis Type - Throughput
Throughput Analysis Report
--------------------------
Block Throughput: 2.50 Cycles Throughput Bottleneck: Port1, Port5
Port Binding In Cycles Per Iteration:
-------------------------------------------------------------------------
| Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 |
-------------------------------------------------------------------------
| Cycles | 2.0 0.0 | 2.5 | 1.0 1.0 | 1.0 1.0 | 0.0 | 2.5 |
-------------------------------------------------------------------------
N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected
! - instruction not supported, was not accounted in Analysis
| Num Of | Ports pressure in cycles | |
| Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | |
---------------------------------------------------------------------
| 2^ | | 1.0 | 1.0 1.0 | | | | CP | vpcmpeqb xmm1, xmm0, xmmword ptr [rdx]
| 2^ | | 0.6 | | 1.0 1.0 | | 0.4 | CP | vpcmpeqb xmm2, xmm0, xmmword ptr [rdx+0x10]
| 1 | 0.9 | 0.1 | | | | 0.1 | CP | vpand xmm2, xmm2, xmm1
| 1 | 1.0 | | | | | | | vpmovmskb eax, xmm2
| 1 | | | | | | 1.0 | CP | cmp eax, 0xffff
| 0F | | | | | | | | jnz 0x18
| 1 | 0.1 | 0.9 | | | | | CP | add rdx, 0x20
| 1 | | | | | | 1.0 | CP | cmp rdx, rsi
| 0F | | | | | | | | jb 0xffffffffffffffe1
В SnB: pcmpeqb может работать на p1/p5. Сплавленная слияния и ветвления может работать только на p5. Неплавкий cmp может работать на p015. Во всяком случае, если одна из ветвей не является макроблоком, цикл может работать на одной итерации за 8/3 = 2.666 циклов. С макро-fusion наилучшим случаем является 7/3 = 2.333 цикла. (IACA не пытается имитировать распределение uops на порты точно так же, как аппаратное обеспечение будет динамически принимать эти решения. Однако мы не можем ожидать идеального планирования с аппаратного обеспечения, поэтому 2 вектора на 2,5 цикла, вероятно, разумны как с макросами -fusions.Uops, которые могли бы использовать port0, иногда украдут порт1 или порт5, уменьшая пропускную способность.)
Как я уже говорил, Хасуэлл лучше справляется с этой петлей. IACA считает, что HSW может запускать цикл на одной итерации на 1.75c, но это явно неправильно, потому что принятая петля-ветвь завершает группу проблем. Он будет выдаваться в повторяющемся шаблоне 4,3 мк. Но исполнительные блоки могут обрабатывать большую пропускную способность, чем интерфейс для этого цикла, поэтому он действительно должен быть в состоянии идти в ногу с интерфейсом на Haswell/Broadwell/Skylake и работать на одной итерации за 2 такта.
Дальнейшее разворачивание большего количества vpcmpeqb/vpand составляет всего 2 мкп на вектор (или 3 без AVX, где мы будем загружать на царапину, а затем использовать это как пункт назначения для pcmpeqb.) Таким образом, при достаточной развертке, мы должны иметь возможность делать 2 векторных нагрузки за такт. Без AVX это было бы невозможно без трюка PAND, так как векторная загрузка/сравнение/movmsk/test-and-branch - 4 раза. Большие разматывания делают больше работы для декодирования конечной позиции, где мы нашли совпадение: скалярный цикл очистки cmp может быть хорошей идеей, когда мы находимся в этом районе. Возможно, вы можете использовать один и тот же скалярный цикл для очистки не-множественных размеров 32B.
Если вы используете SSE, с movdqu/pcmpeqb xmm,xmm, мы можем использовать режим индексированной адресации, не затрачивая нас на расчеты, потому что загрузка movdqu всегда представляет собой единую нагрузку, независимо от режима адресации. (В отличие от магазина нет необходимости в микроплавлении). Это позволяет нам сохранить нуль накладных расходов цикла, используя базовый указатель, указывающий на конец массива, и индекс, отсчитывающий от нуля. например add %[idx], 32/js, пока индекс отрицательный.
С AVX, однако, мы можем сохранить 2 uops с использованием режима однократной адресации, поэтому vpcmpeqb %[v1], %[pat], [ %[p] + 16 ] может быть микро-предохранителем. Это означает, что нам нужна структура цикла add/cmp/jcc, которую я использовал в примере. То же самое относится к AVX2.