наноупражнение: LEA power

Код (Text):

1. ;=====================================================================
2.             lea     ecx,[eax*2+eax] ; eax*3                        *77
3.             shl     eax,4           ; eax*16
4.             lea     eax,[eax*4+eax] ; eax*16*5
5.             sub     eax,ecx         ; eax*16*5 - eax*3
6. ;=====================================================================

 

bogrus

Для 18,26,33,77 можно и за меньшее число инструкций сделать



All

Для 65 найдено решение в 2 инструкции.

Для 23,37,91 найдены решения в 3 инструкции.

Также найдены оптимальные решения для некоторых констант не входивших в задание 8)

Но в общем активности не наблюдается, неужели ни одна из оставшихся констант вам не нравится?



33 39 41 53 52 54 56

57 58 61 67 68 70 71 77

78 79 83 85 87 89 90

 

Для 33 тоже очевидное решение в два хода:

Код (Text):

1.                 lea     ecx,[eax*8]
2.                 lea     eax,[eax+ecx*4]

 

61,41,52,65:

Код (Text):

1.  
2. .data
3. const_61 dd 04325C54h
4. const_41 dd 063E7064h
5. const_52 dd 04EC4EC5h
6. const_65 dd 03F03F04h
7.  
8. .code
9.     mov edx,eax
10.     shl eax,2
11.     div const_xx
12.  

или, если источник в edx, то две операции:

Код (Text):

1.  
2.     lea eax,[edx*4]
3.     div const_xx
4.  

 

boozook

Таким макаром можно и в одну инструкцию уложиться

61,41,52,65:

.data

const_61 dd 0,61,122,183...

const_41 dd 0,41,82,123...

const_52 dd 0,52,104,156...

const_65 dd 0,65,130,195...



.code

lea eax,[eax*4+const_xx]



All

Кстати началось Hugi Compo 25: http://www.frontiernet.net/~fys/hugi/hcompo.htm

Задача оптимизировать решение игры Sudoku.

Интересная игра между прочим.

 

_G3

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

 

А в чем проблема-то?

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



p.s. кстати, идеи в этом алгоритме те же, что и в этой ветке: взвешивание двоичных деревьев, разложение на множители и т.п...

 

77:



lea ebx,[eax+eax*8]

lea ebx,[eax+ebx*2]

lea eax,[eax+ebx*4]



Nothing

>>А в чем проблема-то?

Покажи на примере числа 876341

 

_G3

Программа выдала вот это: (K - это число)

(K<<20 - K<<17 - K<<15 - K<<13 - K<<8 + K<<6 - K<<3 - K<<1 - K)

Переводить в lea не буду - лень



Всего 8 сдвигов и сложений (или вычитаний, что одно и то же по сути). С lea вижу проблемы только в том, что множитель там может быть только 1,2,4,8 - и все, остальные приходится делать сдвигами, правда есть преимущество в том, что можно хранить временные результаты в других регистрах (хотя это нечестно, их тогда сохранять и восстанавливать надо!)



Я вот одного не пойму, а зачем кому-то что-то быстро умножать на 876341 на x86 архитектуре? Во-первых число слишком большое и кривое, на практике вряд ли встретится, а во-вторых - штатное умножение mul/imul побыстрее будет на таких числах . Такие упражнения с lea хороши для небольших чисел - там и выигрыщ может быть и изящество проявить можно...

 

Тоже лень думать, я написал брутфорсер Цифры ещё не кончились?

Код (Text):

1. ;============================     ;============================
2.  lea     eax,[eax*2+eax] ; 39      lea     eax,[eax*4]     ; 68
3.  lea     ecx,[eax*2+eax] ;         lea     ecx,[eax*2]     ;
4.  lea     eax,[ecx*4+eax] ;         lea     eax,[ecx*8+eax] ;
5. ;============================     ;============================
6.  lea     ecx,[eax*4+eax] ; 41      lea     ecx,[eax*2]     ; 70
7.  lea     eax,[ecx*8+eax]           lea     eax,[ecx*8+eax] ;
8. ;============================      lea     eax,[eax*4+ecx] ;
9.  lea     ecx,[eax*2+eax] ; 53     ;============================
10.  lea     eax,[ecx*8+eax] ;         lea     ecx,[eax*8+eax] ; 83
11.  lea     eax,[eax*2+ecx] ;         lea     eax,[eax*2+ecx] ;
12. ;============================      lea     eax,[ecx*8+eax] ;
13.  lea     eax,[eax*2]     ; 54     ;============================
14.  lea     eax,[eax*2+eax] ;         lea     eax,[eax*4+eax] ; 85
15.  lea     eax,[eax*8+eax] ;         lea     ecx,[eax*2] ;
16. ;============================      lea     eax,[ecx*8+eax] ;
17.  lea     eax,[eax*8]     ; 56     ;============================
18.  lea     ecx,[eax*2+eax] ;         lea     ecx,[eax*4+eax] ; 87
19.  lea     eax,[ecx*2+eax] ;         lea     eax,[ecx*8+eax] ;
20. ;============================      lea     eax,[eax*2+ecx] ;
21.  lea     eax,[eax*2+eax] ;        ;============================
22.  lea     ecx,[eax*8+eax] ; 57      lea     ecx,[eax*4+eax] ; 89
23.  lea     eax,[ecx*2+eax] ;         lea     eax,[ecx*4+eax] ;
24. ;============================      lea     eax,[eax*4+ecx]
25.  lea     ecx,[eax*4+eax] ; 61     ;============================
26.  lea     eax,[eax*2+ecx] ;         lea     eax,[eax*2]     ; 90
27.  lea     eax,[eax*8+ecx] ;         lea     eax,[eax*4+eax] ;
28. ;============================      lea     eax,[eax*8+eax] ;
29.  lea     ecx,[eax*2+eax] ; 67     ;============================
30.  lea     eax,[eax*8]     ;
31.  lea     eax,[eax*8+ecx] ;
32. ;============================

