Как стать автором
Обновить

Комментарии 95

Что мешает -О3 дооптимизировать до одинаковых таймингов?

Например в варианте BM_SSE_COUNT_LOADU компилятор дополнительно раскрывает цикл на 4 итерации, но не делает это для BM_SSE_COUNT_SET_EPI.
           cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
  401040:       c5 f9 75 0c 48          vpcmpeqw (%rax,%rcx,2),%xmm0,%xmm1
  401045:       c5 f9 d7 f1             vpmovmskb %xmm1,%esi
  401049:       f3 0f b8 f6             popcnt %esi,%esi
  40104d:       48 01 d6                add    %rdx,%rsi
  401050:       c5 f9 75 4c 48 10       vpcmpeqw 0x10(%rax,%rcx,2),%xmm0,%xmm1
  401056:       c5 f9 d7 d1             vpmovmskb %xmm1,%edx
  40105a:       f3 0f b8 d2             popcnt %edx,%edx
  40105e:       48 01 f2                add    %rsi,%rdx
  401061:       c5 f9 75 4c 48 20       vpcmpeqw 0x20(%rax,%rcx,2),%xmm0,%xmm1
  401067:       c5 f9 d7 f1             vpmovmskb %xmm1,%esi
  40106b:       f3 0f b8 f6             popcnt %esi,%esi
  40106f:       c5 f9 75 4c 48 30       vpcmpeqw 0x30(%rax,%rcx,2),%xmm0,%xmm1
  401075:       48 01 d6                add    %rdx,%rsi
  401078:       c5 f9 d7 d1             vpmovmskb %xmm1,%edx
  40107c:       f3 0f b8 d2             popcnt %edx,%edx
  401080:       48 01 f2                add    %rsi,%rdx
Понятно что получается разный асемблер. Вопрос — почему он разный. Компилятор «не додумался» или вы «не учли краевой случай который компилятор учел».
Можно посмотреть, но, скорее всего, компилятор увидел число итераций, «понял», что ему придётся в дополнение к развёрнутому циклу ещё сделать пролог и эпилог большей (для обработки не выровнянного случая) и решил, что «овчинка выделки не стоит».

Векторизация и loop unrolling — это пока ближе к чёрной магии, чем к науке. Там тонны эвристик…
Хм. А как-то странно долго исследовать производительность на -O0, после чего сделать краткую сноску что будет с -O3, где результат совсем не так впечатляет. Ну и с "-O3 -march=corei7" SSE будет задействован автоматически. А еще можно попробовать взять icc вместо clang…
То, что компилятор «додумался» сделать на маленькой программке, совсем не гарантирует того, что он это сделает на большой. Поэтому лучше самому понимать, как писать более оптимальные варианты.
Через год оптимальные варианты станут менее оптимальными из-за нового AVX1024/AVX2048/…
Лучше критичные к производительности части выносить в отдельные функции, которые отдавать компилятору, проверяя выхлоп и делая замеры. Объём программы не влияет на качество оптимизации отдельно взятой функции. Зато код можно будет собрать при необходимости и под старые процессоры и под другие архитектуры.
AVX-512 уже 6 лет, и пока он появился только на ксяонах. Не стоит надеяться на то, что завтра производители подгонят процессоры, послезавтра компиляторы, а к концу недели быдлокод будет летать как фанера над Парижем.
Полностью отдавать действительно критичные части программы компилятору — тоже плохая идея. Компилятор не может правильно расположить данные в памяти и построить качественную архитектуру программы — он всего лишь выдаст код, который от него потребуют. Потребуете что-нибудь не то — оптимизаций не получите.
Через год оптимальные варианты станут менее оптимальными из-за нового AVX1024/AVX2048/…

Это ничего не меняет, это изменит лишь одну константу в нормальном коде, а в хорошем коде вообще само всё заработает.

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

Ну да, чтобы он не смог.

Объём программы не влияет на качество оптимизации отдельно взятой функции.

Дело не в объёме программы, а сложности задачи, которая вынесена в ту самую «функцию». С простой может повести, с чем-то более-менее сложным — поможет только чудо.

Зато код можно будет собрать при необходимости и под старые процессоры и под другие архитектуры.

Это итак работает без проблем. Допустим, мой код, который BM_SSE_COUNT_NG_NAIVESUMM — спокойно собирается и под старые процессоры и под другие архитектуры. Для автоматической поддержки AVX2/AVX512/AVX1024/AVX2048/… — там нужно только реализовать обобщённую функцию summ();

Далее можно поменять __vector_size__(16) на __vector_size__(32) и будет не sse, а avx2, на 64 — будет avx512.

И как я уже говорил — она без проблем собирается и для других процессоров/архитектур: godbolt.org/z/muBfnL

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

Кто-нибудь из минусующих хочет объясниться? Все(по крайне мере я) хотят знать — почему то, что написано в комменте плохо, либо почему и с чем конкретные люди несогласны?
В общем то компиляторы от интела и нвидии они решают.
Даже простая замена g на i добавит процентов 20%.
Плюс вылизанные библиотеки которые нужно уметь использовать.
И выбор инструмента, под каждую задачу.

Не зря проект на С++ собирается ООООЧЕНЬ долго
На CPU может и решают, а на GPU всё значительно хуже. Неоднократно получал кратное ускорение в CUDA просто вдумчиво переписав Сишный код на PTX (это их «ассемблер»). Имхо для эффективного автораспараллеливания надо дорабатывать совремненые ЯВУ, расширять их синтаксис.
Имхо для эффективного автораспараллеливания надо дорабатывать совремненые ЯВУ, расширять их синтаксис.
Такие уже есть.
Тоже хотелось бы сравнение с -Ofast -march=native
1) Так как приводится время исполнения кода, контролировалась ли неизменность частоты процессора i7-8750H?
и еще размышления, не в коей мере НЕ замечания:
2) АVX2 — не ускорит по сравнению с SSE?
3) Intel C++/Fortran (IPP, MKL ?) позволят добавить к векторизации автоматическое распараллеливание.
Если Fortran, то дополнительно использовать coarray для данной задачи очень просто.
p.s. просто пятикратное ускорение из за автоматической векторизации и префетча,
встречалось мне на еще P4 на реальной расчетной задаче моделирования.
1) Да, в соответствии с рекомендацией github.com/google/benchmark#disable-cpu-frequency-scaling
2) AVX нет на десктопных CPU, но думаю, что его использование может ещё ускорить.
3) Распараллеливание — это всё же другой подход, при условии, что все ядра загружены, от распараллеливания не будет выгоды.
AVX2 есть на i7-8750H и на большинстве CPU.
Если ядра уже загружены, разумеется.
Действительно есть, я был уверен, что он есть только на Xeon'ах:
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed adx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp flush_l1d
Значит будет продолжение, с использованием AVX.
Вы с AVX512. перепутали. Вот это чудо есть очень мало где. А AVX и AVX2 — почти везде…
если брать всякие целероны и пентиумы, то на них же еще не завезли
А если взять 80386, то там и сопроцессора может не оказаться!
Автор явно хочет выжать из конкретного железа максимум:

Перечислить все необходимые feature, например -mpopcnt
Указать целевую архитектуру процессора поддерживающего необходимые feature, например -march=corei7
Дать компилятору возможность использовать все расширения процессора, на котором происходит сборка: -march=native


