強まっていこう

あっちゃこっちゃへ強まっていくためのブログです。

FizzBuzz を無駄にベンチマークしてみた By Nim、golang、Rust、Crystal、その他

プログラミング Nim IT 技術

FizzBuzz 2つのパターン

Fizz Buzz - Wikipedia

3で割り切れる場合は Fizz、5で割り切れる場合は Buzz、3と5で割り切れる場合は FizzBuzz、それ以外は数字を表示すると言う FizzBuzz の書き方って大きく分けて2種類ありますよね。

その2つのパターンを粗暴なプログラマーにオススメな言語だけど殆どの人達が見たこともないであろう Nim で書いてみます。


まぁやってることが簡単なんで言語が違えどわかりますよね。

1つは愚直に全ての条件を書いてしまうパターン。

let n = 600_000
for i in 1..n:
  if i mod 3 == 0 and i mod 5 == 0: echo "FizzBuzz"
  elif i mod 3 == 0: echo "Fizz"
  elif i mod 5 == 0: echo "Buzz"
  else: echo i

もう1は文字列連結を使って条件の被りを回避するパターン。

let n = 600_000
for i in 1..n:
  var str = ""
  if i mod 3 == 0: str = "Fizz"
  if i mod 5 == 0: str &= "Buzz"
  if str == "": echo i else: echo str

Wikipedia の例だと数値を出力文字列に代入しちゃってますが、なるべく軽くするために代入を避けるべく条件分岐で数値と文字列を吐き分けるているのがクソどうでも良いこだわりだったりします。

自分的にはこちらの方が好みなんですよね。なんか同じ条件を書くのが嫌なんですよ。わかります？この感覚。
前者の方はどうしてもバカっぽく見えちゃいます。見づらいですし、条件変える時に2箇所いじる必要ありますし。良い事無い気がするんですよね。

でも前者はモジュロ演算が2個多いとは言え文字列連結が無い分はえぇんじゃなかろうか？

気になっちゃったのでベンチしてみました。

いざベンチ

独断と偏見で前者を「愚直」、後者は「エレガント」として表記しています。

1回目

言語 愚直 エレガント
C 0.06 0.07
Crytal 0.33 0.34
Perl 0.35 0.38
Nim 0.37 0.40
Rust 0.44 0.48
PHP 0.51 0.48
golang 0.59 0.76
Ruby 0.61 0.75
Node.JS 13.59 13.73

2回目

言語 愚直 エレガント
C 0.07 0.08
Crytal 0.35 0.36
Perl 0.35 0.36
Nim 0.37 0.38
Rust 0.46 0.49
PHP 0.49 0.47
golang 0.62 0.72
Ruby 0.60 0.84
Node.JS 13.23 13.36

うーん、さすがに前者の方が若干早いですね・・・っておいPerl。

なんであんたが Crystal と競って Nim と Rust、golang より早いねん。コンパイルされてるやつらが負けるとか無いでしょ。
と言うか C との速度差はなんですか。不甲斐なさ過ぎでしょう。Rust なんて PHP といい勝負しちゃってますし golang に至っては負けちゃってます。あぁ情けなや。
Ruby と Crystal は同じコードですがさすがに倍以上 Crystal が早いですね。ですが Crystal はコンパイル速度が気絶するほど遅いんですよねぇ・・・そこがネック。

つぅか Node.js よ、お前どうなっとんじゃ。しゃれにならんでしょ、これ。v8.0.0 でやってたのでバージョン上げりゃ速くなるかなと思い v8.2.1 に上げてみましたが変わらず、と言うかむしろちょっと遅くなると言うね。

何がダメなんだろうかと思ってちょっと調べたら console.log がダメな模様。process.stdout.write に変えてみました。

言語 愚直 エレガント
Node.JS(write) 5.81 5.45
Node.JS(write) 5.44 4.92

おおー！倍速くなった！ってやっぱおせぇし。他と比べて10倍遅いですからね。こう言う処理は Node.js 使うなって話ですね。

しかも他と違い愚直よりもエレガントの方が早いと言う良くわからない状況になりましたが、んなこたどうでも良いです。しょうもないレベルで遅いですから。

golang は []byte に append するともっと遅くなっちゃいました。流石に文字列が短いと + 演算子の方が強いです。

まとめ

今回ベンチしてわかったことは

  • 愚直に書いたらほんの少し早いかもね
  • Perl が意外とこう言う処理はえぇ
  • Nim、Crystal、Rust もっとがんばれよ
  • Node.js は使い所によっては相当ポンコツ
  • C はやはり帝王

