Как наиболее эффективно сохранить часть __m128i / __ m256i, игнорируя при этом некоторое количество элементов с начала / конца

К сожалению, у меня не получилось так быстро, как хотелось бы, поэтому я оставлю вопрос открытым, если кто-то знает ответ получше.

Откуда возникла проблема.

Я искал, как реализовать инклюзивное сканирование на месте поверх AVX2. Расширения SIMD. Мое решение полностью основано на: @Zboson ответе.

  [a      b           c               d        ]
+ [0      a           b               c        ]
= [a   (a + b)     (b + c)         (c + d)     ]
+ [0      0           a            (a + b)     ]
= [a   (a + b)   (a + b + c)   (a + b + c + d) ]

Каждый алгоритм диапазона, который я реализовал ранее, хорошо работал со следующим шаблоном итерации (код sudo):

auto aligned_f = previous_aligned_address(f);
auto aligned_l = previous_aligned_address(l);
ignore_first_n ignore_first{f - aligned_f};

if (aligned_f != aligned_l) {
   step(aligned_f, ignore_first);  // Do a simd step, ignoring everything 
                                   // between aligned_f and f.
   aligned_f += register_width;
   ignore_first = ignore_first_n{0};

   // Big unrolled loop.
   main_loop(aligned_f, aligned_l);

   if (aligned_f == aligned_l) return;
}

ignore_last_n ignore_last {aligned_l + register_width - l};
ignore_first_last ignore = combine(ignore_first, ignore_last);

// Do a simd step, ignoring everything between aligned_l and l.
// + handle the case when register is bigger than the array size.
step(aligned_l, ignore);

(Если вы не знаете, почему это нормально - см.).

Как упоминалось в @PeterCordes и @PaulR, если вы измените шаблон итерации - смешайте некоторые другие значения и сделайте простое невыровненное хранилище, и это, вероятно, то, что мне придется сделать. Тогда вы можете сделать не более одного истинно замаскированного хранилища - только когда регистр не подходит полностью.

Однако это больше сгенерировано сборкой, и я не был уверен, реализовал ли я store(address, register, ignore) наиболее эффективным способом - отсюда и был мой вопрос.

ОБНОВЛЕНИЕ: попробовал это, даже ничего не смешивая, вы можете просто сначала загрузить 2 перекрывающихся регистра, а затем сохранить их обратно. Все стало немного хуже. Это не кажется хорошей идеей, по крайней мере, для инклюзивного сканирования.

Измерения

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

Я показываю измерения для 2 случаев ‹256, 1> - использовать 256-битные регистры, без разворачивания,‹ 256, 2> - дважды развернуть основной цикл.

ПРИМЕЧАНИЕ. В тестах я учитываю возможные проблемы с выравниванием кода, выравнивая код тестирования 64 различными способами и выбирая минимальное значение.

_mm_maskmoveu_si128

Первоначально я выбрал _mm256_maskstore для sizeof(T) >= 4 и 2 _mm_maskmoveu_si128 для остальных.

Это, как вы можете видеть, - выполнено очень плохо - для char мы проигрываем скалярному коду примерно 10 раз, примерно 20 раз для short и 2 раза для int.

Используйте memcpy для char и short

Я пробовал несколько разных вещей: использовать _mm256_maskstore для short, memcpy для int, написать собственный встроенный memcpy для моего случая. Лучшее, что я получил: memcpy за char и short и maskstore за int.

Это выигрыш для char, разница в пару наносекунд между использованием без развертывания и двойным развертыванием, около 30% потерь для short и 50% потерь для int.

Итак, по крайней мере, с моей реализацией store(ptr, reg, ignore) мне нужно сделать другой шаблон итераций, если я не хочу очищать циклы.

Объявление для store(addr, reg, ignore)

ПРИМЕЧАНИЕ: я удалил оболочки и адаптеры, возможно, добавил несколько ошибок.

// Only showing one ignore_broadcast, they are very similar and
// are actually generated with templates
template <register_256 Register, std::same<int> T>
inline __m256i ignore_broadcast(ignore_first_n ignore) {
     __m256i idxs = _mm256_set_epi32(7, 6, 5, 4, 3, 2, 1, 0);
     __m256i n_broadcasted = _mm256_set1_epi32(ignore.n - 1);
     return _mm256_cmpgt_epi32(idxs, n_broadcasted);
}