даже native использует.

А вы и так использовали AVX — ваши SSE регистры — это AVX регистры на самом деле ;-)

Именно так. Автор совершенно не обратил внимания, что вместо команд SSE компилятор нагенерил команд AVX (они имеют префикс «v» в мнемокоде).
SSE — xmm0-15
AVX (256) — ymm0-15
AVX512 — zmm0-31

xmm0 на всем современном железе — верхняя часть ymm0, сhange my mind. Отсюда вырастают грабли с vzeroupper

Это же не отменяет того факта, что мнемоники «xmm» были введены SSE?

Грабли с vzeroupper вылезают из-за вполне естественного желания вендоров не перегружать процессорную логику: не добавлять новые регистры, а расширять старые, не делать отдельные ALU-модули для 128- и 256-битных операций.

Конкретно в данном случае — нет. Команды vpcmpeqw, vpmovmskb — это всё AVX-команды, и работают они с AVX-регистрами. Если в качестве аргумента такой команды передаётся XMM-регистр, а не YMM, то команда просто обнуляет верхнюю половину YMM-регистра. Сделано так было из соображений упрощения внутрипроцессорной логики.

НЛО прилетело и опубликовало эту надпись здесь
Подскажите, а можно ли ускорить такое?

Есть массив значений V(alues). Есть массив Q(uery), который содержит индексы массива V. Нужно получить массив R(esult) по следующему правилу: из массива Q выбираем индекс, по нему выбираем значение из V. То есть:
R[i] = V[ Q[i] ]

А в идеале такая цепочка преобразований может быть достаточно длинной, например:
R[i] = V[ A1[ A2[ Q[i] ] ] ]

Есть ли SIMD инструкции, для подобной задачи?
Точно не гарантирую, но, IMHO, должны быть.
p.s. тут интуитивно встает вопрос, следует ли считать такое выражение векторно, но поэтапно?
по идее операцию V[ Q[i] ] можно представить в виде квадратной матрицы из нулей и единиц, где единицы будут стоять на тех индексах, откуда берутся значения (т.е. она будет верхне- или нижне- угольной):
R[i] = V[ Q[i] ] --> Rvector = Vmatrix * Qvector
так что цепочки таких преобразований — это цепочки матриц, которые можно умножить и получить ускорение.

Допустим так:


V = (10 20 30)
Q = ( 2  3   1)
Expected R = (20 30 10)

                 ( 0 1 0 )
R = (10 20 30) x ( 0 0 1 ) = (20 30 10)
                 ( 1 0 0 )

Выражение для https://matrixcalc.org: {{10,20,30}} * {{0,0,1},{1,0,0},{0,1,0}}


Тогда нужен быстрый способ преобразовать 2 в (0 1 0).

нужен быстрый способ преобразовать 2 в (0 1 0).
А чем плоха мемоизация, т.е. создать массив
строка(1) = (1 0 0 ..)
строка(2) = (0 1 0 ..)
строка(3) = (0 0 1 ..)
и брать оттуда? или у вас вектора на миллионы компонент?

UPD: если вопрос просто в ускорении цепочки, то вполне возможно оставить их в виде векторов, потому что две перестановки всегда можно преобразовать в одну по формуле Vba[i] = Va[ Vb[i] ]
т.е. для R[i] = V[ A1[ A2[ Q[i] ] ] ]
это будет R[i] = VA1A2[ Q[i] ] где VA1A2[i] = A2[ A1[ V[i] ] ]
В AVX2 есть инструкции VGATHERDPD/VGATHERQPD/VGATHERDPS/VGATHERQPS, которые как раз делают такой доступ: R[i] = V[Q[i]]
Вот только природу не обманешь: произвольный доступ к памяти дорог. Если у вас будет много этих инструкций — вы никакого ускорения не получите. За исключением случая когда вы читаете буквально чуть не соседние элементы массива — но для таких случаев есть многочисленные шаффлы.

Ага, толку от gather как с козла молока — выглядит красиво только в асм аутпуте

Согласен, при слишком сильно разбросанном доступе gather быстрее не будет. Но при этом процессор будет декодировать только одну инструкцию вместо нескольких. Так что он может потребить чуточку меньше электричества. А вообще, по-хорошему, надо проверять на конкретных задачах, будет ли прирост производительности от использования gather.
В очень многих случаях эти массивы быстро окажутся в кэше процессора. Да и prefetch никто не отменял.
prefetch требует предсказуемых паттернов доступа к памяти, плюс свободной шины.

Как тут написали выше: в 90% случаев пользы от этих инструкций нету. Хотя на спор сделать задачу, где они выиграют, конечно, можно…
А как вы это себе представляете? Ну, на физическом уровне? Доступ в память — штука медленная. Ибо шина памяти у процессора одна и если, не дай бог, придётся идти аж в DIMM, «по большому» — это это сотни тактов процессора.

Соответственно вариантов два:
1. Ваши функции A1, A2, Q — возвращают значение из очень узкого диапазона — и тогда можно использовать разные трюки.
2. Ваши функции A1, A2, Q — бегают по довольно большому диапазону — и тогда вы «убьёте весь кеш»… О какой-то скорости после этого говорить бессмысленно.

Пожалуй единственный случай, когда соответствующие AVX2 инструкции могут быть полезны — это, условно «маппинг bad block'ов». Когда подавляющее большинство обсуждаемых индексов — это последовательности 1, 2, 4,… — но некоторые редкие элементы прыгают куда-то «в сторону»…
В давние времена, когда SSE3 было новинкой, я разрабатывая ПО для моделирования СТЭ жел. дороги, добился заметного ускорения операций с комплексными числами — использовал в Delphi ассемблерные вставки с SIMD-операциями, например:
//Умножение комплексных чисел
function CMul(const X,Y:Complex):Complex;
{$IFNDEF SIMD}
begin
     Result:=SetComplex(X.Re*Y.Re-X.Im*Y.Im,X.Im*Y.Re+X.Re*Y.Im);
end;
{$ELSE}
asm
        movupd      XMM0, [EAX]//       X.Im X.Re
        DB $F2,$0F,$12,$12//    movddup     xmm2, [EDX] XMM2 Y.Re
        add EDX, $8
        DB $F2,$0F,$12,$0A//    movddup     xmm1, [EDX] XMM1 Y.Im
        mulpd       xmm1, xmm0 //X.Im*Y.Im X.Re*Y.Im
        mulpd       xmm2, xmm0 //Y.Re*X.Im Y.Re*X.Re
        shufpd      xmm1, xmm1, $1 //X.Re*Y.Im X.Im*Y.Im
        DB $66,$0F,$D0,$D1 //addsubpd    xmm2, xmm1
        movupd      [ECX], xmm2
end;
{$ENDIF}

SSE инструкции работают с выровненной памятью по 16 бит.
Правильно «байт».

И, на счет последнего варианта, не думаю, что это повлияет на быстродействие, но все же хорошим тоном было бы не кастовать к указателю и разыменовывать, а прописать _mm_load_si128.
Кстати, вроде как movemask и popcnt — не самые приятные операции; не пробовали аккумулировать результат SIMD-регистрах, а потом уже комбинировать результат? Я имею в виду что-то вроде следующего:

__m128i accumulator = _mm_setzero_si128( );

auto const value = _mm_set1_epi16( VAL );

