Ваш лучший выбор - SIMD, используя AVX1 на вашем процессоре Sandybridge. Компиляторы недостаточно умны, чтобы автоматически векторизовать ваши циклы за битами, даже если вы пишете их без ответвлений, чтобы дать им больше шансов.
И, к сожалению, недостаточно умен, чтобы автоматически векторизовать быструю версию, которая постепенно расширяется и добавляется.
См. , есть ли обратная инструкция к инструкции movemask в intel avx2? для краткого изложения методов растрового изображения -> векторных для различных размеров. Предложение Ext3h в другом ответе хорошо: распаковка битов в нечто более узкое, чем массив окончательного подсчета, дает вам больше элементов на инструкцию. Байты эффективны с SIMD, и затем вы можете сделать до 255 вертикальных paddb без переполнения перед распаковкой для накопления в массив 32-битных счетчиков.
Для хранения всех 64 uint8_t элементов требуется только 4x 16-байтовых __m128i векторов, поэтому эти аккумуляторы могут оставаться в регистрах, добавляя их в память только при расширении до 32-битных счетчиков во внешнем цикле.
Распаковка не обязательно должна быть в порядке : вы всегда можете перетасовать target[] один раз в самом конце, собрав все результаты.
Внутренний цикл можно развернуть для запуска с 64- или 128-битной векторной загрузкой и распаковать 4 или 8 различными способами, используя pshufb (_mm_shuffle_epi8).
Еще лучшая стратегия - постепенно расширяться
Начиная с 2-разрядных аккумуляторов, затем маскируйте / сдвигайте, чтобы расширить их до 4-разрядных. Таким образом, в самом внутреннем цикле большинство операций работают с «плотными» данными, а не «разводят» их слишком много сразу. Более высокая плотность информации / энтропии означает, что каждая инструкция выполняет больше полезной работы.
Использование SWAR методов для 32-битного 2-битного добавления внутри скалярных или SIMD-регистров легко / дешево, потому что мы все равно должны избегать возможности выполнения вершины элемента. При правильном SIMD мы потеряли бы это количество, а при использовании SWAR мы испортили бы следующий элемент.
uint64_t x = *(input++); // load a new bitmask
const uint64_t even_1bits = 0x5555555555555555; // 0b...01010101;
uint64_t lo = x & even_1bits;
uint64_t hi = (x>>1) & even_1bits; // or use ANDN before shifting to avoid a MOV copy
accum2_lo += lo; // can do up to 3 iterations of this without overflow
accum2_hi += hi; // because a 2-bit integer overflows at 4
Затем вы повторяете до 4 векторов 4-битных элементов, затем 8 векторов 8-битных элементов, затем вам нужно расширить до 32 и накапливать в массиве в памяти, потому что вы все равно исчерпаете регистры и эта работа с внешним внешним циклом достаточно редка, поэтому нам не нужно беспокоиться о переходе на 16-битный режим. (Особенно если мы вручную векторизируем).
Самый большой недостаток: этот не автоматически векторизован, в отличие от версии @njuffa. Но с gcc -O3 -march=sandybridge для AVX1 (затем запускается код на Skylake), этот запущенный скаляр 64-разрядная на самом деле все еще немного быстрее , чем 128-разрядная AVX, автоматически векторизованная asm из кода @ njuffa.
Но это время для Skylake, у которого есть 4 скалярных порта ALU (и mov-elmination), в то время как Sandybridge не имеет mov-el сокращений и имеет только 3 порта ALU, поэтому скалярный код, вероятно, достигнет узких мест внутреннего порта выполнения. (Но SIMD-код может быть почти таким же быстрым, потому что есть много AND / ADD, смешанных со сдвигами, и у SnB есть исполнительные блоки SIMD на всех 3 его портах, на которых есть какие-либо ALU. Haswell только что добавил порт 6 для скалярного -только включая смены и филиалы.)
При хорошей ручной векторизации это должно быть почти в 2 или 4 раза быстрее.
Но если вам нужно выбрать между этим скаляром или @ njuffa с автовекторизацией AVX2, @ njuffa быстрее на Skylake с -march=native
Если построение на 32-битной цели возможно / требуется, это сильно сказывается (без векторизации из-за использования uint64_t в 32-битных регистрах), в то время как векторизованный код почти не страдает (потому что вся работа происходит в векторных регистрах такой же ширины).
// TODO: put the target[] re-ordering somewhere
// TODO: cleanup for N not a multiple of 3*4*21 = 252
// TODO: manual vectorize with __m128i, __m256i, and/or __m512i
void sum_gradual_widen (const uint64_t *restrict input, unsigned int *restrict target, size_t length)
{
const uint64_t *endp = input + length - 3*4*21; // 252 masks per outer iteration
while(input <= endp) {
uint64_t accum8[8] = {0}; // 8-bit accumulators
for (int k=0 ; k<21 ; k++) {
uint64_t accum4[4] = {0}; // 4-bit accumulators can hold counts up to 15. We use 4*3=12
for(int j=0 ; j<4 ; j++){
uint64_t accum2_lo=0, accum2_hi=0;
for(int i=0 ; i<3 ; i++) { // the compiler should fully unroll this
uint64_t x = *input++; // load a new bitmask
const uint64_t even_1bits = 0x5555555555555555;
uint64_t lo = x & even_1bits; // 0b...01010101;
uint64_t hi = (x>>1) & even_1bits; // or use ANDN before shifting to avoid a MOV copy
accum2_lo += lo;
accum2_hi += hi; // can do up to 3 iterations of this without overflow
}
const uint64_t even_2bits = 0x3333333333333333;
accum4[0] += accum2_lo & even_2bits; // 0b...001100110011; // same constant 4 times, because we shift *first*
accum4[1] += (accum2_lo >> 2) & even_2bits;
accum4[2] += accum2_hi & even_2bits;
accum4[3] += (accum2_hi >> 2) & even_2bits;
}
for (int i = 0 ; i<4 ; i++) {
accum8[i*2 + 0] += accum4[i] & 0x0f0f0f0f0f0f0f0f;
accum8[i*2 + 1] += (accum4[i] >> 4) & 0x0f0f0f0f0f0f0f0f;
}
}
// char* can safely alias anything.
unsigned char *narrow = (uint8_t*) accum8;
for (int i=0 ; i<64 ; i++){
target[i] += narrow[i];
}
}
/* target[0] = bit 0
* target[1] = bit 8
* ...
* target[8] = bit 1
* target[9] = bit 9
* ...
*/
// TODO: 8x8 transpose
}
Нас не волнует порядок, поэтому accum4[0] имеет 4-битные аккумуляторы для каждого 4-го бита, например. Последним исправлением, необходимым (но еще не реализованным) в самом конце, является транспонирование 8x8 массива uint32_t target[64], , которое может быть эффективно выполнено с использованием unpck и vshufps только с AVX1.( Транспонировать поплавок 8x8 с использованием AVX / AVX2 ).А также цикл очистки для последних до 251 маски.
Мы можем использовать любую ширину элемента SIMD для реализации этих сдвигов;мы все равно должны маскироваться для ширины ниже 16-битной (SSE / AVX не имеет сдвигов гранулярности, только 16-битный минимум.)
Результаты тестов в Arch Linux i7-6700k из тестового ремня @ njuffa, с этим добавлено( Godbolt ) N = (10000000 / (3*4*21) * 3*4*21) = 9999864 (т. Е. 10000000, округленное до кратного 252 итерационного коэффициента "развертывания", поэтому моя упрощенная реализация выполняет тот же объем работы, не считая повтор-заказ target[], что не делает, поэтому выводит результаты о несоответствии. Но количество отпечатков совпадает с другой позицией ссылочного массива.)
Я запускал программу 4 раза подряд (чтобы убедиться,ЦП прогрелся до максимальной скорости турбокомпрессора) и взял один из прогонов, который выглядел хорошо (ни один из 3-х кратно аномально высоких).
ref: лучший битовый цикл (следующий раздел)
быстро:код @ нюффа.(автоматическая векторизация с использованием 128-битных целочисленных инструкций AVX).
постепенный: моя версия (не векторизована gcc или clang, по крайней мере, не во внутреннем цикле.) gcc и clang полностью развертывают внутренние 12 итераций.
gcc8.2 -O3 -march=sandybridge -fpie -no-pie
ref: 0,331373 секунды, быстрый: 0,011387 секунд, постепенный: 0,009966 секунд gcc8.2 -O3 -march=sandybridge -fno-pie -no-pie
ref: 0,397175 секунд, быстрый: 0,011255 секунд,постепенное: 0,010018 с clang7.0 -O3 -march=sandybridge -fpie -no-pie
ref: 0,352381 с, быстрое: 0,011926 с, постепенное: 0,009269 с (очень низкое значение для порта 7 мопов, clang использует индексированную адресацию для магазинов) clang7.0 -O3 -march=sandybridge -fno-pie -no-pie
ref: 0,293014 с , быстрый: 0,011777 с, постепенный: 0,009235 с
-марш = skylake (допуская AVX2 для 256-битных целочисленных векторов) помогает обоим, но больше всего @ njuffa, потому что большая часть его векторизована (включая его самый внутренний цикл):
gcc8.2 -O3 -march=skylake -fpie -no-pie
ref: 0,328725 с, быстрое: 0,007621 с, постепенное: 0,010054 с (gcc не показывает усиления для «постепенного», только «быстрое») gcc8.2 -O3 -march=skylake -fno-pie -no-pie
ref: 0,333922 с, быстрый: 0,007620 с, постепенный: 0,009866 с
clang7.0 -O3 -march=skylake -fpie -no-pie
ref: 0,260616 с,быстрый: 0,007521 с, постепенный: 0,008535 с (ИДК, почему постепенный быстрее, чем -march = Sandybridge;он не использует BMI1 andn.Я думаю, потому что он использует 256-битный AVX2 для внешнего цикла k = 0..20 с vpaddq)
clang7.0 -O3 -march=skylake -fno-pie -no-pie
ref: 0.259159 с , быстро: 0,007496 с , постепенное: 0,008671 с
Без AVX только SSE4.2: (-march=nehalem), причудливое ускорение ускоренияс AVX / мелодия = песчаный мост."fast" только чуть медленнее, чем с AVX.
gcc8.2 -O3 -march=skylake -fno-pie -no-pie
ref: 0,337178 с, быстрый: 0,011983 с, постепенный: 0,010587 с clang7.0 -O3 -march=skylake -fno-pie -no-pie
ref: 0,293555 с , быстрый: 0,012549 с, постепенный: 0,008697 с
-fprofile-generate / -fprofile-use помогают некоторым для GCC, особеннодля версии «ref», где по умолчанию она вообще не разворачивается.
Я выделил лучшее, но часто они находятся в пределах допустимых помех друг для друга.Неудивительно, что -fno-pie -no-pie иногда был быстрее: индексирование статических массивов с помощью [disp32 + reg] является , а не режимом индексированной адресации, просто base + disp32, поэтому он никогда не запускается на процессорах семейства Sandybridge.
Но с gcc иногда -fpie был быстрее;Я не проверял, но я предполагаю, что gcc просто как-то выстрелил себе в ногу, когда возможна абсолютная 32-битная адресация.Или просто невинно выглядящие различия в code-gen вызвали проблемы с выравниванием или uop-кешем;Я не проверял подробно.
Для SIMD мы можем просто делать 2 или 4x uint64_t параллельно, накапливая только горизонтально на последнем шаге, где мы расширяем байты до 32-битных элементов. (Возможно, путем перетасовки в очереди изатем используя pmaddubsw с множителем _mm256_set1_epi8(1) для добавления горизонтальных пар байтов в 16-битные элементы.)
TODO: векторизация вручную __m128i и __m256i (и __m512i) версии этого.Должно быть примерно в 2, 4, или даже 8 раз быстрее, чем «постепенное» время, указанное выше. Вероятно, предварительная выборка HW все еще может идти в ногу с этим, за исключением, может быть, версии AVX512 с данными, поступающими из DRAM, особенно если есть конфликт от другихпотоки.Мы выполняем значительный объем работы с каждым прочитанным словом.
Устаревший код: улучшения в битовом цикле
Ваша портативная скалярная версия тоже может быть улучшена ускорение с ~ 1,92 секунды ( с общей ошибкой прогнозирования ветвления 34% , с быстрыми зацикленными комментариями!) До ~ 0,35 с (clang7.0 -O3 -march=sandybridge) с надлежащим случайным входом на 3,9 ГГцSkylake.Или 1,83 с для версии с ветвлением с != 0 вместо == m, поскольку компиляторы не могут доказать, что m всегда имеет ровно 1 установленный бит, и / или оптимизировать соответственно.
(против 0,01 с для@ njuffa или моя быстрая версия выше, так что это совершенно бесполезно в абсолютном смысле, но стоит упомянуть в качестве общего примера оптимизации использования кода без ответвлений.)
Если вы ожидаете случайное сочетание нулей ите, которые вы хотите что-то без разветвлений, которые не будут неправильно прогнозировать.Выполнение += 0 для элементов, которые были равны нулю, избегает этого, а также означает, что абстрактная машина C определенно касается этой памяти независимо от данных.
Компиляторам не разрешается изобретать записи, поэтому, если они хотят автоматически-векторизируйте вашу if() target[i]++ версию, им придется использовать хранилище в маске, например x86 vmaskmovps, чтобы избежать неатомарного чтения / перезаписи неизмененных элементов target.Поэтому некоторым гипотетическим будущим компиляторам, которые могут автоматически векторизовать простой скалярный код, было бы легче с этим.
В любом случае, один из способов написать это - target[i] += (pLong[j] & m != 0);, используя преобразование bool-> int, чтобы получить 0/ 1 целое число.
Но мы получим лучший ассемблер для x86 (и, вероятно, для большинства других архитектур), если просто сдвинуть данные и изолировать младший бит с помощью &1.Компиляторы довольно глупы и, похоже, не замечают этой оптимизации.Они хорошо оптимизируют счетчик дополнительных циклов и превращают m <<= 1 в add same,same для эффективного смещения влево, но они все еще используют xor-zero / test / setne для создания целого числа 0/1.
Внутренний цикл, подобный этому, компилируется немного эффективнее (но все же намного хуже, чем мы можем сделать с SSE2 или AVX, или даже скалярный, используя таблицу поиска @ chrqlie, которая будет оставаться горячей в L1d при многократном использованиивот так, разрешив SWAR в uint64_t):
for (int j = 0; j < 10000000; j++) {
#if 1 // extract low bit directly
unsigned long long tmp = pLong[j];
for (int i=0 ; i<64 ; i++) { // while(tmp) could mispredict, but good for sparse data
target[i] += tmp&1;
tmp >>= 1;
}
#else // bool -> int shifting a mask
unsigned long m = 1;
for (i = 0; i < 64; i++) {
target[i]+= (pLong[j] & m) != 0;
m = (m << 1);
}
#endif
Обратите внимание, что unsigned long не гарантированно является 64-битным типом и не поддерживается в x86-64 System V x32 (ILP32 в64-битный режим) и Windows x64.Или в 32-разрядных интерфейсах ABI, таких как i386 System V.
Скомпилировано в проводнике компилятора Godbolt с помощью gcc, clang и ICC , это меньше на 1 моп в цикле с gcc.Но все они просто скаляры, clang и ICC развернуты на 2.
# clang7.0 -O3 -march=sandybridge
.LBB1_2: # =>This Loop Header: Depth=1
# outer loop loads a uint64 from the src
mov rdx, qword ptr [r14 + 8*rbx]
mov rsi, -256
.LBB1_3: # Parent Loop BB1_2 Depth=1
# do {
mov edi, edx
and edi, 1 # isolate the low bit
add dword ptr [rsi + target+256], edi # and += into target
mov edi, edx
shr edi
and edi, 1 # isolate the 2nd bit
add dword ptr [rsi + target+260], edi
shr rdx, 2 # tmp >>= 2;
add rsi, 8
jne .LBB1_3 # } while(offset += 8 != 0);
Это немного лучше, чем мы получаем от test / setnz.Без развертывания bt / setc могли бы быть равными, но компиляторы плохо используют bt для реализации bool (x & (1ULL << n)) или bts для реализации x |= 1ULL << n.
Еслиу многих слов самый высокий установленный бит намного ниже бита 63, зацикливание на while(tmp) может быть выигрышем .Неправильные прогнозы ветвей делают его не стоящим, если он экономит от ~ 0 до 4 итераций большую часть времени, но если он часто экономит 32 итерации, это может стоить того.Возможно, разверните исходный код, чтобы цикл проверял только tmp каждые 2 итерации (потому что компиляторы не будут выполнять это преобразование за вас), но тогда ветвь цикла может быть shr rdx, 2 / jnz.
В семействе Sandybridge это 11 мопов с плавким доменом для внешнего интерфейса на 2 бита ввода.(add [mem], reg с неиндексированным режимом адресации микросопрягает нагрузку + ALU и адрес хранилища + данные хранилища, все остальное - одиночные uop. Add / jcc macro-fuses. См. Руководство Agner Fog и https://stackoverflow.com/tags/x86/info). Таким образом, он должен работать примерно с 3 циклами на 2 бита = один uint64_t на 96 циклов (Sandybridge не «разворачивается» внутри своего буфера цикла, так что число мопов, не кратное 4, в основном округляетсявверх, в отличие от Haswell и более поздних версий).
против не развернутой версии gcc: 7 мопов на 1 бит = 2 цикла на бит. Если вы скомпилировали с gcc -O3 -march=native -fprofile-generate / test-run / gcc -O3 -march=native -fprofile-use,Оптимизация по профилю позволила бы развернуть цикл.
Это, вероятно, медленнее, чем ветвящаяся версия для полностью предсказуемых данных, как вы получаете из memset с любым повторяющимся байтовым шаблоном . Я бы предложилзаполнение массива случайно сгенерированными данными из быстрого PRNG, например, xorshift + SSE2, или, если вы просто синхронизируете цикл подсчета, тогда используйте все, что захотите, например rand().