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

Исходные данные:



1. Есть DIn размером 8 байт либо в памяти либо в регистре MMX, на выбор.

2. Есть таблица tXlat 256 элементов размером 1 байт, система не прослеживается. Может быть преобразована в любой нужный вид, размер элементов может быть расширен.

3. Есть DOut размером 8 байт либо в памяти, либо в регистре MMX. Может совпадать с DIn, если это надо для скорости



Требуется:

Преобразовать каждый байт из DIn по таблице tXlat в байт результата DOut (в том же порядке), т.е.



DIn.0 -> tXlat -> DOut.0

DIn.1 -> tXlat -> DOut.1

...

DIn.7 -> tXlat -> DOut.7



Вот мой собственный вариант, быстрее не получается:

tXlat расширена до dword, все данные выровнены по align 8

Код (Text):

1.  
2. _doXlat proc near
3.     mov edx, dword ptr SBIn
4.     lea ebx, DOut
5.     lea eax, tXlat
6.  
7.     mov ecx, edx
8.     and ecx, 0FFh
9.     mov ecx, [eax+ecx*4]
10.     mov [ebx], cl
11.        
12.     mov ecx, edx
13.     and ecx, 0FF00h
14.     shr ecx, 8
15.     mov ecx, [eax+ecx*4]
16.     mov [ebx+1], cl
17.        
18.     mov ecx, edx
19.     and ecx, 0FF0000h
20.     shr ecx, 10h
21.     mov ecx, [eax+ecx*4]
22.     mov [ebx+2], cl
23.        
24.     mov ecx, edx
25. ;   and ecx, 0FF000000h
26.     shr ecx, 18h
27.     mov ecx, [eax+ecx*4]
28.     mov [ebx+3], cl
29.        
30.     mov edx, dword ptr DIn+4
31.        
32.     mov ecx, edx
33.     and ecx, 0FFh
34.     mov ecx, [eax+ecx*4]
35.     mov [ebx+4], cl
36.        
37.     mov ecx, edx
38.     and ecx, 0FF00h
39.     shr ecx, 8
40.     mov ecx, [eax+ecx*4]
41.     mov [ebx+5], cl
42.        
43.     mov ecx, edx
44.     and ecx, 0FF0000h
45.     shr ecx, 10h
46.     mov ecx, [eax+ecx*4]
47.     mov [ebx+6], cl
48.        
49.     mov ecx, edx
50. ;   and ecx, 0FF000000h
51.     shr ecx, 18h
52.     mov ecx, [eax+ecx*4]
53.     mov [ebx+7], cl
54.  
55.     retn
56. _doXlat endp
57.  

Если подскажете, как сделать быстрее, буду весьма рад.

 

1. Почему не попробовать работать с таблицей tXlat как с таблицей байтов? Я много раз сталкивался при изучении программ с тем, что авторы не заморачиваются на выравнивание на кратные 4 или 8 байтам элементов таблиц. Поэтому вместо

mov ecx, [eax+ecx*4]

у тебя будет

mov cl, [eax+ecx]



2. Сохранение оттранслированных байтов можно сделать так:

lea edi, DOut

lea ebx, tXlat

...

mov al, [ebx+ecx]

stosb

 

А насколько тврой код быстрее (или медленнее) того, что выдает обычный сишный компилятор?

--

typedef unsigned char UCHAR;

extern const UCHAR Table[256];



void Decode( UCHAR *DOut, const UCHAR *DIn )

{

int i;

for(i = 0; i < 8; ++i)

{

DOut = Table[ DIn ];

}

}

--

_Decode PROC NEAR

; parameter 1: 4 + esp

; parameter 2: 8 + esp

mov edx, DWORD PTR [esp+4]

mov eax, DWORD PTR [esp+8]

movzx ecx, BYTE PTR [eax]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx], cl

movzx ecx, BYTE PTR [eax+1]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx+1], cl

movzx ecx, BYTE PTR [eax+2]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx+2], cl

movzx ecx, BYTE PTR [eax+3]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx+3], cl

movzx ecx, BYTE PTR [eax+4]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx+4], cl

movzx ecx, BYTE PTR [eax+5]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx+5], cl

movzx ecx, BYTE PTR [eax+6]

mov cl, BYTE PTR _Table[ecx]

mov BYTE PTR [edx+6], cl

movzx eax, BYTE PTR [eax+7]

mov al, BYTE PTR _Table[eax]

mov BYTE PTR [edx+7], al

ret

_Decode ENDP

 

psw1