for ( size_t i = 0; i < ARR_SIZE; i += 8 )
{
	auto const current_value = _mm_load_si128( allignedArr + i );
	accumulator = _mm_add_epi16( accumulator, _mm_and_si128( _mm_cmpeq_epi16( value, current_value ), _mm_set1_epi16( 0x1 ) ) );
}

size_t cnt =
	_mm_extract_epi16( accumulator, 0 ) +
	_mm_extract_epi16( accumulator, 1 ) +
	_mm_extract_epi16( accumulator, 2 ) +
	_mm_extract_epi16( accumulator, 3 ) +
	_mm_extract_epi16( accumulator, 4 ) +
	_mm_extract_epi16( accumulator, 5 ) +
	_mm_extract_epi16( accumulator, 6 ) +
	_mm_extract_epi16( accumulator, 7 );


Правда, это можно использовать только для массивов размера <= 2^19, но все же.

Кстати, сланг способен оптимизировать простой код по подсчету единиц на popcnt, но когда вы это делаете для массива — он решает что куда быстрее вычислять popcnt векторно вручную

Кстати, я тоже как-то увлекался оптимизацией различных алгоритмов, написал метод Гаусса с использованием итераторов, основанных на указателях, но, как показала практика, обогнать оптимизирующий компилятор мне не удалось. Я правда не использовал специальные инструкции, как автор статьи.
Интересно посмотреть сравнение оптимизирующего компилятора и метода, предложенного автором.
Что интересно: в режиме -O3 код с невыровненным доступом и явным вызовом loadu работает быстрее.

А ответ простой: невыровненный доступ запрещён при использовании команд SSE, но не команд AVX. Автор же, указав соответствующий ключ компилятора, заставил его сгенерить не SSE-команды, а аналогичные AVX-команды.

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

на современных камнях вроде бы париться за выравнивание особо не стоит — перфоманс почти не влияет

Да, при последовательном доступе совершенно не влияет, выровнено ли чтение или нет.
Но до появления AVX париться приходилось, потому что SSE-команды иначе бросали исключения.

Добавил вариант(1 c sse, 2 c avx2) где вместо movemask делается and(set1_epi16(1)); sum_epi16 в цикле, в конце цикла 3 раза hadd + extract_epi16(0) + (avx2 ? extract_epi16(8) : 0). Ускорение уже не в 4(7) раза, а в 6(12.5).


Intel(R) Core(TM) i5-7267U CPU @ 3.10GHz
Run on (4 X 3100 MHz CPU s)
CPU Caches:
  L1 Data 32K (x2)
  L1 Instruction 32K (x2)
  L2 Unified 262K (x2)
  L3 Unified 4194K (x1)
------------------------------------------------------------
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_Count                    228 ns        227 ns    3088640
BM_SSE_COUNT_SET_EPI         82 ns         81 ns    8573808
BM_SSE_COUNT_LOADU           57 ns         57 ns   11927684
BM_SSE_COUNT_DIRECT          66 ns         65 ns   10831051
BM_SSE_HADD                  39 ns         38 ns   18249460
BM_AVX2_COUNT                29 ns         29 ns   24458164
BM_AVX2_HADD                 18 ns         18 ns   39366536

UPD
оптимизатор это превратил в (vpcmpeqw+vpsubw) на каждые 16 uint16_t. согласно спеке throughput = 0.5 + 0.33 (предполагаем зависимость). Общее время — (0.5 + 0.33) * 1024 / 16 / 3.2 = 16.6ns, что очень похоже на правду.

using int16_vec_t = int16_t __attribute__((__vector_size__(16)));

auto vhadd(int16_vec_t a, int16_vec_t b) {
  return __builtin_ia32_phaddw128(a, b);
}

auto vhsumm(int16_vec_t v) {
  v = vhadd(v, v);
  v = vhadd(v, v);
  v = vhadd(v, v);
  return v;
}

auto summ(int16_vec_t v) {
  return v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + v[6] + v[7];
}



