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

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

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

#if defined __ARM_NEON__
#   include <arm_neon.h>
#endif
#include <stdint.h>
#include <stddef.h>

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<mixedLength/2; ++i) {
        array1[i] = mixed[2*i];
        array2[i] = mixed[2*i + 1];
    }
}

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

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 запусков в секунду (ПРИМЕЧАНИЕ. Этот метод не является безопасным по порядку байтов, результат зависит от порядка следования байтов ЦП. В вашем случае массив1 и массив2, вероятно, поменяны местами, поскольку 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 на 16 бит и mixed на 32 бита.

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

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

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

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

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

Чередовать: 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.

Отменить чередование: 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, а не movss или pinsrd.)

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

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

С 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--;
    }
}

С 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, а вторая считает до нуля.

ИЗМЕНИТЬ вот лучшая версия:

/* 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.