Есть битовый массив из N строк. В каждой строке по N бит. Длина строки (N+7)/8 байт или (N+31)/32 двойных слов (кому как больше нравится). Можно в конец массива даже добавить несколько строк добавить чтобы и их количество было кратно 8 или 32. Требуется транспонировать этот массив. То есть бит номер X из строки номер Y меняется с битом номер Y из строки номер X. У кого нибудь есть соображения как это сделать наиболее быстрым способом? При необходимости можно использовать дополнительный массив. Swap(array[ecx].bt[edx],array[edx].bt[ecx]) не годится.

Black_mirror
ОК, я взял домой :)

Я думаю можно так попробовать...

для восьмибитового массива:
на входе:
esi - адрес входного массива
edi - адрес выходного массива

входной массив меняет свои значения - не уцелевает

xor ebx,ebx ;счетчик строк
loop1:
mov ecx,7 ;счетчик столбцов
loop2:
rcr byte ptr [esi+ebx],1
rcl byte ptr [edi+ecx],1
dec ecx
jns loop2
inc ebx
cmp ebx,8
jne loop1

PS: не проверял работоспособность, только на бумажке :))

Johnikum
Проблемма не в том какие комманды мы будем использовать, а в том что прочитав байт из исходного массива, мы должны записать по одному биту в 8 строк выходного массива. Массив очень большой. Сможет ли кеш кешировать сразу 8 или 9 областей? Если на каждый прочитанный или записанный бит будет заполнятся строка кеша - будет нехорошо. У меня когда я читал всего из 3х областей взависимости от того какое между ними было расстояние производительность менялась в 2-3 раза.

Black_mirror
сразу 8 или 9 областей
каких именно областей массива - я не совсем понял

Johnikum
Я имел ввиду области памяти из которых производится чтение или в которые поизводится запись. Количество бит в строке несколько тысяч, поэтому о одной строке кеща не могут содержатся данные из двух или более областей. Вполне может получится так что при записи бита в одну строку массива из кеша будет выгружатся другая. И когда очередь дойдет до нее то придется считывать заного. И так будет происходить на каждой итерации!

Можно разбить решение всей задачи на три этапа:
1. Поменять (транспонировать) блоки битового массива, попутно упорядочить последовательно каждый блок в памяти.
2. Транспонировать биты каждого блока.
3. Упорядочить блоки. (перевести из последовательной структуры в "смешанную").

Теперь подробнее. Есть массив N*N битов.
Пусть, для простоты счета, N=1024. Тогда строк будет 1024, а байтов в строке 128 (=1024/8). Всего 128 кило. Пусть размер кеша будет 8 кило (=8192 байта). Тогда максимальный размер блока, который может поместиться в кеш, 256*256 бит (256*32 байт).
Теперь чисто условно разбиваем массив на блоки размера 256*32 - смотри рисунок 1.

Этап первый.
Транспонируем блоки массива (рис. 2) и одновременно упорядочиваем блоки в памяти (рис. 3).

Этап второй.
Транспонируем биты каждого блока. Я так думаю тут лучше всего делать простой SWAP, как в постановке задачи - ведь весь блок лежит в кеше.

Этап третий.
Упорядочиваем блоки. рис. 3 -> рис. 2

PS: для маленького массива этот алгоритм, я думаю, не подойдет - слишком много перетасовок в памяти, а для большого ...
PPS: кода пока нет
PPPS: рисунки в аттаче


600153459__pics.tif

Johnikum
Как красиво получается: весь кеш используется! Спасибо за идею. Код не нужен.
А я пытался сделать маленькие блоки ...

Johnikum
Замечательно: БЛОКИ так и только ТАК.
Но. Вот насчёт кеша.

Этап первый.
Транспонируем блоки массива (рис. 2) и одновременно упорядочиваем блоки в памяти (рис. 3).

Транспонирование блоков, если я верно понял это траспанирование бит в них?

Или нет? Если нет.
Что такое тогда упорядочивание?

======================================================

То есть я беру первый блок и начинаю перемещать в нём биты. При этом я точно знаю, что блок полностью попал в кеш.
Так ли это?

То есть, когда я считываю две области в 32 байта, стоящие рядом, не вытесняет ли вторая область первую?

Если нет, тогда вроде бы весь блок оказывается в кеше - цель достигнута. И при этом массив должен быть выровнен на границу 4k.

Кстати хороший пример, для того, чтобы проверить истину.

Edmond
Транспонирование блоков, если я верно понял это траспанирование бит в них?

Транспонирование блоков - это обмен местами битовых блоков, но не самих битов в этих блоках, иначе мы потеряем скорость.

Что такое тогда упорядочивание?
до упорядочивания блоки лежат примерно так:
(кусок блока = КБ)
КБ1 : КБ2 : КБ3 : КБ4 ... : КБ1 : КБ2 : КБ3 : КБ4 ... и т.д.
Упорядочивание - размещение в памяти, после него блоки(Б) лежат так:
Б1 : Б2 : Б3 : Б4 ...