Эффективный способ переупорядочения векторных данных (интерпретируется как трехмерный массив)

Question

Я работаю над приложением, написанным на C ++, которое должно обрабатывать некоторые данные, хранящиеся в непрерывном пространстве памяти, которые интерпретируются как трехмерный массив. Для эффективной обработки данных мне нужно изменить порядок данных в памяти.

Итак, вот пример: Исходные данные находятся в памяти, и у меня есть доступ к данным через указатель данных (uint16_t*), который интерпретируется как 3D-массив и имеет следующие размеры:
xSize=4, ySize=4, zSize=3
В памяти данные расположены следующим образом: (d _{x, y, z} )

д_ 0,0,0 | д_ 1,0,0 | д_ 2,0,0 | д_ 3,0,0 | д_ 0,1,0 | д_ 1,1,0 | д_ 2,1,0 | д_ 3,1,0 | .... | д_ 3,0,2 | д_ 3,1,2 | д_ 3,2,2 | д_ 3,3,2 |

Теперь я хотел бы получить данные в порядке z, y, x:

д_ 0,0,0 | д_ 0,0,1 | д_ 0,0,2 | д_ 0,1,0 | д_ 0,1,1 | д_ 0,1,2 | .... | д_ 2,3,2 | д_ 3,3,0 | д_ 3,3,1 | д_ 3,3,2 |

Я сделал реализацию со следующими циклами:

for (uint32_t z = 0; z < zSize; z++) {
    for (uint32_t y = 0; y < ySize; y++) {
        for (uint32_t x = 0; x < xSize; x++) {
            uint32_t readPos = z * xSize * ySize + y * xSize + x;
            uint32_t outPos = y * xSize * zSize + x * zSize + z;
            *(dataOutPtr + outPos) = *(dataInPtr + readPos);
        }
    }
}

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

Answer 1

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

Очевидно, что вы должны посетить каждый элемент, и ваше внутреннее тело цикла примерно настолько же эффективно, насколько это возможно.

Может быть возможно распараллелить это - кто-то другой должен будет исследовать это, как я надеваюу меня там нет знаний - но с фундаментальной точки зрения C ++ я считаю, что вы уже делаете все, что можете.По крайней мере, если вы не можете предварительно обработать или исправить исходные данные, или если вы не можете жить без переупорядочивания вообще (например, если на самом деле вас не волнует локальность кэша, и поэтому вы можете просто изменить свою схему индексации как фасад).