Оптимизация маленькой ассемблерной вставки в VB

Пытаюсь сравнивать скорости выполнения кода, сгенерированного VB, и ассемблерной вставки в VB. Для этого взял массивчик ArrToCalc(1 To 200000000) As Byte и заполняю его в VB произвольными значениями от нуля до девяти:

Код (Text):

1.   Randomize
2.   For Par = 1 To 200000000
3.     ArrToCalc(Par) = Int(Rnd * 10)
4.   Next Par

То же самое делает вставка:

Код (Text):

1.     MOV ESI,[EBP+0Ch]    ;отсюда читаем указатель на массив
2.     MOV ECX,[EBP+10h]   ;отсюда размер массива
3.     MOV EBX, 10             ;будем находить остаток от деления на 10, чтобы получить [0..9]
4.     RDTSC
5.     @@:
6.         IMUL EAX,15A4E35h  ;это число нашел здесь на форуме :-)
7.         ADD EAX,1
8.         PUSH EAX
9.         XOR EDX, EDX
10.         DIV EBX
11.         MOV [DS:ECX+ESI-1],DL
12.         POP EAX
13.     LOOP @B

У VB-кода уходит на цикл около 36 секунд. У Asm-вставки около 3 секунд. Так вот может можно как-то еще сократить время генерации? Например, если я уберу работу со стеком в цикле, а вместо этого брать тики буду внутри цикла перед imul? Но боюсь, что от этого разброс значений пострадает.

 

Можно без потери разброса заменить push eax/pop eax на mov edi,eax/mov eax,edi - тогда не будет некоторых обращений к памяти

Кроме того, Интелы не рекомендуют использовать loop XXX, а рекомендуют вместо этого dec ecx/jnz XXX.

 

10110111
О. Внатуре. Как я сам не догадался. Спасибо. Для начала неплохо. Правда я на входе в функцию не забивал в стек edi, но уж лучше один раз, чем в цикле.

Не совсем понимаю почему. Перегрузка конвейера в каких-то левых ситуациях? А насчет dec ecx... его не рекомендуют заменять на sub ecx, 1, как inc ecx на add ecx, 1?

 

loop - тормозная инструкция, которая существует только для совместимости. Вообще комплексные инструкции (вроде loop) на современных камнях работают медленнее элементарных (dec / jcc).

Да, но разница незначительна. См. А. Фога.

 

Всякие push\pop и loop тут конечно никчему, но это мелочь по сравнению с div EBX, которую лучше заменить умножением на константу

Код (Text):

1. mov edi,eax         ;сохраняем edx
2. mov edx, 01999999Ah ;умножаем на 2^32/10
3. mul edx            
4. mov eax,edi
5. lea edx,[edx+4*edx] ;в edx - частное, умножаем на 5
6. add edx,edx         ;умножаем на 2
7. sub edi,edx         ;остаток
8. sbb edx,edx         ;коррекция остатка для eax > 40000004h
9. and edx,10
10. add edi,edx         ;скорректированный остаток

PS: Интересно, а зачем понадобилось сохранять 200Мб такого мусора Тут само чтение\запись в память такого объема приличные тормоза дает

 

Если заменять, то лучше как add ecx,-1. На старых камнях sub работает чуть медленнее, чем add. Но это действительно мелочь по сравнению с DIV.

Я так понимаю, неважно, будет ли это реальный остаток, или нет... Главное, чтобы это было 0<=f(eax)<=9? Тогда вместо умножений/делений можно использовать код:

Код (Text):

1. and eax,15  ;0<=eax<=15
2. add eax,-9  ;-9<=eax<=6
3. cdq ;Три инструкции для получения abs(eax)
4. xor eax,edx
5. sub eax,edx ;0<=eax<=9

 

10110111
Если уж оптимизмровать то до конца

Код (Text):

1. AAA       ;В AL будет остаток отделения на 10.

 

Тогда уж не AAA, а AAM

 

10110111
AAA быстрее чем AAM.

 

10110111

Если равномерность распределения не важна, то да, т.к. в твоем варианте числа 1..6 будут выпадать в 2 раза чаще, чем 0,7,8,9

Pavia

Во-первых, ААА делает то же самое, что и код 10110111, а для получения остатка от деления AL на 10 нужно использовать AAM
Во-вторых, что оптимизировать - размер или скорость на отдельно взятой линейке P6 ?
Загляни в instruction_tables А.Фога и посмотри латентности AAA и AAM, особенно для P4

Хотя использовать для взятия остатка только часть младших бит еах - это мысль. Например, если использовать 5 бит, то неравномерность будет всего 3/32 ~ 1/10 - тут можно и табличку замутить

 