static void BM_SSE_COUNT_NG_HSUMM(benchmark::State &state) {
  
  for(auto _: state) {
    auto cnt = int16_vec_t{} - 1;
    auto it = (int16_vec_t *)allignedArr, end = (int16_vec_t *)(allignedArr + ARR_SIZE);
    while(it < end) {
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
    }
    cnt = -1 - cnt;
    auto res = vhsumm(cnt)[0];
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_HSUMM);


static void BM_SSE_COUNT_NG_NAIVESUMM(benchmark::State &state) {
  
  for(auto _: state) {
    auto cnt = int16_vec_t{};
    auto it = (int16_vec_t *)allignedArr, end = (int16_vec_t *)(allignedArr + ARR_SIZE);
    while(it < end) {
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
    }
    auto res = summ(cnt);
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_NAIVESUMM);


оптимизатор это превратил в (vpcmpeqw+vpsubw) на каждые 16 uint16_t.


Действительно, гцц осилил превратить превратить второй в подобие первого решения.

согласно спеке throughput = 0.5 + 0.33 (предполагаем зависимость).

Это тут непричём.

Общее время — (0.5 + 0.33) * 1024 / 16 / 3.2 = 16.6ns, что очень похоже на правду.

Абсолютно неверно. Никакие трупуты не складываются, особенно так колхозно.

cnt += (*it == VAL) & 1; ++it;

Это зависимое днище, оно будет упираться в летенси vpsubw, который(очевидно) 1такт. Остальное стоит ноль. Отклонения от 20(вниз) — это лишь следствие реорганизации вычислений.
Это тут непричём.

Неточно выразился, конечно же независимость.


Абсолютно неверно.

Возможно я не прав, но я вижу 64 * 2 + eps инструкций которые выполняются в цикле, причем это суммарно занимает 18 * 3.1 ~= 56 тактов на цикл, причем соотношение сохраняется при росте размера задачи (пока она влезает в L1). Реорганизация вычислений действительно может случатся, я не смотрел как написан libbenchmark (rdtscp?). Но даже rdtscp разрешает реордеринг, который может всё испортить, если компилятор развернет цикл бенчмарка.


Никакие трупуты не складываются, особенно так колхозно

А как они по-вашему должны складываться, как среднее гармоническое?
На работе посмотрю выхлоп IACA, только после этого будет понятно что там на самом деле, а пока мы знаем что ядро умеет делать 2 vpcmpeqw за такт, и 3 vpsubw за такт. Также нет ничего что бы помешало выполнять эти инструкции параллельно (при наличии нужного числа регистров и использовании нужного числа аккумуляторов). Этого уже должно хватать на 5/6 такта на 16 элементов, а если еще и они друг другу не мешают — то и 1/2 такта (во что я лично не верю, т.к. skylake на картинке только 3 INT Vect ALU).
Моя реализация скорее всего упирается в l1i, хотя на 6 итераций я использую 72 байта инструкций, а кеш должен уметь читать 96.


BENCHMARK 4096 (clang)
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               944 ns        942 ns     708115
BM_ShiftCount                          394 ns        392 ns    1748745
BM_SbbCount                            454 ns        447 ns    1580556
BM_Sbb2Count                           465 ns        460 ns    1572391
BM_SSE_COUNT_NG_HSUMM_ARRAY            183 ns        182 ns    3813966
BM_SSE_COUNT_NG_HSUMM                  109 ns        109 ns    6448166
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        143 ns        140 ns    5204190
BM_SSE_COUNT_NG_NAIVESUMM              149 ns        148 ns    4719780
BM_SSE_COUNT_SET_EPI                   320 ns        319 ns    2228249
BM_SSE_COUNT_LOADU                     233 ns        233 ns    2998886
BM_SSE_COUNT_DIRECT                    236 ns        235 ns    2997461
BM_SSE_HADD                            150 ns        149 ns    4609448
BM_AVX2_COUNT                          114 ns        114 ns    6065280
BM_AVX2_HADD                            77 ns         77 ns    9087605
BM_AVX2_HADD2                           76 ns         76 ns    8660472

BENCHMARK 4096 (g++-8)
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               967 ns        958 ns     692185
BM_ShiftCount                          390 ns        389 ns    1794035
BM_SbbCount                            443 ns        442 ns    1573041
BM_Sbb2Count                           448 ns        446 ns    1583743
BM_SSE_COUNT_NG_HSUMM_ARRAY            181 ns        180 ns    3766114
BM_SSE_COUNT_NG_HSUMM                  108 ns        108 ns    6484183
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        138 ns        137 ns    4938655
BM_SSE_COUNT_NG_NAIVESUMM              146 ns        146 ns    4791501
BM_SSE_COUNT_SET_EPI                   308 ns        307 ns    2280309
BM_SSE_COUNT_LOADU                     236 ns        234 ns    2973763
BM_SSE_COUNT_DIRECT                    232 ns        231 ns    3009575
BM_SSE_HADD                            151 ns        150 ns    4695529
BM_AVX2_COUNT                          116 ns        116 ns    6000600
BM_AVX2_HADD                            76 ns         76 ns    9235438
BM_AVX2_HADD2                           76 ns         75 ns    8653085

BENCHMARK 1024 (clang)
-----------------------------------------------------------------------
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               223 ns        222 ns    3164557
BM_ShiftCount                          103 ns        101 ns    6838475
BM_SbbCount                            112 ns        112 ns    5843657
BM_Sbb2Count                           114 ns        113 ns    6204464
BM_SSE_COUNT_NG_HSUMM_ARRAY             15 ns         15 ns   48139412
BM_SSE_COUNT_NG_HSUMM                   29 ns         29 ns   24739178
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY         22 ns         22 ns   31956904
BM_SSE_COUNT_NG_NAIVESUMM               35 ns         35 ns   19836715
BM_SSE_COUNT_SET_EPI                    82 ns         82 ns    8580219
BM_SSE_COUNT_LOADU                      57 ns         57 ns   12195122
BM_SSE_COUNT_DIRECT                     58 ns         57 ns   12200861
BM_SSE_HADD                             38 ns         38 ns   18213135
BM_AVX2_COUNT                           29 ns         29 ns   24371053
BM_AVX2_HADD                            18 ns         18 ns   38745102
BM_AVX2_HADD2                           15 ns         15 ns   46509774

BENCHMARK 1024 (g++-8)
-----------------------------------------------------------------------
Benchmark                                Time           CPU Iterations
-----------------------------------------------------------------------
BM_Count                               221 ns        221 ns    3104351
BM_ShiftCount                          103 ns        102 ns    6613569
BM_SbbCount                            114 ns        113 ns    6270379
BM_Sbb2Count                           112 ns        111 ns    6243366
BM_SSE_COUNT_NG_HSUMM_ARRAY             15 ns         15 ns   48197085
BM_SSE_COUNT_NG_HSUMM                   28 ns         28 ns   24614519
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY         22 ns         22 ns   31906505
BM_SSE_COUNT_NG_NAIVESUMM               35 ns         35 ns   19846164
BM_SSE_COUNT_SET_EPI                    82 ns         82 ns    8507949
BM_SSE_COUNT_LOADU                      57 ns         57 ns   11635638
BM_SSE_COUNT_DIRECT                     59 ns         58 ns   11748120
BM_SSE_HADD                             38 ns         38 ns   18002911
BM_AVX2_COUNT                           29 ns         29 ns   24417043
BM_AVX2_HADD                            18 ns         18 ns   39480660
BM_AVX2_HADD2                           15 ns         15 ns   47806044

code
#include <benchmark/benchmark.h>
#include <x86intrin.h>
#include <emmintrin.h>
#include <immintrin.h>
#include <cstring>
#include <stdlib.h>

#define ARR_SIZE 4096
#define VAL 50

static int16_t *getRandArr() {
    auto res = new int16_t[ARR_SIZE];
    for (int i = 0; i < ARR_SIZE; ++i) {
        res[i] = static_cast<int16_t>(rand() % (VAL * 2));
    }
    return res;
}

static auto arr = getRandArr();

static int16_t *getAllignedArr() {
    void *res;
    posix_memalign(&res, 64, sizeof(int16_t) * ARR_SIZE);
    //auto res =  aligned_alloc(16, sizeof(int16_t) * ARR_SIZE);
    memcpy(res, arr, sizeof(int16_t) * ARR_SIZE);
    return static_cast<int16_t *>(res);
}

static auto allignedArr = getAllignedArr();

static void BM_Count(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        for (int i = 0; i < ARR_SIZE; ++i)
            if (arr[i] == VAL)
                ++cnt;
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_Count);

static void BM_ShiftCount(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          diff |= (diff >> 1) & 0xEFFFEFFFEFFFEFFFUL;
          diff |= (diff >> 2) & 0xCFFFCFFFCFFFCFFFUL;
          diff |= (diff >> 4) & 0x0FFF0FFF0FFF0FFFUL;
          diff |= (diff >> 8) & 0x00FF00FF00FF00FFUL;
          diff &= 0x0001000100010001UL;
          sum += diff;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_ShiftCount);

static void BM_SbbCount(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          if ((diff >> 0) & 0xFFFF) ++sum;
          if ((diff >>16) & 0xFFFF) ++sum;
          if ((diff >>32) & 0xFFFF) ++sum;
          if ((diff >>48) & 0xFFFF) ++sum;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_SbbCount);

static void BM_Sbb2Count(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          if (diff & 0x000000000000FFFFUL) ++sum;
          if (diff & 0x00000000FFFF0000UL) ++sum;
          if (diff & 0x0000FFFF00000000UL) ++sum;
          if (diff & 0xFFFF000000000000UL) ++sum;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_Sbb2Count);

using int16_vec_t = int16_t __attribute__((__vector_size__(16)));

auto vhadd(int16_vec_t a, int16_vec_t b) {
  return __builtin_ia32_phaddw128(a, b);
}

auto vhsumm(int16_vec_t v) {
  v = vhadd(v, v);
  v = vhadd(v, v);
  v = vhadd(v, v);
  return v;
}

auto summ(int16_vec_t v) {
  return v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + v[6] + v[7];
}

static void BM_SSE_COUNT_NG_HSUMM_ARRAY(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{} - 1;
    for (size_t i = 0; i < ARR_SIZE; i += 64) {
      cnt += ((int16_vec_t*)allignedArr)[i] == VAL;
      cnt += ((int16_vec_t*)allignedArr)[i + 16] == VAL;
      cnt += ((int16_vec_t*)allignedArr)[i + 32] == VAL;
      cnt += ((int16_vec_t*)allignedArr)[i + 48] == VAL;
    }
    cnt = -1 - cnt;
    auto res = vhsumm(cnt)[0];
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_HSUMM_ARRAY);

static void BM_SSE_COUNT_NG_HSUMM(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{} - 1;
    // for (size_t i = 0; i < ARR_SIZE; i += 16) {
    //   cnt += ((int16_vec_t*)allignedArr)[i] == VAL;
    // }
    auto it = (int16_vec_t *)allignedArr, end = (int16_vec_t *)(allignedArr + ARR_SIZE);
    while(it < end) {
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
      cnt += (*it == VAL); ++it;
    }
    cnt = -1 - cnt;
    auto res = vhsumm(cnt)[0];
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_HSUMM);

static void BM_SSE_COUNT_NG_NAIVESUMM_ARRAY(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{};
    for (size_t i = 0; i < ARR_SIZE; i += 64) {
      cnt += (((int16_vec_t*)allignedArr)[i] == VAL) & 1;
      cnt += (((int16_vec_t*)allignedArr)[i + 16] == VAL) & 1;
      cnt += (((int16_vec_t*)allignedArr)[i + 32] == VAL) & 1;
      cnt += (((int16_vec_t*)allignedArr)[i + 64] == VAL) & 1;
    }
    auto res = summ(cnt);
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_NAIVESUMM_ARRAY);

static void BM_SSE_COUNT_NG_NAIVESUMM(benchmark::State &state) {

  for(auto _: state) {
    auto cnt = int16_vec_t{};
    // for (size_t i = 0; i < ARR_SIZE; i += 16) {
    //   cnt += (((int16_vec_t*)allignedArr)[i] == VAL) & 1;
    // }
    auto it = (int16_vec_t *)allignedArr, end = (int16_vec_t *)(allignedArr + ARR_SIZE);
    while(it < end) {
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
      cnt += (*it == VAL) & 1; ++it;
    }
    auto res = summ(cnt);
    benchmark::DoNotOptimize(res);
  }
}

BENCHMARK(BM_SSE_COUNT_NG_NAIVESUMM);

static void BM_SSE_COUNT_SET_EPI(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = _mm_set_epi16(arr[i + 7], arr[i + 6], arr[i + 5], arr[i + 4], arr[i + 3], arr[i + 2],
                                        arr[i + 1], arr[i]);
            cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_SSE_COUNT_SET_EPI);

static void BM_SSE_COUNT_LOADU(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = _mm_loadu_si128((__m128i *) &arr[i]);
            cnt += _popcnt32(_mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr)));
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_SSE_COUNT_LOADU);