どっちの書き方が云々よりも予想していなかった実行速度の優劣に驚きましたね。

コード

今回ベンチ取ったコードを載せておきます。

C

#include <stdio.h>

int main(void) {
  int n = 600000;
  int i = 1;
  for (i = 1; i <= n; i++) {
    if (i % 3 == 0 && i % 5 == 0) {
      printf("FizzBuzz\n");
    }
    else if (i % 3 == 0) {
      printf("Fizz\n");
    }
    else if (i % 5 == 0) {
      printf("Buzz\n");
    }
    else {
      printf("\%d\n", i);
    }
  }
  return 0;
}

#include <stdio.h>

int main(void) {
  int n = 600000;
  int i = 1;
  for (i = 1; i <= n; i++) {
    char str[9] = "";
    if (i % 3 == 0) {
      sprintf(str, "Fizz");
    }
    if (i % 5 == 0) {
      sprintf(str, "%sBuzz", str);
    }
    if (*str) {
      puts(str);
    }
    else {
      printf("%d\n", i);
    }
  }
  return 0;
}

Crystal + Ruby

n = 600000
(1..n).each do |i|
  if i % 3 == 0 && i % 5 == 0
    puts "FizzBuzz"
  elsif i % 3 == 0
    puts "Fizz"
  elsif i % 5 == 0
    puts "Buzz"
  else
    puts i
  end
end

n = 600000
(1..n).each do |i|
  str = ""
  str = "Fizz" if i % 3 == 0
  str += "Buzz" if i % 5 == 0
  if str == ""
    puts i
  else
    puts str
  end
end

Perl

#!/usr/bin/perl

use strict;

my $n = 600_000;
for (1..$n) {
  if ($_ % 3 == 0 and $_ % 5 == 0) {
    print "FizzBuzz\n";
  }
  elsif ($_ % 3 == 0) {
    print "Fizz\n";
  }
  elsif ($_ % 5 == 0) {
    print "Buzz\n";
  }
  else {
    print "$_\n";
  }
}

#!/usr/bin/perl

use strict;

my $n = 600_000;
for (1..$n) {
  my $str = '';
  $_ % 3 == 0 and $str = "Fizz";
  $_ % 5 == 0 and $str .= "Buzz";
  print $str ? "$str\n" : "$_\n";
}

Nim

let n = 600_000
for i in 1..n:
  if i mod 3 == 0 and i mod 5 == 0: echo "FizzBuzz"
  elif i mod 3 == 0: echo "Fizz"
  elif i mod 5 == 0: echo "Buzz"
  else: echo i

let n = 600_000
for i in 1..n:
  var str = ""
  if i mod 3 == 0: str = "Fizz"
  if i mod 5 == 0: str &= "Buzz"
  if str == "": echo i else: echo str

Rust

fn main() {
  let n = 600000;
  for i in 1..n {
    if i % 3 == 0 && i % 5 == 0 {
      println!("FizzBuzz"); 
    }
    else if i % 3 == 0 {
      println!("Fizz"); 
    }
    else if i % 5 == 0 {
      println!("Buzz"); 
    }
    else {
      println!("{}", i); 
    }
  }
}

fn main() {
  let n = 600000;
  for i in 1..n {
    let mut str = "".to_owned();
    if i % 3 == 0 {
      str.push_str("Fizz");
    }
    if i % 5 == 0 {
      str.push_str("Buzz");
    }
    if str.len() > 0 {
      println!("{}", str);
    }
    else {
      println!("{}", i);
    }
  }
}

PHP

#!/usr/bin/php
<?php

$n = 600000;
for ($i = 1; $i <= $n; $i++) {
  if ($i % 3 == 0 && $i % 5 == 0) {
    echo "FizzBuzz\n";
  }
  elseif ($i % 3 == 0) {
    echo "Fizz\n";
  }
  elseif ($i % 5 == 0) {
    echo "Buzz\n";
  }
  else {
    echo "$i\n";
  }
}

#!/usr/bin/php
<?php

$n = 600000;
for ($i = 1; $i <= $n; $i++) {
  $str = '';
  if ($i % 3 == 0) {
    $str = "Fizz";
  }
  if ($i % 5 == 0) {
    $str .= "Buzz";
  }
  echo $str != "" ? "$str\n" : "$i\n";
}

golang

package main

import (
  "fmt"
)

