Форум на Исходниках.RU

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Tue, 19 Dec 2017 14:10:02 +0000

Jin X: Возможно, это косяк программы для теста. Тем не менее, изменения были конкретно после замены [ecx] и [edx] на [ebp-...], так что не исключено :)

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

leo — Tue, 19 Dec 2017 08:06:56 +0000

leo:

Цитата Jin X @ 17.12.17, 11:09

А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит?

Во-первых, не факт, что есть реальное ускорение, а не глюки тестирования на уровне "ловли блох", поскольку

Цитата Jin X @ 17.12.17, 11:09

Я немного оптимизировал измерялку, ...
И замена [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. Поэтому либо действуют какие-то другие механизмы, если выигрыш реально есть, либо его нет и все объясняется несовершенством тестирования.

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Mon, 18 Dec 2017 21:03:05 +0000

Jin X: cppasm, я ж говорю: в ecx предварительно загружается адрес ebp-4 (lea ecx,[ebp-4]).

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

cppasm — Mon, 18 Dec 2017 09:49:58 +0000

cppasm:

Цитата Jin X @ 17.12.17, 11:09

А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит?

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

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Sun, 17 Dec 2017 11:54:41 +0000

Jin X: Если кому интересно (D7) :)

SpdTest.zip (, : 152)

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Sun, 17 Dec 2017 11:09:47 +0000

Jin X: Всё ясно, спасибо за разъяснение :victory:
А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит?

Добавлено 17.12.17, 11:42
А вообще, ты знаешь, leo, всё-таки твой код (без цикла) работает быстрее, чем

push [ecx]

mov eax,[edx]

pop [edx]

mov [ecx],eax

Я немного оптимизировал измерялку, получилось быстрее (и результаты стабильнее). Хотя в цикле получилось так же.
И замена [ecx] на [ebp-4] не влияет уже на скорость :)
Но в сравнении с

push [ecx]

mov eax,[edx]

mov [ecx],eax

pop [edx]

получилось так же (в т.ч. в цикле).

И даже

push [ecx]

mov [ecx],eax

pop eax

немного быстрее, чем:

push eax

mov eax,[ecx]

pop [ecx]

(хотя это, вероятно, уже из-за влияния окружения, даже несмотря на то, что непосредственно перед кодом стоит cpuid, а после rdtscp). Это как раз тот случай, когда нужно просто тупо пробовать оба варианта :)

Добавлено 17.12.17, 11:49
Жалко wbinvd из-под юзера сделать нельзя... <_<
(хотя для данного кода это вряд ли на что-то повлияло бы)

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

leo — Sun, 17 Dec 2017 08:32:44 +0000

leo:

Цитата Jin X @ 16.12.17, 12:34

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

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Sat, 16 Dec 2017 21:22:06 +0000

Jin X: Ещё (про обмен регистра с памятью):

push eax

mov eax,[ecx]

pop [ecx]

как будто бы немного быстрее работает (результаты тестов нестабильные, но ощущение такое)...
И опять же, есть разница: используется ли именно [ecx] или [ebp-4].

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Sat, 16 Dec 2017 12:34:40 +0000

Jin X: 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). Вот эту загадку хотелось бы разгадать ещё...

Добавлено 16.12.17, 12:43
Кстати, вариант:

push [ecx]

mov eax,[edx]

pop [edx]

mov [ecx],eax

Чуть короче и работает немного быстрее твоего (и в цикле, и по 1 почти всегда, но точно не медленнее).

Но всё равно:

push [ebp-4]

mov eax,[ebp-8]

pop [ebp-8]

mov [ebp-4],eax

Немного быстрее. Почему???!!!!! :blink:

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

leo — Sat, 16 Dec 2017 11:26:25 +0000

leo:

Цитата Jin X @ 14.12.17, 19:46

Давай ещё для обмена 2-х элементов памяти

Аналогично

push [ecx]

mov eax,[edx]

mov [ecx],eax

pop eax

mov [edx],eax

Кол-во инструкций то же, что и в варианте с xor, но работать должно быстрее, т.к. вместо одной цепочки из 5 зависимых операций используется две независимых цепочки 3+2 - один из основных рулов оптимизации break dependance chain реально рул-ит :)

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Thu, 14 Dec 2017 23:58:54 +0000