static void BM_SSE_COUNT_DIRECT(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = *(__m128i *) &allignedArr[i];
            auto mask = _mm_movemask_epi8(_mm_cmpeq_epi16(sseVal, sseArr));
            cnt += _popcnt32(mask);
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_SSE_COUNT_DIRECT);

static void BM_SSE_HADD(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm_set1_epi16(VAL);
        auto sseOne = _mm_set1_epi16(1);
        auto sseSum = _mm_set1_epi16(0);
        for (int i = 0; i < ARR_SIZE; i += 8) {
            auto sseArr = *(__m128i *) &allignedArr[i];
            auto mask_ff = _mm_cmpeq_epi16(sseVal, sseArr);
            auto mask_01 = _mm_and_si128(mask_ff, sseOne);
            sseSum = _mm_add_epi16(sseSum, mask_01);
        }
        sseSum = _mm_hadd_epi16(sseSum, _mm_set1_epi16(0));
        sseSum = _mm_hadd_epi16(sseSum, _mm_set1_epi16(0));
        sseSum = _mm_hadd_epi16(sseSum, _mm_set1_epi16(0));
        cnt = _mm_extract_epi16(sseSum, 0);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_SSE_HADD);

static void BM_AVX2_COUNT(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm256_set1_epi16(VAL);
        for (int i = 0; i < ARR_SIZE; i += 16) {
            auto sseArr = *(__m256i *) &allignedArr[i];
            auto mask_ff = _mm256_cmpeq_epi16(sseVal, sseArr);
            cnt += _popcnt32(_mm256_movemask_epi8(mask_ff));
        }
        benchmark::DoNotOptimize(cnt >> 1);
    }
}

BENCHMARK(BM_AVX2_COUNT);

static void BM_AVX2_HADD(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm256_set1_epi16(VAL);
        auto sseOne = _mm256_set1_epi16(1);
        auto sseSum = _mm256_setzero_si256();
        for (int i = 0; i < ARR_SIZE; i += 16) {
            auto sseArr = *(__m256i *) &allignedArr[i];
            auto mask_ff = _mm256_cmpeq_epi16(sseVal, sseArr);
            sseSum = _mm256_sub_epi16(sseSum, mask_ff); 
        }
        sseSum = _mm256_hadd_epi16(sseSum, _mm256_set1_epi16(0));
        sseSum = _mm256_hadd_epi16(sseSum, _mm256_set1_epi16(0));
        sseSum = _mm256_hadd_epi16(sseSum, _mm256_set1_epi16(0));
        cnt = _mm256_extract_epi16(sseSum, 0) +
              _mm256_extract_epi16(sseSum, 8);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_AVX2_HADD);

