コグノスケ

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

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

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

根本治療は意外と難しい

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

• 削除したい: "この -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

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

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

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

OS、アーキテクチャ系。

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

C言語とかコンパイラ。

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

趣味、生活系。

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

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

FizzBuzzを速くする2（高速アルゴリズムの紹介）

目次: ベンチマーク

FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。前回は自作のアルゴリズムを紹介したので、今回は他の方が開発した高速化手法を紹介したいと思います。名前がないようなので、オフセット0xf6アルゴリズム（仮）と呼ぶことにします。

前回の最速（9桁10桁狙い撃ち＋vmsplice）も含めて、ソースコードはGitHubに置いています（GitHubへのリンク）。

整数演算と文字列変換のトレードオフ

FizzBuzzの高速化の難しい点は、数値のインクリメント（=1ずつ増やす）と数字を文字列に変換する処理の両立です。単純な方法としては、現在の数値を整数で保持する方法、文字列で保持する方法が考えられます。

• 整数で保持: 演算は高速、文字列への変換は低速
• 文字列で保持: 演算は低速（繰り上がり処理にループが必要で遅い）、文字列変換は不要なので最速

どちらも一長一短で困りました。

整数演算と文字列変換の両立

このトレードオフを見事に解決しているのがオフセット0xf6アルゴリズム（仮）です。最初に要点を列挙しますと、

• 1バイト1桁（例えば64ビット変数なら8桁収まる）
• 各桁を0xf6でオフセット（0: 0xf6, 1: 0xf7, ..., 9: 0xff）
• 桁上がりするまでは数値のインクリメントは整数演算
• 桁上がりすると下の桁が全部0になるので、Trailing Zeroとマスク演算で0xf6をセットし直す

桁は1つ目に書いた通り、10進数1桁を1バイトで表現します。情報量としては過剰に見えますが文字列変換との両立のためです。

桁とバイト表現

数の表現ですが0 = 0xf6, 1 = 0xf7, 2 = 0xf8, ... 9 = 0xffとします。10進数の123397ならば0xf6f6f7f8_f9f9fffdとなります。

10進数と相当するバイト表現

桁上がりするまで数値インクリメントは+1の整数演算で実現できます。

インクリメント処理は+1の加算処理と同等

ここまではオフセットが変なだけの普通の整数です。

桁の繰り上がり処理

このアルゴリズムは桁の繰り上がり処理がエレガントで、+1の整数演算で適切な桁までの繰り上げが発生します。つまり加算命令1発で良く、ループ処理は必要ありません。先の例では下位の3桁が399から400になります。

桁の繰り上がりが発生した様子

面倒な処理は不要で、+1の整数加算だけで、1の桁より上位の桁（この例だと10の桁も）が全て正しく繰り上がります。このアルゴリズムのナイスポイントその1です。

繰り上がった桁は値0x00になるので手当が必要です。先の例だと12399: 0xf6f6f7f8_f9f9ffffに+1すると、124xx: 0xf6f6f7f8_f9fa0000になって、下位の2桁（10の桁、1の桁）が無意味な値になっています。次の演算を行うには0x00の部分を10進数の0を意味する0xf6に戻す必要があります。

戻し方はまずCTZ (Count Trailing Zeros)で下位の連続している0のビット数を取得します。先の例ですと、下位24ビットが0xfa0000 = 0b1111_1010_0000_0000_0000_0000ですので、17ビットです。Nとします。

0xf6をセットすべきバイト範囲の計算

CTZビット数Nを8の倍数に切り下げ（= 16ビット）て、mask = (1 << N) - 1とし、下位16ビットに1がセットされた（= 0x00000000_0000ffff）マスクを作成します。その後(元の数値) |= 0xf6f6f6f6_f6f6f6f6 & maskを計算して、下位16ビットに0xf6をセットします。

下位の連続した0x00のバイトのみに0xf6をセット

これで桁の繰り上げ処理は完了です。ループ処理は一切不要。アルゴリズムのナイスポイントその2です。