Точной статистики по этой конкретной процедуре у меня нет, но производительность алгоритма в целом существенно падает.

 

crypto

Возникает такое ощущение, что байтовые комады "эмулируются" работой с целыми 32битными регистрами и маскировкой. Во всяком случае, даже чтение 32бит, выровненых по границе, происходит быстрее, чем чтение одного байта и расширение его до 32бит (movzx)

 

andy_biiig



Непонятно. При выполнении твоего и компиляторового кода в цикле (100 млн) разность значений rdtsc на цикл составляет (у меня) ~29 для твоего кода и ~26-27 для кода компилятора С, причем без разницы, байтовая ли таблица перекодировки или из двойных слов.

 

Debug build ?



Если не жалко памяти, можно попробовать таблицы по 2 байта, т.е. объединить In[0]+I[1],...:



lea esi,offset ExtTable

lea edi,offset Out

movzx eax,word ptr In+2

movzx ebx,word ptr In+6

mov cx,[esi+eax]

mov dx,[esi+ebx]

movzx eax,word ptr In+0

movzx ebx,word ptr In+4

shl ecx,16

shl edx,16

mov cx,[esi+eax]

mov dx,[esi+ebx]

mov [edi],ecx

mov [edi+4],edx



Ну или как-то так...

 

psw1

у меня больной алгоритм, практически весь на MMX, исходник на асме уже около 120 килобайт



Ветвлений там нет совсем, даже циклы развернуты. Искомая процедура вызывается 56 раз за один проход алгоритма.



С моим вариантом отрабатывает ~90000 проходов в секунду, с твоим ~85000. Не могу быстро пересчитать разницу на один вызов процедурки, но уменьшение скорости заметное.



А, да, у меня Athlon 64. Мож в этом дело? Мож на интеле другие тайминги получаются?



З.ы. Кстати, у меня там 40 команд, а у тебя 26. Разница почти вдвое. А по тикам разница даже в твоем расчете небольшая, хотя и не в мою пользу.

А данные ты, как это по русски, __declspec(align(8))? А то во всех руководствах по оптимизации пишут что-то вроде "выравнивать в памяти кратно размеру, влияет на скорость доступа"

 

Я, конечно, дилетант, но первое, что бросается в глаза - работа с одним регистром, частая работа с памятью. Вот вариант (in в edi/esi, out в ebx/ecx, epb указывает на txlat, txlat - как у тебя, dword[256]):

Код (Text):

1. xor ebx, ebx
2. xor ecx, ecx
3.  
4. mov eax, edi
5. mov edx, esi
6. and eax, 0FFh
7. and edx, 0FFh
8. mov ebx, [ebp+eax*4]
9. mov ecx, [ebp+edx*4]
10.  
11. mov eax, edi
12. mov edx, esi
13. shr eax, 8
14. shr edx, 8
15. and eax, 0FFh
16. and edx, 0FFh
17. mov eax, [ebp+eax*4]
18. mov edx, [ebp+edx*4]
19. shl eax, 8
20. shl edx, 8
21. or  ebx. eax
22. or  ecx, edx

...

и т.д.

Есть смысл попробовать объединить это с идеей Чингачгука. Хотя, без сомнений, нужно искать решение для x86_64, а ещё лучше - для Athlon64, если это первичная целевая платформа.

 

Можно преобразовать таблицу так, чтобы в ней заранее хранились "сдвинутые" значения и избавиться от пары сдвигов. Или я что-то не так понимаю?

 

ash

Время на выполнение твоего варианта соотносится со временем моего примерно 4:3. Хочу отметить, что сдвигать налево и ORить я пробовал, чтобы в память потом писать сразу 32. Оказалось, что просто записать байт в [ebx+n] это быстрее, чем его шифтить. Другое дело что да, задействую больше регистров для "развязки" и попытаюсь перемешать получение первого и второго двордов для их красивой раскладки на V-pipe и U-pipe



serious

Таблицу, если надо, можно преобразовать как угодно.

Вплоть до того , что вместо 0x00000012 использовать 0x12121212 (к примеру) и лишние байтики маскировать. Правда, пока это не помогло.

 

Можно обычной пересылкой

Код (Text):

1.             movzx   eax,byte[DIn]
2.             movzx   eax,byte[tXlat+eax]
3.             mov     byte[DOut],al
4.             movzx   eax,byte[DIn+1]
5.             movzx   eax,byte[tXlat+eax]
6.             mov     byte[DOut+1],al
7.             ...
8.             movzx   eax,byte[DIn+7]
9.             movzx   eax,byte[tXlat+eax]
10.             mov     byte[DOut+7],al

