コグノスケ

100万回のHello, World!

目次: ベンチマーク

Twitterで100万回のHello, World!問題を見かけ、面白そうだったのでやってみました。消えてしまった時のためにレギュレーションを書き写しておくと、

• 設問: ループや再帰なしで100万回Hello, World!するには？
• 条件: for, while, goto, 再帰, 1000バイト越え, 外部ファイルは使用禁止

Cだとマクロを入れ子にする、setjmp/longjmpやsignalでgotoの代わりにする、辺りが設問意図のようです。C++だとクラスAのコンストラクタでHello, World!を書いておいて、A hoge[100 * 10000]のように配列宣言する方法があるみたいです。なるほどスマート。スクリプト言語だと大抵は繰り返し処理の構文があるので、あまり難しくないみたいです。最近の言語にとっては手ごたえのない問題かもしれません。

ツイートの引用をざっと見た感じだとアセンブラでやっている人がいなかったので、Cのふりしたアセンブラ（というかほぼバイナリ直書き）でチャレンジしました。

const char _start[] __attribute__((section(".text"))) = {
        0xbb, 0x40, 0x42, 0x0f, 0x00, //ebx 1000000
        0x66, 0xb8, 0x01, 0x00, //ax
        0x89, 0xc7, //edi
        0x66, 0xba, 0x0e, 0x00, //dx
        0x48, 0x8d, 0x35, 0x0c, 0x00, 0x00, 0x00, //esi
        0x0f, 0x05, //syscall
        0xff, 0xcb, //dec ebx
        0x75, 0xe9, //jne
        0x66, 0xb8, 0x3c, 0x00, //ax
        0x0f, 0x05, // syscall
        'H', 'e', 'l', 'l', 'o', ',', ' ',
        'W', 'o', 'r', 'l', 'd', '!', '\n', '\0',
};

これだけです。ソースコードのサイズは433バイトで、コメントなどは削っていませんが余裕で1000バイト以下に収まります。何が書いてあるのかわからんと思うので逆アセンブルした結果も載せます。

0000000000401000 <_start>:
  401000:       bb 40 42 0f 00          mov    $0xf4240,%ebx         ★0xf4240 = 100万
  401005:       66 b8 01 00             mov    $0x1,%ax
  401009:       89 c7                   mov    %eax,%edi
  40100b:       66 ba 0e 00             mov    $0xe,%dx
  40100f:       48 8d 35 0c 00 00 00    lea    0xc(%rip),%rsi        # 401022 <_start+0x22>
  401016:       0f 05                   syscall                      ★write(1, "Hello, World!\n", 14)に相当する
  401018:       ff cb                   dec    %ebx
  40101a:       75 e9                   jne    401005 <_start+0x5>   ★goto 2行目
  40101c:       66 b8 3c 00             mov    $0x3c,%ax
  401020:       0f 05                   syscall                      ★exit()に相当、libcを使っていないのでretするとSEGVする

★ここから下はHello, World!の文字列なので命令列としては無意味

  401022:       48                      rex.W
  401023:       65 6c                   gs insb (%dx),%es:(%rdi)
  401025:       6c                      insb   (%dx),%es:(%rdi)
  401026:       6f                      outsl  %ds:(%rsi),(%dx)
  401027:       2c 20                   sub    $0x20,%al
  401029:       57                      push   %rdi
  40102a:       6f                      outsl  %ds:(%rsi),(%dx)
  40102b:       72 6c                   jb     401099 <_start+0x99>
  40102d:       64 21 0a                and    %ecx,%fs:(%rdx)

次に動作確認しましょう。

$ gcc -static -nostdlib a.c

/tmp/ccdifyE1.s: Assembler messages:
/tmp/ccdifyE1.s:4: Warning: ignoring changed section attributes for .text

$ ./a.out | head
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!

$ ./a.out | wc
1000000 2000000 14000000

Hello, World!が繰り返し出ていること、100万行出ていること、異常事態（SEGVなど）が発生しないことを見ています。これで良さそうですね。

アセンブラで書いただけではつまらない

アセンブラでやる人がいないのは、jmp命令がgotoと同等なので当たり前にクリアできて何も面白くないからだと思います。なのでもう少しこだわって「1000バイト以下」のレギュレーションを極めましょう。

• 設問: ループや再帰なしで100万回Hello, World!するには？
• 条件: for, while, goto, 再帰, 1000バイト越え（ソースコード、バイナリともに）, 外部ファイルは使用禁止

レギュレーションを上記のように強化しました。

1000バイト以下に収めよう（バイナリも） - まずはstrip

まずは先ほど動作確認したバイナリのサイズを確認します。

$ gcc -static -nostdlib a.c

/tmp/ccdifyE1.s: Assembler messages:
/tmp/ccdifyE1.s:4: Warning: ignoring changed section attributes for .text

$ ls -la a.out

-rwxr-xr-x 1 katsuhiro suzuki 4864  2月 25 03:23 a.out

$ strip -s a.out

$ ls -la a.out

-rwxr-xr-x 1 katsuhiro suzuki 4544  2月 25 03:25 a.out

$ strip -s -R .note.gnu.build-id -R .comment a.out

strip: a.out: warning: empty loadable segment detected at vaddr=0x400000, is this intentional?

$ ls -la a.out

-rwxr-xr-x 1 katsuhiro suzuki 4360  2月 25 03:28 a.out

実質の命令列＋文字列で50バイトくらいなのにバイナリは4KBを超えています。なんだこれは。stripしても300バイトほどしか減りません。readelfで確認すると.note.gnu.build-idと.commentというセクションがstripされずに残っていたため、排除しましたが500バイトほどしか減りません。

