Go to Qiita Advent Calendar 2024 Top
LoginSignup
16
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@fujitanozomu(藤田 望)

最速のFizzBuzzを目指してみた

Last updated at Posted at 2017-11-25

はじめに

FizzBuzz の 100 までの結果を予め用意しておいて関数呼び出し一発で出力すりゃ速いんじゃね? という過去に誰もが思い付いた使い古されたネタです。

とりあえず C で書いてみた

とりあえず C で書いてみました。
文字列出力は、

  • puts() は文字列の終了判定で '\0' のチェックを行うので遅そう
  • printf() は '%' の判定も行うので更に遅そう
  • fwrite() は良さげだがシステムコールに近い筈の write() の方が尚良かろう

という判断で write() を使って行っています。
ソースを再帰的にインクルードし、gcc の機能であるインクルードの深さを表すマクロ __INCLUDE_LEVEL__ を参照して FizzBuzz の文字列を生成しています。

fizzbuzz.c
#if __INCLUDE_LEVEL__ == 0
  #define N 100
  #include <stdlib.h>
  #include <unistd.h>
  #include <errno.h>
  #define _toString(n) #n
  #define toString(n) _toString(n)
  static const char s[] =
#endif

#if __INCLUDE_LEVEL__ >= 1
  #if __INCLUDE_LEVEL__ % 15 == 0
    "FizzBuzz"
  #elif __INCLUDE_LEVEL__ % 3 == 0
    "Fizz"
  #elif __INCLUDE_LEVEL__ % 5 == 0
    "Buzz"
  #else
    toString(__INCLUDE_LEVEL__)
  #endif
  "\n"
#endif

#if __INCLUDE_LEVEL__ < N
  #include __FILE__
#endif

#if __INCLUDE_LEVEL__ == 0
  ;

  int main(void)
  {
      const char* p = s;
      size_t l = sizeof(s) - 1;

      while (l > 0) {
          ssize_t s;
          do {
              s = write(STDOUT_FILENO, p, l);
          } while (s < 0 && errno == EINTR);
          if (s < 0) {
              return EXIT_FAILURE;
          }
          p += s;
          l -= s;
      }
      return EXIT_SUCCESS;
  }
#endif

実行とビルドは Ubuntu 17.10.1 の amd64 版上で gcc を使用して行っています。

$ gcc -Wall -Wextra -O2 -s -Wl,--gc-sections -o fizzbuzz -Wl,-M=fizzbuzz.map fizzbuzz.c && ./fizzbuzz
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz
$

実行ファイルのサイズは 6112バイトとなりました。複数のダイナミックリンクライブラリが実行時にリンクされるようです。

$ ls -l fizzbuzz
-rwxr-xr-x 1 fujita fujita 6112 Apr  7 15:23 fizzbuzz
$ ldd fizzbuzz
	linux-vdso.so.1 =>  (0x00007ffecc319000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f1a3dce5000)
	/lib64/ld-linux-x86-64.so.2 (0x00007f1a3e2c7000)
$

`-statc' を指定して静的リンクを行ったところ、内容の割には巨大な 約700k バイトというサイズの実行ファイルとなってしまいました。

$ gcc -Wall -Wextra -O2 -s -Wl,--gc-sections -o fizzbuzz -Wl,-M=fizzbuzz.map fizzbuzz.c -static
$ ls -l fizzbuzz
-rwxr-xr-x 1 fujita fujita 714736 Apr  7 15:24 fizzbuzz
$

何が問題か

凡そ当初考えていたことは達成しているのですが、これでもまだ最速を目指すには次の問題があります。
プログラム実行の際には、予めキャッシュされている場合を除けばプログラムは大抵の場合には実行の前に HDD 等の外部記憶装置から主記憶装置に読み込まれます。現在一般に使用されている SATA 3.0 を採用したディスク装置はスペック上の転送速度は 600MB/秒 であり、仮にこの額面通りの性能が出たとしても先の例の 約700k バイトの実行ファイルはファイル本体部分の転送だけで約 1.1m 秒も掛かってしまう計算となります。6112バイトの例でも、プログラム実行の前にプログラム本体の読み込みだけではなくダイナミックリンクライブラリの読み込みとダイナミックリンクの動作も発生することとなるので単純な話ではありません。
以上をまとめると、最速の FizzBuzz を目指すには

  • 実行ファイルは小さいほうが良い
  • ダイナミックリンクはないほうが良い

ということとなります。

そんなわけでアセンブラだ

そんなわけでアセンブラで組んでみました。

fizzbuzz.s
        .equiv  N, 100

        .equiv  SYS_EXIT, 60
        .equiv  SYS_WRITE, 1
        .equiv  STDOUT_FILENO, 1
        .equiv  EINTR, 4
        .equiv  EXIT_SUCCESS, 0
        .equiv  EXIT_FAILURE, 1

        .text
        .global _start
_start:
        movl    $length, %edx
        leaq    string(%rip), %rsi
        movl    $STDOUT_FILENO, %edi
0:
        movl    $SYS_WRITE, %eax
        syscall
        orl     %eax, %eax
        jns     1f
        cmpl    $-EINTR, %eax
        je      0b
        movl    $EXIT_FAILURE, %edi
        jmp     2f
1:
        leaq    (%rsi, %rax), %rsi
        subl    %eax, %edx
        jnz     0b

        movl    $EXIT_SUCCESS, %edi
2:
        movl    $SYS_EXIT, %eax
        syscall

string:
  .altmacro
  .macro num n
    .ascii "\n"
  .endm
        .set    i, 1
  .rept N
    .if i % 15 == 0
        .ascii  "FizzBuzz"
    .elseif i % 3 == 0
        .ascii  "Fizz"
    .elseif i % 5 == 0
        .ascii  "Buzz"
    .else
        num %i
    .endif
        .ascii  "\n"
        .set    i, i + 1
  .endr
        .equiv  length, . - string

        .end

x64 用に書いていており、Linux のシステムコールを使用しています。実行とビルドは Ubuntu 17.10.1 の amd64 版上で GNU binutils を使用して行っています。

$ as fizzbuzz.s -o fizzbuzz.o ; ld fizzbuzz.o -e _start -s -o fizzbuzz -M=fizzbuzz.map ; ./fizzbuzz
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz
$

実行ファイルはサイズが 808 バイト、ダイナミックリンクライブラリを必要としないものとなりました。

$ ls -l fizzbuzz
-rwxr-xr-x 1 fujita fujita 808 Apr  7 15:26 fizzbuzz
$ ldd fizzbuzz
        not a dynamic executable
$

おわりに

以上です。

16
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
16
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?