2021/06/04(Fri)
○[オレオレN6] gprof(1)とdlopen(3)
ワイド文字扱うプログラムの性能テストを実施する時に困るのがCitrusがdlopen(3)を使うプラグインシステムってことなんだよな。 gprof(1)で統計情報とるのにgccに-pgオプションつけてプロファイリングを有効にするともれなくdlopen(3)が無効になるので、i18n moduleの動的ロードができずsetlocale(3)に失敗してしまうのだ。
そもそもSolarisとかだと-pgつきでコンパイルした場合、dlopen(3)したライブラリの統計情報は取れない制限はあれど動的ロードに失敗するなんてことは無かったように思うのだがもう昔のこと過ぎて覚えてない。 これってNだけの制限事項だったりしたらアレね…まぁそのへん調査しはじめると脱線が止まらずいつまでたっても本線に戻れないので考えないようにする。
そもそも同じくdlopen(3)を使うのCitrus iconvの性能ボトルネック調査にふつーにgprof(1)使って特定してた記憶があるんだがどうやってたんだっけ俺。 なんかもうこういうツールの使い方を長いブランクですっかり忘れてしまった感がある、思い出さないと…
@前回のrbtree(3)が遅いって話の続き
昨日の記事書いた後に気づいたのだけど、Nにもとっくの昔にtree(3)あるじゃねーのびっくり。今は亡きsystraceが移植された18年前から存在しとった模様。
なんでrbtree(3)とtree(3)で二重に赤黒木の実装持ってんだよという話なんだが、その当時だとrbtree.h(rb.h)はlibkernにしかなくユーザランドでは使えなかったからっぽい。 じゃあrbtree(3)をユーザーランドに移す時どっちかに統一しろやという話なのだが、rbtree(3)の作者はmatt@(立浪すら頭の上がらない桑田の息子ではない方)だったのでいつものお察し案件であった。
まぁ機能重複とかチャメシインシデントではある、例えばlibc内のconstant database実装(読込専用のKVS)もすでにcitrus_dbというものが存在するのを知りつつわざわざcdb(5)という車輪の再発明を突っ込むドイツ人とかもいたので、Linusおじさんみたいな独裁者がこーゆー連中うまく捌かんとグダグダになりますわね。
話脱線するけど昔懐かしLinusおじさんのNVIDIA🖕動画、「これはNVIDIAのGPUを利用したディープフェイク動画ですか？」といってる人を某所でみて大草原。いやー彼のひととなりを知らずにコンピューターの偉い人くらいにしか思ってないと簡単に認知が歪むんすね。
@簡単なテストでプロファイルとってみた
やる気ねえのでごく簡単に。
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdlib.h>
#include <wchar.h>
#include "bmw.h"
static void *
map(const char *path, size_t *size)
{
int fd;
struct stat st;
void *mapped;
if ((fd = open(path, O_RDONLY|O_CLOEXEC)) == -1)
abort();
if (fstat(fd, &st) == -1)
abort();
if (!S_ISREG(st.st_mode))
abort();
mapped = mmap(NULL, (size_t)st.st_size, PROT_READ,
MAP_FILE|MAP_PRIVATE, fd, (off_t)0);
if (mapped == MAP_FAILED)
abort();
*size = (size_t)st.st_size;
return mapped;
}
int
main(void)
{
const wchar_t *txt, *pat, *cp;
size_t txtsize, patsize, txtlen, patlen, i;
bmw_pat_t b;
txt = map("../test/test.txt", &txtsize);
pat = map("../test/pat.txt", &patsize);
txtlen = wcslen(txt);
patlen = wcslen(pat) - 1;
for (i = 0; i < 50000; ++i) {
b = bmw_comp(pat, patlen);
cp = bmw_exec(b, txt, txtlen);
bmw_free(b);
}
munmap(__UNCONST(txt), txtsize);
munmap(__UNCONST(pat), patsize);
}
テストデータとパターンをファイルから読む込む、前述の通りLC_CTYPEが使えない問題があるので、ファイルをUTF-32LE(BOMなし)で保存してwchar_tかの如く扱うことで対処する。
テストデータには青空文庫の夢野久作「ドグラマグラ」を使った、パターンは同作中の最後の方から適当に「昨十九日（火曜日）正午頃～」の一文を選んだ。 これを50000回実行した結果のプロファイルを行う、うわーほんとクッソ雑。
こっちがNのrbtree(3)を使って採取したgprof(1)の結果の抜粋。
$ time ./test
58.05s real 58.03s user 0.00s system
index % time self children called name
-----------------------------------------------
0.90 11.11 50000/50000 main [2]
[3] 63.9 0.90 11.11 50000 bmw_comp [3]
3.67 1.94 70200000/118100000 rb_tree_find_node [4]
2.10 2.58 20450000/20450000 rb_tree_insert_node [6]
0.04 0.78 20500000/20500000 malloc [12]
0.00 0.00 50000/50000 rb_tree_init [64]
-----------------------------------------------
2.50 1.32 47900000/118100000 bcrskip [7]
3.67 1.94 70200000/118100000 bmw_comp [3]
[4] 50.1 6.17 3.26 118100000 rb_tree_find_node [4]
3.26 0.00 883500000/1037250000 bmw_bcrext_compare_key [8]
-----------------------------------------------
0.23 3.83 47900000/47900000 bmw_exec [5]
[7] 21.6 0.23 3.83 47900000 bcrskip [7]
2.50 1.32 47900000/118100000 rb_tree_find_node [4]
-----------------------------------------------
0.07 1.70 50000/50000 main [2]
[10] 9.4 0.07 1.70 50000 bmw_free [10]
0.17 0.65 20450000/20450000 rb_tree_remove_node [11]
0.01 0.66 20500000/20500000 free [15]
0.20 0.00 20500000/20500000 rb_tree_iterate [24]
こちらがtree(3)を使っての結果。
$ time ./test
47.83s real 47.81s user 0.01s system
index % time self children called name
-----------------------------------------------
0.66 6.40 50000/50000 main [2]
[3] 57.3 0.66 6.40 50000 bmw_comp [3]
2.35 1.22 70200000/118100000 bmw_bcrext_tree_RB_FIND [4]
0.76 1.31 20450000/20450000 bmw_bcrext_tree_RB_INSERT [8]
0.05 0.72 20500000/20500000 malloc [11]
-----------------------------------------------
1.61 0.83 47900000/118100000 bcrskip [6]
2.35 1.22 70200000/118100000 bmw_comp [3]
[4] 48.7 3.96 2.04 118100000 bmw_bcrext_tree_RB_FIND [4]
2.04 0.00 883500000/1037250000 bmw_bcrext_compare_key [7]
-----------------------------------------------
0.29 4.54 47900000/47900000 bmw_exec [6]
[8] 22.8 0.29 4.54 47900000 bcrskip [8]
0.09 4.46 47900000/118100000 bmw_bcrext_tree_RBT_FIND [4]
-----------------------------------------------
0.09 1.30 50000/50000 main [2]
[9] 11.3 0.09 1.30 50000 bmw_free [9]
0.02 0.68 20500000/20500000 free [13]
0.10 0.45 20450000/20450000 bmw_bcrext_tree_RB_REMOVE [17]
0.05 0.00 20450000/20450000 bmw_bcrext_tree_RB_NEXT [25]
0.00 0.00 50000/50000 bmw_bcrext_tree_RB_MINMAX [61]
検索(find)と追加が(insert)rbtree(3)の方が遅いよね。
とはいえcalledの回数みれば判ると思うけど僅かな差が積もり積もった結果なので、普通のプログラムなら性能差が問題になることは無いので普通でない人以外は安心してよろしい。
それにそもそもO由来のtree(3)の方が性能がいいとはいえど、実はOのtree(3)には
- RB_*
- RBT_*
という2つの実装が存在してNにも移植されてる前者が高速なのだけど、後者はrbtree(3)の性能低下なんぞ誤差にみえるくらいクソ性能悪いんだよな。
$ time ./test
120.27s real 105.54s user 0.01s system
index % time self children called name
-----------------------------------------------
1.46 11.43 50000/50000 main [2]
[3] 60.8 1.46 11.43 50000 bmw_comp [3]
0.13 6.53 70200000/118100000 bmw_bcrext_tree_RBT_FIND [4]
0.05 3.80 20450000/20450000 bmw_bcrext_tree_RBT_INSERT [9]
0.06 0.69 20500000/20500000 malloc [17]
0.00 0.17 50000/50000 bmw_bcrext_tree_RBT_INIT [32]
-----------------------------------------------
0.09 4.46 47900000/118100000 bcrskip [8]
0.13 6.53 70200000/118100000 bmw_comp [3]
[4] 52.8 0.21 10.99 118100000 bmw_bcrext_tree_RBT_FIND [4]
5.21 5.77 118100000/118100000 rb_find [5]
-----------------------------------------------
5.21 5.77 118100000/118100000 bmw_bcrext_tree_RBT_FIND [4]
[5] 51.8 5.21 5.77 118100000 rb_find [5]
2.06 2.25 883500000/1037250000 bmw_bcrext_tree_RBT_COMPARE [7]
1.46 0.00 883500000/1078150000 rb_e2n [13]
-----------------------------------------------
0.29 4.54 47900000/47900000 bmw_exec [6]
[8] 22.8 0.29 4.54 47900000 bcrskip [8]
0.09 4.46 47900000/118100000 bmw_bcrext_tree_RBT_FIND [4]
-----------------------------------------------
0.09 1.88 50000/50000 main [2]
[12] 9.3 0.09 1.88 50000 bmw_free [12]
0.04 0.79 20500000/20500000 free [15]
0.04 0.68 20450000/20450000 bmw_bcrext_tree_RBT_REMOVE [18]
0.02 0.22 20450000/20450000 bmw_bcrext_tree_RBT_NEXT [28]
0.09 0.00 50000/50000 bmw_bcrext_tree_RBT_MIN [38]
さすがにこれ誤差だよと無視できない遅さなんやな、そもそもRBT_*はマニュアルにも載ってないのだけどなんで追加したんだろうな。
このRBT_*の方の作者はOのdeveloperのdlg@で最近(2016年)の仕事なのだが、特に意味なく追加されたとはOの厳格なレビューシステム上考えにくいのでなんか理由があるんだろうな。 まぁqueue(3)だって機能毎に何種類もありそれぞれ性能も違うので必要に応じての使い分けるべきなんだろう、きっとRBT_*にはRB_*には無い素敵な器官が備わってるに違いない俺にはよくわからないし調べる気力もないが。
はい最後、赤黒木でなく配列を使った最初の実装での結果。
$ time ./test
50.05s real 49.73s user 0.00s system
-----------------------------------------------
26.98 1.86 50000/50000 main [1]
[3] 85.3 26.98 1.86 50000 bmw_comp [3]
0.86 1.00 50000/50000 qsort [7]
0.00 0.00 50000/50000 malloc [30]
-----------------------------------------------
0.35 3.49 47900000/47900000 bmw_exec [4]
[5] 11.4 0.35 3.49 47900000 bcrskip [5]
2.22 1.27 47900000/47900000 bsearch [6]
-----------------------------------------------
2.22 1.27 47900000/47900000 bcrskip [5]
[6] 10.3 2.22 1.27 47900000 bsearch [6]
1.27 0.00 389700000/562750000 bmw_bcrext_cmp [8]
-----------------------------------------------
0.01 0.00 50000/50000 bmw_free [12]
[13] 0.0 0.01 0.00 50000 free [13]
0.00 0.00 50000/50000 idalloc [28]
テストデータを改めてパターンに含まれる文字種が大幅に増えたので、前回はrbtree(3)よりも3倍速いシャアが来るだったのに同じくらいにまで劣化してしまった。 クッソ雑な実装なので重複排除に毎回配列を頭から嘗めてるし最後にはqsort(3)とかやっとるしな、そらそうなるよ知ってた。だからこそ赤黒木で再実装したんだけど。
ただまぁbcrskip()の部分だけみるとbsearch(3)の方が速いですわな二分探索と二分探索木の計算量ってどうだったっけ、うーん性能出すためには自前でAVL木とかも実装してテストしろってアリ地獄コースなんですかこれ。 またどんどん横道逸れてって本題解決しないパターンじゃないですかやだー。