CTZにループが必要では？と思われるかもしれませんが、世の中には素敵なアルゴリズムがあってループなしで計算可能です。また現代のCPUはCTZ専用命令を持っていることが多く、基本命令の組み合わせより高速に処理できることが多いです。

文字列への変換

桁の繰り上がり処理の素晴らしさが伝わったところで、文字列への変換を紹介します。といっても極めて単純で高速です。0xc6c6c6c6_c6c6c6c6を減算するだけです。

一見すると意味不明ですが、ASCIIコードを考えるとわかると思います。0を表すバイト表現は0xf6でした。0xc6を引くと0xf6 - 0xc6 = 0x30になります。'0'はASCIIコードで0x30です。それだけで文字の'0'に変換できてしまいます。0以外の数値はどうなるかというと、

• 0: 0xf6 - 0xc6 = 0x30 = '0'
• 1: 0xf7 - 0xc6 = 0x31 = '1'
• 2: 0xf8 - 0xc6 = 0x32 = '2'
• ...
• 9: 0xff - 0xc6 = 0x39 = '9'

となります。他の位置のバイトも同様で、減算1回で8桁を8文字に変換できます。このアルゴリズムのナイスポイントその3です。

アルゴリズムとは関係ないですが、文字列をメモリに書くときはエンディアンに注意です。x86系CPUはリトルエンディアンなので、文字列に変換した64bit変数（0x30303132_33343938）をそのままメモリに書くと順序が逆転し、メモリには0x38 0x39 0x34 0x33 0x32 0x31 0x00 0x00、つまり"89432100"になります。

本当は"00123498"と書いてほしいので、メモリに書く前にビッグエンディアンに変換すれば良いです。この処理はバイトスワップと呼ばれたりします。これもループ不要の処理で、現代のCPUだと専用命令を持っている場合もあります。

以上がオフセット0xf6アルゴリズム（仮）のナイスポイントの紹介でした。いやあ、良く考え付いたなこれ。感心しました。

エレガントで速い

遅くなる要素は見当たりませんが、最後に測定しましょう。

# https://github.com/katsuster/fizzbuzz/blob/main/fizzbuzz2.c

33.3GiB 0:00:09 [3.39GiB/s] [         <=>                                      ]

real    0m9.824s
user    0m7.447s
sys     0m5.064s

約45倍まで速くなりました。素晴らしいです。

参考までに、前回私が作成した9桁10桁狙い撃ちの力業アルゴリズム（約42倍）はこのくらい。

# https://github.com/katsuster/fizzbuzz/blob/main/fizzbuzz.c

33.3GiB 0:00:10 [3.16GiB/s] [          <=>                                     ]

real    0m10.543s
user    0m8.921s
sys     0m4.067s

ボロ負けというほど差は付いていませんが、コードのエレガントさは大いに差がありましたね。当たり前ですが、リングバッファやvmsplice()のような共通して使える工夫は双方で使いました。ですから純粋にFizzBuzz最適化アルゴリズムの差と言えましょう。

FizzBuzzを速くする3（CPUを変えてみよう）

目次: ベンチマーク

FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。前回は高速なアルゴリズムを紹介しましたが、CPUを変えたら傾向がどうなるかも見ておきます。

測定環境は、

• AMD Ryzen 7 5700X
• DDR4-3200 32GB x 2
• Linux kernel 6.4.13 (Debian 6.4.13-1)
• GCC 13.2.0 (Debian 12.2.0-14)
• glibc 2.37 (Debian 2.37-7)

では順に測定しましょう。

# fizzbuzz_simple.c

33.3GiB 0:01:41 [ 335MiB/s] [ <=>                                              ]

real    1m41.715s
user    1m38.481s
sys     0m31.222s

# fizzbuzz_myitoa.c

33.3GiB 0:00:22 [1.48GiB/s] [                     <=>                          ]

real    0m22.478s
user    0m14.279s
sys     0m11.151s

# fizzbuzz_9_10.c

33.3GiB 0:00:08 [4.12GiB/s] [        <=>                                       ]

real    0m8.080s
user    0m3.138s
sys     0m12.550s

