目次: ベンチマーク
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アルゴリズム(仮)と一緒です。再掲します。
レジスタ幅が倍になって楽勝かと思いきや、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日の日記参照)も含めて、時間と高速化の度合いをまとめると、
FizzBuzzの種類 | Pentium J4205の実行時間 | 倍率 | Ryzen 7の実行時間 | 倍率 |
---|---|---|---|---|
自前itoa | 1m6.621s | - | 15.759s | - |
30個まとめる | 38.860s | x1.7 | 9.152s | x1.7 |
オフセット0xf6 | 9.671s | x6.8 | 2.063s | x7.6 |
SSE命令 | 6.815s | x9.7 | 1.857s | x8.4 |
さすがSSE命令ですね。素晴らしい効き目です。
ソースコードはこちらからどうぞ。
横浜で大学の研究室の先輩のお葬式(正確には無宗教のお別れの会)がありました。突然の訃報にただただ驚き、悲しみを覚えるばかりでした。45歳は若すぎます……。喪主はお兄さんが務めておられました。お兄さんは初来日だそうですが、初来日が弟さんのお葬式なんて悲しすぎます……。英会話すると、自分の英語のヘボさと理解の怪しさをビシビシ感じます。
大学の研究室のみなさまと久しぶりに会えました。故人の思い出をたくさん話せたかなと思います。
最近は毎日リモートワークの人も珍しくありませんが、1人暮らしor共働きで家人が居ないなどの場合、自宅で倒れてしまっても誰も気づけない欠点があることに気づかされました。だから全員毎日出社すべしとは思いませんけども、周りが気づける方法があると良いなとは思います。
会場近くのお花屋さんで献花用のお花を買いたくて、徒歩より移動しやすかろうと車で向かったのは失敗でした。横浜横須賀道路が激しく渋滞していてかなり時間が掛かりました。周りの車を見ると埼玉?千葉?県外ナンバーばかりです、なぜこんなところに……って連休で遠出する人達かあ。3連休初日の朝であることを忘れていました。
会場までの所要時間が良くわからなかったので、1時間くらい余裕見て出発したのが功を奏し、幸いなことに遅刻はしませんでした。
目次: ベンチマーク
FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。今回はあるCPUでうまくいっても、他のCPUでは効果がないケースをご紹介します。
実験用に4つのコードを用意しました。出力がボトルネックになって測定結果が不必要に遅く見えないよう、vmspliceとバッファリングは最初から実装します。
30個まとめて処理する最適化で速くなるのはほぼ確実でしょう。3つ目は、前回(2023年9月23日の日記参照)紹介したオフセット0xf6アルゴリズムです。これも速くなるのはほぼ確実でしょう。
4つ目は、前々回(2023年9月21日の日記参照)紹介した9桁と10桁を狙い撃ちで最適化する方法です。自前のitoa()には効果抜群でしたので、オフセット0xf6アルゴリズムとの相乗効果にも期待したいところです。
まずは省電力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(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桁狙い撃ちで最適化すると逆に遅くなりました。時間と高速化の度合いをまとめると、
FizzBuzzの種類 | Pentium J4205の実行時間 | 倍率 | Ryzen 7の実行時間 | 倍率 |
---|---|---|---|---|
自前itoa | 1m6.621s | - | 15.759s | - |
30個まとめる | 38.860s | x1.7 | 9.152s | x1.7 |
オフセット0xf6 | 9.671s | x6.8 | 2.063s | x7.6 |
9桁10桁狙い撃ち | 8.906s | x7.4 | 2.112s | x7.4 |
Ryzen 7 5700Xでなぜ遅くなるのか?は内部構造を知らないので何とも言えませんが、あるCPUに効く最適化が他のCPUだと効果がなかったり逆効果になったりすることは良くあります。
ソースコードはこちらからどうぞ。
< | 2023 | > | ||||
<< | < | 10 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 | - | - | - | - |
合計:
本日:
管理者: Katsuhiro Suzuki(katsuhiro( a t )katsuster.net)
This is Simple Diary 1.0
Copyright(C) Katsuhiro Suzuki 2006-2023.
Powered by PHP 8.3.8.
using GD bundled (2.1.0 compatible)(png support.)