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

Тема в разделе "WASM.A&O", создана пользователем Black_mirror, 7 дек 2005.

  1. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Код (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. ;=====================================================================
     
  2. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    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
     
  3. cresta

    cresta Active Member

    Публикаций:
    0
    Регистрация:
    13 июн 2004
    Сообщения:
    2.257
    Для 33 тоже очевидное решение в два хода:


    Код (Text):
    1.                 lea     ecx,[eax*8]
    2.                 lea     eax,[eax+ecx*4]
     
  4. boozook

    boozook New Member

    Публикаций:
    0
    Регистрация:
    3 апр 2003
    Сообщения:
    18
    Адрес:
    Russia
    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.  




    :)
     
  5. _G3

    _G3 New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    41
    Адрес:
    Russia
    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.

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

    boozook New Member

    Публикаций:
    0
    Регистрация:
    3 апр 2003
    Сообщения:
    18
    Адрес:
    Russia
    _G3

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

    Nothing New Member

    Публикаций:
    0
    Регистрация:
    4 авг 2003
    Сообщения:
    139
    Адрес:
    Russia
    А в чем проблема-то? :)

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



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

    _G3 New Member

    Публикаций:
    0
    Регистрация:
    15 июл 2003
    Сообщения:
    41
    Адрес:
    Russia
    77:



    lea ebx,[eax+eax*8]

    lea ebx,[eax+ebx*2]

    lea eax,[eax+ebx*4]



    Nothing

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

    Покажи на примере числа 876341 ;)
     
  9. Nothing

    Nothing New Member

    Публикаций:
    0
    Регистрация:
    4 авг 2003
    Сообщения:
    139
    Адрес:
    Russia
    _G3

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

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

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



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



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

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Тоже лень думать, я написал брутфорсер :) Цифры ещё не кончились?
    Код (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
     
  11. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Код (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. ;============================      ;============================
     
  12. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    > "Тоже лень думать"

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

    С одной стороны задачка занудно-тривиальная - можно и без брутфорсера за пять минут элементарную табличку в 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 тика