func main() {
  n := 600000;
  for i := 1; i <= n; i++ {
    if i % 3 == 0 && i % 5 == 0 {
      fmt.Printf("FizzBuzz\n")
    } else if i % 3 == 0 {
      fmt.Printf("Fizz\n")
    } else if i % 5 == 0 {
      fmt.Printf("Buzz\n")
    } else {
      fmt.Printf("%d\n", i)
    }
  }
}

package main

import (
  "fmt"
)

func main() {
  n := 600000;
  for i := 1; i <= n; i++ {
    str := ""
    if i % 3 == 0 {
      str = "Fizz"
    }
    if i % 5 == 0 {
      str += "Buzz"
    }
    if str != "" {
      fmt.Printf("%s\n", str)
    } else {
      fmt.Printf("%d\n", i)
    }
  }
}

Node.js

var n = 600000;
for (var i = 1; i <= n; i++) {
  if (i % 3 == 0 && i % 5 == 0) {
    console.log("FizzBuzz");
  }
  else if (i % 3 == 0) {
    console.log("Fizz");
  }
  else if (i % 5 == 0) {
    console.log("Buzz");
  }
  else {
    console.log(i);
  }
}

var n = 600000;
for (var i = 1; i <= n; i++) {
  var str = "";
  if (i % 3 == 0) {
    str = "Fizz";
  }
  if (i % 5 == 0) {
    str += "Buzz";
  }
  console.log(str ? str : i);
}

Node.js(write)