это ~16 тактов на PIII и быстрее не получится т.к. 16 чтений необходимо, только уменьшать их кол-во, т.е. пробовать как сказал Chingachguk и лучше делать запись такой же размерностю как и чтение (word\word), правда насколько это важно для атлона я не знаю

 

bogrus

Вставил в проект, попробовал. Стало медленнее. Все-же читать сразу 32 бита в регистр и сдвигать его оказалось быстрее, чем читать эти байты последовательно. По крайней мере на моем Athlon 64.



насчет идеи Chingachguk: Сейчас таблица, расширенная до 32бит, занимает 1 килобайт и в кэше оказывается без вопросов. При сдваивании таблицы она займет 256 килобайт. Боюсь, появятся пенальти на кэше.



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



P.S. Блин, ну что бы интелу было не сделать в MMX какой-нить "pxltb mm0, xTable" пакетную трансляцию

 

Угу ... а потом вставишь\изменишь ещё что-то в проекте и станет быстрее Лучше делать не так, а сперва очистить процедуру от всего лишнего, выровнять её данные, подготовить разные варианты и измерять на всех целевых процессорах добиваясь минимального кол-ва тактов каждого варианта, потом полученные такты делить на частоту камней и переводить во время (т.к. 10 тактов на PIII c частотой 600Мгц выполняются в несколько раз медленнее, чем 10 на PIV с 2400Мгц), затем выбрать средний вариант в соотв. с пропрорцией целевых камней %)



На PIII твой вариант по тактам тормознее почти в два раза, а по времени я уже не говорю

 

bogrus

Тут я с тобой согласен. Правда, с некоторыми оговорками. Во первых, основной таргет - АМД. Во вторых, доиа то у меня все равно другого нет. В третьих, все варианты я пробовал как отдельно (тестилка только с этой процедурой), так и в составе всего алгоритма. Что касается именно твоего варианта, так он у меня в "отдельном" тесте на 100 млн итераций показал 1250-1300 мсек, тогда как мой 960 - 980. К чему бы это?

--- со скоростями не совсем точно, я кое-что упустил. На самом деле разница еще больше

 

andy_biiig

Хитрые эти AMD

Вот например, в твоем исходном варианте есть ненужная зависимость по данным and ecx + shr ecx

Теоретически лучше ее убрать и сдвигать данные в исходном регистре edx

Код (Text):

1.   mov ecx,edx
2.   shr edx,8
3.   and ecx,0FFh

