Ручная оптимизация (кусок из самописаной библиотеки)

Привет местным и не совсем.
Написал библиотечку, все работает, все отлично. Критические участки кода библиотеки сразу решил писать на ассемблере, чтобы потом иметь возможность подкрутить вручную (чем сейчас и планирую занятся, ибо полученная скорость работы не совсем устраивает. Точнее - устраивает, но не совсем .
После отладки взял в руки отладчик и нашел процедуру, которая кушает 99% от времени работы всей dll. Чтобы не быть голословным, сразу закину код

Код (Text):

1.   local objsz : DWORD
2.   local phyp : DWORD
3.   local pobjs : DWORD
4.   local usedmask : DWORD
5.   local askedmask : DWORD
6.   local nonnil : DWORD
7.   local first_nil_par : DWORD
8.  
9.   local objsc : DWORD
10.   local pars : DWORD
11.   local res : DWORD
12. ...
13.  oneobjdword:
14.     ; and+xor one part
15.     ; EBX = dword index
16.     mov EDI, pobjs ; 2.46%
17.     nop ; 2.28
18.    
19.     mov ECX, usedmask ; 0.14
20.     mov ESI, askedmask ; 0.41
21.    
22.     mov EDX, [EDI+4*EBX] ; object state (dword #EBX) ; 1.57
23.     mov EAX, [ECX+4*EBX] ; used mask (dword #EBX) ; 8.25                
24.     mov EDI, [ESI+4*EBX] ; asked mask (dword #EBX) ; 0.47
25.    
26.     and EDX, EAX ; 1.18
27.     xor EDX, EDI ;want 0 ; 2.76
28.  
29.     bsf EDI, EDX ; find nonnil bits ; 3.18
30.     jz NIL_NIL ; 5.75
31.  
32.     shl EBX, 5 ; 3.58
33.     bsr ESI, EDX ; 1.92
34.    
35.     lea ECX, [EBX + EDI] ;1 bit par_number ; 1.35
36.     lea EDI, [EBX + ESI] ;2 bit par_number ; 0.14
37.      
38.     mov ESI, bitidx ; 1.62
39.     shr EBX, 5 ; 0.46
40.    
41.     mov EAX, dword ptr [ESI+4*EDI] ; 0.73
42.     mov EDX, dword ptr [ESI+4*ECX] ; 9.63
43.    
44.     mov ESI, EAX ; 0.23
45.     mov ECX, first_nil_par ; 2.11
46.    
47.     inc ESI ; 0.33
48.     inc EDX ; 2.22
49.    
50.     cmp ESI, ECX ; 0.1
51.     setne AL ; 2.29
52.    
53.     cmp EDX, ECX ; 2.56
54.     setne CL ; 0.04
55.    
56.     add AL, CL ; 0.99
57.     jz NIL_NIL ; nothing new ; 0
58.    
59.     cmp ESI, EDX ; 2.42
60.     setne CL ; 0.24
61.    
62.     add AL, CL ; 0.72
63.     mov EDX, nonnil ; 2.43
64.    
65.     dec AL ; 0.03
66.     mov first_nil_par, ESI ; new non-nil par ; 2.73
67.    
68.     sub EDX, EAX ; 0.02
69.     jna ONE_ONE ; limit exceeded ; 0
70.    
71.     mov nonnil, EDX ; 2.69
72.   NIL_NIL::  
73.     inc EBX ; 8.88
74.     mov EDX, objsz ; 4.04
75.    
76.     cmp EBX, EDX ; 2.94
77.     jne oneobjdword ;for all dwords ; 0
78.     ...

Пытался читать интеловские маны по оптимизации, что оказалось не очень подъемным (на изучение необходимых техник уйдут минимум месяцы). Пробовал что-то менять, но результат удручающий.
Просьба помочь, направить и/или отправить что-то почитать (не шибко тяжелое).
Проц - Sandy Bridge (Core i7).
Благодарю за внимание.

 

современные компиляторы очень резво оптимизируют код и раскидывают его по конвеерам, просто собирать на icc или gcc)

 

Да, я понимаю, но хотелось бы выжать реально максимум, пусть даже платформно зависимо, ибо ну очень критично.
added: ну и в принципе с такими техниками ознакомиться было бы весьма интересно.

 

Vilco
На этом (wasm.ru) сайте есть полно статей по оптимизации.

Реально действующих методик на самом деле не так много.
Основное увеличение скорости достигается за счёт распараллеливания кода.
1. Раскидывания по ядрам. Прирост на критическом участке в n раз (n число ядер).
2. много данных одна команда. То есть над несколькими данными параллельно выполняется одна команда анг SIMD.
Для этого ваш код надо переписать на SSE c использованием регистров XMM. А да возможно понадобится пересмотреть организацию данных. Прирост в зависимости от размера данных 1-8 раз
3. Параллелизации команд. Современное ядро может выполнять одновременно несколько команд 1-4 если нет зависимости по данным (регистрам). В цикле это выражается в дублирование инструкций. Обычно работает над соседними элементами, выполняя аналогичный код. Так называемая раскрутка цикла. Прирост 1-4 раза.
4. Если данных много то можно ещё заняться оптимизацией работы с памятью (кэшами, ОЗУ, цифровые носители). Тут сводится к группировке данных и обработки блоками. Прирост может быть внушительным.

 

PS. Возьми другой профилировщик, а твой походу недостоверные данные выводит.

 

Спасибо за развернутый ответ.
Тут наверное стоит пояснить, чот распараллеливать сам этот кусок кода смысла практического нет, т.к. у меня очередь однотипных задач, которые я уже раскидал по ядрам (т.е. они заняты все и считают одновременно).
Ещё 1 направление - выжать ещё немного из перехода на 64битный код (что по моим подсчетам должно сократить время исполнения раза в полтора).
Это все понятно. Задам тогда вопрос немного по-другому - можно ли ручной оптимизацией выжать ещё что-то? Даже если это будет незначительный прирост для конечного результата это будет существенно.

Не нашел где в процентиках посмотреть, но думаю все и так примерно ясно:

Код (Text):

1. oneobjdword: ;18 tacts is too much, optimize this
2. ; and+xor one part
3. mov EDI, pobjs ; 183.919s
4. nop ; 148.351s
5.  
6. mov ECX, usedmask ; 15.507s
7. mov ESI, askedmask ; 30.417s
8.  
9. mov EDX, [EDI+4*EBX] ; object state dword#EBX ; 121.615s
10. mov EAX, [ECX+4*EBX] ; 583.945s
11. mov EDI, [ESI+4*EBX] ; 69.663s
12.  
13. and EDX, EAX ; 77.215s
14. xor EDX, EDI ;wait 0 ; 222.440s
15.  
16. bsf EDI, EDX ; 202.476s
17. jz NIL_NIL ; 454.236s
18.  
19. shl EBX, 5 ; 259.969s
20. bsr ESI, EDX ;6 tacts ; 119.297s
21.  
22. lea ECX, [EBX + EDI] ;1 bit par_number ; 65.251s
23. lea EDI, [EBX + ESI] ;2 bit par_number ; 29.923s
24.  
25. mov ESI, bitidx ; 104.856s
26. shr EBX, 5 ; 33.613s
27. mov EAX, dword ptr [ESI+4*EDI] ; 32.730s
28. mov EDX, dword ptr [ESI+4*ECX] ; 651.348s
29.  
30. mov ESI, EAX ; 21.836s
31. inc ESI ; 15.666s
32. inc EDX ; 152.311s
33.  
34. cmp ESI, ECX ; 7.624s
35. setne AL ; 141.430s
36.  
37. cmp EDX, ECX ; 163.801s
38. setne CL ; 4.946s
39.  
40. add AL, CL ; 50.164s
41. jz NIL_NIL ; nothing new ; 0.738s
42.  
43. cmp ESI, EDX ; 156.294s
44. setne CL ; 20.945s
45.  
46. add AL, CL ; 46.583s
47. mov EDX, nonnil ; 146.386s
48. dec AL ; 24.440s
49. mov first_nil_par, ESI ; new non-nil par ; 158.654s
50.  
51. sub EDX, EAX ; 29.990s
52. jna ONE_ONE ; limit exceeded ; 0.637s
53. mov nonnil, EDX ; 187.823s
54.  
55. NIL_NIL::  
56. inc EBX ; 608.818s
57. mov EDX, objsz ; 249.915s
58. cmp EBX, EDX ; 166.440s
59. jne oneobjdword ;for all dwords ; 0.647s

 

Используйте С++ компилятор с интринсиками.

 

Вам на санди не ассемблером нужно заниматься, а параллелить .

С чего это вдруг? Векторизация, распараллеливание это да.

 

Это неочевидно, но с того что в коде гоняются битовые маски. Чем больше размер регистра, тем больше битов есть возможность обработать за эти пару тактов.
А код распараллелил. У меня все ядра загружены, с этим проблем нет.

 

Тогда AVX вам в руки.

 

Спасибо, гляну.

 

Vilco

В-принципе согласен с указанными выше рекомендациями - попробовать на хорошем C-compiler'е собрать и так далее но ... лучше сделать один раз вручную чтобы потом с умом компелировать.

Вот относящееся к совету Pavia - часть III (AGI):

Код (Text):

1. mov EAX, dword ptr [ESI+4*EDI] ; 0.73
2.     mov EDX, dword ptr [ESI+4*ECX] ; 9.63
3.    
4.     mov ESI, EAX ; 0.23
5.     mov ECX, first_nil_par ; 2.11

Если ваш "профелировщик" не врет - сразу видно что две однотипные команды жрут совершенно разное время - 0.73 vs 9.63. 10 раз!! Как версия это сбой конвеера из-за следующей команды загрузки используемого в текущей команде регистра:

Код (Text):

1.     mov EDX, dword ptr [[b]ESI[/b]+4*ECX] ; 9.63
2.     mov [b]ESI[/b], EAX ; 0.23

Самое простое - попробовать использовать другой регистр (если есть) или элемент стека - [esp+X] вовсе не хуже чем использование регистра (на текущих процессорах) - конпеляторы типа VC не стесняютсо использовать именно этот метод ИЛИ просто выполнить команду следующую за критической (если возможно):

Код (Text):

1. mov EAX, dword ptr [ESI+4*EDI] ; 0.73
2.     mov EDX, dword ptr [ESI+4*ECX] ; 9.63
3.     mov ECX, first_nil_par ; 2.11    
4.     mov ESI, EAX ; 0.23

 

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

 

Все профилировщики "врут", когда показывают "какие-то" проценты или секунды на уровне отдельных команд, т.к. для суперскалярных процев, декодирующих и отправляющих в отставку до 3-4 команд за один такт, просто невозможно указать какое-то время на одну команду. Чтобы не повторяться, см. к примеру тут и\или тут

 

Ну а если отставить профилировщики в сторону, можно ли как-то качественно улучшить данный кусок кода?

 

В данном куске кода читаются три массива неизвестной длины, и если данные не в кэше, то "качественно" тут ничего особо не наоптимизируешь, т.к. вся "мелочная" оптимизация просто утонет на фоне загрузки данных из ОЗУ.

Что касается "качества" асм-кода, то подробно разбираться лень, а на вскидку бросается в глаза "злоупотребление" загрузкой данных в регистры вместо использования операций непосредственно с памятью (по кр.мере and+xor), но из-за большого числа переменных по любому "красиво" не получится

 

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

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

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

Скажем, вот операция inc EBX, не зря она обоими профилировщиками "награждена" большими временами. Она зависит не только от shr EBX, 5 или предыдушего выполнения самой же этой inc EBX в предыдущем цикле, но и неявно от чуть ранее идущей sub EDX, EAX из-за регистра флагов - операция inc меняет только некоторые биты регистра флагов, остальные она должна оставить как есть. Замените inc EBX на команду add EBX,1, и зависимость от регистра флагов пропадет, поскольку add полностью переписывает регистр флагов, и поэтому может выполниться не дожидаясь выполнения sub EDX, EAX. А из-за этого раньше смогут выполниться и загрузки в начале следующей итерации цикла (опять же, пусть не смущает то, что регистры уже используются в других операциях, которые вроде бы раньше по порядку выполнения - проц использует при вычислениях не архитектурные регистры, а большую кучу неименованных регистров, назначая каждой операции персональное сопоставление неименованных и архитектурных).

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

 

Спасибо откликнувшимся.
Размеры массивов зависят от объема исходной БД, посему могут достигать и гигабайтовых размеров.
Про граф спасибо, здравая идея, но пока отложу её в долгий ящик и попытаю счастье с векторизацией.

Верно подметили. Хотя есть там несколько ньюансов, но я думаю что это все устранимо.

 

Если у вас однотипные/трудоёмкие расчёты, то gpu будет очень не плохим вариантом.

 

Правильно CUDA рулит ^_^