コグノスケ

FizzBuzzを速くする7（コンパイラによる違い）

目次: ベンチマーク

FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。今回は実装の改善ではなく、コンパイラを変えたらどうなるか試しました。gccとclangのどちらが速いかは場合によるみたいで、一筋縄ではいかないです。

基本戦略

ソースコードが散らかっていたので再整理し、実装も少し見直してシンプルにしています。最適化のアイデアや仕組みは今まで解説した通りです。

単純: 20231019_fizzbuzz_simple.c

第1回で紹介（2023年9月21日の日記参照）した、条件分岐と剰余演算とprintf()を使った単純な実装です。全てはここから始まりました。

独自itoa(): 20231019_fizzbuzz_base.c

第1回で紹介（2023年9月21日の日記参照）した、独自のitoa()を実装した単純な実装です。でも実装の主眼はそちらではなく、ダブルバッファリングとvmsplice()を導入して、以降の改善で出力側がボトルネックにならないようにしています。

30個まとめ: 20231019_fizzbuzz_30.c

第1回で少し紹介（2023年9月21日の日記参照）した、一度に30個処理することで条件分岐や剰余演算を省いた実装です。

オフセット0xf6アルゴリズム（仮）: 20231019_fizzbuzz_offset.c

第2回で紹介（2023年9月22日の日記参照）した、桁上がりと文字列変換の効率を両立したエレガントなアルゴリズムを用いた実装です。

1桁落とし: 20231019_fizzbuzz_div10.c

第6回で紹介（2023年10月12日の日記参照）した、30個まとめるアイデアをもう一歩改善した実装です。

オフセット0xf6アルゴリズム（仮）SSE版: 20231019_fizzbuzz_sse.c

第5回で紹介（2023年10月9日参照）した、オフセット0xf6アルゴリズム（仮）をSIMD命令（SSE4.1）を使って最適化した実装です。

各最適化のアイデアは基本的に独立しており順不同で適用できますが、いくつか依存関係があります。

• オフセット0xf6アルゴリズム（仮）の発展 → オフセット0xf6アルゴリズム（仮）SIMD版
• 30個まとめの発展 → 1桁落とし

自分で実装してみたい人以外は気にしなくて良いと思います。

環境

省電力PCの測定環境は、

• 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)
• clang 14.0.6

デスクトップPCの測定環境は、

• 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)
• clang 14.0.6

です。

測定

全てのログを載せると大変なことになるので、clang -O3かつ省電力PC（CPU: Pentium J4205）で測定した結果のみを載せます。

# clang 20231019_fizzbuzz_simple.c -msse4 -O3

33.3GiB 0:07:38 [74.5MiB/s] [                                      <=>         ]

real    7m38.004s
user    7m31.530s
sys     0m50.762s

# clang 20231019_fizzbuzz_base.c -msse4 -O3

33.3GiB 0:00:59 [ 573MiB/s] [                                     <=>          ]

real    0m59.485s
user    0m58.090s
sys     0m4.266s

# clang 20231019_fizzbuzz_30.c -msse4 -O3

33.3GiB 0:00:56 [ 606MiB/s] [                                        <=>       ]

real    0m56.258s
user    0m54.688s
sys     0m4.597s

# clang 20231019_fizzbuzz_offset.c -msse4 -O3

33.3GiB 0:00:16 [2.01GiB/s] [               <=>                                ]

real    0m16.548s
user    0m15.406s
sys     0m3.040s

# clang 20231019_fizzbuzz_div10.c -msse4 -O3

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

real    0m9.804s
user    0m8.510s
sys     0m3.004s

# clang 20231019_fizzbuzz_sse.c -msse4 -O3

33.3GiB 0:00:04 [7.36GiB/s] [    <=>                                           ]

real    0m4.528s
user    0m3.856s
sys     0m1.875s

コンパイラの種類も変えて測定した結果を載せます。Pentium J4205でSSE版の実装を連続で実行すると負荷が掛かりすぎる（？）のか、サーマルスロットリングに引っかかるのか、極端に速度が低下してしまうことがあるため、30秒くらい間を空けて実行しています。

最速はclang -O3でしたが、常にclangの生成するコードが速い訳でもなければ、場合によってはO3がOsより遅くなることもありまして最適化の奥深さを感じます。

ソースコード

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

•  単純
•  独自itoa()
•  30個まとめ
•  オフセット0xf6アルゴリズム（仮）
•  1桁落とし
•  オフセット0xf6アルゴリズム（仮）SSE版

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命令

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

目次: ベンチマーク

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での巻き返しが凄いです。