template <template Register, typename T, typename Ignore>
void store(Register reg, T* ptr, Ignore ignore) {
    if constexpr (sizeof(T) >= 4) {
        const auto mask = ignore_broadcast<Register, T>(ignore);
        _store::maskstore(ptr, mask, reg);
        return;
    }

    std::size_t start = 0, n = sizeof(reg) / sizeof(T);
    if constexpr (std::is_same_v<Ignore, ignore_first_n>) {
        start += ignore.n;
        n -= ignore.n;
    } else if constexpr (std::is_same_v<Ignore, ignore_last_n>) {
        n -= ignore.n;
    } else {
        static_assert(std::is_same_v<Ignore, ignore_first_last>);
        start += ignore.first_n;
        n -= ignore.first_n + ignore.last_n;
    }

    // This requires to store the register on the stack.
    std::memcpy(raw_ptr + start, reinterpret_cast<T*>(&reg) + start, n * sizeof(T));
}

Что делает memcpy

Это memcpy вызывается.

Он реализует копирование менее 32 байт следующим образом:

    #if VEC_SIZE > 16
        /* From 16 to 31.  No branch when size == 16.  */
    L(between_16_31):
        vmovdqu        (%rsi), %xmm0
        vmovdqu        -16(%rsi,%rdx), %xmm1
        vmovdqu        %xmm0, (%rdi)
        vmovdqu        %xmm1, -16(%rdi,%rdx)
        ret
    #endif
    L(between_8_15):
        /* From 8 to 15.  No branch when size == 8.  */
        movq        -8(%rsi,%rdx), %rcx
        movq        (%rsi), %rsi
        movq        %rcx, -8(%rdi,%rdx)
        movq        %rsi, (%rdi)
        ret
    L(between_4_7):
        /* From 4 to 7.  No branch when size == 4.  */
        movl        -4(%rsi,%rdx), %ecx
        movl        (%rsi), %esi
        movl        %ecx, -4(%rdi,%rdx)
        movl        %esi, (%rdi)
        ret
    L(between_2_3):
        /* From 2 to 3.  No branch when size == 2.  */
        movzwl        -2(%rsi,%rdx), %ecx
        movzwl        (%rsi), %esi
        movw        %cx, -2(%rdi,%rdx)
        movw        %si, (%rdi)
        ret

Итак, в основном - возьмите самый большой регистр, который подходит, и сделайте два перекрывающихся магазина. Я попытался сделать это встроенным образом - вызов memcpy был быстрее - хотя, возможно, я поступил неправильно.

Сборка и код

Чтение моего кода может быть немного сложным, особенно потому, что я полагаюсь на библиотеку eve, которая еще не является открытым исходным кодом.

Итак, я собрал и опубликовал пару листингов сборок:

, a hrefling для отмены сборки = "https://github.com/DenisYaroshevskiy/unsq_eve/blob/7c01a4631c393330b11776b36082a390a011e81f/disassemble/disassemble.s#L54" rel = "nofollow noreferrer"> Короче полная сборка, без разворачивания

Мой код можно найти здесь

PS: Измерение большого размера

Если вам интересно, на достаточно большом массиве этот тип векторизации - хорошая победа. Например, на 10'000 байтах.

Примерно 5 раз для символов, 3 раза для коротких и 2 раза для целых.

PS: при развертывании

Я не придумал какой-то умной раскрутки. Самая простая двойная развертка дает около 10% выигрыша для 10000 байт short. Развертывание еще не помогло. Я подозреваю, что причина того, что выигрыш так мала, в том, что алгоритм довольно сложен.

Не было места, чтобы добавить это, но это связано.

Этот вопрос расширился для меня до более общего вопроса:
Как изменить массив на месте, если его размер не делится на размер регистра SIMD.

Подобно тому, что сказал @PaulR, я рассмотрел несколько подходов:

1. скалярная очистка.
2. использовать store (игнорировать) (как-то замаскировать перед первым байтом и после последнего байта)
3. если размер массива позволяет это, перекрывайте первые / последние хранилища соседними.
4. полностью используйте невыровненные загрузки / хранилища и сделайте замаскированное хранилище в качестве последнего шага.

ПРИМЕЧАНИЕ. Отнеситесь к результатам с недоверием, сравнительный анализ - это сложно, и я могу ошибаться.

Выравнивание кода

Краткая версия: размещение вашего кода в двоичном файле существенно влияет на производительность.
Расширенная версия: блог easy perf, Обсуждение конференции llvm

Контрольные точки

Я беру массив заданного размера в байтах и ​​применяю к нему алгоритм.
Я проверяю все выравнивания кода от 0 до 64, добавляя слайд такого размера перед тестом.
(Безоперационный слайд не выполняется при измерении).

Подробности см. В предыдущем ответе. Я использую maskstore для int и memcpy для char и short.

Алгоритмы / Код

Я в основном сосредоточен здесь на удвоении каждого элемента (x = x + x).
Я называю этот алгоритм transform.

