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

邦訳が出た際に、「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億での結果。

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)

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;
}

   7 / d:3.26613s (q=0)
   n / 7:1.2568s (q=142857142)

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

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

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

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

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

Dan the Delighted

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