Быстрое копирование каждого второго байта в новую область памяти

Question

Мне нужен быстрый способ скопировать каждый второй байт в новую область памяти malloc. У меня есть необработанное изображение с данными RGB и 16 битами на канал (48 бит), и я хочу создать изображение RGB с 8 битами на канал (24 бита).

Есть ли более быстрый способ, чем копирование в байтовом режиме? Я не знаю много о SSE2, но я полагаю, что это возможно с SSE/SSE2.

Answer 1

Ваши RGB-данные упакованы, поэтому нам не нужно заботиться о границах пикселей. Проблема заключается только в упаковке каждого второго байта массива. (По крайней мере, в пределах каждой строки вашего изображения; если вы используете шаг строки 16 или 32B, заполнение может быть не целым числом пикселей.)

Это может быть эффективно выполнено с использованием тасов SSE2, AVX или AVX2. (Также AVX512BW, и, возможно, даже больше с AVX512VBMI, но первые процессоры AVX512VBMI, вероятно, не будут иметь очень эффективной vpermt2b , тасование байтов с 2-мя входами.)

---

Вы можете использовать SSSE3 pshufb чтобы получить байты, которые вы хотите, но это только случайный случай с 1 вводом, который даст вам 8 байтов вывода. Хранение 8 байтов за раз требует больше общих инструкций хранения, чем сохранение 16 байтов за раз. (Вы также столкнулись с проблемой пропускной способности тасования на процессорах Intel начиная с Haswell, которые имеют только один порт тасования и, следовательно, пропускную способность на один такт). (Вы также можете рассмотреть 2x pshufb + por чтобы накормить магазин 16B, и это может быть хорошо для Райзена. Используйте 2 различных вектора управления тасованием, один из которых помещает результат в низкий 64b, а другой - в высокий 64b. См. Преобразование 8 16-битного регистра SSE в 8-битные данные).

Вместо этого возможно использовать _mm_packus_epi16 (packuswb). Но так как он насыщает, а не отбрасывает ненужные байты, вы должны подать на его вход данные, которые вы хотите сохранить в младшем байте каждого 16-битного элемента.

В вашем случае это, вероятно, старший байт каждого компонента RGB16, отбрасывая 8 младших разрядов из каждого компонента цвета. т.е. _mm_srli_epi16(v, 8), Чтобы обнулить старший байт в каждом 16-битном элементе, используйте _mm_and_si128(v, _mm_set1_epi16(0x00ff)) вместо. (В этом случае не обращайте внимания на все, что связано с использованием не выровненной нагрузки для замены одной из смен; это простой случай, и вам просто нужно использовать два AND для подачи на PACKUS.)