static void BM_AVX2_HADD2(benchmark::State &state) {
    for (auto _ : state) {
        int64_t cnt = 0;

        auto sseVal = _mm256_set1_epi16(VAL);
        auto sseOne = _mm256_set1_epi16(1);
        auto sseSum0 = _mm256_setzero_si256();
        auto sseSum1 = _mm256_setzero_si256();
        for (int i = 0; i < ARR_SIZE; i += 32) {
            auto sseArr0 = *(__m256i *) &allignedArr[i];
            auto sseArr1 = *(__m256i *) &allignedArr[i + 16];
            auto mask_ff0 = _mm256_cmpeq_epi16(sseVal, sseArr0);
            auto mask_ff1 = _mm256_cmpeq_epi16(sseVal, sseArr1);
            sseSum0 = _mm256_sub_epi16(sseSum0, mask_ff0); 
            sseSum1 = _mm256_sub_epi16(sseSum1, mask_ff1); 
        }
        sseSum0 = _mm256_add_epi16(sseSum0, sseSum1);
        sseSum0 = _mm256_hadd_epi16(sseSum0, _mm256_set1_epi16(0));
        sseSum0 = _mm256_hadd_epi16(sseSum0, _mm256_set1_epi16(0));
        sseSum0 = _mm256_hadd_epi16(sseSum0, _mm256_set1_epi16(0));
        cnt = _mm256_extract_epi16(sseSum0, 0) +
              _mm256_extract_epi16(sseSum0, 8);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_AVX2_HADD2);

BENCHMARK_MAIN();
cnt += (((int16_vec_t*)allignedArr)[i] == VAL) & 1;
cnt += (((int16_vec_t*)allignedArr)[i + 16] == VAL) & 1;
cnt += (((int16_vec_t*)allignedArr)[i + 32] == VAL) & 1;
cnt += (((int16_vec_t*)allignedArr)[i + 64] == VAL) & 1;

Очевидно, что это неверный код.

Возможно я не прав, но я вижу 64 * 2 + eps инструкций которые выполняются в цикле, причем это суммарно занимает 18 * 3.1 ~= 56 тактов на цикл, причем соотношение сохраняется при росте размера задачи (пока она влезает в L1).

Это попытка подбить неверное представление под результат. Для того, что такого не было — надо взять флоаты, где различия уже более существенны и даже в таком колхозе сложно что-то перепутать.

Реорганизация вычислений действительно может случатся, я не смотрел как написан libbenchmark (rdtscp?). Но даже rdtscp разрешает реордеринг, который может всё испортить, если компилятор развернет цикл бенчмарка.

Я не про это, а про реорганизацию вычислений в теле цикла, которому может(и делает) компилятор.

Этого уже должно хватать на 5/6 такта на 16 элементов, а если еще и они друг другу не мешают — то и 1/2 такта (во что я лично не верю, т.к. skylake на картинке только 3 INT Vect ALU).

Вообще трупут — это очень глупая метрика от интела. Хотя интел нигде не писал 1/4 такта — это скорее всякие таблицы. Но я дам объяснение — man «zero idioms».

По поводу всего остального — считаю, что там всё неверно. У меня сейчас нет времени на «почему?». Как будет — отвечу подробнее.

Ну если есть 3 параллельных алу, но наверное они зачем-то нужны?
"zero idioms" — Как я понял это про полную элиминацию, у нас же все результаты важны и нужны. Возможно я неправильно представляю себе процессор, и то что я принимал за результат параллельной конвейерной обработки (muops unfused domain) есть всего лишь результат macrofusion. Как будет время поэкспериментирую с uarch-bench + libpfc, должно быть наглядно видно работу muops.
P.S. таблица с портами
Про skylake написано что sub может идти на p0, p1, p5; cmp — p0, p1.


исправленные результаты
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        183 ns        182 ns    3837383
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY         17 ns         17 ns   40434848

haswell
Model name:            Intel(R) Core(TM) i7-4790K CPU @ 4.00GHz

CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
Load Average: 0.20, 0.27, 0.20
--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_Count                               148 ns          148 ns      4735708
BM_ShiftCount                          107 ns          107 ns      6542438
BM_SbbCount                            514 ns          514 ns      1363918
BM_Sbb2Count                           513 ns          513 ns      1366066
BM_SSE_COUNT_NG_HSUMM_ARRAY           17.9 ns         17.9 ns     39193335
BM_SSE_COUNT_NG_HSUMM                 33.6 ns         33.6 ns     20792054
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY       18.3 ns         18.3 ns     38331316
BM_SSE_COUNT_NG_NAIVESUMM             35.8 ns         35.8 ns     19558590
BM_SSE_COUNT_SET_EPI                   352 ns          352 ns      1989417
BM_SSE_COUNT_LOADU                    92.6 ns         92.6 ns      7564254
BM_SSE_COUNT_DIRECT                   91.7 ns         91.7 ns      7625196
BM_SSE_HADD                           62.2 ns         62.2 ns     11142194
BM_AVX2_COUNT                         49.0 ns         49.0 ns     14261594
BM_AVX2_HADD                          33.5 ns         33.5 ns     20831687
BM_AVX2_HADD2                         25.5 ns         25.5 ns     27379074

--------------------------------------------------------------------------
Benchmark                                Time             CPU   Iterations
--------------------------------------------------------------------------
BM_Count                               583 ns          583 ns      1200624
BM_ShiftCount                          410 ns          410 ns      1589399
BM_SbbCount                           2048 ns         2048 ns       341928
BM_Sbb2Count                          2046 ns         2046 ns       342064
BM_SSE_COUNT_NG_HSUMM_ARRAY            102 ns          102 ns      6859708
BM_SSE_COUNT_NG_HSUMM                  134 ns          134 ns      5268616
BM_SSE_COUNT_NG_NAIVESUMM_ARRAY        104 ns          104 ns      6409371
BM_SSE_COUNT_NG_NAIVESUMM              133 ns          133 ns      5282830
BM_SSE_COUNT_SET_EPI                  1413 ns         1413 ns       497718
BM_SSE_COUNT_LOADU                     357 ns          357 ns      1964100
BM_SSE_COUNT_DIRECT                    355 ns          355 ns      1976462
BM_SSE_HADD                            239 ns          239 ns      2934372
BM_AVX2_COUNT                          183 ns          183 ns      3829745
BM_AVX2_HADD                           107 ns          107 ns      6562871
BM_AVX2_HADD2                         93.6 ns         93.6 ns      7396527
«zero idioms» — Как я понял это про полную элиминацию

Это про то, как add/xor и ещё много чего может иметь трупут 1/4 такта.

BM_SSE_COUNT_NG_NAIVESUMM_ARRAY 18.3 ns 18.3 ns 38331316
BM_SSE_COUNT_NG_NAIVESUMM 35.8 ns 35.8 ns 19558590

Я очень сомневаюсь в том, что подобная разница может существовать. Опять явно что-то не так.

Однако зря для сей задачи не рассмотрели варианты параллельного исполнения с помощью Grand Central Dispatch или вручную std::thread(), thrd_create(), pthread_create()…

Часто возникает интересная ситуация, параллельный векторизованый код и параллельный не векторизованый код, при работе в Hyper Threading, работают примерно одинаково в виду того, что ядро одно ж.

Мало того ж, параллельный векторизованый код и паралельный не векторизованый код, и при работе на разных ядрах/процессорах, бывает, просто упирается в производительность ОЗУ.
Задействовать параллелизм для массива длиной 1024 элементов? Накладные расходы всё съедят.
Если пул рабочих потоков уже готов и осталось только раздать отрезки вектора, то с GDC даже для 1024 элементов это будет более/менее эффективно. Но если со стартом рабочих потоков, то увы, УПС ;)
Если потоки спят, то их пробуждение — задача не из быстрых. Да и переключение контекста — очень медленная штука.

Если просто играть в пинг-понг с другим потоком с помощью системных вызовов, то будет порядка 100 тысяч обменов сообщениями в секунду, или 10 мкс на одно сообщение. Это непозволительно много.

Если же рассмотреть ситуацию, когда потоки не засыпают, а крутятся в спинлоках и насилуют адресное пространство атомарными операциями, то и тут всё тоже будет не так радужно: атомарные операции блокируют шину, и чем больше потоков пытается работать с атомарными операциями, тем пропорционально дольше они будут выполняться. То есть один поток зависнет на одной операции на 5 нс, два потока — по 10 нс каждый и т.д. Если в пуле 4 потока, то это задержка каждого минимум на 20 нс до старта, а потом 20 нс на передачу результата, итого +40 нс на накладные расходы в идеальном случае.
Насчет насилия, потоками в «активном» ожидании, то тот же std::memory_order_acquire не насилует и не блокирует «шину», даже если таковая существует.

Но у Intel есть ещё PAUSE для исключения помех потоков на том же ядре и, даже, есть ещё MONITOR/MWAIT для энергоэффективной и быстрой реализации спинлоков, «барьеров с ожиданием» и т.п. Так что ваш расчёт накладных расходов..., он для процессоров из прошлого века.

Есть Grand Central Dispatch, оригинально, для macOS и FreeBSD, но и, наверняка, можно найти и GPL готовые изделия на тех же технологиях. Там всё не так просто ввиду ряда ограничений на Intel, но решаемо.

Вы бы изучили матчасть сначала, что ли. Прямо каша какая-то.


то тот же memory_order_acquire не насилует и не блокирует «шину», даже если она существует.

К процессорам x86 это вообще никак не относится, не вводите людей в заблуждение.


