
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シフト命令はシフト幅が定数でなければなりません。可変値を指定するとコンパイルエラーになります。

_mm_slli_si128()のシフト幅に定数以外を指定したときのエラー

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オプションを付けてください。

Pentium J4205での実行結果

# 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）で測定します。

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命令ですね。素晴らしい効き目です。

ソースコード

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

SSE命令で最適化

編集者:すずき(2024/07/10 02:04)

コメント一覧

コメントはありません。

この記事にコメントする

2023年10月7日

permalink

編集する

お葬式

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

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

リモートワーク

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

横浜の道路は大渋滞

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

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

編集者:すずき(2024/07/10 02:02)

コメント一覧

コメントはありません。

この記事にコメントする

2023年10月1日

permalink

編集する

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）で測定します。

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）で測定します。

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桁狙い撃ちで最適化すると逆に遅くなりました。時間と高速化の度合いをまとめると、