Но на AMD с его 3xALU +3xAGU это может ничего не дать, а в К7 можно даже проиграть, т.к. в нем номер ALU\AGU однозначно определяется порядком операции в 3-йке декодирования. Поэтому может быть зависимость от выравнивания кода и порядка следования and и shr (м.б. лучше чередовать and+shr и shr+and - надо смотреть CodeAnalyst'ом).



Другая "фича" K7 это упорядоченные запросы на чтение данных из L1 (в AMD64 не поймешь - с одной стороны говорят о переупорядочивании, а с другой стороны таже проблема AGI, что и в К7). Наверное поэтому обычная пересылка по Bogrus'у на атлоне получается хуже, если загрузка следующих байтов DIn вынуждена ждать чтения tXlat и сохранения в DOut. Если дело в этом, то можно попробовать сгруппировать операции: сначала загрузка нескольких байт DIn в разные регистры, затем загрузка tXLat, потом выгрузка. Кстати, в отличие от пеньков атлоны могут вычислять параллельно до 3 адресов и выдавать в LSU по два запроса чтения\записи за такт (в пеньках по одному, но зато неупорядоченно без всяких AGI).



Ну и "суперфича" AMD64 в том, что он 32\64 битные операнды памяти грузит на 1 такт быстрее, чем 8-битные (и mov r8,mem8 и movzx r32,mem8). Вот только не знаю, стоит ли из-за этого увеличивать размер таблицы в 4 раза. Ведь чтобы таблица попала в кэш, ее туда нужно загрузить из ОЗУ, а 1Кб на атлонах это на 12 линеек больше, чем 256 байт. Соответственно 12 доп.циклов обмена с ОЗУ по сотне-другой тиков - не хило получается. Для грубой прикидки можно взять потери до 8 тиков на movzx и 12*200=2400 на загрузку таблицы из ОЗУ, тогда игра стоит свеч только при числе проходов не менее 2400/8 = 300.

Уж про таблицы в 64K или 256К c адресацией вордами и говорить нечего



PS: U- и V-конвееры давно почили вместе с последними PMMX В атлонах рулит динамическое исполнение 3xALU+3xAGU с переупорядочиванием микроопераций, предсказанием и спекулятивным исполнением ветвлений

 

leo

Да, все так и есть. Причем, в твоем исполнении звучит очень понятно, не то что в доках AMD Еще бы с учетом этого код оптимизировать. Особенно MMX, так как из этой процедурки, похоже, выжато почти все.



А чтобы не быть голословным о скоростях, вот пример:



Прогон 100 млн итераций, процессор Athlon 64 3200+



prc0 need 2093 millisecond - bogrus, но таблица расширена до 32 бит.

prc1 need 2110 millisecond - bogrus, оригинал

prc2 need 1312 millisecond - мой вариант





Если в моем варианте раскомментировать одну строку

prefetcnta [конец таблицы], можно отыграть еще около 100 мсек



В приложении (меньше килобайта) основной файл тестового проекта на MS VS2003

_858441812__tabTst.rar

 

Если так плохо с памятью, то можно сократить до 10-ти чтений и 2-х записей двордами (таблица тоже расширена), надо потестить как shrd поведет себя на амд (зависимость может отобразится)

Код (Text):

1. ;==============================================
2.             mov     ecx,dword[DIn]
3.             mov     eax,ecx
4.             and     eax,0xff
5.             mov     eax,dword[tXlat+eax*4]
6.             shrd    ecx,eax,8
7.             mov     eax,ecx
8.             and     eax,0xff
9.             mov     eax,dword[tXlat+eax*4]
10.             shrd    ecx,eax,8
11.             mov     eax,ecx
12.             and     eax,0xff
13.             mov     eax,dword[tXlat+eax*4]
14.             shrd    ecx,eax,8
15.             mov     eax,ecx
16.             and     eax,0xff
17.             mov     eax,dword[tXlat+eax*4]
18.             shrd    ecx,eax,8
19.             mov     dword[DOut],ecx
20. ;==============================================
21.             mov     ecx,dword[DIn+4]
22.             mov     eax,ecx
23.             and     eax,0xff
24.             mov     eax,dword[tXlat+eax*4]
25.             shrd    ecx,eax,8
26.             mov     eax,ecx
27.             and     eax,0xff
28.             mov     eax,dword[tXlat+eax*4]
29.             shrd    ecx,eax,8
30.             mov     eax,ecx
31.             and     eax,0xff
32.             mov     eax,dword[tXlat+eax*4]
33.             shrd    ecx,eax,8
34.             mov     eax,ecx
35.             and     eax,0xff
36.             mov     eax,dword[tXlat+eax*4]
37.             shrd    ecx,eax,8
38.             mov     dword[DOut+4],ecx
39. ;==============================================

 

bogrus

Ой плохо себя повела shrd на AMD



Вставлено в предыдущий тест. Время - 3156 мсек.

 

andy_biiig

Попробуй вариант с бОльшим числом регистров (с расширенной таблицей)

Без учета push\pop на атлоне вроде как должно укладываться в 16 тиков

Код (Text):

1. ;uses ebx,edi,esi
2. ;----------------
3.   mov edx,[DIn]
4.   mov eax,[DIn+4]
5.   movzx edi,dl
6.   movzx ecx,al
7.   shr eax,8
8.   mov edi,[tXlat+edi*4]  ;0
9.   mov ecx,[tXlat+ecx*4]  ;4
10.   movzx ebx,al
11.   shr eax,8
12.   mov ebx,[tXlat+ebx*4]  ;5
13.   movzx esi,al
14.   shr eax,8
15.   shr edx,8
16.   mov esi,[tXlat+esi*4]  ;6
17.   mov eax,[tXlat+eax*4]  ;7
18.   shl ebx,8
19.   or ebx,ecx
20.   movzx ecx,dl
21.   shr edx,8
22.   mov ecx,[tXlat+ecx*4]  ;1
23.   mov [Dout],edi         ;сохраняем dword, потом переписываем старшие байты
24.   shl esi,16
25.   or esi,ebx
26.   movzx ebx,dl
27.   shr edx,8
28.   mov ebx,[tXlat+ebx*4]   ;2
29.   mov edx,[tXlat+edx*4]   ;3
30.   shl eax,24
31.   or eax,esi
32.   mov [DOut+1],cl
33.   mov [DOut+2],bl
34.   mov [DOut+3],dl
35.   mov [DOut+4],eax