# fizzbuzz_vmsplice.c

33.3GiB 0:00:03 [10.6GiB/s] [   <=>                                            ]

real    0m3.159s
user    0m2.828s
sys     0m1.654s

基本的にPentiumで有効な高速化手法はRyzenでも有効ですが、効き目という観点で見ると違いがあります。Ryzenの場合、自作アルゴリズムの要である9桁10桁の狙い撃ちがあまり効かないようです。

オフセット0xf6アルゴリズム（仮）も測定しましょう。昨日のコードから少し変更しているのでPentiumでも測りなおします。

# https://github.com/katsuster/fizzbuzz/blob/main/fizzbuzz2.c

33.3GiB 0:00:09 [3.40GiB/s] [         <=>                                      ]

real    0m9.789s
user    0m7.660s
sys     0m4.847s

# https://github.com/katsuster/fizzbuzz/blob/main/fizzbuzz2.c

33.3GiB 0:00:02 [15.3GiB/s] [  <=>                                             ]

real    0m2.184s
user    0m1.827s
sys     0m1.422s

自作アルゴリズムとオフセット0xf6アルゴリズム（仮）を比べると、Pentium J4205の場合はさほど差はありませんでしたが、Ryzen 7の場合は1.5倍程度と大きく差がついています。理由は良くわかりませんが、自作アルゴリズムの方にRyzen 7が苦手とする処理があるのでしょう。

まとめるとこんな感じです。最初（2023年9月21日の日記）にレギュレーションのところで説明したように、1から2^32-2まで（約42億回）FizzBuzzしているのですが、たった2秒で終わってしまいます。Ryzen速いですね……。

FizzBuzzを速くする4（うまくいかないこともある）

目次: ベンチマーク

FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。今回はあるCPUでうまくいっても、他のCPUでは効果がないケースをご紹介します。

実験用に4つのコードを用意しました。出力がボトルネックになって測定結果が不必要に遅く見えないよう、vmspliceとバッファリングは最初から実装します。

• 20231001_fizzbuzz_base.c: 自前のitoaのみ（比較元として使う）
• 20231001_fizzbuzz_30.c: 30個まとめる最適化
• 20231001_fizzbuzz_offset.c: オフセット0xf6アルゴリズム（仮）に置き換え
• 20231001_fizzbuzz_fixed.c: 9桁と10桁を狙い撃ちで最適化

30個まとめて処理する最適化で速くなるのはほぼ確実でしょう。3つ目は、前回（2023年9月23日の日記参照）紹介したオフセット0xf6アルゴリズムです。これも速くなるのはほぼ確実でしょう。

4つ目は、前々回（2023年9月21日の日記参照）紹介した9桁と10桁を狙い撃ちで最適化する方法です。自前のitoa()には効果抜群でしたので、オフセット0xf6アルゴリズムとの相乗効果にも期待したいところです。

省電力PCでの効果

まずは省電力PC（CPU: Pentium J4205）で測定します。

# 20231001_fizzbuzz_base.c

33.3GiB 0:01:06 [ 512MiB/s] [                               <=>                ]

real    1m6.621s
user    1m4.461s
sys     0m5.356s

# 20231001_fizzbuzz_30.c

33.3GiB 0:00:38 [ 877MiB/s] [                                    <=>           ]

real    0m38.860s
user    0m37.459s
sys     0m4.377s

# 20231001_fizzbuzz_offset.c

33.3GiB 0:00:09 [3.45GiB/s] [         <=>                                      ]

real    0m9.671s
user    0m8.047s
sys     0m3.726s

# 20231001_fizzbuzz_fixed.c

33.3GiB 0:00:08 [3.74GiB/s] [        <=>                                       ]

real    0m8.906s
user    0m6.955s
sys     0m4.216s

いずれの最適化も効いていて、4つ目が最速です。良いですね。

デスクトップPCでの効果

次はデスクトップPC（CPU: Ryzen 7 5700X）で測定します。

# 20231001_fizzbuzz_base.c

33.3GiB 0:00:15 [2.11GiB/s] [               <=>                                ]

