На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Перед отправкой сообщения внимательно прочтите правила раздела!!!
1. Запрещается обсуждать написание вирусов, троянов и других вредоносных программ!
2. Помните, что у нас есть FAQ раздела Assembler и Полезные ссылки. Не поленитесь, загляните в эти разделы перед созданием темы. Возможно, так уже имеется решение вашего вопроса.

3. Настоятельно рекомендуем обратить особое внимание на правила форума, которые нарушаются чаще всего:
  3.1. Заголовок темы должен кратко отражать её суть. Темы с заголовками типа "Срочно помогите!" или "Ассемблер" будут отправляться в Корзину для мусора.
  3.2. Исходники программ обязательно выделяйте тегами [code]...[/code] (одиночные инструкции можно не выделять).

Не забывайте также про главные Правила форума!

Так что добро пожаловать и приятного вам общения!!! ;)
 
Модераторы: Jin X, Qraizer
  
> Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!
    Как известно, инструкция xchg, оперирующая с памятью, занимается нехорошим делом: блокировкой шины. Иногда, конечно, это дело очень даже полезное, но гораздо чаще – нет.

    Давайте подумаем: чем можно заменить эту инструкцию (скажем, xchg [ecx],eax) для максимизации скорости?
    Конечно, первое, что приходит в голову – это:
    ExpandedWrap disabled
      mov edx,[ecx]
      mov [ecx],eax
      mov eax,edx
    Скорость взлетает ощутимо – проверено.
    Но! Тут используется дополнительный регистр! А если лишнего регистра нет? Что делать?

    Может, я откровенно туплю, но пока в голову не приходит ничего лучше, чем:
    ExpandedWrap disabled
      push eax
      push [ecx]
      pop eax
      pop [ecx]
    или
    ExpandedWrap disabled
      xadd [ecx],eax
      sub [ecx],eax
    Но второй вариант работает даже медленнее, чем первый (в цикле, по крайней мере)!!!

    Ах, да, есть же ещё:
    ExpandedWrap disabled
      xor eax,[ecx]
      xor [ecx],eax
      xor eax,[ecx]
    Он работает быстрее, чем xadd и чуть быстрее, чем push/pop в цикле (и тем более xchg), но скорость всё равно низкая...

    Задача №2 (усложнённая). Нам нужно обменять 2 элемента в памяти (а-ля xchg [ecx],[edx]). В распоряжении у нас максимум 1 регистр.
    То бишь такое не прокатит:
    ExpandedWrap disabled
      mov eax,[edx]
      mov ebx,[ecx]
      mov [edx],ebx
      mov [ecx],eax
    (тут 2 регистра)

    Тут, конечно, относительно быстрым будет:
    ExpandedWrap disabled
      mov eax,[ecx]
      xor eax,[edx]
      xor [edx],eax
      xor eax,[edx]
      mov [ecx],eax

    А вот это:
    ExpandedWrap disabled
      fld dword ptr [ecx]
      fld dword ptr [edx]
      fstp dword ptr [ecx]
      fstp dword ptr [edx]
    ...ещё быстрее варианта с xor (примерно вдвое!) :D

    Но хочется большего!!!
    Покумекаем? :)

    p.s. Всяческие варианты с MMX/SSE (или каким-нибудь особенным набором инструкций) прошу не предлагать как основные решения. Как дополнительные – ну ок, сгодятся.
    vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
      Цитата Jin X @
      пока в голову не приходит ничего лучше, чем:

      ExpandedWrap disabled
        push [ecx]
        mov [ecx], eax
        pop eax
        Jin X, ты ж понимаешь, что это баловство? Скорость будет зависеть от любого чиха в окружении. Элементарно вдруг окажется, что параллельное ядро решило инвалидировать интересную строку кеша. Плюс зависимости по регистрам в окаймляющем коде. Плюс ветвления с неоднозначной предсказуемостью незадолго до или после. Плюс зависимости от исполнительных блоков, которые ты каким-нибудь xadd и/или sub отнимешь у команд за десяток инструкций от своего "xchg". ИМХО просто не используешь xchg, и этого достаточно. Ибо главный тормоз тут lock, который вносит избыточную упорядоченность в исполнительный поток. Нет lock, нет проблемы, остальное от лукавого.
        Сообщение отредактировано: Qraizer -
        Одни с годами умнеют, другие становятся старше.
          leo, отличный вариант, кстати! Давай ещё для обмена 2-х элементов памяти ;)

          Qraizer, есть вещи, на которые мы можем повлиять (какие инструкции использовать и как их сочетать с другими), а есть те, на которые не можем (параллельные процессы, ядро и пр). Наша задача работать с тем, на что мы повлиять можем. Согласись, что всегда один код (или инструкция) будет работать "в среднем" быстрее, чем другой. А в некоторых случаях всегда быстрее (типа dec ecx+jnz против loop, если не брать во внимание 8086 и т.п. экзотику).
          Например, вариант от leo по любому будет быстрее, чем 2 push'а и pop'а. А если у нас будет несколько хороших вариантов, то будет из чего выбирать... По крайней мере, мы всегда можем вставить разные варианты в критические участки кода и потом сравнить общую скорость работы функции (при прочих приблизительно равных).
          vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
            Цитата Jin X @
            А если у нас будет несколько хороших вариантов, то будет из чего выбирать...
            Ну т.е. открываем справочник по инструкциям, включаем фантазию и набираем мульён вариантов. А критерии сравнения для выбора формулируем как? На языке Теории Групп?
            Одни с годами умнеют, другие становятся старше.
              Как какие критерии? Скорость. Вызываем функцию (по наиболее частому сценарию или со случайными данными), замеряем скорость, сравниваем с другой... какие проблемы?
              И зачем миллион вариантов? К чему перебирать очевидно глупые варианты? Нормальных вариантов-то, по сути, не так много. Десяток-другой от силы наберётся. И то с трудом.
              vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                Цитата Jin X @
                Давай ещё для обмена 2-х элементов памяти

                Аналогично
                ExpandedWrap disabled
                  push [ecx]
                  mov eax,[edx]
                  mov [ecx],eax
                  pop eax
                  mov [edx],eax

                Кол-во инструкций то же, что и в варианте с xor, но работать должно быстрее, т.к. вместо одной цепочки из 5 зависимых операций используется две независимых цепочки 3+2 - один из основных рулов оптимизации break dependance chain реально рул-ит :)
                  leo, а в чём прикол последних двух инструкций (вместо просто pop [edx])?
                  По-любому же pop eax не может выполниться раньше, чем mov [edx],eax...

                  В цикле разница в скорости не заметна, а вот по 1 разу наблюдается интересная картина:
                  Именно в таком виде вариант с pop eax работает быстрее.
                  Но! Если заменить [ecx] и [edx] на [ebp-4] и [ebp-8] (т.е. локальные переменные функции), то быстрее начинает работать вариант с pop [ebp-8].
                  Это при том, что в первом варианте перед этим делается lea ecx,[ebp-4] + lea edx,[ebp-8] (и тут неважно: делаю я это непосредственно перед этими манипуляциями или перед rdtscp, которая производит сериализацию... но тут я, естественно, уже использую esi и edi, а не ecx и edx). Вот эту загадку хотелось бы разгадать ещё...

                  Добавлено
                  Кстати, вариант:
                  ExpandedWrap disabled
                    push [ecx]
                    mov eax,[edx]
                    pop [edx]
                    mov [ecx],eax
                  Чуть короче и работает немного быстрее твоего (и в цикле, и по 1 почти всегда, но точно не медленнее).

                  Но всё равно:
                  ExpandedWrap disabled
                    push [ebp-4]
                    mov eax,[ebp-8]
                    pop [ebp-8]
                    mov [ebp-4],eax
                  Немного быстрее. Почему???!!!!! :blink:
                  vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                    Ещё (про обмен регистра с памятью):
                    ExpandedWrap disabled
                      push eax
                      mov eax,[ecx]
                      pop [ecx]
                    как будто бы немного быстрее работает (результаты тестов нестабильные, но ощущение такое)...
                    И опять же, есть разница: используется ли именно [ecx] или [ebp-4].
                    vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                      Цитата Jin X @
                      leo, а в чём прикол последних двух инструкций (вместо просто pop [edx])?

                      Это не прикол, а "бездумное" применение общего правила оптимизации - avoid complex instructions. По количеству макро- и микро-опов эти варианты полностью эквивалентны. Но pop m состоит из двух макро-опов, поэтому в Intel Core она может декодироваться только на первом декодере в начале такта. В общем случае это может приводить к неполному использованию пропускной способности декодера. Например, в моем "тупом" варианте декодер загружен на 100% - в первом такте проходят сложная push m и следующие за ней две простых команды, во втором - две простых и плюс еще две простых из последующего окружения, например, управления цикла - dec r + jnz. А в твоем варианте, декодирование pop m переносится на второй такт, что приводит к переносу в следующий такт одной из команд последующего окружения - например, если это цикл с dec r + jnz, то декодирование jnz сдвигается на следующий такт и приводит к чистой потере одного такта (т.к. после jсс декодирование и выполнение следующей итерации цикла всегда начинается с нового такта).
                      Однако, пропускная способность декодера это далеко не самый главный, и не самый тонкий\блошиный фактор оптимизации. Например, если управление циклом состоит не из двух простых команд, а из трех и более, то переход jcc по любому смещается на следующий такт, поэтому замена двух простых команд на сложную pop m, может и не приводить к потере такта на jcc. Но самым тонким моментом является конфликт портов исполнения команд, который невозможно предусмотреть иначе, как либо теоретически - расписав всю последовательность предполагаемого исполнения микроопов, либо практически - с помощью обезьяньей игры в перестановку команд. А в данном коде вероятность таких конфликтов весьма высока, т.к. весь код состоит только из загрузки и выгрузки в память. Поэтому не исключено, что использование pop m в данном коде приводит к реальному выигрышу за счет устранения конфликта портов несмотря на теоретический проигрыш в пропускной способности декодера.
                        Всё ясно, спасибо за разъяснение :victory:
                        А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит?

                        Добавлено
                        А вообще, ты знаешь, leo, всё-таки твой код (без цикла) работает быстрее, чем
                        ExpandedWrap disabled
                          push [ecx]
                          mov eax,[edx]
                          pop [edx]
                          mov [ecx],eax
                        Я немного оптимизировал измерялку, получилось быстрее (и результаты стабильнее). Хотя в цикле получилось так же.
                        И замена [ecx] на [ebp-4] не влияет уже на скорость :)
                        Но в сравнении с
                        ExpandedWrap disabled
                          push [ecx]
                          mov eax,[edx]
                          mov [ecx],eax
                          pop [edx]
                        получилось так же (в т.ч. в цикле).

                        И даже
                        ExpandedWrap disabled
                          push [ecx]
                          mov [ecx],eax
                          pop eax
                        немного быстрее, чем:
                        ExpandedWrap disabled
                          push eax
                          mov eax,[ecx]
                          pop [ecx]
                        (хотя это, вероятно, уже из-за влияния окружения, даже несмотря на то, что непосредственно перед кодом стоит cpuid, а после rdtscp). Это как раз тот случай, когда нужно просто тупо пробовать оба варианта :)

                        Добавлено
                        Жалко wbinvd из-под юзера сделать нельзя... <_<
                        (хотя для данного кода это вряд ли на что-то повлияло бы)
                        vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                          Если кому интересно (D7) :)

                          Прикреплённый файлПрикреплённый файлSpdTest.zip (203,02 Кбайт, скачиваний: 17)
                          vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                            Цитата Jin X @
                            А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит?

                            Приходжит в голову кэш.
                            EBP у тебя же на стековый фрэйм указывает, правильно?
                            Стэк скорее всего уже в кэш заружен, а другой участок памяти загружается при первом обращении если до этого не использовался.
                              cppasm, я ж говорю: в ecx предварительно загружается адрес ebp-4 (lea ecx,[ebp-4]).
                              vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                                Цитата Jin X @
                                А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит?

                                Во-первых, не факт, что есть реальное ускорение, а не глюки тестирования на уровне "ловли блох", поскольку
                                Цитата Jin X @
                                Я немного оптимизировал измерялку, ...
                                И замена [ecx] на [ebp-4] не влияет уже на скорость

                                Во-вторых, не исключено, что в Intel Core в общем случае действительно м.б. разница между этими вариантами. Это связано с проблемой "чтения после записи", когда опережающее (или одновременное) чтение возможно только в том случае, когда адрес\размер чтения не перекрывается с адресом\размером предыдущей записи (пока она еще не выполнена). Поэтому осторожные AMD всегда сначала вычисляют реальные адреса чтения\записи и выполняют опережающее чтение только в случае несовпадения адреса с предыдущей записью (отсюда и известная проблема AMD под названием AGI - address generation interlock). В нагло-бесшабашных P4, наоборот, никаких предварительных проверок совпадения адресов не делалось, и возможные ошибки устранялись за счет ужасно тормозного replay (перезапуска конвеера с места ошибочного чтения). А в P6, и особенно в Intel Core (судя по фичам в документации) используется некий предварительный анализ возможности\невозможности совпадения адресов еще на стадии планирования, а не исполнения команд (коронная фраза - address to bee seemd not the same). При этом чтение\запись с адресацией через один и тот же регистр, но с разными смещениями типа [ebp-4] и [ebp-8], как раз поддаются анализу на стадии планирования, т.к. конкретное значение регистра ebp тут роли не играет, и планировщик может сделать вывод о несовпадении адресов чисто по коду микрооперации (индекс регистра одинаковый, а смещения разные). Соотв-но, это может давать некоторый выигрыш за счет опережающего запуска команд чтения.

                                PS: Но как в конкретном варианте #8 с ebp этот простой механизм не действует, т.к. push [ebp-4] пишет по адресу относительно esp, а следующий mov eax, [ebp-8] читает относительно ebp. Поэтому либо действуют какие-то другие механизмы, если выигрыш реально есть, либо его нет и все объясняется несовершенством тестирования.
                                  Возможно, это косяк программы для теста. Тем не менее, изменения были конкретно после замены [ecx] и [edx] на [ebp-...], так что не исключено :)
                                  vpmultishiftqb vscatterpf0dps vfmsubadd132pd vgatherpf1dps vpclmulhqlqdq vcmptrue_ussd vaeskeygenassist
                                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                  0 пользователей:


                                  Рейтинг@Mail.ru
                                  [ Script Execution time: 0,1726 ]   [ 18 queries used ]   [ Generated: 17.07.18, 11:39 GMT ]