I know I believe in nothing but it is my sweet nothing.:2021年06月05日分

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倍近く速くなってるわけでしてな。