おっと……これは？もしかして意外と難しいのか？

1000バイト以下に収めよう（バイナリも） - 変な空白を消そう

バイナリのセクションヘッダを眺めていると、なぜか.textが0x1000から配置されています。

セクションヘッダ:
  [番] 名前              タイプ           アドレス          オフセット
       サイズ            EntSize          フラグ Link  情報  整列
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000401000  00001000 ★この時点でバイナリサイズ4KBが確定
       0000000000000031  0000000000000000  AX       0     0     32
  [ 2] .shstrtab         STRTAB           0000000000000000  00001031
       0000000000000011  0000000000000000           0     0     1

デフォルトリンカースクリプト（gccに-Wl,-verboseオプションを渡すと表示できます）を調べると、特に何も指定しない場合.textは0x400000+SIZEOF_HEADERSというアドレスに配置されることがわかります。

SECTIONS
{
  PROVIDE (__executable_start = SEGMENT_START("text-segment", 0x400000));
  . = SEGMENT_START("text-segment", 0x400000) + SIZEOF_HEADERS;

SIZEOF_HEADERSを決定する仕組みがいまいち分からないですが、恐らくSIZEOF_HEADERS = 0x1000でしょう。0x400000のような大きなアドレスの場合はプログラムヘッダのロードアドレスで調整するので、0x400000の0データがバイナリに書かれることはありません。しかし一定サイズ以下（今回のような0x1000など）の場合はバイナリに0データを埋め込んで開始位置を調整するようです。

この仕組みを逆手にとって.textの開始アドレス下位をもっと手前のアドレスにずらすことで、ELFヘッダやプログラムヘッダを避けながら開始位置調整用の無駄な0データを削除できるはずです。

$ gcc -static -nostdlib -Wl,-Ttext=0x400160 a.c

$ ls -la a.out

-rwxr-xr-x  1 katsuhiro suzuki 1120  2月 25 03:43 a.out


セクションヘッダ:
  [番] 名前              タイプ           アドレス          オフセット
       サイズ            EntSize          フラグ Link  情報  整列
  [ 0]                   NULL             0000000000000000  00000000
       0000000000000000  0000000000000000           0     0     0
  [ 1] .text             PROGBITS         0000000000400160  00000160 ★0x1000から0x160に詰められた
       0000000000000031  0000000000000000  AX       0     0     32
  [ 2] .note.gnu.bu[...] NOTE             00000000004000e8  000000e8
       0000000000000024  0000000000000000   A       0     0     4
  [ 3] .comment          PROGBITS         0000000000000000  00000191
       000000000000001f  0000000000000001  MS       0     0     1
  [ 4] .symtab           SYMTAB           0000000000000000  000001b0
       0000000000000090  0000000000000018           5     2     8
  [ 5] .strtab           STRTAB           0000000000000000  00000240
       000000000000001d  0000000000000000           0     0     1
  [ 6] .shstrtab         STRTAB           0000000000000000  0000025d
       000000000000003d  0000000000000000           0     0     1

開始アドレス下位を0x1000から0x160までずらすとバイナリ中の0データ領域が減り、一気に1120バイトまで減りました。劇的な効果です。変更により動作不良を起こしていないかも忘れずにチェックします（動作チェックのログは省略）。

もう一息削れば1000バイトはすぐそこですが、、、

$ gcc -static -nostdlib -Wl,-Ttext=0x400140 a.c

/tmp/cc5LlyKi.s: Assembler messages:
/tmp/cc5LlyKi.s:4: Warning: ignoring changed section attributes for .text
/usr/bin/ld: section .text LMA [0000000000400140,0000000000400170] overlaps section .note.gnu.build-id LMA [0000000000400120,0000000000400143]
collect2: error: ld returned 1 exit status

残念ながら.textの開始アドレス下位を0x140にすると「別のセクションと重なってるぞ！」と怒られてリンクエラーになります。.note.gnu.build-idセクションと重なっているとのこと。

1000バイト以下に収めよう（バイナリも） - さようならbuild-id

とりあえず.note.gnu.build-idセクションは無くても実行できるので、-Wl,--build-id=noneで消し去ります。.note.gnu.build-idセクションがいなくなった分、.textセクションをさらに前の0x100まで詰められます。

$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none a.c

/tmp/cctmYikq.s: Assembler messages:
/tmp/cctmYikq.s:4: Warning: ignoring changed section attributes for .text

$ ls -la a.out

-rwxr-xr-x  1 katsuhiro suzuki  936  2月 25 03:52 a.out

やりました。stripに頼らずとも1000バイトを下回ることができました。最初の4KBを見たときはどうなるかと思いましたが、意外と何とかなるものです。

1000バイト以下に収めよう（バイナリも） - ダメ押しのstrip

既に目標は達成しましたが、さらに.commentセクションの排除と、stripするとどこまで減るか試しましょう。まずは.commentセクションの排除です。

$ gcc -static -nostdlib -Wl,-Ttext=0x400100 -Wl,--build-id=none -fno-ident a.c

$ ls -la a.out

-rwxr-xr-x  1 katsuhiro suzuki  840  2月 25 04:55 a.out

次はstripです。.symtabセクションと.strtabセクションが消えます。

$ strip -s ./a.out

$ ls -la　a.out

-rwxr-xr-x  1 katsuhiro suzuki  520  2月 25 04:56 a.out

サイズは520バイトまで減らせました。1000バイトの約半分です。もっと複雑な処理でも詰め込めるでしょう。私はx86_64アセンブラが得意じゃないので、何か書いてやろうという気は起きませんけど……。