преобразование таблиц - оптимизация по скорости

leo

Я тут поменял материнку и слегка разогнал процессор, так что результаты чуть ушли. Но важно соотношение а не общий показатель.

Моя/твоя соотносятся как 938/1109



Вот такие пироги ...

 

Соотношение конечно важно, но не очень конструктивно

Интересно бы в тактах оценить - хотя бы пересчитать из мсек-ов через частоту проца и число повторов. Но лучше конечно определять через RDTSC (поищи по форуму тестовую прогу wintest или спроси у bogrus'а), ну а еще лучше посмотреть на симуляцию пайпа CodeAnalyst'ом



PS: У меня атлона под рукой нет, поэтому сам проверить не могу. Мануалы мануалами, но хотелось-бы понять, чего этому зверю по жизни нравится, а что нет

 

Что конкретно сделать CodeAnalyst'ом? Он у меня есть, только правильно пользоваться им я пока не научился. Да и Athlon у меня живет меньше месяца. RDTSC от раза к разу дает разный результат, даже при задирании приоритета под самый упор. Усреднить?

 

Насчет CodeAnalyst'а ничего сказать не могу. Может S_T_A_S_ откликнется, как главный симулятор ))



Что касается RDTSC, то разные результаты могут получаться по несколькии причинам

1) результаты первого (иногда и второго) прохода всегда получаются завышенными, из-за того что код и данные еще не загружены в кэш и не настроено предсказание переходов (при наличии ветвлений)

2) в разных проходах используются разные данные - возможна подгрузка данных в кэш, зависимость латентности некоторых операций от операндов, изменение направления ветвлений

3) вклинивание винды, если время выполнения теста превышает квант времени потока

4) влияние параллельного потока в (квази)двухпроцессорных системах, особенно с убогим Hyper-Threading'ом P4



Поэтому в отличие от измерений по GetTickCount, с RDTSC нужно поступать совершенно по другому - не крутить циклы с огромным числом повторений, а наоборот стремиться уложиться в квант 10 мс, и ес-но ничего не усреднять, а выводить серию результатов по 6-10 проходам. Если не используется H-T, нет виндовых прерываний и измерения проводятся на одних и тех же данных (данные в кэше и переходы ведут себя одинаково), то обычно первые два результата получаются завышенными, а остальные идут (практически) тик в тик - это и есть искомый результат.



Есть некоторые особенности:

1) в P4 и атлонах во избежание огромных пенальти нельзя писать данные в секцию кода.

2) в P4 дискретность RDTSC составляет 4 тика, а в P4E все 8, поэтому точнее 4(8) тиков можно оценивать только результаты тестирования циклов (в пересчете на цикл)

3) если для сериализации RDTSC используется CPUID, то при наличии в тестовом куске записи в память возникает дополнительная задержка на выталкивание буферов записи в кэш, которая обычно выполняется в фоне. В этом сл. более точные рез-ты на пеньках дает замена CPUID на CLD (на атлонах неизвестно)

4) ну и с H-T в P4 одна морока, результаты могут различаться в десятки раз.

 

Я и незнаю, wintest вообще нормально работает на x64?

Там цветные картинки S_T_A_S_ когда-то вылаживал, на них видно в каких юнитах и сколько тактов выполняется каждая команда

 

leo

Каюсь, посыпаю голову пеплом...



Я же тестовый проект в MSVS делал, а у него хватило интеллекта сохранять/восстанавливать изменяемые регистры ESI, EDI на стеке. Это здорово подкашивало твой вариант. Обнаружил, разглядывая код в CodeAnalyst. Поправил, почувствовал разницу.

Вот результат по RDTSC.

prc0 ticks: 178 17 17 21 21 17 17 17 17 17 - твоя

prc2 ticks: 179 24 24 24 26 24 24 24 24 24 - моя



Иногда в первой итерации получается еще медленнее



-- Но вот в конечном проекте итог получается медленнее.



вызовы располагаются примерно так:

Код (Text):

