2021/06/05(Sat)
○[オレオレN6] 続・rbtree(3)遅くね
前回記事で普通のプログラムならあまりtree(3)とrbtree(3)の性能差は気にしなくていいと書いたけど、最適化オプションありだと歴然とした差がでてくるので、性能が求められるケースではtree(3)使うべきなんやな。 いまんとこプロファイルに-pgつけてコンパイルしてるからinline化とか無視されるのでそれほど差は出ないのだけども。
どうしてもrbtree(3)は何度となく呼ばれるキーの比較が関数ポインタ経由なので遅くなるわね、tree(3)だとinlineで定義できるから比較が文字のコードポイントの大小比較みたいに単純なほど高速になる。
つーことで 過去記事の暇つぶしで実装したオレオレJSONパーサーもrbtree(3)でなくtree(3)使うように変更しますかね、rbtree(3)より移植性よろしいしRBT以外はヘッダファイルだけで完結するから同梱しやすい。
残る問題はmalloc(3)がボトルネックって話なのだけど、アロケーター用意のめんどくさいので手抜きして
--- bmw.c.orig 2021-06-05 10:19:47.000000000 +0900
+++ bmw.c 2021-06-05 10:46:39.000000000 +0900
@@ -58,6 +58,8 @@ struct bmw_pat {
size_t lastp; /* last index of pattern */
struct bmw_bcrext_tree bcrext;/* bad character rule */
size_t md2; /* mini delta */
+ size_t size;
+ struct bmw_bcrext nodes[];
};
bmw_pat_t
@@ -71,26 +73,24 @@ bmw_comp(const wchar_t *pat, size_t patl
assert(pat != NULL);
- if (patlen < 1)
+ if (patlen < 1 ||
+ patlen > (SIZE_MAX - sizeof(*b)) / sizeof(b->nodes[0]))
return NULL;
- b = malloc(sizeof(*b));
+ b = malloc(sizeof(*b) + patlen * sizeof(b->nodes[0]));
if (b == NULL)
return NULL;
b->pat = pat;
b->patlen = patlen;
b->lastp = b->patlen - 1;
RB_INIT(&b->bcrext);
+ b->size = 0;
for (i = 0; i < patlen; ++i) {
c = (wint_t)pat[i];
skip = b->lastp - i;
tmp.c = c;
node = RB_FIND(bmw_bcrext_tree, &b->bcrext, &tmp);
if (node == NULL) {
- node = malloc(sizeof(*node));
- if (node == NULL) {
- bmw_free(b);
- return NULL;
- }
+ node = &b->nodes[b->size++];
node->c = c;
RB_INSERT(bmw_bcrext_tree, &b->bcrext, node);
}
@@ -144,13 +144,5 @@ bmw_exec(bmw_pat_t b, const wchar_t *s,
void
bmw_free(bmw_pat_t b)
{
- struct bmw_bcrext *node, *next;
-
- assert(b != NULL);
-
- RB_FOREACH_SAFE(node, bmw_bcrext_tree, &b->bcrext, next) {
- RB_REMOVE(bmw_bcrext_tree, &b->bcrext, node);
- free(node);
- }
free(b);
}
とパターン文字列分のnodeを事前に作っておくだけで解消し20%ほど速くなった。 まぁこれだとパターン文字列には同じ文字いっぱいあるとメモリの無駄が大きくなるのだが、もうこれでいいよって気もしてきた(飽きてる)。
こっちが都度malloc(3)版
$ time ./test
48.21s real 47.90s user 0.04s system
index % time self children called name
-----------------------------------------------
0.73 5.78 50000/50000 main [2]
[3] 58.3 0.73 5.78 50000 bmw_comp [3]
2.13 0.84 70200000/118100000 bmw_bcrext_tree_RB_FIND [4]
0.93 1.03 20450000/20450000 bmw_bcrext_tree_RB_INSERT [7]
0.08 0.79 20500000/20500000 malloc [10]
-----------------------------------------------
0.03 1.33 50000/50000 main [2]
[9] 12.2 0.03 1.33 50000 bmw_free [9]
0.04 0.59 20500000/20500000 free [13]
0.12 0.49 20450000/20450000 bmw_bcrext_tree_RB_REMOVE [14]
0.07 0.00 20450000/20450000 bmw_bcrext_tree_RB_NEXT [27]
0.02 0.00 50000/50000 bmw_bcrext_tree_RB_MINMAX [31]
そしてこちらが一気にmalloc(3)版
$ time ./test
37.84s real 37.64s user 0.01s system
index % time self children called name
-----------------------------------------------
0.79 4.67 50000/50000 main [1]
[3] 61.2 0.79 4.67 50000 bmw_comp [3]
2.16 0.75 70200000/118100000 bmw_bcrext_tree_RB_FIND [4]
0.84 0.90 20450000/20450000 bmw_bcrext_tree_RB_INSERT [7]
0.00 0.01 50000/50000 malloc [21]
-----------------------------------------------
0.00 0.01 50000/50000 main [1]
[17] 0.1 0.00 0.01 50000 bmw_free [17]
0.00 0.01 50000/50000 free [18]
これだけで10秒高速化ってのは大きいな。
あとは検索に有利といわれるAVL木を試したいところなんだけど、自分で書く前に GNU libavl使ってみたがあまりいい結果は出なかった。
こちらがGNU libavlのAVL木での測定結果。
$ time ./test
67.93s real 67.86s user 0.04s system
index % time self children called name
-----------------------------------------------
1.14 11.05 50000/50000 main [2]
[3] 57.8 1.14 11.05 50000 bmw_comp [3]
3.74 1.41 70200000/118100000 avl_find [4]
0.18 4.64 20450000/20450000 avl_insert [5]
0.05 1.02 20500000/41000000 malloc [12]
0.00 0.00 50000/50000 avl_create [47]
-----------------------------------------------
2.56 0.96 47900000/118100000 bcrskip [9]
3.74 1.41 70200000/118100000 bmw_comp [3]
[4] 41.2 6.30 2.37 118100000 avl_find [4]
2.37 0.00 876100000/1158500000 bmw_bcrext_cmp [10]
-----------------------------------------------
0.05 4.02 50000/50000 main [2]
[8] 19.3 0.05 4.02 50000 bmw_free [8]
1.57 1.13 20450000/20450000 avl_delete [11]
0.03 0.71 20500000/40950000 free [15]
0.58 0.00 20500000/20500000 avl_t_first [22]
0.00 0.00 50000/50000 avl_t_init [63]
-----------------------------------------------
0.31 3.52 47900000/47900000 bmw_exec [6]
[9] 18.2 0.31 3.52 47900000 bcrskip [9]
2.56 0.96 47900000/118100000 avl_find [4]
そんで同じく赤黒木での測定結果。
$ time ./test
61.31s real 61.23s user 0.05s system
index % time self children called name
-----------------------------------------------
1.04 8.45 50000/50000 main [2]
[3] 54.0 1.04 8.45 50000 bmw_comp [3]
3.23 1.05 70200000/118100000 rb_find [4]
0.14 3.08 20450000/20450000 rb_insert [7]
0.07 0.89 20500000/41000000 malloc [12]
0.00 0.00 50000/50000 rb_create [48]
-----------------------------------------------
2.20 0.71 47900000/118100000 bcrskip [8]
3.23 1.05 70200000/118100000 bmw_comp [3]
[4] 40.9 5.43 1.76 118100000 rb_find [4]
1.76 0.00 883500000/1156100000 bmw_bcrext_cmp [11]
-----------------------------------------------
0.05 3.60 50000/50000 main [2]
[6] 20.7 0.05 3.60 50000 bmw_free [6]
1.24 1.08 20450000/20450000 rb_delete [10]
0.02 0.80 20500000/40950000 free [14]
0.47 0.00 20500000/20500000 rb_t_first [22]
0.00 0.00 50000/50000 rb_t_init [64]
-----------------------------------------------
0.29 2.92 47900000/47900000 bmw_exec [5]
[8] 18.3 0.29 2.92 47900000 bcrskip [8]
2.20 0.71 47900000/118100000 rb_find [4]
巷ではAVL木は赤黒木より検索速いなんていわれてるけど逆に遅いやんけ、追加が遅いのはまぁ当然なんだけど。 あと実装上のオーバーヘッドでrbtree(3)よりも遅いというね。
そういやナイーブ法での速度を計測するのを忘れてたのでmemmem(3)のワイド文字版でっちあげて測定。
$ time ./test
76.72s real 76.08s user 0.01s system
つーことで48秒→76秒だから1.6倍くらいは速くなってますかね、もちろんパターンを使い回せるケースであればもっと効果は劇的なんだけど。
ちなみに同じテストデータをUTF-8にしてBM法すなわちbm(3)使って検索すると
$ time ./test
10.80s real 10.76s user 0.01s system
ナイーブ法すなわちmemmem(3)で検索すると
$ time ./test
340.02s real 338.79s user 0.00s system
と34倍近いことを考えると微妙な気分にはなる、でもわずかでも速いは正義。
まぁでもUTF-8の場合1,402,795バイト中から4,196バイトを検索してるのだけど、ワイド文字であれば472,412文字から1,404文字を検索と計算量減るので、ナイーブ法とBM法の差はそりゃ見た目小さくなるのは当然ではある。 ナイーブ法同士を比較してもワイド文字ってだけですでにUTF-8よか4.5倍近く速くなってるわけでしてな。