leo
Сам бы заглянул в мануэлы от интел и убедился что делает AAA и почему она не соответствует коду от 10110111.
Я еще и в доки от AMD успел заглянуть.

 

Pavia
А сам то заглядывал ?
AAA - ascii adjust after addition
if ((AL and 0Fh) > 9) or (AF = 1) then AL = AL+6
И чем это по сути отличается от варианта 10110111 ? Точно такая же переброска "лишних" 6 значений из диапазона 0..15 в диапазон 0..9 - какой ты тут остаток от деления на 10 увидел ?
(кстати после mul флаг AF и вовсе undefined)

 

leo

В принципе делить весь eax на 10 не обязательно. Разброс не сильно пострадает, если делить на 10 только al. Поэтому мог бы подойти и aam. Но я рассчитывал на то, что диапазон получаемых случайных значений может быть любым, и, если мне нужно получить диапазон от нуля до 22, то финты с заменой на умножения вроде не проходят, т.к. 23 - число вроде как простое и заменить на умножения, наверное, не получится. (хотя разумеется мне бы и в голову не пришло менять div ebx на такую кучу кода. Да и вообще, я уже привык чувствовать себя чайником).

Ну я ж в первом посте написал, что просто пытаюсь сравнить VB и асм-вставки в VB. А для заметного различия во времени надо бы и массивчик побольше подобрать. А так как я нахожу еще и сумму значений всех чисел, и, к тому же, VB-шный long может хранить значения до двух млрд, то более 200 млн значений в пределах десяти могли бы вывести меня за пределы long'а. Поэтому я решил остановиться на двухстах метрах.
10110111

Учитывая то, что сказал leo:

... в общем неплохо бы оставить разброс равномерным.
P.S. Может лучше заменить

Код (Text):

1. xor edx, edx
2. div ebx

на

Код (Text):

1. and eax, 0FFh
2. div bl

? Тогда согласно справочнику количество тактов на div'е может упасть с 41 до 17.

 

В общем довольно странно получается. Остановился я пока на вот таком варианте:

Код (Text):

1.     MOV ESI,[EBP+0Ch]
2.     MOV ECX,[EBP+10h]
3.     MOV EBX, 10
4.     RDTSC
5.     @@:
6.         IMUL EAX,15A4E35h
7.         ADD EAX,1
8.         MOV EDI,EAX
9.         XOR EDX,EDX
10.         DIV EBX
11.         MOV [DS:ECX+ESI-1],DL
12.         MOV EAX,EDI
13.     ADD ECX,-1
14.     JNZ @B

DIV пока ничем не заменял, т.к. предложенные варианты рассчитаны исключительно на диапазон [0..9]. Вот этот код дает около 2,5 секунд.
Если заменить push eax/pop eax на mov edi,eax/mov eax,edi, то накидывается еще 100 мсек. Если заменить только add ecx,-1/jnz @B на loop @B, то накидывается еще около 120 мсек. При этом если заменить в обоих местах (втыкнуть и работу со стеком и loop), то цикл работает целых 3 секунды (т.е. плюс еще 500 мсек). Странно.
Но еще более странно, что, когда я xor edx,edx/div ebx заменил на and eax,0FFh/div bl, то цикл вместо 2,5 секунд стал работать 3,1 секунды. Как это вообще можно объяснить?!

 

Хе, похоже мы заблудились в трех соснах, а задачка то для произвольного диапазона решается элементарно
Eсли у нас есть равномерно распределенное число в диапазоне 0..N-1, то для перевода его в диапазон 0..M-1 нужно просто умножить его на M и разделить на N. Ес-но в качестве N нужно\можно брать степень 2-х. В данном случае можно просто заменить div ebx на mul ebx и в edx получится число в заданном диапазоне

Код (Text):

1.   IMUL EAX,15A4E35h
2.   ADD EAX,1
3.   MOV EDI,EAX
4.   MUL EBX  ;<--- edx = eax*ebx/2^32
5.   MOV [DS:ECX+ESI-1],DL
6.   MOV EAX,EDI

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

Что касается "странностей" с задержками, то по-видимому ты на атлоне (или P6) эаспериментируешь и мелкие различия могут быть вызваны разными условиями декодирования (изменениями числа\размера инструкций и их положения относительно выравненных 16-байтных блоков декодирования). А если при замене на div bl еще забыть заменить в mov mem, dl на al то можно нарваться на хитрые эффекты блокировки конвеера из-за переполнения очереди записи

 