1.  
2.         movq    SBIn,   mm0
3.        
4.         [b]call _dotablexlat[/b]
5.        
6.         movq    mm7, SBOut
7.  
8.         movq    mm0, BC1Out6
9.         pxor    mm0, mm7
10.         movq    BC1Out6, mm0
11.        
12.         movq    mm1, mm2
13.         pxor    mm1, mm0
14.         movq    BC1Out2, mm1
15.  
16.         movq    mm2, mm3
17.         pxor    mm2, mm0
18.  
19.         movq    mm3, BC1Out0
20.         pxor    mm3, mm0
21.                
22.         call    _do???????
23.        
24.         movq    mm1, BC1Out4
25.         pxor    mm1, mm7
26.         movq    BC1Out4, mm1
27.  
28.         movq    mm0, KB+53*8
29.         pxor    mm0, mm1   
30.         movq    SBIn,   mm0
31.  
32.         [b]call _dotablexlat[/b]
33.  
34.        
35.  

 

bogrus

> "wintest вообще нормально работает на x64?"Речь идет о x86 legacy mode, поэтому должно быть нормально



andy_biiig

17 тиков это гуд, значит мануалы AMD в первом приближении рулят и в простых случаях можно обойтись и без CodeAnalyst'а



Но вот смотрю я на твой MMX-код и думается мне, что если бы не большое число задействованных регистров, то на 32-битных было бы быстрее. Во-первых, после call _dotablexlat сразу идет загрузка результата в mm7 - типичный store-to-load forwarding stall. Сохраняли по частям, а грузим целиком 64 бита, форвардинг отдыхает, проц. неизвестно сколько ждет отставки последней записи и попадания данных в кэш (мануалы говорят о up to tens clock cycles). Тут по кр.мере нужно загрузку mm0 поставить раньше mm7. Да и латентности mmx-операций вдвое больше 32-битных..

 

andy_biiig



Лучше _dotablexlat сделать макросом, а не подпрограммой, что бы код инлайнился. На вызов+возврат тратится время.



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



Делайте в Аналисте симуляцию пайпа, смотрите как зелёные (светлые и тёмные) квадратики расположены - это ваполниние (впрочем, там тултипы всплывают, если навести мышкой, и зависимости пишет). Если есть красные - то совсем ахтунг, нужно что-то менять.



Попробовал помучить код leo (и даже показалось, что улучшил его на такт =))... Похоже теория как всегда что-то упрощает.

На картинке код нерабочий, просто что бы показать, что некоторых команд бояться не стоит: если 3ю (movzx) поменять на mov - ничего не меняется. А вот замена вроде movzx edi, dh вроде как даёт выигрыш =)



У кода проблема - слишком высока плотность, а команды многие зависимы. Если бы их как то разбавить вот тем mmx что в реальном сорце - имхо самую большую выгоду можно получить будет.



1018780220__xlat.PNG

 

leo

Регистров MMX используется не просто много, они используются все . В той процедурке, которую я вопросиками пометил, заюзаны остальные.



Весь фокус в том, что операции в алгоритме производятся с байтовыми величинами, и для скорости обрабатывается 8 наборов одновременно, "на всю ширину MMX"



Только табличное преобразование, которое мы тут мучаем, и не удалось переписать на MMX

S_T_A_S_



Это преобразование используется в процедурке с развернутым циклом, вызывается 56 раз. Процедурка уже около 1700 строк, но разворачивание цикла имело плюсы по алгоритму - избавился от циклического сдвига данных в массиве.



Будут ли минусы, если я туда еще наинлайню?



CodeAnalyst вываливается на попытке симуляции. На простом примере ничего, а на реальной программе - кирдык. Мож ему треды не нравятся? Там все вычисления в отдельном треде.

 

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



К тому же, вот такие участки можно будет переписать под обычные регистры:

Код (Text):

1. movqmm7, SBOut
2. movqmm0, BC1Out6
3. pxormm0, mm7
4. movqBC1Out6, mm0

По поводу трэдов - хз, всегда симулировал только однотрэдовые приложения. Скорее всего они мешают, т.к. трэды выполняются в разных контекстах.

 

S_T_A_S_

> "замена вроде movzx edi,dh вроде как даёт выигрыш =)"

Странно как-то - на твоей картинке movzx edi,dh выполняется на такт раньше, чем mov edx,[..]

