コグノスケ

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

目次: ベンチマーク - まとめリンク

昨日（2023年9月22日の日記参照）の続き。アルゴリズムの差を見てきましたが、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を速くする2（高速アルゴリズムの紹介）

目次: ベンチマーク - まとめリンク

昨日（2023年9月21日の日記参照）の続き。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桁が499から500になります。

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

面倒な処理は不要で、+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最適化アルゴリズムの差と言えましょう。