Это должно быть возможно примерно при 8 элементах (1 вектор AVX2) за 2,5 такта или около того (на ядро) на современном x86-64, таком как Skylake или Zen 2, с использованием AVX2. Или за 2 часа с раскруткой. Или на вашем процессоре Piledriver, возможно, 1x 16-байтовый вектор индексов на 3 такта с AVX1 _mm_cmpeq_epi32.
Общая стратегия работает с 2-8 сегментами. И для байтовых, 16-битных или 32-битных элементов. (Таким образом, байтовых элементов дает вам 32 элемента, гистограммированных за 2 такта лучший случай, с небольшим количеством внешних-l oop служебных данных для сбора счетчиков байтов до их переполнения.)
Обновление: или отображая int на 1UL << (array[i]*8), чтобы увеличить один из 4 байтов счетчика с добавлением SIMD / SWAR, мы можем go приблизиться к 1 такту на вектор 8 int на SKL или на 2 такта на Zen2. (Это еще более конкретно: от c до 4 или менее сегментов и ввода int, и не сокращается до SSE2. Для этого требуются переменные сдвиги или, по крайней мере, AVX1 переменные тасовки.) Использование байтовых элементов с первой стратегией вероятно, все еще лучше с точки зрения количества элементов в цикле.
Как указывает @ Jona sH, у вас могут быть разные ядра, работающие над разными частями входного массива. Одно ядро может приблизиться к насыщению пропускной способности памяти на типичных настольных ПК, но у многоядерных Xeon пропускная способность памяти на ядро ниже, а совокупная потребность в них выше, и им нужно больше ядер для насыщения пропускной способности L3 или DRAM. Почему Skylake намного лучше, чем Broadwell-E, для пропускной способности однопоточной памяти?
l oop, которая работает по несколько дней подряд.
В одном списке ввода, который очень и очень медлен для итерации, поэтому он по-прежнему не переполняет счетчики int? Или повторяющиеся вызовы с разными большими списками (например, ваш ~ 900k тестовый массив)?
Я полагаю, что хочу избежать увеличения индекса для списка или массива, поскольку он, кажется, занимает много времени?
Это возможно потому, что вы тестировали с отключенной оптимизацией Не делай этого, это вообще не имеет смысла; Разный код замедляется на разные суммы, отключая оптимизацию. Более явные шаги и переменные tmp часто могут сделать код в режиме отладки медленнее, потому что есть больше вещей, на которые нужно посмотреть с помощью отладчика. Но они могут просто оптимизироваться до обычного приращения указателя l oop, когда вы компилируете с обычной оптимизацией.
Итерирование по массиву может эффективно компилироваться в asm.
Медленная часть - это зависимость Цепочка сквозной памяти для увеличения индекса переменной массива. Например, в процессоре Skylake адресат памяти add с одним и тем же адресом неоднократно сталкивается с узкими местами примерно с шагом в 6 тактов, поскольку следующий add должен ждать загрузки значения, сохраненного предыдущим. (Переадресация из буфера хранилища означает, что ему не нужно ждать, пока он зафиксирует сначала кэширование, но он все же намного медленнее, чем добавление в регистр.) См. Также руководства по оптимизации Agner Fog: https://agner.org/optimize/
С счетами, распределенными только по 4 сегментам, у вас будет много случаев, когда инструкции ждут перезагрузки данных, сохраненных другой недавней инструкцией, поэтому вы даже не можете достичь почти 1 элемента на тактовый цикл вы могли бы, если бы счетчики были хорошо распределены по большему количеству счетчиков, которые все еще были горячими в кеше L1d.
Одним хорошим решением этой проблемы является развертывание l oop с несколькими массивами счетчиков. Методы векторизации гистограммы в SIMD? . Например, вместо int[] indexes = { 0, 0, 0, 0 }; вы можете сделать его двумерным массивом из четырех счетчиков каждый. Вам придется вручную развернуть l oop в исходном коде, чтобы выполнить итерацию по входному массиву, и обработать последние 0..3 оставшиеся элементы после развернутой части.
Это хороший метод для небольшие или средние массивы счетчиков, но они становятся плохими, если репликация счетчиков начинает приводить к пропаданию кэша.
Использование узких целых чисел для экономии пропускной способности кэша / памяти. Еще одна вещь, которую вы можете / должны сделать, - это использовать как можно более узкий тип для ваших массивов значений 0..3 : каждое число может помещаться в байт, поэтому использование 8-битных целых чисел спасет вас в 4 раза больше занимаемой кэш-памяти / пропускной способности памяти. x86 может эффективно загружать / хранить байты в / из полных регистров. С SSE4.1 у вас также есть SIMD pmovzxbd, чтобы сделать его более эффективным для автоматической векторизации, когда у вас есть byte_array[i], используемый с int_array[i] в al oop. (Когда я говорю x86 Я имею в виду включение x86-64, в отличие от ARM или PowerP C. Конечно, вы на самом деле не хотите компилировать 32-битный код, который Microsoft называет «x86») с очень небольшое количество ведер, например 4 Это похоже на работу для SIMD сравнений. В x86 SSE2 число int элементов на 16-байтовый вектор данных равно вашему количеству гистограмм. У вас уже была идея SIMD, когда вы пытались рассматривать число как четыре отдельных байтовых элемента. См. https://en.wikipedia.org/wiki/SIMD#Software Но 00_01_10_11 - это просто синтаксис исходного уровня для читаемых человеком разделителей в числах, а double - это тип с плавающей точкой, внутреннее представление которого не так же, как для целых чисел. И вы определенно не хотите использовать строки; SIMD позволяет выполнять такие вещи, как одновременная работа с 4 элементами целочисленного массива. Лучший способ, который я вижу, - это подсчитывать совпадения для каждого из 4 значений, а не отображать элементы в счетчики. Мы хотим обрабатывать несколько элементов параллельно, но при сопоставлении их со счетчиками могут возникать коллизии, когда в одном векторе элементов есть повторяющиеся значения. Вам нужно увеличить этот счетчик в два раза. Скалярный эквивалент этого: int counts[4] = {0,0,0,0};
for () {
counts[0] += (arr[i] == 0);
counts[1] += (arr[i] == 1);
counts[2] += (arr[i] == 2); // count matches
//counts[3] += (arr[i] == 3); // we assume any that aren't 0..2 are this
}
counts[3] = size - counts[0] - counts[1] - counts[2];
// calculate count 3 from other counts
, что (в C ++) G CC -O3 на самом деле будет автоматически векторизовать в точности так, как я делал ниже : https://godbolt.org/z/UJfzuH. Clang даже развертывает его при автоматической векторизации, поэтому он должен быть лучше , чем моя версия с ручной векторизацией для int входов. Тем не менее, она не так хороша, как альтернативная стратегия vpermilps для этого случая. (И вам все равно нужно вручную векторизовать, если вы хотите, чтобы байтовые элементы имели эффективные узкие суммы, расширяясь только во внешнем l oop.) С байтовыми элементами см. Как рассчитывать вхождения символов с использованием SIMD . Размер элемента слишком узок для счетчика; он переполнится после 256 отсчетов. Таким образом, вы должны расширить либо внутреннюю l oop, либо использовать вложенные циклы для некоторого накопления перед расширением. Я не знаю C#, поэтому я мог бы написать код в сборке x86 или в C ++ с внутренностями. Возможно, C ++ intrinsics более полезен для вас. C# имеет какие-то векторные расширения, которые должны сделать возможным его перенос. Это C ++ для x86-64, использующий встроенные функции AVX2 SIMD. См. { ссылка } для получения дополнительной информации. // Manually vectorized for AVX2, for int element size
// Going nearly 4x as fast should be possible for byte element size
#include <immintrin.h>
void count_elements_avx2(const std::vector<int> &input, unsigned output_counts[4])
{
__m256i counts[4] = { _mm256_setzero_si256() }; // 4 vectors of zeroed counters
// each vector holds counts for one bucket, to be hsummed at the end
size_t size = input.size();
for(size_t i = 0 ; i<size ; i+=8) { // 8x 32-bit elements per vector
__m256i v = _mm256_loadu_si256((const __m256i*)&input[i]); // unaligned load of 8 ints
for (int val = 0 ; val < 3; val++) {
// C++ compilers will unroll this with 3 vector constants and no memory access
__m256i match = _mm256_cmpeq_epi32(v, _mm256_set1_epi32(val)); // 0 or all-ones aka -1
counts[val] = _mm256_sub_epi32(counts[val], match); // x -= -1 or 0 conditional increment
}
}
// transpose and sum 4 vectors of 8 elements down to 1 vector of 4 elements
__m128i summed_counts = hsum_xpose(counts); // helper function defined in Godbolt link
_mm_storeu_si128((__m128i*)output_counts, summed_counts);
output_counts[3] = size - output_counts[0]
- output_counts[1] - output_counts[2];
// TODO: handle the last size%8 input elements; scalar would be easy
}
Это прекрасно компилируется с помощью clang (в проводнике компилятора Godbolt ). Предположительно, вы можете написать C#, который компилируется в подобный машинный код. Если нет, подумайте о вызове нативного кода из компилятора C ++ (или написанного от руки в asm, если вы не можете получить действительно оптимальный код из компилятора). Если ваш реальный вариант использования выполняет столько итераций, сколько и ваш тест, это может амортизировать дополнительные издержки, если входной массив не нужно копировать. # from an earlier version of the C++, doing all 4 compares in the inner loop
# clang -O3 -march=skylake
.LBB0_2: # do {
vmovdqu ymm7, ymmword ptr [rcx + 4*rdx] # v = load arr[i + 0..7]
vpcmpeqd ymm8, ymm7, ymm3 # compare v == 0
vpsubd ymm4, ymm4, ymm8 # total0 -= cmp_result
vpcmpeqd ymm8, ymm7, ymm5
vpsubd ymm2, ymm2, ymm8
vpcmpeqd ymm7, ymm7, ymm6 # compare v == 2
vpsubd ymm1, ymm1, ymm7 # total2 -= cmp_result
add rdx, 8 # i += 8
cmp rdx, rax
jb .LBB0_2 # }while(i < size)
Расчетная производительность Skylake в лучшем случае: ~ 2,5 циклов на вектор (8 int или 32 int8_t) или 2 с развертыванием. Без AVX2, используя только SSE2, у вас были бы дополнительные movdqa инструкции и только 4 элемента по вектору. Это все равно будет победа против скалярной гистограммы в памяти. Даже 1 элемент / тактовая частота хороши и должны выполняться с SSE2, который может работать на любом процессоре x86-64. Если, конечно, нет ошибок в кэше, аппаратная предварительная выборка в L1d опережает l oop , Это может произойти только с данными, уже горячими в кеше L2, по крайней мере. Я также предполагаю, что из-за выравнивания памяти нет остановок; в идеале ваши данные должны быть выровнены на 32 байта. Если это обычно не так, возможно, стоит обработать первую невыровненную часть и затем использовать выровненные нагрузки, если массив достаточно большой. Для байтовых элементов самый внутренний l oop будет выглядеть аналогично (с vpcmpeqb и vpsubb, но будет выполняться не более 255 (не 256) итераций перед суммированием до 64-битных счетчиков, чтобы избежать переполнения. Таким образом, пропускная способность на вектор будет одинаковой , но с 4-кратным числом элементов на вектор. См. https://agner.org/optimize/ и https://uops.info/ для подробного анализа производительности. Например, vpcmpeqd для мопов .info Внутренний l oop - это всего лишь 9 мопов с плавкой областью для Haswell / Skylake, поэтому наилучшее узкое место во внешнем интерфейсе - около 1 итерации на 2,25 цикла (конвейер 4 мегапикселя). Эффекты Small-l oop несколько мешают: Снижается ли производительность при выполнении циклов, у которых число мопов не кратно ширине процессора? - у Skylake есть l oop буфер отключен при обновлении микрокода Для ошибки, но даже до этого 9 мегапикселей l oop выдавали чуть хуже, чем один итер в среднем на 2,25 цикла, скажем, 2,5 цикла. Skylake работает vpsubd на портах 0, 1 или 5, и запускается vpcmpeqd на портах 0 или 1. Таким образом, узкое место на портах 0,1,5 составляет 6 векторов ALU для 3 портов или 1 итерация на 2 цикла. Таким образом, узкое место внешнего интерфейса преобладает. (Более широкий внешний интерфейс Ice Lake может позволить узкому месту на заднем конце даже без развертывания; те же самые внутренние пропускные способности там, если вы не используете AVX512 ...) Если бы clang проиндексировал конец массива и посчитал индекс до нуля (так как он все равно решил использовать режим индексированной адресации), он мог бы сохранить моп в общей сложности 8 мопов = один итер на 2 циклы в переднем конце, соответствующие заднему узкому месту. (В любом случае, скалярный add и слитый макрос cmp/jcc, или ветвь add/jcc l oop могут работать на порту 6, и нагрузка не конкурирует с портами ALU.) Повтор выполнения UUUU ALU зависит от загрузка не должна быть проблемой даже в случае пропадания кэша, если узким местом является ALU-мопы, обычно будет много старых мопов, ожидающих готовности исполнительного модуля, а не ожидающих загрузки данных. Развертывание на 2 будет иметь то же самое преимущество: амортизация, что 2 мопа l oop накладных расходов. Таким образом, 16 мопов для 2 входных векторов. Это довольно многократное значение ширины конвейера в SKL и IceLake и ширины конвейера с одним мопом в Zen. Развертывание еще больше может позволить внешнему интерфейсу опередить выполнение, но с ними даже любые задержки внутреннего интерфейса позволят внешнему интерфейсу создать подушку мопов в планировщике. Это позволит ему выполнять загрузку достаточно рано. Zen2 имеет более широкий интерфейс (6 моп или 5 инструкций, IIU C). Ни одна из этих инструкций не является многопользовательской, потому что Zen2 расширил векторные ALU до 256-битных, так что это 5 однопопулярных команд. vpcmpeq* работает на FP 0,1 или 3, так же как и vpsubd, поэтому узкое место на внутреннем сервере такое же, как на Skylake: 1 вектор на 2 цикла. Но более широкий внешний интерфейс устраняет это узкое место, оставляя критический путь, являющийся внутренним, даже без развертывания. Zen1 принимает 2 мопа на 256-битную векторную операцию (или больше для пересечения полосы, но это просто 2 моп). Таким образом, предположительно, 12/3 = 4 цикла на вектор из 8 или 32 элементов, при условии, что он может эффективно провести эти мопы через интерфейс. Я предполагаю, что зависимость циклов задержки с 1 циклом через счетчик векторы хорошо спланированы бэкэндами и не приводят ко многим потерянным циклам. Вероятно, не имеет большого значения, особенно если у вас есть какие-то узкие места в памяти в реальной жизни. (В Piledriver операции SIMD-integer имеют задержку в 2 цикла, но 6 операций ALU для двух векторных портов ALU, которые могут их запускать, составляют 1 вектор (128 бит) на 3 цикла, поэтому даже без развертывания достаточно работы, чтобы скрыть эту задержку.) Я не анализировал горизонтальную часть этого. Он находится за пределами l oop, поэтому он должен запускаться только один раз за звонок. Вы пометили эту микрооптимизацию, но нам, вероятно, не нужно беспокоиться об этой части. Другие числа сегментов
Базовый вариант этой стратегии - 2 сегмента: считать совпадения с одной стороны, count_other = size - count.
Мы знаем, что каждый элемент является одной из этих 4 возможностей, поэтому мы можем предположить, что любой x, который не равен 0, 1 или 2, 3 без проверки. Это означает, что нам не нужно считать совпадения для 3 на всех , и мы можем получить счет для этого сегмента из size - sum(counts[0..2]).
(см. Историю изменений для вышеупомянутого анализа перфорации перед выполнением этой оптимизации. Я изменил числа после этой оптимизации и обновления ссылки Godbolt, надеюсь, я ничего не пропустил.)
AVX512 на Skylake-Xeon
для 64 -байтовых векторов нет vpcmpeqd, чтобы сделать вектор из всех нулевых (0) или всех один (-1) элементов. Вместо этого вы бы сравнили его с регистром маски и использовали бы его для добавления маски с слиянием set1(1). Как и c = _mm512_mask_add_epi32(c, _mm512_set1_epi32(1)).
К сожалению, неэффективно делать скалярный подсчет битовых масок результата сравнения.
Случайный просмотр кода: в вашем первом тесте:
int[] valueLIST = indexers.ToArray();
Это кажется бессмысленным; Согласно документам MS (https://docs.microsoft.com/en-us/dotnet/standard/collections/), список эффективно индексируется. Я думаю, что это эквивалентно C ++ std::vector<T>. Вы можете просто повторить его, не копируя в массив.
Альтернативная стратегия - сопоставить 0..3 с набором битов в одном байте типа int
Хорошо, если вы можете ' Сузьте свои элементы до байтов для ввода, чтобы сохранить пропускную способность памяти.
Но, говоря о том, может быть, стоит использовать 2x _mm256_packs_epi32 (vpackssdw) и _mm256_packs_epi16 (vpacksswb), чтобы сузить до 8-битные целые числа перед счетом с 3x pcmpeqb / psubb. Это стоит 3 мопа на 4 входных вектора, чтобы упаковать до 1 с байтовыми элементами.
Но если ваш вход имеет начальные элементы int, это может быть лучше, чем упаковывать и затем сравнивать 3 способа.
У вас есть 4 сегмента, а int имеет 4 байта. Если мы сможем преобразовать каждый int элемент в 1 в нижней части соответствующего байта, это позволило бы добавить с _mm256_add_epi8 до 255 внутренних l-1332 * итераций перед расширением до 64-битных счетчиков. (Со стандартным _mm256_sad_epu8 против нулевого трюка до байтов без знака hsum без переполнения.)
Есть 2 способа сделать это. Первый: использует тасование в качестве справочной таблицы. AVX2 vpermd работает (_mm256_permutexvar_epi32), используя данные в качестве вектора индекса и константу _mm256_set_epi32(0,0,0,0, 1UL<<24, 1UL<<16, 1UL<<8, 1UL<<0) в качестве перетасовываемых данных. Или наберите вектор, чтобы использовать AVX1 vpermilps в качестве LUT с вектором LUT, имеющим эти байты также в верхней половине.
vpermilps лучше: меньше мопов на AMD Zen 1, и более низкая задержка везде, потому что это на линии (Может вызывать задержку обхода на некоторых процессорах, снижая преимущество задержки, но все же не хуже, чем vpermd).
По некоторым причинам vpermilps с векторным управлением имеет пропускную способность 2 цикла на Zen2, хотя это все еще один моп. Или 4 цикла на Zen1 (для версии 2 UOP YMM). Это 1 цикл на Intel. vpermd еще хуже для AMD: больше мопов и такая же низкая пропускная способность.
vpermilps xmm (16-байтовый вектор) на Piledriver имеет 1 / тактовую пропускную способность в соответствии с тестированием Agner Fog и работает в режиме "ive" c "домен. (Таким образом, на самом деле он имеет дополнительную задержку обхода задержки, когда используется с «предполагаемыми» операндами с плавающей запятой, но не с целым числом).
// Or for Piledriver, __m128 version of this
__m256 bytepatterns = _mm256_casts256_ps(_mm256_set_epi32(
1<<24, 1<<16, 1<<8, 1<<0,
1<<24, 1<<16, 1<<8, 1<<0) );
__m256i v = _mm256_loadu_si256((const __m256i*)&input[i]);
v = _mm256_castps_si256(_mm256_permutevar_ps(bytepatterns, v)); // vpermilps 32-bit variable shuffle
counts = _mm256_add_epi8(counts, v);
// after some inner iterations, separate out the
// set1_epi32(0x000000ff) counts, 0x0000ff00 counts, etc.
Это создаст чередующиеся счетчики внутри каждого элемента int. Они переполнятся, если вы не накопите их до 256 отсчетов. См. Как подсчитывать вхождения символов с помощью SIMD для простой версии этого с одним счетчиком.
Здесь мы можем развернуть и использовать 2 разных вектора LUT, поэтому, когда мы хотим сгруппировать все значения для 0 вместе мы могли бы смешать 2 вектора вместе и маскировать остальные.
В качестве альтернативы тасованию мы можем сделать это с переменными сдвигами AVX2.
sums += 1UL << (array[i]*8);, где *8 - это число бит в байте, также выполненное со сдвигом , Я написал его как скалярное выражение C ++, потому что теперь у вас есть шанс увидеть, как ваша идея байтов в целом числе может действительно работать. Пока мы не допускаем переполнения отдельных байтов, не имеет значения, добавляет ли байты SIMD перенос блока между байтами или если мы используем 32-битные элементы dword.
Мы сделали бы это с AVX2 как :
__m256i v = loadu...();
v = _mm256_slli_epi32(v, 3); // v *= 8
v = _mm256_sllv_epi32(_mm256_set1_epi32(1), v);
counts = _mm256_add_epi8(counts, v);
Это 2 сменные инструкции плюс vpaddb. На Skylake сдвиги с переменным числом vpsllvd дешевы: однопроцессные и работают на нескольких портах. Но на Haswell и Zen это медленнее. (Та же пропускная способность, что и vpermilps для AMD)
И 2 мопа для 2 портов по-прежнему не превышают 1 моп для 1 порта для версии с произвольным воспроизведением. (Если только вы не используете обе стратегии поочередно для распределения работы по всем портам ALU в SKL.)
Так или иначе, самый внутренний l oop может go 1 вектор за такт или, может быть, немного лучше с осторожным чередованием методов сдвига и тасования.
Но это потребует некоторого небольшого количества накладных расходов, амортизируемых по 128 или 255 внутренним итерациям l oop.
Эта очистка в конец мог бы смешать 2 вектора вместе, чтобы получить вектор со счетчиками всего для 2 блоков, а затем vpshufb (_mm256_shuffle_epi8) сгруппировать счетчики байтов для одного и того же блока в одни и те же слова. Тогда vpsadbw (_mm256_sad_epu8) против нуля может горизонтально суммировать эти байтовые элементы в каждом qword для _mm256_add_epi64. Таким образом, external-l oop работа должна быть 2 vpblendw, 2x vpshufb, 2x vpsadbw, 2x vpaddq, а затем вернуться к другим 255 итерациям внутреннего l oop. Возможно, также проверяется, что вы находитесь в пределах 255 итераций от конца массива, чтобы установить границу l oop для внутренней итерации.