Но у Intel есть ещё PAUSE для исключения помех потоков на том же ядре

Это альтернатива NOP, просто более эффективная. Чудес она не делает.


есть ещё MONITOR/MWAIT для энергоэффективной и быстрой реализации спинлоков

Эти операции недоступны в пользовательском режиме. А переключаться в ядро — терять драгоценные наносекунды.


Есть Grand Central Dispatch, оригинально, для macOS и FreeBSD, но и, наверняка, можно найти и GPL готовые изделия на тех же технологиях. Там всё не так просто ввиду ряда ограничений на Intel, но решаемо.

И, собственно, что? Это просто библиотека пользовательского уровня, и чудес она тоже не делает. Избавить от архитектурных ограничений она не сможет.

Хм.


то тот же memory_order_acquire не насилует и не блокирует «шину», даже если она существует.
К процессорам x86 это вообще никак не относится, не вводите людей в заблуждение.
Типа у процессоров x86 нет команд LFENCE/SFENCE/MFENCE ?! Или что?

В смысле «насилия над „шиной“», то конкретно у Intel работает протокол синхронизации кэш и активное ожидание установки переменной путём её чтения совершенно не тормозит другие ядра и/или процессоры. Другое дело, что эффективная работа с такой переменой предполагает использование std::memory_order_acquire и соответствующей инструкции.
Это альтернатива NOP, просто более эффективная. Чудес она не делает.
А нам и не нужны чудеса. Протокол синхронизации кэш обеспечивает, что код на других ядрах/процессора не тормозится, а PAUSE обеспечивает, что соседний(-ие) HT не практически не замедляются.
есть ещё MONITOR/MWAIT для энергоэффективной и быстрой реализации спинлоков
Эти операции недоступны в пользовательском режиме. ...
Как бы, во-первых, мне известны процессоры на которых они доступны в пользовательском режиме. И, во-вторых, будут новые ж.
… А переключаться в ядро — терять драгоценные наносекунды.
… Это просто библиотека пользовательского уровня, и чудес она тоже не делает. Избавить от архитектурных ограничений она не сможет.
Как бы пул рабочих потоков на котором основан Grand Central Dispatch без поддержки ядра ОС не особо осмыслен. И он таковую имеет.

А в части MONITOR/MWAIT, для процессоров в которых они не поддерживаются на пользовательском уровне (или не имеют аналогичных инструкции). Да таких большинство, но Вы преувеличиваете накладные на выход из системного вызова, который использует MONITOR/MWAIT. А спусковой флаг для них можно поднять в пользовательском пространстве ж ;)
Типа у процессоров x86 нет команд LFENCE/SFENCE/MFENCE ?! Или что?

Есть, но практического смысла в них нет, т.к. в x86 процессорах операции чтения-записи уже упорядочены.


то конкретно у Intel работает протокол синхронизации кэш и активное ожидание установки переменной путём её чтения совершенно не тормозит другие ядра и/или процессоры

Да, не тормозит, но и не блещет производительностью. Одна итерация пинг-понга с другим потоком, в бесконечном цикле копирующем содержимое переменной, у меня занимает 75-90 нс. Это в несколько раз дольше, чем через атомарную операцию. С другой стороны, при большом числе потоков это может дать выигрыш.


Да таких большинство, но Вы преувеличиваете накладные на выход из системного вызова, который использует MONITOR/MWAIT.

В контекте параллельной обработки массива всего из 1024 ячеек — не думаю, что преувеличиваю.


Как бы пул рабочих потоков на котором основан Grand Central Dispatch без поддержки ядра ОС не особо осмыслен. И он таковую имеет.

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

Есть, но практического смысла в них нет, т.к. в x86 процессорах операции чтения-записи уже упорядочены.
Эмм, нет. x86 запросто реордерит операции с памятью на уровне процессора, и в реализации многопоточных структур данных эти инструкции необходимы.

https://stackoverflow.com/questions/19093137/does-x86-sse-instructions-have-an-automatic-release-acquire-order/27302931#27302931


Если вы для ускорения работы с памятью используете MOVNT*-инструкции, то вам действительно нужно использовать барьеры. В остальных случаях — нет.

Там написано следующее:
Reads may be reordered with older writes to different locations
Так что реордер все таки есть.
Но я честно говоря думал что load/load и store/store тоже могут реордериться, так что спасибо за прояснение.
Именно что "… to different locations ..."
То есть побочные эффекты от этого реордера мы не увидим.
preshing.com/20120515/memory-reordering-caught-in-the-act
Тут описано, как можно ощутить этот эффект. Но с тем, что это очень нечастый случай, я согласен.
Там забавная история. Интел пишет что-то типа такого в своих мануалах: «в существующих процессорах перестановок нет, но в будущем они возможны, так что пишите так, чтобы они не влияли». Давно уже пишет. Лет 15, наверное. Потому что заработчикам ПО на проблемы разработчиков процессора плевать — и они пишут, часто полагаясь не то, что перестановок нет.

За исключением библиотек, поддерживающих мобильник и, соответственно, ARM…
атомарные операции блокируют шину

Какую шину?

То есть один поток зависнет на одной операции на 5 нс, два потока — по 10 нс каждый и т.д.

Почему?

итого +40 нс на накладные расходы в идеальном случае.

Не воспроизводится, вот бенчмарк:

#include <atomic>
#include <chrono>
#include <thread>

constexpr auto n = 1e9;
std::atomic<size_t> an = n;

namespace chrono = std::chrono;
auto start = chrono::high_resolution_clock::now();

void stop() {
  auto time = chrono::nanoseconds(chrono::high_resolution_clock::now() - start).count();
  fprintf(stderr, "%fns/dec\n", time / n);
  std::exit(0);
}

void work() {
  while(true) {
    if(!an--) stop();
  }
}


int main(int argc, char * argv[]) {
  size_t threads = (argv[1]) ? std::stoul(argv[1]): 1;
  while(--threads)
    std::thread{work}.detach();
  work();
}


Почему?

Потому что количество атомарных операций пропорционально числу потоков, которым делегируется выполнение задачи. Но несколько атомарных операций параллельно выполняться не может, они выстроятся в очередь.


Какую шину?

См. мануал по префиксу LOCK.


Не воспроизводится, вот бенчмарк:

А вот результат:


F:\Projects\Other\AtomicTest\Release>AtomicTest.exe
5.768351ns/dec

F:\Projects\Other\AtomicTest\Release>AtomicTest.exe 2
20.703706ns/dec

F:\Projects\Other\AtomicTest\Release>AtomicTest.exe 3
21.045200ns/dec

F:\Projects\Other\AtomicTest\Release>AtomicTest.exe 4
21.267553ns/dec

Всё воспроизводится. Вне зависимости от числа потоков время на одну атомарную операцию увеличивается, либо остаётся тем же. Если у нас 3 потока — первый увидит задание через 20 нс, второй — через 40 нс, третий — через 60 нс и т.д. А потом ещё собирать статус об завершении выполнения заданий. Но тут одновременного завершения не будет, поэтому все скорее всего попадут на 5 нс.

А зачем в этом примере атомарные операции? Мы можем свести все к map-reduce, пусть каждый поток получает свою сумму и затем складываем полученные суммы.

А зачем в этом примере атомарные операции?