real    0m15.759s
user    0m15.425s
sys     0m1.345s

# 20231001_fizzbuzz_30.c

33.3GiB 0:00:09 [3.64GiB/s] [         <=>                                      ]

real    0m9.152s
user    0m8.886s
sys     0m1.176s

# 20231001_fizzbuzz_offset.c

33.3GiB 0:00:02 [16.2GiB/s] [  <=>                                             ]

real    0m2.063s
user    0m1.762s
sys     0m1.070s

# 20231001_fizzbuzz_fixed.c

33.3GiB 0:00:02 [15.8GiB/s] [  <=>                                             ]

real    0m2.112s
user    0m1.802s
sys     0m1.080s

なんと9桁と10桁狙い撃ちで最適化すると逆に遅くなりました。時間と高速化の度合いをまとめると、

Ryzen 7 5700Xでなぜ遅くなるのか？は内部構造を知らないので何とも言えませんが、あるCPUに効く最適化が他のCPUだと効果がなかったり逆効果になったりすることは往々にしてあるという好例に思います。

ソースコード

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

•  自前のitoaのみ
•  30個まとめる最適化
•  オフセット0xf6アルゴリズム（仮）に置き換え
•  9桁と10桁を狙い撃ちで最適化

お葬式

横浜で大学の研究室の先輩のお葬式というか無宗教のお別れの会がありました。突然の訃報にただただ驚き、悲しみを覚えるばかりでした。45歳は若すぎます……。喪主はお兄さんが務めておられました。お兄さんは初来日だそうですが、初来日が弟さんのお葬式なんて悲しすぎます……。英会話すると、自分の英語のヘボさというか理解の怪しさをビシビシ感じます。

大学の研究室のみなさまと久しぶりに会えました。故人の思い出をたくさん話せたかなと思います。

リモートワーク

最近は毎日リモートワークの人も珍しくありませんが、1人暮らしor共働きで家人が居ないなどの場合、自宅で倒れてしまっても誰も気づけないという欠点があることに気づかされました。だから全員毎日出社すべしとは思いませんけども、周りが気づける方法があると良いなとは思います。

横浜の道路は大渋滞

会場近くのお花屋さんで献花用のお花を買いたくて、徒歩より移動しやすかろうと車で向かったのは失敗でした。横浜横須賀道路が激しく渋滞していてかなり時間が掛かりました。周りの車を見ると埼玉？千葉？県外ナンバーばかりです、なぜこんなところに……って連休で遠出する人達かあ。3連休初日の朝だということを忘れていました。

会場までの所要時間が良くわからなかったので、1時間くらい余裕見て出発したのが功を奏し、幸いなことに遅刻はしませんでした。

FizzBuzzを速くする5（SIMD最適化の紹介）

目次: ベンチマーク

FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。以前紹介（2023年9月22日の日記参照）したオフセット0xf6アルゴリズム（仮）ですが、SIMD命令（今回はSSE4.1を使います）を使って書き換えるとさらに速くなります。

この最適化は私が考えたものではなく、High throughput Fizz Buzz - Code Golf Stack Exchangeに投稿されていたxiver77さんのコードを元にしています。Cで書かれたコードでは最も高速のようです。

基本戦略

オフセット0xf6アルゴリズム（仮）では64bitで10進数の8桁を一度に計算しました。2^32全域を扱うには10桁必要なので、上8桁と下8桁に分けて繰り上がり処理が必要でした。SSEならレジスタ幅が128bitありますので16桁を一度に計算できます。良いですね。

基本戦略はオフセット0xf6アルゴリズム（仮）と一緒です。再掲します。

• 1バイト1桁（例えば64ビット変数なら8桁収まる）
• 各桁を0xf6でオフセット（0: 0xf6, 1: 0xf7, ..., 9: 0xff）
• 桁上がりするまでは数値のインクリメントは整数演算
• 桁上がりすると下の桁が全部0になるので、Trailing Zeroとマスク演算で0xf6をセットし直す

レジスタ幅が倍になって楽勝かと思いきや、SIMD命令には色々な制限があるので演算に工夫が必要です。

