Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.147.79.32] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Как известно, инструкция 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] Задача №2 (усложнённая). Нам нужно обменять 2 элемента в памяти (а-ля xchg [ecx],[edx]). В распоряжении у нас максимум 1 регистр. То бишь такое не прокатит: mov eax,[edx] mov ebx,[ecx] mov [edx],ebx mov [ecx],eax Тут, конечно, относительно быстрым будет: 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] Но хочется большего!!! Покумекаем? p.s. Всяческие варианты с MMX/SSE (или каким-нибудь особенным набором инструкций) прошу не предлагать как основные решения. Как дополнительные – ну ок, сгодятся. |
Сообщ.
#2
,
|
|
|
Цитата Jin X @ пока в голову не приходит ничего лучше, чем: push [ecx] mov [ecx], eax pop eax |
Сообщ.
#3
,
|
|
|
Jin X, ты ж понимаешь, что это баловство? Скорость будет зависеть от любого чиха в окружении. Элементарно вдруг окажется, что параллельное ядро решило инвалидировать интересную строку кеша. Плюс зависимости по регистрам в окаймляющем коде. Плюс ветвления с неоднозначной предсказуемостью незадолго до или после. Плюс зависимости от исполнительных блоков, которые ты каким-нибудь xadd и/или sub отнимешь у команд за десяток инструкций от своего "xchg". ИМХО просто не используешь xchg, и этого достаточно. Ибо главный тормоз тут lock, который вносит избыточную упорядоченность в исполнительный поток. Нет lock, нет проблемы, остальное от лукавого.
|
Сообщ.
#4
,
|
|
|
leo, отличный вариант, кстати! Давай ещё для обмена 2-х элементов памяти
Qraizer, есть вещи, на которые мы можем повлиять (какие инструкции использовать и как их сочетать с другими), а есть те, на которые не можем (параллельные процессы, ядро и пр). Наша задача работать с тем, на что мы повлиять можем. Согласись, что всегда один код (или инструкция) будет работать "в среднем" быстрее, чем другой. А в некоторых случаях всегда быстрее (типа dec ecx+jnz против loop, если не брать во внимание 8086 и т.п. экзотику). Например, вариант от leo по любому будет быстрее, чем 2 push'а и pop'а. А если у нас будет несколько хороших вариантов, то будет из чего выбирать... По крайней мере, мы всегда можем вставить разные варианты в критические участки кода и потом сравнить общую скорость работы функции (при прочих приблизительно равных). |
Сообщ.
#5
,
|
|
|
Цитата Jin X @ Ну т.е. открываем справочник по инструкциям, включаем фантазию и набираем мульён вариантов. А критерии сравнения для выбора формулируем как? На языке Теории Групп? А если у нас будет несколько хороших вариантов, то будет из чего выбирать... |
Сообщ.
#6
,
|
|
|
Как какие критерии? Скорость. Вызываем функцию (по наиболее частому сценарию или со случайными данными), замеряем скорость, сравниваем с другой... какие проблемы?
И зачем миллион вариантов? К чему перебирать очевидно глупые варианты? Нормальных вариантов-то, по сути, не так много. Десяток-другой от силы наберётся. И то с трудом. |
Сообщ.
#7
,
|
|
|
Цитата Jin X @ Давай ещё для обмена 2-х элементов памяти Аналогично push [ecx] mov eax,[edx] mov [ecx],eax pop eax mov [edx],eax Кол-во инструкций то же, что и в варианте с xor, но работать должно быстрее, т.к. вместо одной цепочки из 5 зависимых операций используется две независимых цепочки 3+2 - один из основных рулов оптимизации break dependance chain реально рул-ит |
Сообщ.
#8
,
|
|
|
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). Вот эту загадку хотелось бы разгадать ещё... Добавлено Кстати, вариант: push [ecx] mov eax,[edx] pop [edx] mov [ecx],eax Но всё равно: push [ebp-4] mov eax,[ebp-8] pop [ebp-8] mov [ebp-4],eax |
Сообщ.
#9
,
|
|
|
Ещё (про обмен регистра с памятью):
push eax mov eax,[ecx] pop [ecx] И опять же, есть разница: используется ли именно [ecx] или [ebp-4]. |
Сообщ.
#10
,
|
|
|
Цитата 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 в данном коде приводит к реальному выигрышу за счет устранения конфликта портов несмотря на теоретический проигрыш в пропускной способности декодера. |
Сообщ.
#11
,
|
|
|
Всё ясно, спасибо за разъяснение
А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит? Добавлено А вообще, ты знаешь, 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] Добавлено Жалко wbinvd из-под юзера сделать нельзя... (хотя для данного кода это вряд ли на что-то повлияло бы) |
Сообщ.
#12
,
|
|
|
Сообщ.
#13
,
|
|
|
Цитата Jin X @ А вот с ускорением после замены [ecx] на [ebp-4] ничего в голову не приходит? Приходжит в голову кэш. EBP у тебя же на стековый фрэйм указывает, правильно? Стэк скорее всего уже в кэш заружен, а другой участок памяти загружается при первом обращении если до этого не использовался. |
Сообщ.
#14
,
|
|
|
cppasm, я ж говорю: в ecx предварительно загружается адрес ebp-4 (lea ecx,[ebp-4]).
|
Сообщ.
#15
,
|
|
|
Цитата 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. Поэтому либо действуют какие-то другие механизмы, если выигрыш реально есть, либо его нет и все объясняется несовершенством тестирования. |