ПРИМЕЧАНИЕ: мой код, вероятно, сложно читать, поэтому я предоставляю сборку для всего. https://disassemble/disassemble.s#L8"> https://disassemble/disassemble.s#L8"> https://disassemble/nofollownoreferrerfree"> https://disassemble/http: //www.http://http://http://www.nofollownoreferrer //gcc.godbolt.org/z/MrKGEG "rel =" nofollow noreferrer "> godbolt std :: transform

transform<256, 4> - версия с выровненными чтения / записи первым и последним хранилищами должна иметь дело с частичным выходом за границы с помощью store(ignore). Развертываю 4 раза, компилятор разворачивает еще сверху. 256 - 256-битные регистры.

Что мне интересно, так это то, что в хорошем сценарии я не вижу каких-либо штрафов за использование невыровненных загрузок / хранилищ (это то, что используют как std::transform, так и мой transform_unaligned).

Также полезно посмотреть на влияние выравнивания кода

Я обычно подозреваю, что ветки в таких колебаниях выравнивания кода, но transform_unaligned не более ветвистые, чем transform. Так, может быть, невыровненное чтение чувствительно?

Заключение: предполагая, что вы можете контролировать выравнивание своего кода, стратегия обработки границ имеет значение только при небольшом размере массива.

Магазины - это то, что дорого

Сравним 3 алгоритма на 40 короткометражках: reduce, transform, inclusive_scan. reduce делает гораздо больше добавлений, а также кучу свопов, по сравнению с transform, когда он приближается к inclusive_scan.

Однако мы видим, что вычисление для сокращения гораздо менее важно, чем сохранение для преобразования. Мы также можем сказать, что множество сдвигов и вычислений для inclusive_scan составляют чуть более 20% его времени (преобразование выполняет все те же действия, за исключением гораздо более простых вычислений).

Я пытался профилировать, чтобы получить больше информации, но я недостаточно хорош в этом.

Сравнение различных стратегий для 40 байт данных

Я бы хотел избавиться от отслаивания петель (есть причины, не связанные с производительностью, почему это раздражает). Очевидно, что если я буду достаточно маленьким (например, до 1 или 2 элементов), это не сработает. Я произвольно решил, что если я побью очистку петли на 40 байтах, это будет успехом.

Два игнор против пилинга

Подход по умолчанию для выполнения store(ignore) превосходит очистку петель для символов и коротких замыканий, но теряет около 25% для целых чисел.

Два игнорирования против невыровненного и одно игнорирование

Использование невыровненных загрузок / хранилищ для получения одного игнорирования кажется нецелесообразным - разница составляет 0,2 наносекунды, что, по моему мнению, является шумом.

Перекрытие против двух игнорировать

Перекрывающиеся магазины - это выигрыш для персонажей и короткометражек, поскольку здесь используется memcpy вместо store(ignore). Однако это не решает мою проблему для int.

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

Учитывая повышенную сложность, не думаю, что буду этим пользоваться.

Два игнорирования против пилинга, инклюзивное сканирование

Для полноты картины репост обновленных результатов для inclusive_scan - отслаивания петель выглядит очень привлекательно. В этом есть смысл, поскольку на 40 байтах очень мало вычислительной выгоды. (40 байтов означают два регистра, поэтому 64 байта, но 24 из них потрачены впустую).

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

P.S. Отслаивание петель при чтении данных.

std::reduce будет автоматически векторизован, и петля будет снята. Мое сокращение не будет, оно заменит нули элементы, загруженные вне массива. Это хорошая стратегия для 40 байт данных.

Я также видел похожие результаты для find. Конечно, 40 байт - это произвольно маленький размер, и если вы уменьшите его, вы, вероятно, сможете добраться туда, где это выгодно, но это граница, которую я сокращаю.

person Denis Yaroshevskiy    schedule 20.06.2020

comment

Работает ли текущий clang над проблемой производительности uop-cache введено обновлением микрокода Intel для исправления ошибки JCC? Если нет, то это может во многом объяснить эффект выравнивания кода или разворачивания различий, если мы говорим о выравнивании относительно 32-байтовой границы. - person Peter Cordes; 21.06.2020

comment

@PeterCordes - не умеет отвечать. Я знаю 2 вещи: а) Я считаю, что LSB отключен (вы показали мне это в какой-то момент) б) Perf переходит от минимального к максимальному при каждом другом отсутствии операции (0 - плохо, 1 - хорошо, 2 - плохо, 3 - хорошо ... до 64) pasteboard.co/Je2F2RE.png - person Denis Yaroshevskiy; 21.06.2020