Самый быстрый способ транспонирования матрицы 4x4 байт

Ответ 1

Позвольте мне переформулировать ваш вопрос: вы просите C-или С++-единственное решение, которое переносимо. Тогда:

void transpose(uint32_t const in[4], uint32_t out[4]) {
  // A B C D    A E I M
  // E F G H    B F J N
  // I J K L    C G K O
  // M N O P    D H L P

  out[0] = in[0] & 0xFF000000U; // A . . .
  out[1] = in[1] & 0x00FF0000U; // . F . .
  out[2] = in[2] & 0x0000FF00U; // . . K .
  out[3] = in[3] & 0x000000FFU; // . . . P

  out[1] |= (in[0] <<  8) & 0xFF000000U; // B F . .
  out[2] |= (in[0] << 16) & 0xFF000000U; // C . K .
  out[3] |= (in[0] << 24);               // D . . P

  out[0] |= (in[1] >>  8) & 0x00FF0000U; // A E . .
  out[2] |= (in[1] <<  8) & 0x00FF0000U; // C G K .
  out[3] |= (in[1] << 16) & 0x00FF0000U; // D H . P

  out[0] |= (in[2] >> 16) & 0x0000FF00U; // A E I .
  out[1] |= (in[2] >>  8) & 0x0000FF00U; // B F J .
  out[3] |= (in[2] <<  8) & 0x0000FF00U; // D H L P

  out[0] |= (in[3] >> 24);               // A E I M
  out[1] |= (in[3] >>  8) & 0x000000FFU; // B F J N
  out[2] |= (in[3] <<  8) & 0x000000FFU; // C G K O
}

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

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

До сих пор стоимость составляла 12 смен, 12 OR, 16 AND. Если компилятор и платформа хороши, это можно сделать в 9 32-битных регистрах.

Если компилятор очень печален, или на платформе нет переключателя ствола, то некоторые кастинга могут помочь превознести факт, что сдвиги и маски являются просто выделением байта:

void transpose(uint8_t const in[16], uint8_t out[16]) {
  // A B C D    A E I M
  // E F G H    B F J N
  // I J K L    C G K O
  // M N O P    D H L P

  out[0]  = in[0];  // A . . .
  out[1]  = in[4];  // A E . .
  out[2]  = in[8];  // A E I .
  out[3]  = in[12]; // A E I M
  out[4]  = in[1];  // B . . .
  out[5]  = in[5];  // B F . .
  out[6]  = in[9];  // B F J .
  out[7]  = in[13]; // B F J N
  out[8]  = in[2];  // C . . .
  out[9]  = in[6];  // C G . .
  out[10] = in[10]; // C G K .
  out[11] = in[14]; // C G K O
  out[12] = in[3];  // D . . .
  out[13] = in[7];  // D H . .
  out[14] = in[11]; // D H L .
  out[15] = in[15]; // D H L P
}

Если вы действительно хотите перетасовать его на месте, тогда будет выполнено следующее.

void transpose(uint8_t m[16]) {
  std::swap(m[1], m[4]);
  std::swap(m[2], m[8]);
  std::swap(m[3], m[12]);
  std::swap(m[6], m[9]);
  std::swap(m[7], m[13]);
  std::swap(m[11], m[14]);
}

Байт-ориентированные версии могут значительно улучшить код на современных платформах. Может показаться только эталон.

Ответ 2

Вы хотите повысить эффективность и эффективность. Ну, вы не можете иметь это в обоих направлениях. Вы сказали, что хотите сделать это с наименьшим количеством инструкций. Ну, это можно сделать только с одной инструкцией с SSE3, используя инструкцию pshufb (см. Ниже) из набора инструкций x86.

Возможно, ARM Neon имеет нечто эквивалентное. Если вы хотите эффективности (и уверены, что вам это нужно), изучите аппаратное обеспечение.

Эквивалент SSE для _MM_TRANSPOSE4_PS для байтов - использовать _mm_shuffle_epi8 (внутреннее для pshufb) с помощью маски. Определите маску вне основного цикла.

//use -msse3 with GCC or /arch:SSE2 with MSVC
#include <stdio.h>
#include <tmmintrin.h> //SSSE3
int main() {
    char x[] = {0,1,2,3, 4,5,6,7, 8,9,10,11, 12,13,15,16};
    __m128i mask = _mm_setr_epi8(0x0,0x04,0x08,0x0c, 0x01,0x05,0x09,0x0d, 0x02,0x06,0x0a,0x0e, 0x03,0x07,0x0b,0x0f);

    __m128i v = _mm_loadu_si128((__m128i*)x);
    v = _mm_shuffle_epi8(v,mask);
    _mm_storeu_si128((__m128i*)x,v);
    for(int i=0; i<16; i++) printf("%d ", x[i]); printf("\n");
    //output: 0 4 8 12 1 5 9 13 2 6 10 15 3 7 11 16   
}

Ответ 3

Не уверен в скорости, но все в порядке.

template<typename T, std::size_t Size>
void Transpose(T (&Data)[Size][Size])
{
    for (int I = 0; I < Size; ++I)
    {
        for (int J = 0; J < I; ++J)
        {
            std::swap(Data[I][J], Data[J][I]);
        }
    }
}

template<typename T, std::size_t Size>
void Transpose(T (&Data)[Size * Size])
{
    for (int I = 0; I < Size; ++I)
    {
        for (int J = 0; J < I; ++J)
        {
            std::swap(Data[I * Size + J], Data[J * Size + I]);
        }
    }
}

Ответ 4

Эффективное решение возможно на 64-битной машине, если вы это принимаете. Сначала смените 32-битные целые константы на (0,) 1, 2 и 3 байта соответственно [3 shitfs]. Затем маскируйте нежелательные биты и выполняйте логические ORs [12 AND с константой, 12 ORs]. Наконец, сдвиньте назад до 32 бит [3 смены] и зачитайте 32 бита.

ABCD
EFGH
IJKL
MNOP

ABCD
 EFGH
  IJKL
   MNOP

A---
 E---
  I---
   MNOP
=======
AEIMNOP
AEIM

AB--
 -F--
  -J--
   -NOP
=======
ABFJNOP
BFJN

ABC-
 --G-
  --K-
   --OP
=======
ABCGKOP
CGKO

ABCD
 ---H
  ---L
   ---P
=======
ABCDHLP
DHLP

Ответ 5

Я отправил ответ на эту же проблему некоторое время назад для SSE здесь.

Единственными вещами, которые необходимо добавить, являются векторизованные операции загрузки/хранения.

Этот ответ похож на ответ Z бозона на этот вопрос. Здесь можно увидеть примеры загрузки/хранения. Этот ответ отличается тем, что в дополнение к реализации SSE3 существует реализация SSE2, которая гарантирована для работы на любом процессоре x64.

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