虚数の情緒」と一緒に購入した。

棚から声がしたのである。「俺を買え」、と。

「英語版は持っている上に、Google Booksで試し読みまで出来るのに、なぜ?」、と心の中で抗議したのだが、結局買ってしまった。戻ったら案の定英語版が行方不明になっている上、日本語版は単なる翻訳ではなかったからである。訳注も充実している上、原著の証明に不足があればそれまで補完している。

これは楽しい。楽しすぎる。

しかもそれで終わらない。すこぶる役にたっているのだ。

たとえあなたがプログラムを一行も書かなかったとしても。

一時ネガティブな言葉として定着しそうになった「ハッカー」という言葉も、昨今ではほぼ完全に復権しているが、それだけにあまりに幅広い範囲で使われるようになったが、本書「ハッカーのたのしみ」におけるハックは、「Binary Hacks」よりさらに一段下のレベル、すなわちアセンブラー一命令単位のハックである。

目次
推薦の辞[和田英一]
序文[Guy L. Steele, Jr.]
まえがき
第1章 序論
第2章 基本操作
第3章 2の冪乗の境界
第4章 算術的な境界
第5章 ビットの数え上げ
第6章 ワードの探索
第7章 ビットやバイト単位の並べ替え
第8章 乗算
第9章 整数除算
第10章 整数定数による除算
第11章 いくつかの初等関数
第12章 数の表現のための一風変わった基数
第13章 グレイコード
第14章 ヒルベルト曲線
第15章 浮動少数点
第16章 素数に関する式
付録A 4ビットマシンのための算術表
付録B ニュートン表
参考文献
索引

邦訳が出た際に、「404 Blog Not Found:C - でも一番右端の立っているビット位置を求めてみた」のようなことがちょっと流行ったが、本書に出てくるdelightはこういう「バイナリーハッカーにしかわからない」ものだけではない。

たとえば、除算。ただの割り算。人間にとっても四則演算のうちで最も難解なこれは、計算機にとっても苦手な作業の一つであり、本書はこのためだけに二章を割いている。本書の中で著者が最も力を注いでいるのもここだ。

計算機がどれほど割り算を苦手としているかは、以下のベンチマークを走らせてみればわかる。

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

typedef unsigned long long U64;

double timeu(){
    struct timeval now;
    gettimeofday(&now, NULL);
    return now.tv_sec + now.tv_usec/1e6;
}

int main (int argc, char **argv){
    U64 i, q = 0, count = 0;
    double t;
    if (argc > 1){
        count = (U64)atof(argv[1]);
        printf("count = %lld\n====\n", count);
        for (t = timeu(), i = 1; i <= count; i++);
        printf("nop  :%.6gs (q=%lld)\n", timeu() - t, q);
        for (t = timeu(), i = 1; i <= count; i++) q = count + i;
        printf("add +:%.6gs (q=%lld)\n", timeu() - t, q);
        for (t = timeu(), i = 1; i <= count; i++) q = count - i;
        printf("sub -:%.6gs (q=%lld)\n", timeu() - t, q);
        for (t = timeu(), i = 1; i <= count; i++) q = count * i;
        printf("mul *:%.6gs (q=%lld)\n", timeu() - t, q);
        for (t = timeu(), i = 1; i <= count; i++) q = count / i;
        printf("div /:%.6gs (q=%lld)\n", timeu() - t, q);
    }
    return 0;
}

以下はいずれも count = 1e9 = 10億での結果。

iMac Core i7 (Mac OS X v10.6.4; x86_64)
nop  :0.603048s (q=0)
add +:0.601698s (q=2000000000)
sub -:0.620025s (q=0)
mul *:0.598731s (q=1000000000000000000)
div /:6.1419s (q=1)
ServersMan VPS (CentOS 5.5; i386)
nop  :8.06095s (q=0)
add +:8.12022s (q=2000000000)
sub -:8.11993s (q=0)
mul *:14.7257s (q=1000000000000000000)
div /:49.1856s (q=1)

ただ苦手なだけではなく、飛び抜けて苦手といって良いだろう。

それではユーザーは「ただ割り算が終わるのを待つ」しかないのだろうか?

GCCですらただ待たせるようなコードを吐かないことは、以下を見ればわかる。

変数で割るときは(例えばFreeBSD/i386では)こうなるが…

int div7d(int d){
    return 7 / d;
};
div7d:
        pushl   %ebp
        movl    $7, %edx
        movl    %esp, %ebp
        movl    %edx, %eax
        sarl    $31, %edx
        idivl   8(%ebp)
        popl    %ebp
        ret

定数で割る時はこうなる。

int divn7(int n){
    return n / 7;
};
divn7:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %ecx
        pushl   %ebx
        movl    $-1840700269, %ebx
        movl    %ebx, %eax
        popl    %ebx
        imull   %ecx
        popl    %ebp
        leal    (%edx,%ecx), %eax
        sarl    $2, %eax
        sarl    $31, %ecx
        subl    %ecx, %eax
        ret

命令が長くなっている上、-1840700269なんて数字が入っていて、しかもこれを掛け算している。WTF?

にも関わらず、これが高速であることは、上のベンチマークコードのmain()を以下に差し替えてみるとわかる。

int main (int argc, char **argv){
    int i, q = 0, count = 0;
    double t;
    if (argc > 1){
    	count = (int)atof(argv[1]);
    	for (t = timeu(), i = 1; i <= count; i++) q = 7 / i;
    	printf("%8s:%gs (q=%d)\n",  "7 / d", timeu() - t, q);
    	for (t = timeu(), i = 1; i <= count; i++) q = i / 7;
    	printf("%8s:%gs (q=%d)\n",  "n / 7", timeu() - t, q);
    }
    return 0;
}
iMac
   7 / d:3.26613s (q=0)
   n / 7:1.2568s (q=142857142)

速くなったのはわかった。しかしいったいこれはなんなのだ!?

本書の第10章を見れば、わかる。

見てのとおり、このトリックをGCCは知っている上、ユーザーに見えない形で活用している。単なるユーザーは、本書の知見をほとんど必要としないだろう。コンパイラーがよきにはからってくれるのだから。しかし一流の大工たちは、仕事を始める前にまず刃物を研ぐ。刃先を使い捨てに出来る時代にあってもそうしている。

その意味で、本書はプログラマーにとっての砥石なのである。

使い捨ての刃先に頼る、使い捨てのプログラマーに満足できないあなたにとって、これほどのよろこびがあるだろうか。

Dan the Delighted

それにしても、英語版どこいっちゃったんだろ…