Для синхронизации между потоками. Откуда потоки узнают, что им пришла задача? Откуда главный поток узнает, что потоки завершили выполнение задачи?

Потому что количество атомарных операций пропорционально числу потоков, которым делегируется выполнение задачи. Но несколько атомарных операций параллельно выполняться не может, они выстроятся в очередь.

В очередь/не очередь — это ничего не меняет, ведь никто не говорил про параллельность. Вы говорили о замедлении, а из очереди замедление никак не следует. К тому же, откуда взялась эта очередь? Пруфы так и не появились.

См. мануал по префиксу LOCK.

От 386го(судя по «шина» — это действительно так)? Можно ссылку?

Всё воспроизводится.

Где? То, что там 6нс — это просто оно долбит в l1d. Это очевидно поведение, чем дальше оно изменяет данные — тем дальше происходит инвалидация. Но всё это к делу не относится.

Вне зависимости от числа потоков время на одну атомарную операцию увеличивается, либо остаётся тем же.

Где у вас было про «остаётся», покажите? Или это попытка задним числом подменить тезис?

Если у нас 3 потока — первый увидит задание через 20 нс, второй — через 40 нс, третий — через 60 нс и т.д. А потом ещё собирать статус об завершении выполнения заданий. Но тут одновременного завершения не будет, поэтому все скорее всего попадут на 5 нс.

У нас три потока. Замедления не обнаружено(вернее не замедления, а линейное падение производительности в зависимости от кол-ва потоков).

В любом случае, всё это выглядит как бред. Что такое 3 потока? Каким образом это на что-то влияет? А если у нас будет 3 потока и три атомика?

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

В очередь/не очередь — это ничего не меняет, ведь никто не говорил про параллельность.

Посмотрите, с чего ветка комментариев началась.


А если у нас будет 3 потока и три атомика?

В этом случае проблем быть не должно, но надо смотреть поведение на различных процессорах. В моём случае при работе с независимыми атомиками в 4 потока уходит по 6 нс на каждый.

LOCK действительно может блокировать шину. Но только если память некэшируемая (чего в прикладном софте не будет), а также если обращение пересекает границу кэшлайна (не бывает в коде на C). А в случае кэшируемой памяти и выровненного обращения в операциях read-modify-write блокируется только кэшлайн, и всё работает на механизмах обеспечения когерентности.
P.S. Конечно, есть на ноутбуках и AVX/AVX2, но что б за это не думать за возможности конкретного процессорв, у всех компиляторов от clang, до IBM, кроме оптимизаторов/векторизаторов есть ещё и векторные типы а ля OpenC, как расширения языка C.

Типа vector a;… a += (b > c);

P.P.S.

Код ваших примеров немного неоптимален. Ясное дело, popcnt в каждом итерации не нужен же, дешевле суммировать вектора.
Чисто формально вы ещё не исчерпали алгоритмические возможности для классических инструкций. Как насчёт того, чтобы грузить int64 и делать сдвиги и сравнение?
Месье знает толк в извращениях.

Только если подсчитывать число равных v размера 16-бит в массиве, приводимому к int64_t, то на итерации достаточно одного XOR, четырёх масок и четырёх условных суммирований.

Что за условное суммирование? У меня векторное решение, но тут log(16bit) >= общему числу элементов в пачке. Странно что даже такая лапша обгоняет тупой иф.


Benchmark
Benchmark                     Time           CPU Iterations
------------------------------------------------------------
BM_Count                    211 ns        210 ns    3313500
BM_ShiftCount               100 ns         99 ns    7066068
BM_SSE_COUNT_SET_EPI         83 ns         83 ns    8598664
BM_SSE_COUNT_LOADU           57 ns         57 ns   12265424

code
    for (auto _ : state) {
        int64_t cnt = 0;
        uint64_t val4 = VAL;
        val4 |= val4 << 16;
        val4 |= val4 << 32;
        uint64_t sum = 0;
        for (int i = 0; i < ARR_SIZE; i += 4) {
          uint64_t elem = *(uint64_t*)(arr + i);
          uint64_t diff = elem ^ val4;
          diff |= (diff >> 1) & 0xEFFFEFFFEFFFEFFFUL;
          diff |= (diff >> 2) & 0xCFFFCFFFCFFFCFFFUL;
          diff |= (diff >> 4) & 0x0FFF0FFF0FFF0FFFUL;
          diff |= (diff >> 8) & 0x00FF00FF00FF00FFUL;
          diff &= 0x0001000100010001UL;
          sum += diff;
        }
        cnt  = ((sum >> 0) & 0xFFFF);
        cnt += ((sum >>16) & 0xFFFF);
        cnt += ((sum >>32) & 0xFFFF);
        cnt += ((sum >>48) & 0xFFFF);
        benchmark::DoNotOptimize(cnt);
    }
}

BENCHMARK(BM_ShiftCount);
Всё это бесполезно, симдовое cmp намного мощнее. Что угодно там колхозь — даже на 64 битных симдах оно будет быстрее.
ускорять код функции с с константными входами это не академично.

А еще, ты несколько недоработал алгоритм. Зачем делать через movemask + popcnt? Для массивов не более 2^18 элементов можно сначала собирать поэлементную сумму:
auto cmp = _mm_cmpeq_epi16(sseVal, sseArr);
cmp = _mm_and_si128(cmp, _mm_set1_epi16(1));
sum = _mm_add_epi16(sum, cmp);

а потом, в конце цикла, сделать одно горизонтальное сложение (не забывая про переполнение).
Добрый день, я рекомендовал бы посмотреть в сторону openmp, прагма #pragma omp simd
Код будет переносимым, трудозатрат меньше, результат обычно такой же
трудозатрат меньше, результат обычно такой же

Там 4 строчки кода(пишется за пару минут), можете продемонстрировать «сторону openmp»?
#pragma omp simd reduction (+:count)
    for (int i = 0; i < N; i++)
    {
        if (a[i] == 42)
            count++;
    }
Чуда не произошло — это самое медленное решение из всех, хуже обычного во много раз.
Шланг написал:
warning: loop not vectorized: the optimizer was unable to perform the requested transformation; the transformation might be disabled or specified as part of an unsupported transformation ordering [-Wpass-failed=transform-warning]

Судя по выхлопу gcc — он тоже не смог ничего векторизовать, но почему-то об этом не сообщил.
Версия g++ 7.3.0
g++ -O3 -fopenmp main.cpp
Все работает и векторизуется
справедливости ради в icc godbolt.org/z/iSxOm0
и clang 7 всё векторизуется
godbolt.org/z/oruzkO и warningов как вы привели выше нет.
справедливости ради в icc godbolt.org/z/iSxOm0

Я не вижу тут векторизации.

и clang 7 всё векторизуется

Действительно, в 7 шланге работает, даже в их транковом работает. В моём не работает. godbolt.org/z/usAV3s — тут(восьмая версия) аналогичная проблема. Значит где-то они что-то сломали.

Так же, если переписать цикл нормально:
cnt += (arr[i] == VAL);

Сразу заработала автовекторизация в шланге, а в gcc заработал openmp.

В любом случае — качество этой векторизации не особо высокое.
>Я не вижу тут векторизации.
Я либо слепой, либо на ..B3.14: ваша искомая векторизация
Это не векторизация — он делает явно не то, что нужно. Если добавить -march поновее — векторизация появляется.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории