MD5. Оптимизировать... раза в три.

Мне понадобилось написать для одной программки вставку, которая бы считала MD5. За образец взял псевдокод отсюда: http://en.wikipedia.org/wiki/MD5 . Что-то получилось. Но считает 60-70 секунд 700-метровый файл.
Потом нашел вот этот исходник:
http://www.langfine.com/downloads/MD5%20v1.2.zip
и по его образцу сделал новую вставку. Время подсчета для того же файла упало секунды на три (причем там число обращений к RAM колоссально понизилось). Оба раза я читал файл чанками по 40 байт (ровно столько, сколько обрабатывается одной итерацией алгоритма). После этого решил переделать на подсчет с чтением файла по 64 КБ. Тем самым понизил время втрое, т.е. теперь на тот же файл уходит около 20 секунд (прикладываю файл, что в конце концов получилось).
Есть одна программка eXpress CheckSum Calculator... она считает тот же файл примерно за десять секунд (причем подсчитывает за это время MD5, SHA-1 и CRC32). Т.е. мои 20 секунд еще понижать и понижать... секунд наверное до семи-восьми. В связи с этим у меня несколько вопросов:
1) Стоит ли считывать весь файл сразу целиком в память, а потом через него прогонять подсчет MD5? (код существенно упростится, но вдруг файл 3 ГБ занимает... будет ли достаточно политкорректно по отношению к компьютеру сразу так нахально забить память, и не отразится ли это негативно на производительности алгоритма?)
2) Имеет ли смысл использовать при этом кучу или лучше заменить на VirtualAlloc?
3) Имеет ли смысл заниматься перемешкой независимых инструкций или можно смело положиться на out-of-order execution?

Прикладываю, что получилось (снабдил комментариями)... подскажите, что еще можно оптимизировать.

 

Многопоточность?!
зы:
в ссылке точка, вики виснет

 

Забыл упомянуть... а если eXpress CheckSum Calculator считает только MD5, то секунды за три.
twgt
А разве MD5 подразумевает разбиение на потоки? Я не представляю, как ее на несколько потоков разбить. Там каждое следующее действие зависит от предыдущего.

 

l_inc
Я имел виду что она ещё подсчитывает разные чексуммы.

А у твоей программы md5-хэш совпадает с тем, который выдаёт eXpress CheckSum Calculator??

 

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

Смешно было бы говорить о скорости выполнения, если программа вообще не работает.
P.S. Точку в ссылке поправил.

 

Может по 64?

Целиком точно не нужно. Грузи файл кусками от 4 до 16 Мб — и памяти немного занимает, и производительность хорошая.

Ты буфер выделяешь один раз, поэтому это роли не играет.

Имеет только в том случае, если больше оптимизировать нечего. При хешировании файла с диска смысла не имеет =)

А вот прикрутить ко всему этому асинхронное чтение (чтобы хеш вычислялся во время чтения), я думаю, нужно.

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

 

l_inc
В импорт eXpress CheckSum Calculator загляни.
В программе нет алго, она юзает апи Crypt*

 

flankerx

Ну да. По 40h байт.

Тогда заменю на VirtualAlloc. Там хоть хэндл кучи хранить не надо.

Спасибо. Думаю попробую.

Если честно, то я о профайлерах только понаслышке, но мне ничего не стоит удалить кусок кода с подсчетом и оставить чисто чтение из файла, а потом замерять.
twgt

Блин. Знал бы, что есть такие апи, не мучался бы. Благодарю.

 

flankerx
Я немного позамерял. Поменял на VirtualAlloc, читаю по 4 МБ. Получилось, что на чтение файла в чистом виде уходит около 1,2 секунды. А на полный подсчет около 26 секунд (20 секунд было при старом состоянии системы, поэтому эти 26 и те 20 никак не связаны). Т.е. выигрыш при асинхронном чтении будет измеряться в единицах процентов.

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

 

l_inc
Ну всякие мелочи вместо

Код (Text):

1. mov reg,-1h
2. ...
3. MOVZX EBX,AH
4. .......
5. ADD AL,-1

замени на

Код (Text):

1. xor rex,reg
2. dec reg
3. ...
4. xor ebx,ebx
5. xor BL,AH
6. ........
7. dec AL

хотя незнаю насколько это прибавит скорости :/

 

Код (Text):

1. or reg,-1

Вообще советую отказаться от использования однобайтовых регистров с *h (ah,ch,dh...) для наименьшего геммора при переносе на 64х платформу.

 

l_inc

Чтение 700мб файла за 1.2с? Это что, 500 мб/с скорость чтения с винта?

 

Не понимаю чем плох mov reg, -1h. Берет один такт, как и or. И спариваем в обоих конвейерах. Хотя при замене я выиграл на 700 метрах около секунды.
Насчет ADD AL,-1 и DEC AL мне 10110111 как-то написал вот это (о замене DEC ECX на SUB ECX,1):

Не критично, но я не вижу повода делать обратную замену.
А на замене MOVZX EBX,AH на

Код (Text):

1. xor ebx,ebx
2. xchg BL,AH

какие-то сотни миллисекунд даже потерял.

У меня напряг с числом свободных регистров. А до переноса на 64х платформу еще жить и жить.
IceStudent
Собственно говорю, что вижу. Вот код, который на 700-х мегабайтах за 1,2 секунды выполняется:

Код (Text):

1. USE32
2. include 'tables.inc'
3. ;INT3
4. PUSH EBP
5. MOV EBP,ESP
6.     ;[EBP+8h] = Pointer to MD5Hash (out)
7.     ;[EBP+0Ch] = File path (in)
8.     ;[EBP+10h] = Pointer to APIList (in) (CreateFile,CloseHandle,GetFileSize,ReadFile,VirtualAlloc,VirtualFree)
9.     PUSH 0               ;lpNumberOfBytesRead buffer                     [EBP-4h]
10.     PUSH 0               ;hFile storage                                  [EBP-8h]
11.     PUSH 0               ;pointer to the Memory                          [EBP-0Ch]
12.     PUSH 0               ;pointer to the current 512-bit message chunk   [EBP-10h]
13.     PUSH 0               ;EOF flag                                       [EBP-14h]
14.     PUSH EBX
15.     PUSH ESI
16.     PUSH EDI
17.     MOV EBX,[EBP+10h]    ;EBX = Pointer to APIList
18.     ;Allocating memory
19.     PUSH 4h              ;flProtect
20.     PUSH 1000h           ;flAllocationType
21.     PUSH CHUNK_SIZE+40h  ;dwSize
22.     PUSH 0h              ;lpAddress
23.     CALL DWORD [EBX+10h] ;CALL VirtualAlloc
24.     MOV [EBP-0Ch],EAX
25.     MOV [EBP-10h],EAX
26.     ADD DWORD [EBP-10h],CHUNK_SIZE
27.     ;Opening file
28.     PUSH 0h              ;hTemplateFile
29.     PUSH 0h              ;dwFlagsAndAttributes
30.     PUSH 3h              ;dwCreationDisposition
31.     PUSH 0h              ;lpSecurityAttributes
32.     PUSH 0h              ;dwShareMode
33.     PUSH 80000000h       ;dwDesiredAccess
34.     PUSH DWORD [EBP+0Ch] ;lpFileName
35.     CALL DWORD [EBX]     ;CALL CreateFile
36.     MOV [EBP-8h],EAX
37.  
38.     ;Initializing ABCD
39.     MOV EAX,[EBP+8h]
40.     MOV DWORD [EAX],067452301h
41.     MOV DWORD [EAX+4h],0EFCDAB89h
42.     MOV DWORD [EAX+8h],098BADCFEh
43.     MOV DWORD [EAX+0Ch],010325476h
44.  
45.     nextFChunk:
46.         ;Reading file chunk
47.         PUSH 0               ;lpOverlapped
48.         LEA EAX,[EBP-4h]
49.         PUSH EAX             ;lpNumberOfBytesRead
50.         PUSH CHUNK_SIZE      ;nNumberOfBytesToRead
51.         PUSH DWORD [EBP-0Ch] ;lpBuffer
52.         PUSH DWORD [EBP-8h]  ;hFile
53.         MOV EBX,[EBP+10h]
54.         CALL DWORD [EBX+0Ch] ;CALL ReadFile
55.  
56.         ;Appending additional bits
57.         CMP DWORD [EBP-4h],CHUNK_SIZE
58.         JE  notLastFChunk
59.             OR DWORD [EBP-14h],-1h
60.         notLastFChunk:
61.  
62.     CMP DWORD [EBP-14h],0
63.     JE nextFChunk
64.     ;Closing handle to the file and destroying heap
65.     MOV EBX,[EBP+10h]
66.     PUSH DWORD [EBP-8h]  ;hObject
67.     CALL DWORD [EBX+4h]  ;CALL CloseHandle
68.     PUSH 8000h           ;dwFreeType
69.     PUSH 0h              ;dwSize
70.     PUSH DWORD [EBP-0Ch] ;lpAddress
71.     CALL DWORD [EBX+14h] ;CALL VirtualFree
72.     POP EDI
73.     POP ESI
74.     POP EBX
75. MOV ESP,EBP
76. POP EBP
77. RETN 10h

 

Эээ... Вообще-то есть процессоры (и мануалы) и поновее, чем Pentium 1

 

Atlantic
ОК. Учту.

 

l_inc
Хм.. Оффтоп, конечно, но приведи характеристики железа. Откуда читаешь, с флешки? Или с файла в RAM Drive?

 

хочу себе такой винчестер... можно параметры железа в студию?

 

неужели винда всё скешировала?

 

IceStudent masquer
Просто меня эта скорость не удивила, и перепроверять я не стал. Видимо t00x прав. Т.к. при первом чтении файла уходит 18 секунд, а при всех повторных уже 1,2 секунды. Просто я всегда проверял сначала производительность кода, считающего MD5, а потом уже кода-бланка, который просто читал из файла. Тем не менее после кэширования виндой всего файла скорость выполнения кода, считающего MD5, почему-то не меняется (остается в районе 25-27 секунд).
Интересная фишка с eXpress CheckSum Calculator'ом. Оказывается его три секунды - это уже по готовенькому : я всегда сначала тестировал своей прогой, а потом им. Поэтому он уже скэшированный файл получал. Попробовал его только что на новом файле: у него ушло аж 40 секунд!
Теперь вопрос об оптимизации сводится к такому: почему моя программка подсчета MD5 не использует скэшированый файл и как ее заставить это делать?
P.S. TermoSINteZ
Не понял комментария.