Даже если рулит некий data forwarding, то они в лучшем случае должны выполнится одновременно - в чем я сильно сомневаюсь, т.к. аналогичная mov ecx,al как и положено ждет загрузки mov eax,[..]

ИМХО видимо это глюк CodeAnalyst'а

 

S_T_A_S_



movq mm7, SBOut

movq mm0, BC1Out6

pxor mm0, mm7

movq BC1Out6, mm0



Этот код нельзя заменить на обычные регистры. Все разряды MMX используются

 

andy_biiig

Как я уже говорил, неприятный момент во всем этом деле это ограничение на store-to-load forwarding (SLF). Все мануалы и AMD, и Intel говорят о том, что если адрес и\или размер загружаемых данных, которые были "только что" сохранены не совпадают, то возможна "значительная" задержка загрузки данных. Не знаю насколько большой штраф получается в данном случае, но его можно избежать, если _dotablexlat будет просто выдывать результат в регистрах (eax,edx). Тогда дальше можно поступить так

Код (Text):

1.   xor [BS1Out6],eax    ;xxxx - 4 тика (перенесли сюда из _dotablexlat)
2.   xor [BS1Out6+4],edx  ;хххх
3.   ;mov [SBOut],eax     ;.ххх - если нужно
4.   ;mov [SBOut+4],edx   ;.xxx
5.   movd mm0,[BS1Out6]   ;....xxxx - 4 тика без штрафа - данные берутся из буфера записи
6.   movd mm1,[BS1Out6+4] ;....xxxx
7.   ;movq mm7,[SBOut]    ;тут можно и со штрафом
8.   punpackldq mm0,mm1   ;........xx - получили mm0

(Кстати перенос части 32-бит кода из _dotablexlat полезен еще тем, что MMX-конвеер на несколько тактов длиннее целочисленного, поэтому после перехода по ret первому MMX-мопу нужно больше времени, чтобы добраться до исп.устройства)

Аналогичная, но немного отличающаяся ситуация и при втором вызове _dotablexlat. Тут сохраняется SBOut и затем грузятся два дворда, причем в AMD64 младший дворд грузится без штрафа, а старший со штрафом из-за ограничения на SLF (видимо поэтому мой вариант преобразования и оказывается хуже, т.к. он в первую очередь обрабатывает старший дворд). Поэтому эту часть лучше тоже изменить (тут вопрос - что сидит в mm7 и есть ли его копия в памяти)



PS: Насчет скорости MMX и GPR: не знаю, что делает _do????, но замена MMX-кода от call _dotablexlat до call _d??? на GPR с загрузкой и сохранием 32-битных операндов в память дает ту же скорость, что и ММХ (правда размер кода существенно увеличивается). Вот если бы можно было ксорить данные в памяти без переписывания на другое место, то возможно на GPR было бы побыстрее

 

leo

Этак мы по всему коду пройдемся



После загрузки в mm7 значение SBOut более не нужно, а вот в mm7 оно нужно на вход _do????. В принципе, mm4-mm6 свободны (используются как временные в _do????), так что можно оперировать ими, вообще не записывая в SBOut, и даже в SBIn можно не писать. Я еще не обдумал это, т.к. в предыдущей реализации свободных регистров небыло. Теперь есть



_do???? это перемешивание битов, т.е. каждому входному биту соответствует выходной, но с другим номером.



Вход mm7, выход mm7, преобразование фиксированное.

Код (Text):

1.  
2. ;
3. ;       movq    mm7, SBOut 
4.  
5. ; variant 1
6.  
7.         movq    mm6, mm7   
8.         movq    mm5, mm7   
9.         movq    mm4, mm7   
10.  
11.         pand    mm6, Mask292929h
12.         pand    mm5, Mask404040h
13.         pand    mm4, Mask101010h
14.  
15.         psllq   mm6, 1     
16.         psrlq   mm5, 6     
17.         psrlq   mm4, 2     
18.  
19.         paddb   mm4, mm6
20.         paddb   mm4, mm5
21.  
22.         movq    mm6, mm7   
23.         movq    mm5, mm7   
24.  
25.         pand    mm7, Mask020202h
26.         pand    mm6, Mask040404h
27.         pand    mm5, Mask808080h
28.  
29.         psllq   mm7, 6     
30.         psllq   mm6, 3     
31.         psrlq   mm5, 4     
32.  
33.         paddb   mm4, mm6
34.         paddb   mm7, mm5   
35.         paddb   mm7, mm4   
36.  
37.         retn
38.  

 