Jin X: Как какие критерии? Скорость. Вызываем функцию (по наиболее частому сценарию или со случайными данными), замеряем скорость, сравниваем с другой... какие проблемы?
И зачем миллион вариантов? К чему перебирать очевидно глупые варианты? Нормальных вариантов-то, по сути, не так много. Десяток-другой от силы наберётся. И то с трудом.

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Qraizer — Thu, 14 Dec 2017 21:40:01 +0000

Qraizer:

Цитата Jin X @ 14.12.17, 19:46

А если у нас будет несколько хороших вариантов, то будет из чего выбирать...

Ну т.е. открываем справочник по инструкциям, включаем фантазию и набираем мульён вариантов. А критерии сравнения для выбора формулируем как? На языке Теории Групп?

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Thu, 14 Dec 2017 19:46:47 +0000

Jin X: leo, отличный вариант, кстати! Давай ещё для обмена 2-х элементов памяти ;)

Qraizer, есть вещи, на которые мы можем повлиять (какие инструкции использовать и как их сочетать с другими), а есть те, на которые не можем (параллельные процессы, ядро и пр). Наша задача работать с тем, на что мы повлиять можем. Согласись, что всегда один код (или инструкция) будет работать "в среднем" быстрее, чем другой. А в некоторых случаях всегда быстрее (типа dec ecx+jnz против loop, если не брать во внимание 8086 и т.п. экзотику).
Например, вариант от leo по любому будет быстрее, чем 2 push'а и pop'а. А если у нас будет несколько хороших вариантов, то будет из чего выбирать... По крайней мере, мы всегда можем вставить разные варианты в критические участки кода и потом сравнить общую скорость работы функции (при прочих приблизительно равных).

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Qraizer — Thu, 14 Dec 2017 13:09:44 +0000

Qraizer: Jin X, ты ж понимаешь, что это баловство? Скорость будет зависеть от любого чиха в окружении. Элементарно вдруг окажется, что параллельное ядро решило инвалидировать интересную строку кеша. Плюс зависимости по регистрам в окаймляющем коде. Плюс ветвления с неоднозначной предсказуемостью незадолго до или после. Плюс зависимости от исполнительных блоков, которые ты каким-нибудь xadd и/или sub отнимешь у команд за десяток инструкций от своего "xchg". ИМХО просто не используешь xchg, и этого достаточно. Ибо главный тормоз тут lock, который вносит избыточную упорядоченность в исполнительный поток. Нет lock, нет проблемы, остальное от лукавого.

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

leo — Thu, 14 Dec 2017 12:50:38 +0000

leo:

Цитата Jin X @ 13.12.17, 20:43

пока в голову не приходит ничего лучше, чем:

push [ecx]

mov [ecx], eax

pop eax

Ускорить xchg с памятью. Вопрос на засыпку по оптимизации!

Jin X — Wed, 13 Dec 2017 20:43:32 +0000

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

Давайте подумаем: чем можно заменить эту инструкцию (скажем, xchg [ecx],eax) для максимизации скорости?
Конечно, первое, что приходит в голову – это:

mov edx,[ecx]

mov [ecx],eax

mov eax,edx

Скорость взлетает ощутимо – проверено.
Но! Тут используется дополнительный регистр! А если лишнего регистра нет? Что делать?

Может, я откровенно туплю, но пока в голову не приходит ничего лучше, чем:

push eax

push [ecx]

pop eax

pop [ecx]

или

xadd [ecx],eax

sub [ecx],eax

Но второй вариант работает даже медленнее, чем первый (в цикле, по крайней мере)!!!

Ах, да, есть же ещё:

xor eax,[ecx]

xor [ecx],eax

xor eax,[ecx]

Он работает быстрее, чем xadd и чуть быстрее, чем push/pop в цикле (и тем более xchg), но скорость всё равно низкая...

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

mov eax,[edx]

mov ebx,[ecx]

mov [edx],ebx

mov [ecx],eax

(тут 2 регистра)

Тут, конечно, относительно быстрым будет:

mov eax,[ecx]

xor eax,[edx]

xor [edx],eax

xor eax,[edx]

mov [ecx],eax

А вот это:

fld dword ptr [ecx]

fld dword ptr [edx]

fstp dword ptr [ecx]

fstp dword ptr [edx]

...ещё быстрее варианта с xor (примерно вдвое!) :D

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

p.s. Всяческие варианты с MMX/SSE (или каким-нибудь особенным набором инструкций) прошу не предлагать как основные решения. Как дополнительные – ну ок, сгодятся.