80286: Какой самый быстрый способ умножить на 10?

Чтобы умножить число на любое кратное 2, я сдвину его столько раз.

Есть ли такая техника, чтобы умножить число на 10 за меньшее количество циклов?


assembly x86-16 micro-optimization
person Project Zero    schedule 04.04.2020    source источник
comment
Конкретно на 80286, поэтому немедленные сдвиги доступны, но imul reg,reg,10 медленный, а 32-битные режимы адресации, такие как lea ax, [eax + eax*4], недоступны для дешевого x * 5? Заботитесь ли вы о производительности кода на любых более поздних или более ранних процессорах, если то, что оптимально для 286, не является оптимальным в другом месте? У вас есть ссылка на тайминги инструкций 80286?   -  person Peter Cordes    schedule 04.04.2020
comment
Сдвинуть, добавить, сдвинуть? 10*x = (4*x + x) * 2 = ((x << 2) + x) << 1. Это так же, как вы делаете длинное умножение вручную.   -  person Nate Eldredge    schedule 04.04.2020
comment
Да, мой старый друг, сейчас я кодирую только для 80286 (16-бит).   -  person Project Zero    schedule 04.04.2020
comment
@NateEldredge Как значение x останется постоянным при его добавлении после сдвига битов?   -  person Project Zero    schedule 04.04.2020
comment
Вы сохраняете его в другом регистре. mov bx, ax ; shl ax, 2 ; add ax, bx ; shl ax, 1.   -  person Nate Eldredge    schedule 04.04.2020
comment
@NateEldredge: Да, я думаю, что мы застряли в чем-то подобном. Но add same,same быстрее или медленнее, чем shl reg,1 на 286 для этого последнего шага? Вероятно, не имеет значения, в каком порядке вы что-то делаете; 286 не может использовать ILP в x*2 + x*8, и я думаю, что нам нужен 1 mov. Если у вас уже не было значений в SI|DI и BX|BP, вы можете начать с lea ax, [bx + si] или чего-то еще, начиная с x*2   -  person Peter Cordes    schedule 04.04.2020
comment
Будет ли он эффективнее MUL?   -  person Project Zero    schedule 04.04.2020
comment
@ProjectZero: На 286, да, значительно. Порог для выполнения сдвигов/сложений вместо mul с помощью константы составляет как минимум несколько установленных битов даже на P5 Pentium; 10 имеет только 2 установленных бита. На современном Nehalem или более поздних версиях да, лучше, чем 1-операнд mul, но не лучше, чем imul ax, bx, 10. (задержка 3 такта, пропускная способность 1/такт, 1 мкп)   -  person Peter Cordes    schedule 04.04.2020
comment
Может ли кто-нибудь из вас опубликовать ответ, чтобы я мог его принять?   -  person Project Zero    schedule 04.04.2020
comment
Я не уверен, как сравнить смену и добавление, но вы также можете сделать это с четырьмя добавлениями: mov bx, ax ; add ax, ax ; add ax, ax ; add ax, bx ; add ax, ax.   -  person Nate Eldredge    schedule 04.04.2020
comment
Не зная, где найти временную таблицу из 286 инструкций, я не знаю, какой будет самая быстрая версия, поэтому не знаю ответа. Общий метод разбиения умножения на сдвиги и сложения/субпозиции хорошо известен и не является чем-то новым. (Кстати, я упоминал P5 Pentium ранее, потому что вы можете видеть, как GCC оптимизирует умножение на константы при настройке для него с помощью gcc -O3 -march=pentium. Или даже -march=i386. godbolt.org/z/qjD-a3. О, вы могли бы скомпилировать для MIPS, чтобы ограничить GCC только использованием сдвигов и добавления/подписки, а не x86 LEA. Или, может быть, MPS430 как 2- операндная машина.   -  person Peter Cordes    schedule 04.04.2020

Ответы (1)


arrow_upward
4
arrow_downward

В модели 80286 не было переключателя цилиндров, который был представлен в модели 80386. Согласно временным таблицам в документации Microsoft Macro Assembler 5.0 (1987 г.), SHL reg, immed8 занимает 5+n циклов, тогда как SHL reg, 1 занимает 2 цикла. ADD reg, reg занимает 2 цикла, как и MOV reg, reg. IMUL reg16, immed занимает 21 цикл. Следовательно, самый быстрый способ умножить на десять выглядит следующим образом:

           ;       // cycles
shl ax, 1  ; *2    // 2
mov bx, ax ; *2    // 4
shl ax, 1  ; *4    // 6
shl ax, 1  ; *8    // 8
add ax, bx ; *10   // 10

или, альтернативно:

           ;      // cycles
mov bx, ax ; *1   // 2
shl ax, 1  ; *2   // 4
shl ax, 1  ; *4   // 6
add ax, bx ; *5   // 8
shl ax, 1  ; *10  // 10

Десять циклов в любом случае.

person njuffa    schedule 04.04.2020