Вопрос: нужно ли каждый раз специально перемешивать биты в _do????

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



Иначе не знаю, вроде бы на GPR _do???? получается по скорости примерно также или чуть быстрее, но зато объем кода существенно увеличивается. Поэтому из плюсов только устранение проблемы со store-forwarding'ом (если она вообще проявляется и возможная экономия нескольких тактов за счет перекрытия с предыдущим MMX-кодом при спекулятивном исполнении call

 

leo

Sorry, неверно выразился. SBout, полученный по таблице, используется и напрямую, как вход для перемешивания.



Вот реализация этого куска на паскале (я так понимаю, для настоящего гуру язык не важен? ))

Обрабатываемый блок в R[0..7]. Этот алгоритм байт-ориентированный. Асмовый вариант обрабатывает параллельно 8 блоков.

Код (Text):

1.  
2.     for i:=55 downto 0 do
3.     begin
4.       SBin:=kb[i] xor R[6];
5.  
6.       r8buf:=tXlat[SBin] xor R[7];
7. //            ^ с этого преобразования началась наша тема
8.  
9.       R[7]:=R[6];
10.       R[6]:=R[5] xor BitPermute[SBin]; // это _do????, представленная таблицей 256 байт
11.       R[5]:=R[4];
12.       R[4]:=R[3] xor r8buf;
13.       R[3]:=R[2] xor r8buf;
14.       R[2]:=R[1] xor r8buf;
15.       R[1]:=R[0];
16.       R[0]:=r8buf;
17.     end;
18.  

 

В принципе да, можно сделать в таблице tXlat в нижнем байте нормальное значение, в верхнем - перемешанное. Тогда минус перемешивание, но плюс "разрывание" выбранного из таблицы результата по ah,al или масками



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

 

leo

Заменил в твоем варианте

Код (Text):

1.  
2.   mov edx,[SBIn]
3.   mov eax,[SBIn+4]
4.  

на

Код (Text):

1.  
2.   movd edx, mm0
3.   punpckhdq mm0,mm0
4.   movd eax, mm0
5.  

и убрал сохранение SBIn перед вызовами процедуры. Твой вариант стал быстрее моего в итоговом проекте. Видимо, поборол SLF. но время выросло с 17 до 21 тика. Будем думать дальше...

 

Из приведенного тобой куска не очень понятно каким образом параллельно 8 блоков обрабатываются...



Что касается исходного побайтного алгоритма, то его можно попробовать реализовать так:

Код (Text):

1. XTab: db tXlat_0, 0, BitPermute_0, 0  ;совмещенная таблица
2.       db tXlat_1, 0, BitPermute_1, 0      
3.       ...
4. movzx edi,byte [kb+55]
5. mov eax,[R+4]
6. mov edx,[R]              ;-> R[0],R[1],R[2],R[3]
7. bswap eax                ;-> R[7],R[6],R[5],R[4]
8. mov esi,56
9. movzx ecx,ah             ;-> R[6]
10. xor ecx,edi              ;-> SBIn = R[6] xor kb[i]
11. align 16
12. @@:
13.   xor eax,[XTab+ecx*4]   ;-> R[7] xor tXlat, R[6], R[5] xor BitPermute,R[4]
14.   mov ebx,edx
15.   shl edx,8              ;-> 0,R[0],R[1],R[2]
16.   and ebx,0FF000000h     ;-> 0,0,0,R[3]
17.   movzx edi,byte[kb+esi-2] ;предвыборка для след.цикла
18.   movzx ecx,al           ;r8buf = R[7] xor tXlat
19.   imul ecx,01010001h     ;-> r8buf,0,r8buf,r8buf
20.   ror eax,8              ;-> R[6],R[5] xor BitPermute,R[4],r8buf
21.   xor edx,ecx            ;-> r8buf,R[0],R[1] xor R8buf,R[2] xor r8buf
22.   nop                    ;для устр.конфликта с imul
23.   movzx ecx,ah           ;-> R[6] для след.цикла
24.   xor eax,ebx            ;-> R[6],R[5] xor BitPermute,R[4],R[3] xor r8buf
25.   xor ecx,edi            ;-> SBIn = R[6] xor kb[i] для след цикла
26.   dec esi
27.   jnz @B
28. bswap eax

