目次: ベンチマーク
FizzBuzzをご存じでしょうか?元々は英語圏の遊びで、1を最初にして、順に1ずつ足した数を宣言します。ただし3の倍数でFizz、5の倍数でBuzz、15の倍数でFizzBuzzと言わなければなりません。ルールはこれだけで単純です。試しに16まで書いてみるとこんな感じ。
1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16
FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。自作、他作を含めて高速化の例を紹介したいと思います。
FizzBuzzの実行範囲は1から2^32-2とします。すなわち1 ... 0xfffffffeです。出力される文字列は合計で33.3GBになります。
測定方法は簡単です。pvにパイプで繋いで出力の速度を表示します。速度が一定とは限らないので、並行してtimeで実行時間を測定します。出力が間違っていないかどうかテストするプログラムも必要ですが、本筋とは関係ないので省略します。
$ gcc -O3 something.c -o ./fizzbuzz && time taskset 0x1 ./fizzbuzz | taskset 0x4 pv > /dev/null
測定環境は、
いわゆる省電力PCで、そんなに速いPCではありません。
速度の絶対値とともに、一番単純な実装と高速化後で速度が何倍になったかを見ます。高速化のありがたみがわかりやすいでしょ?
// fizzbuzz_simple.c
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
for (unsigned int i = 1; i < 0xffffffff; 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("%u\n", i);
}
}
return 0;
}
何も難しくないです。測定しましょう。
# fizzbuzz_simple.c 33.3GiB 0:07:32 [75.4MiB/s] [ <=> ] real 7m32.741s user 7m25.558s sys 0m51.090s
以降、この速度を基準値とします。
プロファイリング(perf topなど)を見ると、printf()関連の処理に時間が掛かるようです。おそらく、
などが考えられます。対策として、
以上を実装して測定します。整数から文字列への変換は、10000の剰余、10000で除算、を繰り返して4桁ずつ変換します。4桁の数字の変換は起動時に0000から9999までの1000要素のテーブルを作成しておいて、変換時はテーブルからコピーすることで高速化します。
# fizzbuzz_myitoa.c 33.3GiB 0:01:20 [ 424MiB/s] [ <=> ] real 1m20.416s user 1m1.746s sys 0m21.756s
約6倍まで高速化しましたが、まだまだですね。
プロファイルを見ると整数から文字列への変換をする部分が遅いです。FizzBuzz実行範囲の1〜2^32-2にて最も多く出現し、かつ処理が遅い桁数は10桁、次いで9桁の数字です。遅い部分に集中して高速化します。
作っていて気づかれた方もいましょうが、FizzBuzzは15回で同じパターンがループします。つまり数字の桁数が同じであればFizzやBuzzが出てくるバイト位置も毎回同じのため、あらかじめ書いておくことができます。
最初に30回分のFizz, Buzz, FizzBuzzをあらかじめ書いておいた文字列をバッファにコピーします。数字が入る場所はドットで埋めてあります(後で書き換えるのでスペースでも何でも良い)。こんな感じです。
const char tmp10[] =
"FizzBuzz\n..........\n..........\n"
"Fizz\n..........\nBuzz\n"
"Fizz\n..........\n..........\n"
"Fizz\nBuzz\n..........\n"
"Fizz\n..........\n..........\n"
"FizzBuzz\n..........\n..........\n"
"Fizz\n..........\nBuzz\n"
"Fizz\n..........\n..........\n"
"Fizz\nBuzz\n..........\n"
"Fizz\n..........\n..........\n";
その後、数字を入れるべき個所を上書きします。例として4つ上書きした状態を示します。
"FizzBuzz\n1000000021\n1000000022\n"
"Fizz\n1000000024\nBuzz\n"
"Fizz\n1000000027\n..........\n"
"Fizz\nBuzz\n..........\n"
"Fizz\n..........\n..........\n"
"FizzBuzz\n..........\n..........\n"
"Fizz\n..........\nBuzz\n"
"Fizz\n..........\n..........\n"
"Fizz\nBuzz\n..........\n"
"Fizz\n..........\n..........\n";
なぜ15回分ではなく30回分かというと、10回分x 3に分解することができるからです。10回分をまとめるメリットとしては、10の桁より上の桁が全て同じ文字なので一度に書き換えられ、高速化が期待できることです。
コードは長いですが大して難しくないので、興味があればご覧ください。では速度を測ります。
# fizzbuzz_9_10.c 33.3GiB 0:00:25 [1.31GiB/s] [ <=> ] real 0m25.372s user 0m10.515s sys 0m29.643s
約17倍まで高速化しました。いい感じです。
次はFizzBuzzの出口つまりpvコマンドへのパイプに着目します。今はwrite()を使っている状態で、write()でパイプに書き込むとカーネル内でパイプのメモリ領域へのデータコピーが発生して遅くなっています。
そう言われてもどうすれば?と思いますが、Linuxにはカーネル内のメモリコピー処理を省くためのシステムコールvmsplice()が存在します。
ssize_t vwrite(int fd, void *buf, size_t count)
{
struct iovec iov;
ssize_t n;
iov.iov_base = buf;
iov.iov_len = count;
while (iov.iov_len > 0) {
n = vmsplice(1, &iov, 1, 0);
iov.iov_base += n;
iov.iov_len -= n;
}
return count;
}
このようにvmsplice()を呼ぶvwrite関数を作成し、今までwrite()を呼んでいた個所を全てvwrite関数に置き換えます。
カーネル内の実装を調べていないため詳細な理由はわかりませんが、vmsplice()は動きにちょっと癖があってfcntl(F_SETPIPE_SZ)でパイプのサイズをある程度(64KB〜くらい?)大きくしないと、パイプの読み出し側でデータが壊れることがあります。
説明はこれくらいで測定しましょう。
# fizzbuzz_vmsplice.c 33.3GiB 0:00:10 [3.16GiB/s] [ <=> ] real 0m10.543s user 0m8.921s sys 0m4.067s
約42倍まで速くなりました。vmsplice()恐るべし。当初7分も掛かっていた2^32のFizzBuzzが、今やたったの10秒で終わるようになりました。
ソースコードはこちらからどうぞ。
一覧の一覧、まとめのまとめが欲しくなったので作りました。
OS、アーキテクチャ系。
C言語とかコンパイラ。
趣味、生活系。
私は昔からの癖で、文章を書くときに日本語と半角アルファベットの間に半角スペースを入れています。日本語と半角アルファベットが異様にくっついて表示されてしまう環境において、少しでも自然に見えるようにする姑息な手段です。
昔ならまだしも今となってはあまり意味がなく、そろそろやめようかなあと思っています。これから書く文章は自分の気持ち次第なのでどうにでもなりますが、今まで書いた日記はどうしようかな〜と悩んでいます。
過去の日記を眺めていましたが、一括の置換で直すのは結構大変そうです。基本的には「日本語と半角文字」もしくは「半角文字と日本語」の間にあるスペースを消すのですけど、例外的にスペースを維持したいパターンがあります。
残念なことに文脈依存なので区別が付きません。根本治療は諦めて下記の置換で簡易処置しました。
:bufdo %s/\([^a-zA-Z0-9 !-~]\) \([a-zA-Z0-9]\)/\1\2/gc :bufdo %s/\([a-zA-Z0-9]\) \([^a-zA-Z0-9 !-~]\)/\1\2/gc
どうしてもスペースの削除漏れが出るためか、ところどころバランスがおかしいですね……。元々あってもなくても良かったものですから、表示が大きく崩れるでもしない限りはこのままで良いでしょう。
< | 2023 | > | ||||
<< | < | 09 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | - | - | - | 1 | 2 |
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
合計:
本日: