コグノスケ

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