コグノスケ

FizzBuzzを速くする1（自作アルゴリズム）

目次: ベンチマーク

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

測定環境は、

• Intel Pentium J4205/1.5GHz
• DDR3L-1600 8GB x 2
• Linux kernel 6.1.52
• GCC 12.2.0 (Debian 12.2.0-14)
• glibc 2.36 (Debian 2.36-9+deb12u1)

いわゆる省電力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

以降、この速度を基準値とします。

高速化その1 - printfを排除

プロファイリング（perf topなど）を見ると、printf()関連の処理に時間が掛かるようです。おそらく、

• libc内部のバッファリングが遅い？
• 毎回標準出力に書きだしていて遅い？
• 整数から文字列への汎用的な変換処理が遅い？

などが考えられます。対策として、

• リングバッファを実装、リングバッファ終端は少し余分に確保し、はみ出した分は先頭に折り返してコピー（ライトポインタの制御が最小限で済む）
• printf()の代わりにwrite()を使用、write()に与える単位をページ（4KB）の整数倍にする
• 整数から文字列への変換を10進数に限定して高速変換

以上を実装して測定します。整数から文字列への変換は、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倍まで高速化しました。いい感じです。

vmsplice

次は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秒で終わるようになりました。

ソースコード

ソースコードはこちらからどうぞ。

•  単純なFizzBuzz
•  printf排除FizzBuzz
•  9桁10桁狙い撃ちのFizzBuzz
•  vmspliceを使ったFizzBuzz

一覧の一覧 - まとめリンク

一覧の一覧が欲しくなったので作りました。

OS、アーキテクチャ系。

• 目次: Android
• 目次: Arduino
• 目次: FreeRTOS
• 目次: Linux
• 目次: Raspberry Pi
• 目次: RISC-V
• 目次: ROCK64/ROCKPro64
• 目次: Windows
• 目次: Zephyr
• 目次: 独自OS

C言語とかコンパイラ。

• 目次: apt
• 目次: ALSA
• 目次: C言語とlibc
• 目次: GCC
• 目次: LLVM
• 目次: OpenCL
• 目次: OpenOCD
• 目次: ベンチマーク

趣味、生活系。

• 目次: Kindle
• 目次: Might and Magicファミコン版
• 目次: STATIONflow
• 目次: ゲーム
• 目次: サンタ
• 目次: プロバイダ
• 目次: マンガ紹介
• 目次: 自宅サーバー
• 目次: 車
• 目次: 射的
• 目次: 電池

日本語とアルファベットの間にスペースを入れるのをやめた

私は昔からの癖で、文章を書くときに日本語と半角アルファベットの間に半角スペースを入れています。日本語と半角アルファベットが異様にくっついて表示されてしまう環境において、少しでも自然に見えるようにする姑息な手段です。

昔ならまだしも今となってはあまり意味がなく、そろそろやめようかなあと思っています。これから書く文章は自分の気持ち次第なのでどうにでもなりますが、今まで書いた日記はどうしようかな〜と悩んでいます。

根本治療は意外と難しい

過去の日記を眺めていましたが、一括の置換で直すのは結構大変そうです。基本的には「日本語と半角文字」もしくは「半角文字と日本語」の間にあるスペースを消すのですけど、例外的にスペースを維持したいパターンがあります。

• 削除したい: "この -a の項"のような場合の、-記号の前のスペース
• 削除したくない: "タイトル - サイト名"のような場合の、-記号の前後のスペース

残念なことに文脈依存なので区別が付きません。根本治療は諦めて下記の置換で簡易処置しました。

: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

どうしてもスペースの削除漏れが出るためか、ところどころバランスがおかしいですね……。元々あってもなくても良かったものですから、表示が大きく崩れるでもしない限りはこのままで良いでしょう。

Windows - まとめリンク

目次: Windows

一覧が欲しくなったので作りました。

• HDD破壊神Windows 10
• HDDクラッシャーは誰だ
• Windows 10の不思議なところ
• Windows 10の不思議なところ2
• 勝手に何かしているWindows 10
• Windows 10の謎のプロセス
• 勝手に何かしているWindows 10その2
• Windows 10のエクスプローラがクラッシュする
• Windows 10クラッシュの謎
• Windows 10遅くない？
• Windows 10とVirtualBox
• たまにズレちゃうWindows 10
• ノートPCの発熱を抑える方法 - その1
• ノートPCの発熱を抑える方法 - その2
• Windows 10謎の高負荷
• WindowsとLinuxのメモリ割り当て戦略の違い
• Windowsの仮想メモリサイズの謎
• WindowsとRyzen 7 2700の動作周波数
• Windows PCの画面ロックを妨害（Windows API版）
• Windows PCの画面ロックを妨害（JavaScript版）
• デバイスを外してもずっとエラーが出るWindows 10
• Windows 10のタスクバーの困ったところ

Windows 10のタスクバーの困ったところ

目次: Windows

Windows 10は標準でタスクバーボタンの入れ替え機能がありますけど、これがイマイチ使いにくいです。違うアプリならば入れ替えられますが、同じアプリ内でボタンを入れ替えられないのです。

同じアプリ内でボタンを入れ替えられない

Windows 11はさらにダメになっていて、タスクバーボタンの結合を解除する機能がなくなってしまいました。ノートPCはWindows 11にしましたが、デスクトップPCは移行する気が起きません。将来的にタスクバーとボタンという仕組みをなくしたいんでしょうか？

スマホみたいに、何か押さないとタスクの一覧が出ないタイプはすこぶる使いにくくて嫌いなんですよね……。