Оптимизированные по размеру уже известные алгоритмы CRC, Gnome Sort etc...
User
Перемножение чисел без умножения
1 min
Как-то вдруг задумался о перемножении чисел без использования инструкций умножения.
Нужно сказать, что в корне данной задачи лежит сдвиг числа на то количество бит, на котором месте эти биты находятся. Собственно и обнаружил я эту закономерность совершенно случайно.
В результате недолгого мозгового штурма получился следующий ниже код, в регистре esi получаем произведение eax * ebx.
Разумеется представленная версия кода ограничивает результат 32-мя битами, но ведь разрядность при желании можно и расширить, главное - концепция.
Benchmark CPU's Instructions (just before loading the OS) — XCHG vs XOR, XOR, XOR
2 min
Возможно не только мне интересно, а каков микрокод инструкции XCHG на RISC для x86 CISC?Например ни для кого не секрет, что на языках высокого уровня, чтобы обменять значениями две переменные "X" и "Y", нужна ещё одна переменная, скажем "Z".
X=5, Y=7
Z=Y
Y=X
X=Z
X=7, Y=5
Но, процессоры это умеют делать командой XCHG, причём, явно никакой третьей переменной здесь вроде бы как и нет...
X=5, Y=7
XCHG X, Y
X=7, Y=5
Я даже предполагал что сама аббревиатура "XCHG", это ни что иное как "XOR CHANGE", сразу скажу что подтверждения этой догадки я нигде не встречал. Почему XOR CHANGE? Возможно потому что обмен между регистрами происходит с участием логической команды XOR.
X=5, Y=7
XOR X, Y
XOR Y, X
XOR X, Y
X=7, Y=5
Что ж, я решил проверить свою теорию, промерив продолжительность исполнения инструкции "XCHG" и её аналога "XOR, XOR, XOR". Ну а чтобы результаты были максимально детерминированными, я решил запустить всё это дело ещё до загрузки какой-либо операционной системы, т.е. сразу после того, как БИОС компьютера решит загружаться с определённого накопителя. В общем для максимальной чистоты эксперимента, я разместил приведённый ниже код прямо в MBR загрузочного диска (в своём случае я использовал флешку).
Следующий код повторяет инструкцию "XCHG EDI, EAX" 7 раз, а инструкцию "XOR" - 21 раз ну и накапливает затраченные тики процессора. Цикл для каждой тестируемой команды повторяется по 10000 раз. После чего всё это прокручивается ещё и ещё (всего 20 раз), в итоге вычисляется среднее. Как по мне, тест получается довольно "чистый", более-менее детерминированный. Ну а что касается того, равны ли по продолжительности исполнения команда XCHG и три команды XOR, то судя по этому тесту, XCHG выполняется на 5% быстрее, что никак не вписывается в мою теорию :)