Это более или менее, как gcc и clang автоматически векторизуют это, в -O3, За исключением того, что они оба испортили и потеряли важные инструкции ( https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82356, https://bugs.llvm.org/show_bug.cgi?id=34773). Тем не менее, позволяя им автоматически векторизовать с SSE2 (базовый уровень для x86-64), или с NEON для ARM или чем-то еще, это хороший безопасный способ получить некоторую производительность без риска появления ошибок при ручной векторизации. За исключением ошибок компилятора, все, что они генерируют, будет правильно реализовывать семантику C этого кода, которая работает для любого размера и выравнивания:

// gcc and clang both auto-vectorize this sub-optimally with SSE2.
// clang is *really* sub-optimal with AVX2, gcc no worse
void pack_high8_baseline(uint8_t *__restrict__ dst, const uint16_t *__restrict__ src, size_t bytes) {
  uint8_t *end_dst = dst + bytes;
  do{
     *dst++ = *src++ >> 8;
  } while(dst < end_dst);
}

Смотрите код + asm для этой и последующих версий на Godbolt.

// Compilers auto-vectorize sort of like this, but with different
// silly missed optimizations.
// This is a sort of reasonable SSE2 baseline with no manual unrolling.
void pack_high8(uint8_t *restrict dst, const uint16_t *restrict src, size_t bytes) {
  // TODO: handle non-multiple-of-16 sizes
  uint8_t *end_dst = dst + bytes;
  do{
     __m128i v0 = _mm_loadu_si128((__m128i*)src);
     __m128i v1 = _mm_loadu_si128(((__m128i*)src)+1);
     v0 = _mm_srli_epi16(v0, 8);
     v1 = _mm_srli_epi16(v1, 8);
     __m128i pack = _mm_packus_epi16(v0, v1);
     _mm_storeu_si128((__m128i*)dst, pack);
     dst += 16;
     src += 16;  // 32 bytes, unsigned short
  } while(dst < end_dst);
}

---

Но во многих микроархитектурах скорость смещения вектора ограничена 1 на такт (Intel до Skylake, AMD Bulldozer/Ryzen). Кроме того, до AVX512 нет инструкции asm load + shift, поэтому все эти операции трудно выполнить через конвейер. (т.е. мы легко становимся узким местом на переднем конце.)

Вместо сдвига мы можем загрузить адрес, который смещен на один байт, поэтому нужные нам байты находятся в нужном месте. И чтобы маскировать байты, которые мы хотим, имеет хорошую пропускную способность, особенно с AVX, где компилятор может складывать нагрузку + и в одну инструкцию. Если вход выровнен по 32 байта, и мы делаем этот трюк со смещением нагрузки только для нечетных векторов, наши нагрузки никогда не пересекут границу строки кэша. С развертыванием цикла это, вероятно, лучшая ставка для SSE2 или AVX (без AVX2) для многих процессоров.

// take both args as uint8_t* so we can offset by 1 byte to replace a shift with an AND
// if src is 32B-aligned, we never have cache-line splits
void pack_high8_alignhack(uint8_t *restrict dst, const uint8_t *restrict src, size_t bytes) {
  uint8_t *end_dst = dst + bytes;
  do{
     __m128i v0 = _mm_loadu_si128((__m128i*)src);
     __m128i v1_offset = _mm_loadu_si128(1+(__m128i*)(src-1));
     v0 = _mm_srli_epi16(v0, 8);
     __m128i v1 = _mm_and_si128(v1_offset, _mm_set1_epi16(0x00FF));
     __m128i pack = _mm_packus_epi16(v0, v1);
     _mm_store_si128((__m128i*)dst, pack);
     dst += 16;
     src += 32;  // 32 bytes
  } while(dst < end_dst);
}

Без AVX внутренний цикл занимает 6 инструкций (6 моп) на 16B вектор результатов. (С AVX это только 5, так как нагрузка складывается в и). Так как это полностью узкие места на переднем конце, раскрутка петли очень помогает. gcc -O3 -funroll-loops выглядит довольно хорошо для этой версии с векторной ручкой, особенно с gcc -O3 -funroll-loops -march=sandybridge включить AVX.

С AVX, возможно, стоит сделать оба v0 а также v1 с and, чтобы уменьшить внешнее узкое место за счет разделения строки кэша. (И случайные расщепления страниц). Но, возможно, нет, в зависимости от uarch, и если ваши данные уже выровнены или нет. (Разветвление на этом может стоить, так как вам нужно максимально увеличить пропускную способность кэша, если данные горячие в L1D).

С AVX2 256-битная версия с 256-битной загрузкой должна хорошо работать на Haswell/Skylake. С src Выровненный по 64B, смещение-загрузка все равно никогда не разделится на строки кэша. (Это будет всегда загружать байты [62:31] строки кэша, а v0 load будет всегда загружать байты [31:0]). Но работа пакета в пределах 128b дорожек, поэтому после пакета вы должны перемешать (с vpermq) разместить 64-битные блоки в правильном порядке. Посмотрите, как gcc автоматически векторизует скалярную базовую версию с vpackuswb ymm7, ymm5, ymm6 / vpermq ymm8, ymm7, 0xD8,

С AVX512F эта уловка перестает работать, потому что нагрузка 64B должна быть выровнена, чтобы оставаться в пределах одной строки кэша 64B. Но с AVX512 доступны различные тасовки, и пропускная способность ALU uop более ценна (на Skylake-AVX512, где порт 1 отключается, когда 512b мопов находятся в полете). Так v = нагрузка + смена -> __m256i packed = _mm512_cvtepi16_epi8(v) может хорошо работать, даже если он работает только с 256b магазинами.

Правильный выбор, вероятно, зависит от того, выровнены ли ваши src и dst обычно 64B. У KNL нет AVX512BW, так что это, вероятно, применимо только к Skylake-AVX512.