整数演算と桁上がりのSIMD化

値の初期化はnum = _mm_set1_epi8(0xf6)です。8ビットごとに0xf6を並べてくれます。

桁上がりしない場合は1を加算します。具体的には、num = _mm_add_epi64(num, _mm_set_epi64x(0, 1));です。_mm_set_epi64x(0, 1)は上位64bitに0、下位64bitに1をセットしています。ここまでは簡単ですね。

桁上がりする場合は少しややこしいです。下記のようなコードになります。

static void inc_c(struct dec *d)
{
	__m128i aaa;

	//下位64bitに1を加算する
	d->num = _mm_add_epi64(d->num, _mm_set_epi64x(0, 1));

	//0と比較
	//  等しい    : 結果がAll 1（数値的には-1と同じ）
	//  等しくない: 結果がAll 0（数値的には0と同じ）
	aaa = _mm_cmpeq_epi64(d->num, _mm_setzero_si128());
	//128bitの整数と見なして、8bytes = 64bit左シフト
	//  下位64bitが0    : cmpeqの結果がAll 1、シフトで上位がAll 1 = -1
	//  下位64bitが0以外: cmpeqの結果がAll 0、シフトで上位がAll 0 = 0
	aaa = _mm_slli_si128(aaa, 8);
	//減算する
	d->num = _mm_sub_epi64(d->num, aaa);
	//0x00を0xf6に置き換える
	d->num = _mm_max_epu8(d->num, _mm_set1_epi8(0xf6));
}

始めに1を加算します。桁上がりが発生する場合は下位64bitが全て0になりますから、cmpeqで0と比較すれば桁上がりが発生している場合のみ下位64bitがAll 1つまり-1になります。

下位64bitを上位に左シフトして上位の値と減算すると桁上がり処理ができます。わかりにくいですね。図解しましょう。

桁上がりがない場合

桁上がりがある場合

桁上がりで0x00になった部分を0xf6に戻す処理は、SSEには8bitごとにmaxを取れる命令があるので、一発で0x00→0xf6に置き換えできます。cmpeqとandとorでも置き換えられますが、数回試した限りどちらの実装も同じ速さに見えました。

文字列への変換

以前解説した通り、基本的には0xc6を減算、要らない桁を落とす、ビッグエンディアンに変換、の3つの処理を行います。こんなコードになります。

