Самая быстрая операция с чередованием в C?

У меня есть указатель на массив mixed байтов, который содержит чередующиеся байты двух разных массивов array1 и array2 . Скажем, mixed выглядит примерно так:

 a1b2c3d4... 

Мне нужно сделать de-interleave байтов, поэтому я получаю array1 = abcd... и array2 = 1234... Я знаю длину mixed заранее, и длины array1 и array2 2 эквивалентны, оба равны mixed / 2 .

Вот моя текущая реализация ( array1 и array2 уже выделены):

 int i, j; int mixedLength_2 = mixedLength / 2; for (i = 0, j = 0; i < mixedLength_2; i++, j += 2) { array1[i] = mixed[j]; array2[i] = mixed[j+1]; } 

Это позволяет избежать любых дорогостоящих операций умножения или деления, но все же не работает достаточно быстро. Я надеюсь, что есть что-то вроде memcpy который использует индекс, который может использовать операции блочного копирования на низком уровне, чтобы ускорить процесс. Есть ли более быстрая реализация, чем у меня в настоящее время?

редактировать

Целевая платформа – Objective-C для iOS и Mac. Быстрая операция важнее для устройств iOS, поэтому решение, ориентированное на iOS, было бы лучше, чем ничего.

Обновить

Спасибо всем за ответы, особенно Стивен Канон, Грэм Ли и Мекки. Вот моя «главная» функция, которая использует встроенные возможности NEON Стивена, если они доступны, и в противном случае союзные курсоры Грэма с уменьшенным числом итераций, как это было предложено Mecki.

 void interleave(const uint8_t *srcA, const uint8_t *srcB, uint8_t *dstAB, size_t dstABLength) { #if defined __ARM_NEON__ // attempt to use NEON intrinsics // iterate 32-bytes at a time div_t dstABLength_32 = div(dstABLength, 32); if (dstABLength_32.rem == 0) { while (dstABLength_32.quot --> 0) { const uint8x16_t a = vld1q_u8(srcA); const uint8x16_t b = vld1q_u8(srcB); const uint8x16x2_t ab = { a, b }; vst2q_u8(dstAB, ab); srcA += 16; srcB += 16; dstAB += 32; } return; } // iterate 16-bytes at a time div_t dstABLength_16 = div(dstABLength, 16); if (dstABLength_16.rem == 0) { while (dstABLength_16.quot --> 0) { const uint8x8_t a = vld1_u8(srcA); const uint8x8_t b = vld1_u8(srcB); const uint8x8x2_t ab = { a, b }; vst2_u8(dstAB, ab); srcA += 8; srcB += 8; dstAB += 16; } return; } #endif // if the bytes were not aligned properly // or NEON is unavailable, fall back to // an optimized iteration // iterate 8-bytes at a time div_t dstABLength_8 = div(dstABLength, 8); if (dstABLength_8.rem == 0) { typedef union { uint64_t wide; struct { uint8_t a1; uint8_t b1; uint8_t a2; uint8_t b2; uint8_t a3; uint8_t b3; uint8_t a4; uint8_t b4; } narrow; } ab8x8_t; uint64_t *dstAB64 = (uint64_t *)dstAB; int j = 0; for (int i = 0; i < dstABLength_8.quot; i++) { ab8x8_t cursor; cursor.narrow.a1 = srcA[j ]; cursor.narrow.b1 = srcB[j++]; cursor.narrow.a2 = srcA[j ]; cursor.narrow.b2 = srcB[j++]; cursor.narrow.a3 = srcA[j ]; cursor.narrow.b3 = srcB[j++]; cursor.narrow.a4 = srcA[j ]; cursor.narrow.b4 = srcB[j++]; dstAB64[i] = cursor.wide; } return; } // iterate 4-bytes at a time div_t dstABLength_4 = div(dstABLength, 4); if (dstABLength_4.rem == 0) { typedef union { uint32_t wide; struct { uint8_t a1; uint8_t b1; uint8_t a2; uint8_t b2; } narrow; } ab8x4_t; uint32_t *dstAB32 = (uint32_t *)dstAB; int j = 0; for (int i = 0; i < dstABLength_4.quot; i++) { ab8x4_t cursor; cursor.narrow.a1 = srcA[j ]; cursor.narrow.b1 = srcB[j++]; cursor.narrow.a2 = srcA[j ]; cursor.narrow.b2 = srcB[j++]; dstAB32[i] = cursor.wide; } return; } // iterate 2-bytes at a time div_t dstABLength_2 = div(dstABLength, 2); typedef union { uint16_t wide; struct { uint8_t a; uint8_t b; } narrow; } ab8x2_t; uint16_t *dstAB16 = (uint16_t *)dstAB; for (int i = 0; i  0) { const uint8x16x2_t ab = vld2q_u8(srcAB); vst1q_u8(dstA, ab.val[0]); vst1q_u8(dstB, ab.val[1]); srcAB += 32; dstA += 16; dstB += 16; } return; } // iterate 16-bytes at a time div_t srcABLength_16 = div(srcABLength, 16); if (srcABLength_16.rem == 0) { while (srcABLength_16.quot --> 0) { const uint8x8x2_t ab = vld2_u8(srcAB); vst1_u8(dstA, ab.val[0]); vst1_u8(dstB, ab.val[1]); srcAB += 16; dstA += 8; dstB += 8; } return; } #endif // if the bytes were not aligned properly // or NEON is unavailable, fall back to // an optimized iteration // iterate 8-bytes at a time div_t srcABLength_8 = div(srcABLength, 8); if (srcABLength_8.rem == 0) { typedef union { uint64_t wide; struct { uint8_t a1; uint8_t b1; uint8_t a2; uint8_t b2; uint8_t a3; uint8_t b3; uint8_t a4; uint8_t b4; } narrow; } ab8x8_t; uint64_t *srcAB64 = (uint64_t *)srcAB; int j = 0; for (int i = 0; i < srcABLength_8.quot; i++) { ab8x8_t cursor; cursor.wide = srcAB64[i]; dstA[j ] = cursor.narrow.a1; dstB[j++] = cursor.narrow.b1; dstA[j ] = cursor.narrow.a2; dstB[j++] = cursor.narrow.b2; dstA[j ] = cursor.narrow.a3; dstB[j++] = cursor.narrow.b3; dstA[j ] = cursor.narrow.a4; dstB[j++] = cursor.narrow.b4; } return; } // iterate 4-bytes at a time div_t srcABLength_4 = div(srcABLength, 4); if (srcABLength_4.rem == 0) { typedef union { uint32_t wide; struct { uint8_t a1; uint8_t b1; uint8_t a2; uint8_t b2; } narrow; } ab8x4_t; uint32_t *srcAB32 = (uint32_t *)srcAB; int j = 0; for (int i = 0; i < srcABLength_4.quot; i++) { ab8x4_t cursor; cursor.wide = srcAB32[i]; dstA[j ] = cursor.narrow.a1; dstB[j++] = cursor.narrow.b1; dstA[j ] = cursor.narrow.a2; dstB[j++] = cursor.narrow.b2; } return; } // iterate 2-bytes at a time div_t srcABLength_2 = div(srcABLength, 2); typedef union { uint16_t wide; struct { uint8_t a; uint8_t b; } narrow; } ab8x2_t; uint16_t *srcAB16 = (uint16_t *)srcAB; for (int i = 0; i < srcABLength_2.quot; i++) { ab8x2_t cursor; cursor.wide = srcAB16[i]; dstA[i] = cursor.narrow.a; dstB[i] = cursor.narrow.b; } } 

В верхней части моей головы я не знаю библиотечной функции для де-чередующихся двухканальных байтовых данных. Однако стоит написать отчет об ошибке с Apple, чтобы запросить такую ​​функцию.

В то же время, довольно легко векторизовать такую ​​функцию, используя NEON или встроенные функции SSE. В частности, в ARM вы захотите использовать vld1q_u8 для загрузки вектора из каждого исходного массива, vuzpq_u8 чтобы деперемещать их, и vst1q_u8 для хранения полученных векторов; вот приблизительный эскиз, который я не тестировал и даже не пытался построить, но он должен проиллюстрировать общую идею. Более сложные реализации, безусловно, возможны (в частности, NEON может загружать / хранить два 16B-регистра в одной инструкции, что компилятор может не делать с этим, и некоторые объемы конвейерной обработки и / или разворачивания могут быть полезными в зависимости от того, как долго ваши буферы являются):

 #if defined __ARM_NEON__ # include  #endif #include  #include  void deinterleave(uint8_t *mixed, uint8_t *array1, uint8_t *array2, size_t mixedLength) { #if defined __ARM_NEON__ size_t vectors = mixedLength / 32; mixedLength %= 32; while (vectors --> 0) { const uint8x16_t src0 = vld1q_u8(mixed); const uint8x16_t src1 = vld1q_u8(mixed + 16); const uint8x16x2_t dst = vuzpq_u8(src0, src1); vst1q_u8(array1, dst.val[0]); vst1q_u8(array2, dst.val[1]); mixed += 32; array1 += 16; array2 += 16; } #endif for (size_t i=0; i 

Я только проверял это легко, но это показалось, по крайней мере, в два раза быстрее, чем ваша версия:

 typedef union { uint16_t wide; struct { uint8_t top; uint8_t bottom; } narrow; } my_union; uint16_t *source = (uint16_t *)mixed; for (int i = 0; i < mixedLength/2; i++) { my_union cursor; cursor.wide = source[i]; array1[i] = cursor.narrow.top; array2[i] = cursor.narrow.bottom; } 

Обратите внимание, что я не был осторожен с упаковкой структуры, но в этом случае на этой архитектуре это не проблема. Обратите внимание, что кто-то может жаловаться на мой выбор наименования top и bottom ; Я предполагаю, что вы знаете, какая половина этих целых чисел вам нужна.

Хорошо, вот ваш оригинальный метод:

 static void simpleDeint ( uint8_t * array1, uint8_t * array2, uint8_t * mixed, int mixedLength ) { int i, j; int mixedLength_2 = mixedLength / 2; for (i = 0, j = 0; i < mixedLength_2; i++, j += 2) { array1[i] = mixed[j]; array2[i] = mixed[j+1]; } } 

С 10 миллионами записей и -O3 (компилятор должен оптимизировать максимальную скорость), я могу запускать это 154 раза в секунду на моем Mac.

Вот мое первое предложение:

 static void structDeint ( uint8_t * array1, uint8_t * array2, uint8_t * mixed, int mixedLength ) { int i; int len; uint8_t * array1Ptr = (uint8_t *)array1; uint8_t * array2Ptr = (uint8_t *)array2; struct { uint8_t byte1; uint8_t byte2; } * tb = (void *)mixed; len = mixedLength / 2; for (i = 0; i < len; i++) { *(array1Ptr++) = tb->byte1; *(array2Ptr++) = tb->byte2; tb++; } } 

Такой же подсчет и оптимизация, как и раньше, я получаю 193 прогона в секунду.

Теперь предложение Грэма Ли:

 static void unionDeint ( uint8_t * array1, uint8_t * array2, uint8_t * mixed, int mixedLength ) { union my_union { uint16_t wide; struct { uint8_t top; uint8_t bottom; } narrow; }; uint16_t * source = (uint16_t *)mixed; for (int i = 0; i < mixedLength/2; i++) { union my_union cursor; cursor.wide = source[i]; array1[i] = cursor.narrow.top; array2[i] = cursor.narrow.bottom; } } 

Такая же настройка, как и раньше, 198 запусков в секунду (ПРИМЕЧАНИЕ: этот метод не является безопасным для конечных пользователей, результат зависит от конечной цели процессора. В вашем случае array1 и array2, вероятно, меняются местами, поскольку ARM мало ориентирована, поэтому вам придется поменять их в коде ).

Вот мой лучший вариант:

 static void uint32Deint ( uint8_t * array1, uint8_t * array2, uint8_t * mixed, int mixedLength ) { int i; int count; uint32_t * fourBytes = (void *)mixed; uint8_t * array1Ptr = (uint8_t *)array1; uint8_t * array2Ptr = (uint8_t *)array2; count = mixedLength / 4; for (i = 0; i < count; i++) { uint32_t temp = *(fourBytes++); #if __LITTLE_ENDIAN__ *(array1Ptr++) = (uint8_t)(temp & 0xFF); temp >>= 8; *(array2Ptr++) = (uint8_t)(temp & 0xFF); temp >>= 8; *(array1Ptr++) = (uint8_t)(temp & 0xFF); temp >>= 8; *(array2Ptr++) = tb->byte2; #else *(array1Ptr++) = (uint8_t)(temp >> 24); *(array2Ptr++) = (uint8_t)((temp >> 16) & 0xFF); *(array1Ptr++) = (uint8_t)((temp >> 8) & 0xFF); *(array2Ptr++) = (uint8_t)(temp & 0xFF); #endif } // Either it is a multiple of 4 or a multiple of 2. // If it is a multiple of 2, 2 bytes are left over. if (count * 4 != mixedLength) { *(array1Ptr) = mixed[mixedLength - 2]; *(array2Ptr) = mixed[mixedLength - 1]; } } 

Та же настройка, что и выше, 219 раз в секунду, и если я не ошибаюсь, должен работать либо с контентом.

Я рекомендую решение Грэма, но если это действительно критическая скорость, и вы готовы пойти на Ассемблер, вы можете получить еще быстрее.

Идея такова:

  1. Прочитайте целое 32-битное целое число из mixed . Вы получите ‘a1b2’.

  2. Поверните нижний бит 16 бит на 8 бит, чтобы получить «1ab2» (мы используем маленькие континцы, так как это по умолчанию используется в ARM и, следовательно, Apple A #, поэтому первые два байта являются нижними).

  3. Поверните весь правый 32-битный регистр (я думаю, что это правильно …) на 8 бит, чтобы получить «21ab».

  4. Поверните нижний 16 бит на 8 бит, чтобы получить ’12ab’

  5. Напишите младшие 8 бит в array2 .

  6. Поверните весь 32-битный регистр на 16 бит.

  7. Напишите младшие 8 бит в array1

  8. array1 на 16 array2 , array2 на 16 бит и mixed на 32 бит.

  9. Повторение.

Мы обменяли 2 чтения в памяти (предположим, что мы используем версию или эквивалент Грэма) и 4 памяти с одним считыванием памяти, двумя операциями записи в память и четырьмя операциями с регистром. В то время как число операций увеличилось с 6 до 7, операции регистрации быстрее, чем операции с памятью, поэтому это более эффективно. Кроме того, поскольку мы читаем со mixed 32-битного одновременно, а не 16, мы сокращаем управление итерацией наполовину.

PS: Теоретически это также можно сделать для архитектуры с 64-битной архитектурой, но выполнение всех этих поворотов для «a1b2c3d4» приведет вас к безумию.

Для x86 SSE инструкции pack и punpck – это то, что вам нужно. Примеры с использованием AVX для удобства неразрушающих 3-операндовых инструкций. (Не используя инструкции AVX2 256b, так как инструкции 256b pack / unpck выполняют две 128-битные распаковки на дорожках с низким и высоким 128b, поэтому вам нужно будет перетасовать, чтобы все получилось в правильном окончательном порядке.)

Следующая версия будет работать одинаково. Инструкции Asm более короткие, чтобы просто написать быстрый ответ.

Interleave : abcd и 1234 -> a1b2c3d4 :

 # loop body: vmovdqu (%rax), %xmm0 # load the sources vmovdqu (%rbx), %xmm1 vpunpcklbw %xmm0, %xmm1, %xmm2 # low halves -> 128b reg vpunpckhbw %xmm0, %xmm2, %xmm3 # high halves -> 128b reg vmovdqu %xmm2, (%rdi) # store the results vmovdqu %xmm3, 16(%rdi) # blah blah some loop structure. `punpcklbw` interleaves the bytes in the low 64 of the two source `xmm` registers. There are `..wd` (word->dword), and dword->qword versions which would be useful for 16 or 32bit elements. 

De-interleave : a1b2c3d4 -> abcd и 1234

 #outside the loop vpcmpeqb %xmm5, %xmm5 # set to all-1s vpsrlw $8, %xmm5, %xmm5 # every 16b word has low 8b = 0xFF, high 8b = 0. # loop body vmovdqu (%rsi), %xmm2 # load two src chunks vmovdqu 16(%rsi), %xmm3 vpand %xmm2, %xmm5, %xmm0 # mask to leave only the odd bytes vpand %xmm3, %xmm5, %xmm1 vpackuswb %xmm0, %xmm1, %xmm4 vmovdqu %xmm4, (%rax) # store 16B of a[] vpsrlw $8, %xmm2, %xmm6 # even bytes -> odd bytes vpsrlw $8, %xmm3, %xmm7 vpackuswb %xmm6, %xmm7, %xmm4 vmovdqu %xmm4, (%rbx) 

Разумеется, это может быть намного меньше регистраций. Я избегал повторного использования регистров для удобочитаемости, а не производительности. Переименование регистра аппаратного обеспечения делает повторное использование без проблем, если вы начинаете с чего-то, что не зависит от предыдущего значения. (например, movd , not movss или pinsrd .)

Деинтерфейс работает гораздо больше, потому что инструкции pack выполняют подписанную или неподписанную насыщенность, поэтому сначала нужно обнулить верхний 8b каждого элемента 16b.

Альтернативой было бы использование pshufb для упаковки нечетных или четных слов одного источника в регистр 64 регистра. Однако за пределами VPPERM набора команд AMD XOP нет тасования, которое может сразу выбирать байты из 2 регистров (например, любимый vperm ). Таким образом, с помощью SSE / AVX вам понадобится 2 перетасовки для каждого 128b чередующихся данных. И поскольку использование магазина-хранилища может быть узким местом, то для объединения двух 64-битных блоков a в один регистр для настройки хранилища 128b.

С AMD XOP обратное перемежение будет составлять 2x128b, 2 VPPERM и 2x128b.

  1. преждевременная оптимизация плохая

  2. ваш компилятор, вероятно, лучше оптимизирован, чем вы.

Тем не менее, есть вещи, которые вы можете сделать, чтобы помочь компилятору, потому что у вас есть семантическое знание ваших данных, которых не может быть у компилятора:

  1. читать и записывать столько байтов, сколько вы можете, до размера родного слова – операции с памятью дорогостоящие, так что манипуляции в регистрах, где это возможно

  2. разверните петли – загляните в «Устройство Даффа».

FWIW, я выпустил две версии вашего цикла копирования, одну из которых похожа на вашу, вторая – то, что большинство рассмотрит «оптимальный» (хотя и простой) код C:

 void test1(byte *p, byte *p1, byte *p2, int n) { int i, j; for (i = 0, j = 0; i < n / 2; i++, j += 2) { p1[i] = p[j]; p2[i] = p[j + 1]; } } void test2(byte *p, byte *p1, byte *p2, int n) { while (n) { *p1++ = *p++; *p2++ = *p++; n--; n--; } } , void test1(byte *p, byte *p1, byte *p2, int n) { int i, j; for (i = 0, j = 0; i < n / 2; i++, j += 2) { p1[i] = p[j]; p2[i] = p[j + 1]; } } void test2(byte *p, byte *p1, byte *p2, int n) { while (n) { *p1++ = *p++; *p2++ = *p++; n--; n--; } } , void test1(byte *p, byte *p1, byte *p2, int n) { int i, j; for (i = 0, j = 0; i < n / 2; i++, j += 2) { p1[i] = p[j]; p2[i] = p[j + 1]; } } void test2(byte *p, byte *p1, byte *p2, int n) { while (n) { *p1++ = *p++; *p2++ = *p++; n--; n--; } } 

С gcc -O3 -S на Intel x86 они оба выпустили почти идентичный ассемблерный код. Вот внутренние петли:

 LBB1_2: movb -1(%rdi), %al movb %al, (%rsi) movb (%rdi), %al movb %al, (%rdx) incq %rsi addq $2, %rdi incq %rdx decq %rcx jne LBB1_2 

а также

 LBB2_2: movb -1(%rdi), %al movb %al, (%rsi) movb (%rdi), %al movb %al, (%rdx) incq %rsi addq $2, %rdi incq %rdx addl $-2, %ecx jne LBB2_2 

Оба имеют одинаковое количество инструкций, разница учитывается исключительно потому, что первая версия подсчитывается до n / 2 , а вторая отсчитывает до нуля.

EDIT - лучшая версия:

 /* non-portable - assumes little endian */ void test3(byte *p, byte *p1, byte *p2, int n) { ushort *ps = (ushort *)p; n /= 2; while (n) { ushort n = *ps++; *p1++ = n; *p2++ = n >> 8; } } 

в результате чего:

 LBB3_2: movzwl (%rdi), %ecx movb %cl, (%rsi) movb %ch, (%rdx) # NOREX addq $2, %rdi incq %rsi incq %rdx decq %rax jne LBB3_2 

что является меньшим количеством инструкций, поскольку оно использует непосредственный доступ к %cl и %ch .