目次: ベンチマーク
CPUマイクロアーキテクチャとシングルスレッド性能の傾向を見たいなあと思いたち、PassMarkのSingle Threadスコアを並べてみました。
以上が横軸の選択基準です。絶対的な性能差はあまり気にせずに世代ごとの傾向を見ます。
Ryzen 7は階段状になるというのか、世代の変わり目がわかりやすいです。
AMD Ryzen 7各モデルのシングルスレッド性能(クリックで拡大)
マイクロアーキテクチャの変更がシングルスレッド性能にかなり影響するのでしょうか。
Core i7は世代が多いのもあって階段状には見えないですね。Haswellの4GHzモデルが妙に速い(?)以外は、Ryzen 7同様に世代を経るにつれシングルスレッド性能が上がる傾向が見えます。
Intel Core i7各モデルのシングルスレッド性能(クリックで拡大)
Rocket Lakeまでの苦戦とAlder Lake & Raptor Lakeでの巻き返しが凄いです。
目次: ベンチマーク
FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。以前紹介(2023年9月22日の日記参照)したオフセット0xf6アルゴリズム(仮)ですが、一番下の1桁を固定文字列と見なして削減するとさらに速くなります。
思いついたときは大して速くならないと予想しましたが、実装してみると意外に効き目がありました。やってみるものですね。せっかくなのでここに書き残しておきます。
FizzBuzzは15個を1つの単位として同じパターンが出現します。桁上がりを考えて30個を1単位とする最適化が良い、ことを自作アルゴリズムの紹介(2023年9月21日の日記参照)で説明しました。
さらに特定の桁数を狙い撃ちで最適化しましたが、オフセット0xf6アルゴリズム(仮)と相性が良くないようで残念ながら速くなりませんでした(2023年10月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アルゴリズムでは数字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);
数値から文字列への変換がなくなって、使いまわしの文字列出力と固定の文字列の羅列になります。これが結構速度に効くようです。命令そのものも減りますし分岐がほとんどなくなるから(?)でしょうか?
今回紹介した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日の日記参照)も含めて、時間と高速化の度合いをまとめると、
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 |
1桁落とし | 7.898s | x8.4 | 1.799s | x8.7 |
1桁落とし+SSE命令 | 6.147s | x10.8 | 1.744s | x9.0 |
今回の測定では2^32 - 2までしか測っていませんが、もっと大きな数までFizzBuzzする場合、特定の桁数のみを狙った(前回は9桁と10桁に特化)最適化は桁数が変わると効果がなくなるのに対し、1桁落としならば何桁になっても効果があるのが嬉しいところです。
ソースコードはこちらからどうぞ。
目次: ベンチマーク
FizzBuzzの実装は簡単ですが、可能な限り高速に出力しようとするとなかなか面白い遊びになります。今回は実装の改善ではなく、コンパイラを変えたらどうなるか試しました。gccとclangのどちらが速いかは場合によるみたいで、一筋縄ではいかないです。
ソースコードが散らかっていたので再整理し、実装も少し見直してシンプルにしています。最適化のアイデアや仕組みは今まで解説した通りです。
各最適化のアイデアは基本的に独立しており順不同で適用できますが、いくつか依存関係があります。
自分で実装してみたい人以外は気にしなくて良いと思います。
省電力PCの測定環境は、
デスクトップPCの測定環境は、
です。
全てのログを載せると大変なことになるので、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秒くらい間を空けて実行しています。
FizzBuzzの種類 | Pentium, GCC -O3 | 倍率 | Pentium, clang -O3 | 倍率 | Ryzen, GCC -O3 | 倍率 | Ryzen, clang -O3 | 倍率 |
---|---|---|---|---|---|---|---|---|
単純 | 452.839 | - | 458.004 | - | 100.475 | - | 101.528 | - |
独自itoa | 61.995 | x7.3 | 59.485 | x7.7 | 13.547 | x7.4 | 12.737 | x8.0 |
30個まとめ | 39.064 | x11.6 | 56.258 | x8.1 | 8.969 | x11.2 | 13.600 | x7.5 |
オフセット0xf6 | 10.071 | x45.0 | 16.548 | x27.7 | 2.097 | x47.9 | 4.114 | x24.7 |
1桁落とし | 7.687 | x58.9 | 9.804 | x46.7 | 1.684 | x59.7 | 2.712 | x37.4 |
SSE版 | 5.319 | x85.1 | 4.528 | x101 | 1.723 | x58.3 | 1.468 | x69.2 |
FizzBuzzの種類 | Pentium, GCC -Os | 倍率 | Pentium, clang -Os | 倍率 | Ryzen, GCC -Os | 倍率 | Ryzen, clang -Os | 倍率 |
---|---|---|---|---|---|---|---|---|
単純 | 515.882 | - | 457.593 | - | 101.853 | - | 102.073 | - |
独自itoa | 151.588 | x3.4 | 89.760 | x5.1 | 20.747 | x5.0 | 17.753 | x5.8 |
30個まとめ | 60.041 | x8.6 | 55.899 | x8.2 | 10.551 | x9.7 | 13.905 | x7.3 |
オフセット0xf6 | 21.828 | x23.6 | 15.536 | x29.5 | 4.836 | x21.1 | 3.666 | x27.8 |
1桁落とし | 16.237 | x31.8 | 9.902 | x46.2 | 4.787 | x21.3 | 2.456 | x41.6 |
SSE版 | 4.870 | x106 | 4.670 | x98.1 | 1.603 | x63.5 | 1.478 | x69.1 |
最速はclang -O3でしたが、常にclangの生成するコードが速い訳でもなければ、場合によってはO3がOsより遅くなることもありまして最適化の奥深さを感じます。
ソースコードはこちらからどうぞ。
目次: RISC-V
最近はRISC-Vのシングルボードコンピュータ(SBC)が市販されています。嬉しい時代になりました。これからのお買い物の参考としてリストアップしました。
前回(2022年3月17日の日記参照)同様に自治体の接種会場に行きました。ワクチンは前回同様にモデルナ製です。
時期的には5回目の接種時期ですが、私はうっかりしていて1回行くのを忘れてしまい、今回が4回目の接種です。いつもながら看護師を始めとした医療従事者の皆様は非常に親切かつ効率的に働いていました。ありがてぇことです。
マメな世の中の人はみな5回目の接種だからか、接種会場では「5回目の接種でよろ……あら?4回目です?」って2度ほど聞かれました。ワクチンって打つ人は毎回打つし、打たない人は全然打たないのかなあ?
COVIDのワクチンは他のワクチンと比べると副作用が結構強いですよね。熱は解熱剤で何とかなるんですが、とにかく肩が痛い。
この日記にはいくつかヘッダ(Hxタグ)を使っており、文書の構造は下記のようにしています。
しかしどうもGoogleさんはH4タグを拾わないときがあるようで、
こんな風に日付だけが出て、内容が良くわからなくなってしまうことがあります。試しに日記内のトピックを格上げし、日記の日付と同格のH3にして検索結果がどうなるか観察しようと思います。
日付を消すことも少し考えましたが、とりあえず今のままにしておきます。テキスト環境のブラウザで見るときにも日付があると結構見やすいですし(日記の切れ目が分かりやすい……気がする)。
目次: ベンチマーク
FizzBuzzを作っていて気づきましたが、vmsplice()を使うとメチャクチャ速いyesコマンドを実装できます。
昔に紹介した通り(2017年6月14日の日記参照)GNU yes 8.26近辺から出力がとても速くなっています。あとで分析しますがwrite()を使ったときの最速と思われる速度が出ますが、出力先をパイプに限定して良ければvmsplice()を使うことでさらに速くできます。
$ ./yes vmsplice: Bad file descriptor
ちなみに今回紹介する高速化の手法であるvmsplice()はパイプ以外、例えば端末に出そうとするとエラーになりますから、汎用的なyesコマンドの実装としては使えません。状況に制限を掛けてまで高速なyesが欲しい場合が果たしてあるだろうか?と言われると、うーん、すぐには思いつかないですね……。ベンチマークには役に立ちますけども。
本来のyesコマンドの仕様は「引数で受け取った文字列と改行を無限に出力する」ですが、ベンチマークの都合上どこか一定の場所で終わってほしいので、適当に0x2ffffffff行(128億行)くらい出力したら終わりとします。行数は多少増減しても気にしないことにします。デフォルトでは1行2バイト('y'と改行)なので出力するデータ量の合計は24GBくらいになります。
内容的には難しくないので不要な気もしますが、正常動作を確かめるテストプログラムを作ります。基本的に延々と同じ内容の行が出力されるだけなので、全て見なくても0x0fff_ffff(2億行)も見れば十分でしょう。たぶん。
// 20231106_test_yes.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char *argv[])
{
const char *ex;
char expected[256];
char *inbufp = NULL;
size_t insz = 0;
if (argc < 2) {
ex = "y";
} else {
ex = argv[1];
}
snprintf(expected, sizeof(expected), "%s\n", ex);
for (unsigned int i = 1; i < 0xfffffff; i++) {
getline(&inbufp, &insz, stdin);
if ((i & 0xffffff) == 0) {
printf("\r%u ", i);
fflush(stdout);
}
if (strcmp(expected, inbufp) != 0) {
printf("\n");
printf("Not matched in %u\n", i);
printf(" expected: %s\n", expected);
printf(" input : %s\n", inbufp);
return 1;
}
}
printf("\nOK\n");
return 0;
}
本物のyesをテストしてみてfailしないか確かめます。
$ yes | ./test_yes 251658240 OK $ yes aaaaaaaa | ./test_yes aaaaaaaa 251658240 OK ### 引数の指定が効いているか確かめる $ yes | ./test_yes aaaaaaaa Not matched in 1 expected: aaaaaaaa input : y $ yes aaaaaaaa | ./test_yes Not matched in 1 expected: y input : aaaaaaaa
良さそうですね。あとは測定環境です。省電力PCの測定環境は、
デスクトップPCの測定環境は、
準備完了です。ではいってみよう。
最初はprintf()で普通に実装しましょう。
// 20231106_yes_simple.c
#include <stdint.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
const char *arg;
if (argc < 2) {
arg = "y";
} else {
arg = argv[1];
}
for (uint64_t i = 0; i < 0x2ffffffff; i++) {
printf("%s\n", arg);
}
return 0;
}
$ gcc 20231106_yes_simple.c -msse4 -O3 24.0GiB 0:08:31 [48.1MiB/s] [ <=> ] real 8m31.031s user 8m26.537s sys 0m36.512s
一度のprintf()で2バイトしか出力しないので、メチャクチャ遅いですね。
次はwrite()とバッファリングを使います。アイデアは単純で、適当な大きさのバッファに出力する文字を詰められるだけ詰めて、バッファをwrite()に渡して複数行を一気に出力する方法です。本来の処理では不要ですが、ベンチマークのため一度に何行出力しているか覚えておく必要があります。
// 20231106_yes_buf.c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define CHUNKSIZE (4096 * 2)
char output[CHUNKSIZE] __attribute__((aligned(4096)));
int main(int argc, char *argv[])
{
const char *arg;
char out_one[256];
size_t len_one, len = 0;
int d = 0;
if (argc < 2) {
arg = "y";
} else {
arg = argv[1];
}
len_one = snprintf(out_one, sizeof(out_one), "%s\n", arg);
while (len + len_one < sizeof(output) - 1) {
strcat(output, out_one);
len += len_one;
d++;
}
for (uint64_t i = 0; i < 0x2ffffffff - 1; i += d) {
write(1, output, len);
}
return 0;
}
$ gcc 20231106_yes_buf.c -msse4 -O3 24.0GiB 0:00:11 [2.16GiB/s] [ <=> ] real 0m11.095s user 0m1.564s sys 0m20.571s (参考 GNU yesの速度) $ yes --version yes (GNU coreutils) 9.1 (以下略) $ time taskset 0x1 yes | taskset 0x4 pv > /dev/null 24.2GiB 0:00:11 [2.23GiB/s] [ <=> ] ^C real 0m11.600s user 0m1.528s sys 0m21.621s
一気に速くなりました。GNU yesの速度も参考に載せましたが、ほぼ同じ速度です。これがwrite()で出力するときの限界速度でしょう。
最後はvmsplice()です。基本的なアイデアはバッファリング版yesと同じです。ただしvmsplice()に対応するために、ダブルバッファリングとバッファ終端からはみ出た場合の処理を追加します。
// 20231106_yes_vmsplice.c
#define _GNU_SOURCE
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/uio.h>
#define CHUNKSIZE (4096 * 64)
char buf2[2][CHUNKSIZE + 4096] __attribute__((aligned(4096)));
int f __attribute__((aligned(8)));
char output[2048] __attribute__((aligned(4096)));
static void vwrite(int fd, void *buf, size_t count)
{
struct iovec iov;
ssize_t n;
iov.iov_base = buf;
iov.iov_len = count;
while (iov.iov_len > 0) {
n = vmsplice(1, &iov, 1, 0);
if (n < 0) {
perror("vmsplice");
exit(1);
}
iov.iov_base += n;
iov.iov_len -= n;
}
}
int main(int argc, char *argv[])
{
const char *arg;
char out_one[256];
char *p = buf2[f];
size_t len_one, len = 0;
int d = 0;
fcntl(1, F_SETPIPE_SZ, CHUNKSIZE);
if (argc < 2) {
arg = "y";
} else {
arg = argv[1];
}
len_one = snprintf(out_one, sizeof(out_one), "%s\n", arg);
while (len + len_one < sizeof(output) - 1) {
strcat(output, out_one);
len += len_one;
d++;
}
for (uint64_t i = 0; i < 0x2ffffffff - 1; i += d) {
memcpy(p, output, len);
p += len;
int n = p - buf2[f] - CHUNKSIZE;
if (n >= 0) {
vwrite(1, buf2[f], CHUNKSIZE);
f = !f;
memcpy(buf2[f], &buf2[!f][CHUNKSIZE], n);
p = &buf2[f][n];
}
}
return 0;
}
$ gcc 20231106_yes_vmsplice.c -msse4 -O3 24.0GiB 0:00:03 [7.14GiB/s] [ <=> ] real 0m3.367s user 0m1.849s sys 0m3.297s
予想はしていましたがメチャクチャ速くなりました……。vmsplice()恐るべし。
$ gcc 20231106_yes_simple.c -msse4 -O3 24.0GiB 0:01:54 [ 213MiB/s] [ <=> ] real 1m54.938s user 1m52.312s sys 0m22.559s $ gcc 20231106_yes_buf.c -msse4 -O3 24.0GiB 0:00:05 [4.49GiB/s] [ <=> ] real 0m5.347s user 0m0.912s sys 0m9.776s $ gcc 20231106_yes_vmsplice.c -msse4 -O3 24.0GiB 0:00:00 [33.7GiB/s] [<=> ] real 0m0.715s user 0m0.508s sys 0m0.721s
PentiumとRyzen 7の測定結果、どの程度速くなったかを合わせて表にすると、
FizzBuzzの種類 | Pentium, GCC -O3 | 倍率 | Ryzen 7, GCC -O3 | 倍率 |
---|---|---|---|---|
単純 | 511.031 | - | 114.938 | - |
バッファリング | 11.600 | x44.0 | 5.347 | x21.5 |
vmsplice | 3.367 | x151.8 | 0.715 | x160.7 |
使える場所が限定されるとはいえ素晴らしい効き目ですね。ちなみにRyzen 7はバッファサイズを4倍(1MB x 2)にするとさらに速くなって、0.612秒(39.4GiB/s、187.8倍)くらいになります。まさか1秒も掛からないとは思わなんだ……。
ソースコードはこちらからどうぞ。
< | 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.)