NF

地方で働くプログラマ

4回目:乗算の代わりにシフト演算

三日坊主回避。3日くらい過ぎてるけど。
というか、調べてたら色々発散してまとまらなくなりました。取り合えず今回は触りだけ。

概要

今回は、乗算命令は遅いのでシフト演算が使われるよという話。多分有名ですね(除算の方が有名かも)。
2のべき乗に分解できる値との乗算であれば、シフト演算と加算だけで計算でき、そっちの方が計算が高速に出来るそうです。今回は、下の記事にある、ある値(Aとします)を144倍するのを実際やってみます。
41年経った今でも使える、いにしえのx86マシン語AAAをMacで動かす #asm #riscv #x86 / 福野泰介の一日一創 / Create every day by Taisuke Fukuno
 
A × 144 = (A × 128) + (A × 16) = (A × 2^7) + (A × 2^3) という変換を利用します。
(A × 2のべき乗)の部分は左シフトで計算できるので、シフトと加算だけになりますね。例えば(5 × 2^3)の答えは40ですが、5(=101)を3bitシフトすると101000で、これは32+8でちゃんと40ですね。
 
ちなみに最初、2^7なのになんで7bitじゃなくて3bitシフトしかしてないんだろう…と思いましたが、これは(2^4 + 2^7)の部分を(2^4 + (2^4 × 2^3))みたいに変換して共通項を出してるんですね。中学数学(算数?)の復習みたいです。

実践

実際にCentOS7(x86)でアセンブラを出力してみます。このコードをg++ -Sでasmを出力。

int
main(int argc, char* argv[])
{
    printf("%d", argc * 144);  // (1)では147
}

 

(1) 2のべき乗に分解できない数の乗算

まずは2のべき乗に分解できない適当な数(ここでは147(素数ですらない))で試します。
差分の出る箇所だけ抜粋すると、以下のようなコードが出力されます。

movl    8(%ebp), %eax
imull   $147, %eax, %eax

定数「147」が見えてます。知識ないですが多分、1行目がスタックの値(argc)を%eax(eaxレジスタ)に設定、2行目で定数$147と%eaxの乗算結果を%eaxに格納していそうです。
 

(2) 2のべき乗に分解できる数の乗算(最適化なし)

定数を144(=128+16)に変更します。ただし最適化オプションは指定しないので、(1)と同じように定数で「144」が見えると思います…と思ったら違いました。

movl    8(%ebp), %edx
movl    %edx, %eax
sall    $3, %eax
addl    %edx, %eax
sall    $4, %eax

という訳で、最適化しなくても乗算が消えてました。びっくりした。
このコードは、乗算1回の代わりにシフト演算・加算・シフト演算で計算しています。式にすると(((A × 2^3) + A) × 2^4)みたいな感じですかね。
 

(3) 2のべき乗に分解できる数の乗算(最適化あり)

では最適化したらどうなるか。g++ -O2で出力します。

movl    8(%ebp), %edx
movl    $.LC0, %esx
leal    (%eax, %eax, 8), %eax
sall    $4, %eax

salの1つが消えてleaになりました。leaのオペランド「%eax, %eax, 8」は、(eax+(eax × 8))みたいな意味だそうです。lea命令はデータ転送らしいですが、3bitシフトの代わりに定数8を使って同じ計算してます。よく分からないですが、シフトするよりも早いのでしょう。
 
という訳で、昨今の環境でも乗算はシフト演算等に置き換えられてる事が分かりました。

補足情報&リンク集

この辺のbitシフトの話を調べてる時に、時たま「HAKMEM」という単語が出てきました。少し調べると、MITで作成された数値計算用のアルゴリズム集?みたいなもののようです。ぱっと見じゃよく分からないものばかりなので、読み解けたらこのシリーズで幾つか紹介したいと思ってます。
HAKMEM 169 and other popcount implementations
HAKMEM - Wikipedia
 
あと調べものしてた時に見つけた興味あるリンク先をメモ。これもどこかで記事書きたい。
プログラミングする上で必要な書籍および役に立った書籍:d金魚が断然お勧めする書籍
Odd Comments and Strange Doings in Unix
今までに見たソースコードで一番感動したのは
glibc/strcpy.S at master · lattera/glibc · GitHub
http://www.st.rim.or.jp/~phinloda/cqa.html