Комментарии 95
Что мешает -О3 дооптимизировать до одинаковых таймингов?
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 — это пока ближе к чёрной магии, чем к науке. Там тонны эвристик…
Лучше критичные к производительности части выносить в отдельные функции, которые отдавать компилятору, проверяя выхлоп и делая замеры. Объём программы не влияет на качество оптимизации отдельно взятой функции. Зато код можно будет собрать при необходимости и под старые процессоры и под другие архитектуры.
Полностью отдавать действительно критичные части программы компилятору — тоже плохая идея. Компилятор не может правильно расположить данные в памяти и построить качественную архитектуру программы — он всего лишь выдаст код, который от него потребуют. Потребуете что-нибудь не то — оптимизаций не получите.
Через год оптимальные варианты станут менее оптимальными из-за нового 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%.
Плюс вылизанные библиотеки которые нужно уметь использовать.
И выбор инструмента, под каждую задачу.
Не зря проект на С++ собирается ООООЧЕНЬ долго
и еще размышления, не в коей мере НЕ замечания:
2) АVX2 — не ускорит по сравнению с SSE?
3) Intel C++/Fortran (IPP, MKL ?) позволят добавить к векторизации автоматическое распараллеливание.
Если Fortran, то дополнительно использовать coarray для данной задачи очень просто.
p.s. просто пятикратное ускорение из за автоматической векторизации и префетча,
встречалось мне на еще P4 на реальной расчетной задаче моделирования.
2) AVX нет на десктопных CPU, но думаю, что его использование может ещё ускорить.
3) Распараллеливание — это всё же другой подход, при условии, что все ядра загружены, от распараллеливания не будет выгоды.
Если ядра уже загружены, разумеется.
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.
Перечислить все необходимые feature, например -mpopcnt
Указать целевую архитектуру процессора поддерживающего необходимые feature, например -march=corei7
Дать компилятору возможность использовать все расширения процессора, на котором происходит сборка: -march=native
даже native использует.
TLDR проц может сильно сбросить частоту.
А вы и так использовали AVX — ваши SSE регистры — это AVX регистры на самом деле ;-)
AVX (256) — ymm0-15
AVX512 — zmm0-31
xmm0 на всем современном железе — верхняя часть ymm0, сhange my mind. Отсюда вырастают грабли с vzeroupper
Грабли с vzeroupper вылезают из-за вполне естественного желания вендоров не перегружать процессорную логику: не добавлять новые регистры, а расширять старые, не делать отдельные ALU-модули для 128- и 256-битных операций.
Как я понимаю это приводит к небольшому penalty, https://github.com/dotnet/coreclr/pull/20788#discussion_r230869394
Конкретно в данном случае — нет. Команды 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 инструкции, для подобной задачи?
p.s. тут интуитивно встает вопрос, следует ли считать такое выражение векторно, но поэтапно?
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] ] ]
Ага, толку от gather как с козла молока — выглядит красиво только в асм аутпуте
Соответственно вариантов два:
1. Ваши функции A1, A2, Q — возвращают значение из очень узкого диапазона — и тогда можно использовать разные трюки.
2. Ваши функции A1, A2, Q — бегают по довольно большому диапазону — и тогда вы «убьёте весь кеш»… О какой-то скорости после этого говорить бессмысленно.
Пожалуй единственный случай, когда соответствующие AVX2 инструкции могут быть полезны — это, условно «маппинг bad block'ов». Когда подавляющее большинство обсуждаемых индексов — это последовательности 1, 2, 4,… — но некоторые редкие элементы прыгают куда-то «в сторону»…
//Умножение комплексных чисел
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, но все же.
Интересно посмотреть сравнение оптимизирующего компилятора и метода, предложенного автором.
А ответ простой: невыровненный доступ запрещён при использовании команд SSE, но не команд AVX. Автор же, указав соответствующий ключ компилятора, заставил его сгенерить не SSE-команды, а аналогичные AVX-команды.
Поэтому я не удивлюсь, если компилятор соптимизировал этот момент, и для последних двух вариантов сгенерировал идентичный код. Ну а небольшая разница во времени — просто статистическая погрешность.
Добавил вариант(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 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 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 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 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
#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
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
Я очень сомневаюсь в том, что подобная разница может существовать. Опять явно что-то не так.
Часто возникает интересная ситуация, параллельный векторизованый код и параллельный не векторизованый код, при работе в Hyper Threading, работают примерно одинаково в виду того, что ядро одно ж.
Мало того ж, параллельный векторизованый код и паралельный не векторизованый код, и при работе на разных ядрах/процессорах, бывает, просто упирается в производительность ОЗУ.
Если просто играть в пинг-понг с другим потоком с помощью системных вызовов, то будет порядка 100 тысяч обменов сообщениями в секунду, или 10 мкс на одно сообщение. Это непозволительно много.
Если же рассмотреть ситуацию, когда потоки не засыпают, а крутятся в спинлоках и насилуют адресное пространство атомарными операциями, то и тут всё тоже будет не так радужно: атомарные операции блокируют шину, и чем больше потоков пытается работать с атомарными операциями, тем пропорционально дольше они будут выполняться. То есть один поток зависнет на одной операции на 5 нс, два потока — по 10 нс каждый и т.д. Если в пуле 4 потока, то это задержка каждого минимум на 20 нс до старта, а потом 20 нс на передачу результата, итого +40 нс на накладные расходы в идеальном случае.
Но у 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, но решаемо.
И, собственно, что? Это просто библиотека пользовательского уровня, и чудес она тоже не делает. Избавить от архитектурных ограничений она не сможет.
Хм.
Типа у процессоров x86 нет команд LFENCE/SFENCE/MFENCE ?! Или что?то тот же memory_order_acquire не насилует и не блокирует «шину», даже если она существует.К процессорам x86 это вообще никак не относится, не вводите людей в заблуждение.
В смысле «насилия над „шиной“», то конкретно у 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 запросто реордерит операции с памятью на уровне процессора, и в реализации многопоточных структур данных эти инструкции необходимы.
Если вы для ускорения работы с памятью используете MOVNT*-инструкции, то вам действительно нужно использовать барьеры. В остальных случаях — нет.
Reads may be reordered with older writes to different locationsТак что реордер все таки есть.
Но я честно говоря думал что load/load и store/store тоже могут реордериться, так что спасибо за прояснение.
То есть побочные эффекты от этого реордера мы не увидим.
Тут описано, как можно ощутить этот эффект. Но с тем, что это очень нечастый случай, я согласен.
За исключением библиотек, поддерживающих мобильник и, соответственно, 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 нс на каждый.
Типа vector a;… a += (b > c);
P.P.S.
Код ваших примеров немного неоптимален. Ясное дело, popcnt в каждом итерации не нужен же, дешевле суммировать вектора.
Только если подсчитывать число равных v размера 16-бит в массиве, приводимому к int64_t, то на итерации достаточно одного XOR, четырёх масок и четырёх условных суммирований.
Что за условное суммирование? У меня векторное решение, но тут log(16bit) >= общему числу элементов в пачке. Странно что даже такая лапша обгоняет тупой иф.
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
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);
А еще, ты несколько недоработал алгоритм. Зачем делать через 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);
а потом, в конце цикла, сделать одно горизонтальное сложение (не забывая про переполнение).
Код будет переносимым, трудозатрат меньше, результат обычно такой же
трудозатрат меньше, результат обычно такой же
Там 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++ -O3 -fopenmp main.cpp
Все работает и векторизуется
и 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.
В любом случае — качество этой векторизации не особо высокое.
Ускоряем неускоряемое или знакомимся с SIMD