Код (Text):

1. ;============================
2.  lea     eax,[eax*4]     ; 52
3.  lea     ecx,[eax*2+eax] ;
4.  lea     eax,[ecx*4+eax] ;
5. ;============================

Осталось 58 71 78 79 и 876341

 

Код (Text):

1. ;============================      ;============================
2.  lea     eax,[eax*2]     ; 58       lea     eax,[eax*2]     ; 78
3.  lea     ecx,[eax*2+eax] ;          lea     eax,[eax*2+eax] ;
4.  lea     eax,[eax*4+eax] ;          lea     ecx,[eax*2+eax] ;
5.  lea     eax,[ecx*8+eax] ;          lea     eax,[ecx*4+eax] ;
6. ;============================      ;============================
7.  lea     ecx,[eax*2]     ; 71       lea     ecx,[eax*2+eax] ; 79
8.  shl     ecx,5           ;          lea     eax,[eax*2]     ;
9.  sub     ecx,eax         ;          lea     eax,[eax*8+ecx] ;
10.  lea     eax,[eax*8+ecx] ;          lea     eax,[eax*4+ecx] ;
11. ;============================      ;============================

 

> "Тоже лень думать"

Эт-точно, не в бровь, а в глаз

С одной стороны задачка занудно-тривиальная - можно и без брутфорсера за пять минут элементарную табличку в Excel на все 2-3ходовые варианты составить

А с другой стороны не понятно, что дает минимизация числа инструкций. Нужен минимум команд - используй imul, нужен максимум скорости - тогда придется учитывать латентности и возможности распараллеливания, а не тупо считать число команд

Вот для справочки - латентности операций lea и imul:

Код (Text):

1. Проц    lea r32,[r+r*i]  imul r32,imm8
2. ------  ---------------  -------------
3. AMD K7       2                5
4. AMD 64       2                3
5. P6           1                4
6. P4           4               14
7. P4E         1-2(?)           10

Выводы:

1) Три зависимых LEA, удовлетворяющие условию "минимума числа команд" однозначно проигрывают imul на Атлонах, в лучшем случае могут дать 1 тик выигрыша на P6 и 2 тика на P4 (в лучшем, т.к. они нагружают декодер и исполнительные блоки и => придерживают исполнение следующих независимых команд). Пожалуй только для "загадочно-полутормозного" P4E (model 3, Prescott & Co) может быть заметный выигрыш.

2) В P6 lea и shl однотиковые и не параллелятся (идут через один порт p0), а вот на атлонах и P4 можно несколько уменьшить латентность за счет распараллеливания при использовании независимых операций. Поэтому не все варианты с одинаковым числом команд равнозначны. Например, из приведенных 3-ходовых вариантов для множителя 23 самым быстрым является первый вариант _G3, он же "классический" рекомедуемый AMD для K7. Также и для других 3-ходовых существуют более быстрые варианты с одной независимой операцией (элементарно находятся по таблице):

Код (Text):

1. 39=3+9*4          ;все 3,5,9 реализуются через lea
2. 52=16+9*4=32+5*4  ;все 16,32,64 - через shl
3. 56=16+5*8=32+3*8
4. 61=64-3
5. 67=64+3
6. 68=32+9*4
7. 70=64+3*2
8. 77=5+9*8

Ну и при неминимальном числе команд, можно не проиграть на P6 и выиграть на атлонах и P4. Например "очевидное решение" из двух зависимых lea для множителя 33 можно заменить на столь же очевидное решение в 3 хода

Код (Text):

1.   mov ecx,eax
2.   shl eax,5
3.   add eax,ecx

которое может дать те же 2 тика на P6 (если mov проскочит через рорт p1), для атлона даст экономию в 2 тика, а для P4 в 3 тика