Это можно объяснить тем, что при переименовании регистров eax, ax и al - совершенно разные регистры, так что после and eax,0ffh процессору надо обновить регистр ax для div bl. То же самое с div ebx/mov [...],dl.

 

leo

Круто. Тупой я... тупой.

Ну да... можно. Но большой проблемы в замусоривании 200 мегабайт я не вижу. У меня 2 ГБ стоит, бОльшая часть из которых простаивает во время подобных тестов. Винда может, конечно, пытаться сбросить часть массива в pagefile, но ИМХО при таком объеме RAM и частоте обращений к массиву вряд ли (поправьте, если опять гоню).

Экспериментирую на любимом всеми любителями оптимизации P4 HT (3,4 ГГц) .

Ну я не забыл, но почему на al, а не на ah? Остаток ведь вроде в ah остается?
10110111
Я слабо понимаю, что значит "при переименовании регистров", и с каких это пор al - не младший байт ax, а ax - не младшее слово eax, но поверю на слово. Тогда, как я понимаю, "процессору надо обновить регистр ax" выполняется по принципу mov, на что должно уходить не более одного такта. Т.е. вроде выигрыш в 41-17=24 такта это никак не должно компенсировать. Или с какого момента я начинаю нести ерунду?

 

С того, как пытаешься латентности шустрых P6 и атлон применить к неповоротливым монстрам P4
По докам Intel для P4 латентность div составляет > 60 тактов и неизвестно зависит или нет от размера операнда, а по данным А.Фога для P4Е латентость div bl практически такая же как и div ebx, а для P4 (без EM64T) и вовсе латентность div bl больше, чем div ebx (61 против 50, т.е. > 20% как у тебя и получилось). Причины такого дебилизма P4 я не знаю (также как и сильно завышенных латентностей операций типа setcc, adc\sbb и т.п.)

PS: Что касается регистров, то в P4 и атлонах AL,AH и AX являются частями единого регистра EAX (при изменении части автоматически обновляется весь регистр). Это только в P6 при изменении части под нее отводится отдельный внутренний регистр, а полный регистр остается неизменным. Но к данной ситуации это отношения не имеет, т.к. тормоза возникли бы только при чтении целого регистра после изменения части, а тут eax восстанавливается при mov eax,edi

 

leo
Результат при замене div на mul -- супер!!! Время выполнения цикла сильно зависимо от состояния системы, поэтому то, что в прошлый раз выполнялось за 2,5 сек, теперь выполнялось за 2,3 сек. Но при замене xor edx,edx/div ebx на mul ebx в этот раз время с 2,3 сек понизилось до 0,8 сек! Огромное спасибо! И... мне жаль, что я с Вами в первый раз не очень вежливо разговаривал. :-(

10110111 Pavia Quantum
Также премного благодарен. Благодаря Вашим постам тоже узнал много интересного/полезного.

 

Хотел спросить... забыл. Думаю, что вопрос еще в эту тему вписывается. Не подскажете, как из Asm-вставки в VB6 вызвать API (Asm-вставка вызывается типичным CallWindowProc VarPtr(AsmProc(0)), ...)? Т.е. я понимаю, что при большом желании можно реализовать методы получения адресов "а-ля базонезависимый код", но это ИМХО извращение.
Вот способ, который мне пришел в голову:
1) Объвить все API в модуле.
2) В том же модуле реализовать функции-мостики для каждой API в таком духе:

Код (Text):

1. Private Declare Function GetTickCount Lib "kernel32" () As Long
2.  
3. Public Function GetTickCountBridge() As Long
4.  GetTickCountBridge = GetTickCount
5. End Function

3) Асм-вставку вызывать (из любого места программы) примерно вот таким образом:
CallWindowProc VarPtr(AsmProc(0)), RetVal, AddressOf GetTickCountBridge, 0, 0
4) Ну и соответственно сама вставка должна выглядеть примерно вот так:

Код (Text):

1. USE32
2. PUSH EBP
3. MOV EBP,ESP
4.     PUSH EAX
5.     PUSH EBX
6.     MOV EAX,[EBP+0Ch]  ;Здесь адрес GetTickCount
7.     CALL EAX                 ;Здесь соответственно его вызываем
8.     MOV EBX,[EBP+8]
9.     MOV [DS:EBX],EAX    ;В RetVal возвращаем то, что вернула GetTickCount
10.     POP EBX
11.     POP EAX
12. MOV ESP,EBP
13. POP EBP
14. RETN 10h

5) При необходимости вызывать много API передавать в качестве параметра CallWindowProc указатель на массив указателей на функции-мостики.

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