static int out_num(char *buf, struct dec *d)
{
	__m128i aaa, bbb;

	//8bitごとに0xc6を減算
	aaa = _mm_sub_epi64(d->num, _mm_set1_epi8(0xc6));
	//ビッグエンディアンに変換
	bbb = _mm_set_epi64x(0x0001020304050607ULL, 0x08090a0b0c0d0e0fULL);
	aaa = _mm_shuffle_epi8(aaa, bbb);
	//書きこむ必要のない桁をシフトアウト
	aaa = _mm_shuffle_epi8(aaa, mask_shuffle[16 - d->ke]);
	_mm_storeu_si128((__m128i *)buf, aaa);

要らない桁を落とすという処理は整数命令だと簡単でh <<= (落としたい桁数);のように左シフトで簡単に書けましたが、SSE命令だとちょっと厄介です。

さっき使った128bit左シフト_mm_slli_si128()を使えば良いのでは？と思いきや、実はSSEの128bitシフト命令はシフト幅が定数でなければなりません。可変値を指定するとコンパイルエラーになります。

In file included from /usr/lib/gcc/x86_64-linux-gnu/12/include/xmmintrin.h:1316,
                 from /usr/lib/gcc/x86_64-linux-gnu/12/include/immintrin.h:31,
                 from 20231009_fizzbuzz_sse4.c:12:
In function ‘_mm_slli_si128’,
    inlined from ‘inc_c’ at 20231009_fizzbuzz_sse4.c:105:8:
/usr/lib/gcc/x86_64-linux-gnu/12/include/emmintrin.h:1229:19: error: the last argument must be an 8-bit immediate
 1229 |   return (__m128i)__builtin_ia32_pslldqi128 (__A, __N * 8);
      |                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

そのためシフトをshuffle命令で実現しています。コードが非常に見づらいですね……。

確かな性能

まずは省電力PC（CPU: Pentium J4205）で測定します。ビルドするときは-msse4.1オプションを付けてください。

# 20231009_fizzbuzz_sse4.c

33.3GiB 0:00:06 [4.89GiB/s] [      <=>                                         ]

real    0m6.815s
user    0m5.121s
sys     0m3.616s

次はデスクトップPC（CPU: Ryzen 7 5700X）で測定します。

# 20231009_fizzbuzz_sse4.c

33.3GiB 0:00:01 [18.0GiB/s] [ <=>                                              ]

real    0m1.857s
user    0m1.604s
sys     0m1.025s

前回測定分（2023年10月1日の日記参照）も含めて、時間と高速化の度合いをまとめると、

さすがSSE命令ですね。素晴らしい効き目です。

ソースコード

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

•  SSE命令で最適化

マイクロアーキとシングルスレッド性能

目次: ベンチマーク

CPUマイクロアーキテクチャとシングルスレッド性能の傾向を見たいなあと思いたち、PassMarkのSingle Threadスコアを並べてみました。

• AMD系: Ryzen 7の無印となんとかXで終わる品番
• Intel系: Core i7のなんとかKで終わる品番

以上が横軸の選択基準です。絶対的な性能差はあまり気にせずに世代ごとの傾向を見ます。

AMD

Ryzen 7は階段状になるというのか、世代の変わり目がわかりやすいです。

AMD Ryzen 7各モデルのシングルスレッド性能（クリックで拡大）

マイクロアーキテクチャの変更がシングルスレッド性能にかなり影響するのでしょうか。

Intel

Core i7は世代が多いのもあって階段状には見えないですね。Haswellの4GHzモデルが妙に速い（？）以外は、Ryzen 7同様に世代を経るにつれシングルスレッド性能が上がる傾向が見えます。

Intel Core i7各モデルのシングルスレッド性能（クリックで拡大）

Rocket Lakeまでの苦戦とAlder Lake & Raptor Lakeでの巻き返しが凄いです。

FizzBuzzを速くする6（1桁落とし）

目次: ベンチマーク

FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。以前紹介（2023年9月22日の日記参照）したオフセット0xf6アルゴリズム（仮）ですが、一番下の1桁を固定文字列と見なして削減するとさらに速くなります。

思いついたときは大して速くならないと予想しましたが、実装してみると意外に効き目がありました。やってみるものですね。せっかくなのでここに書き残しておきます。

基本戦略

FizzBuzzは15個を1つの単位として同じパターンが出現します。桁上がりを考えて30個を1単位とする最適化が良い、という話を自作アルゴリズムの紹介（2023年9月21日の日記参照）で説明しました。

さらに特定の桁数を狙い撃ちで最適化しましたが、オフセット0xf6アルゴリズム（仮）と相性が良くないようで残念ながら速くなりませんでした（2023年10月1日の日記参照）。

特定の桁数に依存しないように改良したのが今回紹介する方法です。名前がないと不便なので以降「1桁落とし」と呼びます。

1桁減らすメリット

その名の通り1桁減らした数 = 10で割った数を使います。30個単位で処理するときに数値を30ずつ増やしましたが、1桁落としでは3ずつ増やします。

なくなってしまった一番下の桁はFizzやBuzzと同様に固定的に出現する文字列として出力して補填します。何を言っているのか分かりにくいと思うので適当な数（1021〜1050）を例に考えましょう。

102: ...1\n...2\nFizz\n...4\nBuzz\nFizz\n...7\n...8\nFizz\nBuzz\n
103: ...1\nFizz\n...3\n...4\nFizzBuzz\n...6\n...7\nFizz\n...9\nBuzz\n
104: Fizz\n...2\n...3\nFizz\nBuzz\n...6\nFizz\n...8\n...9\nFizzBuzz\n

（注）"..."の部分には左端の数字が入る、と考えてください。

ドット（...）で示したところには数によって変わる部分で、それ以外の部分はどんな数字が来ても常に同じです。常に同じであれば、固定値を出力すれば良いので速くなるでしょう。

数字が10個進むまで上の桁は変わらないので、同じ文字列を何度も使いまわせます。数字から文字列への変換を何度も行わなくて良いので速くなるでしょう。

オフセット0xf6アルゴリズム（仮）への適用

オフセット0xf6アルゴリズムでは数字1個につき1回、文字列への変換をしていました。1桁落としを適用すると数字から文字列への変換は10個に1回で済みます。

static void fizzbuzz30(struct dec *d, uint64_t j)
{
	uint64_t h, l;
	uint32_t wp_before = wp;
	char *p = get_p();
	char *p_s = p;
	int r;

	//数字から文字列への変換、hとlには文字列化された値が返る
	//上位桁はこのあとずっと使いまわす
	to_num(d, &h, &l);

	//...1の上位桁出力
	r = out_fixnum(p, d, h, l); p += r;
	//...1の最下位桁出力（固定文字列）
	r = out_two(p, "1\n");      p += r;

	//...2の上位桁出力
	r = out_fixnum(p, d, h, l); p += r;
	//...2の最下位桁、Fizz出力（固定文字列）
	r = out_2fizz(p);           p += r;

	//...4の上位桁出力
	r = out_fixnum(p, d, h, l); p += r;
	//...4の最下位桁、Buzz、Fizz出力（固定文字列）
	r = out_4bandf(p);          p += r;

	//...7の上位桁出力
	r = out_fixnum(p, d, h, l); p += r;
	//...7の最下位桁出力（固定文字列）
	r = out_two(p, "7\n");      p += r;

	//...8の上位桁出力
	r = out_fixnum(p, d, h, l); p += r;
	//...8の最下位桁、Fizz、Buzz出力（固定文字列）
	r = out_8fandb(p);          p += r;

	//桁上げ考慮したインクリメント（元の処理でいうと+10に相当）
	inc_c(d);

数値から文字列への変換がなくなって、使いまわしの文字列出力と固定の文字列の羅列になります。これが結構速度に効くようです。命令そのものも減りますし分岐がほとんどなくなるから（？）でしょうか？

SSE命令と合わせ技

今回紹介した1桁落としと、前回紹介したSSE命令による最適化（2023年10月9日の日記参照）は独立したアイデアのため、同時に適用できて、さらにハッピーです。

効き目を見たいので、1桁落とし＋SSE命令版も実装します。

測定

省電力PC（CPU: Pentium J4205）で測定します。SSE版をビルドするときは-msse4.1オプションを付けてください。

# 20231012_fizzbuzz_div10.c

33.3GiB 0:00:07 [4.22GiB/s] [       <=>                                        ]

real    0m7.898s
user    0m6.260s
sys     0m3.830s


# 20231012_fizzbuzz_div10_sse.c

33.3GiB 0:00:06 [5.42GiB/s] [      <=>                                         ]

real    0m6.147s
user    0m4.212s
sys     0m4.243s

次はデスクトップPC（CPU: Ryzen 7 5700X）で測定します。

# 20231012_fizzbuzz_div10.c

33.3GiB 0:00:01 [18.6GiB/s] [ <=>                                              ]

real    0m1.799s
user    0m1.482s
sys     0m1.089s


# 20231012_fizzbuzz_div10_sse.c

33.3GiB 0:00:01 [19.1GiB/s] [ <=>                                              ]

real    0m1.744s
user    0m1.480s
sys     0m1.034s

前回測定分（2023年10月1日の日記参照）も含めて、時間と高速化の度合いをまとめると、

今回の測定では2^32 - 2までしか測っていませんが、もっと大きな数までFizzBuzzする場合、特定の桁数のみを狙った（前回は9桁と10桁に特化）最適化は桁数が変わると効果がなくなるのに対し、1桁落としならば何桁になっても効果があるのが嬉しいところです。

ソースコード

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

•  1桁落とし
•  1桁落としとSSE命令