С учетом перекрытия циклов на AMD64 вроде как должно быть ~7 тиков на оборот или ~400 тиков на полную обработку 8 байт (~1мкс на частоте ~2.5ГГц)

PS: в таком варианте предвыборка kb[i-1] читает один лишний байт, поэтому kb не должно стоять в начале секции

 

leo

8 блоков обрабатывается примерно так



Rnew[0] = r1[0] | (r2[0] <<8) | (r3[0] <<16) ...

...

Rnew[7] = r1[7] | (r2[7] <<8) | (r3[7] <<16) ...



Где r1, r2 и т.д. это оригинальные байтовые блоки, а Rnew - 64 разрядный "суперблок", который потом и обрабатывается





Поэтому и по таблице транслируются 8 байт из всех разрядов mmx, и в асмовых процедурах операции производятся целиком над mmx.



----------

После разворачивания приведенного цикла и упрощения алогритм стал выглядеть примерно вот так

Код (Text):

1.  
2. // 1
3.         sbin = kb[55] ^ ib[6];
4.         r[7] ^= tXlat[sbin];
5.         r[5] ^= BitPermute[sbin];
6.         r[3] ^= r[7]; r[2] ^= r[7]; r[1] ^= r[7];
7. // 2
8.         sbin = kb[54] ^ ib[5];
9.         r[6] ^= tXlat[sbin];
10.         r[4] ^= BitPermute[sbin];
11.         r[2] ^= r[6]; r[1] ^= r[6]; r[0] ^= r[6];
12. // 3
13.         sbin = kb[53] ^ ib[4];
14.         r[5] ^= tXlat[sbin];
15.         r[3] ^= BitPermute[sbin];
16.         r[1] ^= r[5]; r[0] ^= r[5]; r[7] ^= r[5];
17.  
18. // всего 56 раз
19.  
20.  

Именно этот код и послужил прообразом для ASM-варианта

Код (Text):

1.  
2. ;// 2
3.  
4.       sbin = kb[54] ^ ib[5];
5.  
6.                 ; слегка пропущено
7.  
8.       r[6] ^= tXlat[sbin];
9.  
10.         movq    SBIn,   mm0
11.        
12.         call    _dotablexlat
13.        
14.         movq    mm7, SBOut
15.  
16.         movq    mm0, BC1Out6
17.         pxor    mm0, mm7
18.         movq    BC1Out6, mm0
19.  
20.       r[2] ^= r[6];
21.        
22.         movq    mm1, mm2 - с предыдущей итерации
23.         pxor    mm1, mm0
24.         movq    BC1Out2, mm1 - сохраняется
25.  
26.       r[1] ^= r[6];
27.  
28.         movq    mm2, mm3 - с предыдущей итерации
29.         pxor    mm2, mm0
30.                                     - остается в регистре mm2 до следующей итерации
31.  
32.       r[0] ^= r[6];
33.  
34.         movq    mm3, BC1Out0
35.         pxor    mm3, mm0
36.                                     - остается в регистре mm3 до следующей итерации
37.                
38.  
39.       r[4] ^= BitPermute[sbin];
40.  
41.         call    _do???????
42.        
43.         movq    mm1, BC1Out4
44.         pxor    mm1, mm7
45.         movq    BC1Out4, mm1
46.  
47. --- А это уже следующая итерация
48. // 3
49.         sbin = kb[53] ^ ib[4];
50.  
51.         movq    mm0, KB+53*8
52.         pxor    mm0, mm1   
53.         movq    SBIn,   mm0
54.  
55.         call    _dotablexlat
56.