var n = 600000;
for (var i = 1; i <= n; i++) {
  if (i % 3 == 0 && i % 5 == 0) {
    process.stdout.write("FizzBuzz\n");
  }
  else if (i % 3 == 0) {
    process.stdout.write("Fizz\n");
  }
  else if (i % 5 == 0) {
    process.stdout.write("Buzz\n");
  }
  else {
    process.stdout.write(i + "\n");(
  }
}

var n = 600000;
for (var i = 1; i <= n; i++) {
  var str = "";
  if (i % 3 == 0) {
    str = "Fizz";
  }
  if (i % 5 == 0) {
    str += "Buzz";
  }
  process.stdout.write(str ? str + "\n" : i + "\n");
}

コンパイルオプション

gcc -o fizzbuzz_c fizzbuzz.c
nim c -d:release -o:fizzbuzz_nim fizzbuzz.nim
crystal build --release -o fizzbuzz_cr fizzbuzz.cr
rustc -O -o fizzbuzz_rs fizzbuzz.rs
go build -o fizzbuzz_go fizzbuzz.go

IO が遅いと id:Haaaa_N さんから指摘があったので試してみた

文字列連結で全部連結して一発出力すると倍早くなった、と指摘があったので試してみました。

id:Haaaa_N さんが書いた Rust のコードはコレ

gist.github.com

Nim も書いてみました。

var str = ""
for i in 1..600_000:
  if i mod 3 == 0 and i mod 5 == 0: str.add "FizzBuzz\n"
  elif i mod 3 == 0: str.add "Fizz\n"
  elif i mod 5 == 0: str.add "Buzz\n"
  else: str.add $i & "\n"
write stdout, str

結果

Rust 0.05s
Nim 0.07s

倍どころじゃなかったですね。しかも Nim 負けましたね。メモリがいっぱいあるなら一気に出すのが一番ですね、やはり。

Nim の文字全列連結版をもっと速く(情報提供 id:ytqwertyさん)

「一番下のnimのコードはRustに習ってstr.add $i & "\n"をstr.add $i; str.add '\n'にすると少し速くなります。」とのことだったのでちょっと試してみたら Rust と並びましたね。& 演算子の呼び出しが足をひっぱるようです。

var str = ""
for i in 1..600_000:
  if i mod 3 == 0 and i mod 5 == 0: str.add "FizzBuzz\n"
  elif i mod 3 == 0: str.add "Fizz\n"
  elif i mod 5 == 0: str.add "Buzz\n"
  else: str.add $i; str.add "\n"
write stdout, str

id:siphilia さんが色々速くしてくれた結果 Rust がなんだか速い

gist.github.com

試してみたんですが、自分の環境でも Rust が速くなりました。帝王 C が負けてる。printf が遅いと id:ytqwerty さんも言っていたので puts にしてみたんですが、イマイチでした。60万回程度のループだと流石にこのレベルの戦いでは意味が無いので、1000万回ループさせて試しました。

C 1.000s
C(puts) 0.96s
Rust 0.73s

なんでしょう、この Rust の速さは。

ちなみに C の puts はこれです。

#include <stdio.h>

int main() {
  int n = 10000000;
  int i = 1;
  for (i = 1; i <= n; i++) {
    if (i % 3 == 0 && i % 5 == 0) {
      puts("FizzBuzz");
    }
    else if (i % 3 == 0) {
      puts("Fizz");
    }
    else if (i % 5 == 0) {
      puts("Buzz");
    }
    else {
      printf("%d\n", i);
    }
  }
  return 0;
}

utaymd さんがやってくれました Nim で爆速に

https://gist.github.com/yuutayamada/fa9415503048ce58b6f47d6a049a8c81

100万回でも 0.001s で処理が終わります。static でやっちゃうとコードがガッツリ展開されるのでファイルサイズは 6.1M とパンチの効いたサイズになりますが、爆速目指すなら大いにアリだと思いました。ただ、ループ回数に限界がありはしますけども。

いやぁ大変参考になりました。

fujita nozomu さんの文字列連結板 C が Nim、Rust を置いてけぼりに

godbolt.org

速いです。Nim と Rust の文字連結一発出力と比べてみました。1000万回ループです。

C 0.27s
Rust 0.94s
Nim 0.85s

こんな感じです。3倍っくらい速いですね。

fujita nozomu さんのコードがさらに謎の速さの領域へ

ideone.com

1000万回回して 0.037s とかです。コードもなんだか凄いですｗ。チューニングされすぎですｗ。

今のところの最速コード C言語

#define UseWrite 1
 
#if UseWrite
#include <unistd.h>
#else
#include <stdio.h>
#endif
#include <string.h>
 
#define n 10000000
 
#if defined(__GNUC__) || defined(__clang__)
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
#else
#define likely(x)   (x)
#define unlikely(x) (x)
#endif
 
char s[10 * n];
char d[8] = "00000000";
 
int main() {
  char* p = s;
  int i = 0;
  int k = 0;
 
  #define num() \
  do { \
    switch (k) { \
    case 7: __asm __volatile("/* 8 */\n"); *p++ = d[0]; \
    case 6: __asm __volatile("/* 7 */\n"); *p++ = d[1]; \
    case 5: __asm __volatile("/* 6 */\n"); *p++ = d[2]; \
    case 4: __asm __volatile("/* 5 */\n"); *p++ = d[3]; \
    case 3: __asm __volatile("/* 4 */\n"); *p++ = d[4]; \
    case 2: __asm __volatile("/* 3 */\n"); *p++ = d[5]; \
    case 1: __asm __volatile("/* 2 */\n"); *p++ = d[6]; \
    case 0: __asm __volatile("/* 1 */\n"); *p++ = d[7]; \
    } \
    *p++ = '\n'; \
  } while (0)
  #define fizz() do {memcpy(p, "Fizz\n", 5); p += 5;} while (0)
  #define buzz() do {memcpy(p, "Buzz\n", 5); p += 5;} while (0)
  #define fizzbuzz() do {memcpy(p, "FizzBuzz\n", 9); p += 9;} while (0)
  #define next() \
  do { \
    if (unlikely(++i > n)) goto end; \
    if (unlikely(++d[7] > '9')) { \
      d[7] = '0'; \
      if (unlikely(++d[6] > '9')) { \
        d[6] = '0'; \
        if (unlikely(++d[5] > '9')) { \
          d[5] = '0'; \
          if (unlikely(++d[4] > '9')) { \
            d[4] = '0'; \
            if (unlikely(++d[3] > '9')) { \
              d[3] = '0'; \
              if (unlikely(++d[2] > '9')) { \
                d[2] = '0'; \
                if (unlikely(++d[1] > '9')) { \
                  d[1] = '0'; \
                  d[0]++; \
                  if (unlikely(k < 7)) {k = 7;} \
                } \
                if (unlikely(k < 6)) {k = 6;} \
              } \
              if (unlikely(k < 5)) {k = 5;} \
            } \
            if (unlikely(k < 4)) {k = 4;} \
          } \
          if (unlikely(k < 3)) {k = 3;} \
        } \
        if (unlikely(k < 2)) {k = 2;} \
      } \
      if (unlikely(k < 1)) {k = 1;} \
    } \
  } while (0)
 
  for (;;) {
    next(); num();
    next(); num();
    next(); fizz();
    next(); num();
    next(); buzz();
    next(); fizz();
    next(); num();
    next(); num();
    next(); fizz();
    next(); buzz();
    next(); num();
    next(); fizz();
    next(); num();
    next(); num();
    next(); fizzbuzz();
  }
 end:
#if UseWrite
  write(STDOUT_FILENO, s, p - s);
#else
  *p = '0';
  printf("%s", s);
#endif
}

(Author fujita nozomuさん)