2021/06/03(Thu)
○[オレオレN6] rbtree(3)遅くない？
@ここは私の夢日記
マーク・〇ッカーバーグとイー〇ン・マスクという巨悪が「世界」を「終了」させる時限式キルスイッチを押した事に気づいてしまった俺、フェー〇ブック内にも少なからずといる抵抗勢力と内通することに成功し手引きによってデータセンターに侵入することに成功する。 素人目には東京モノレール天王洲アイル駅近くの某倉庫屋にしか見えないが、ここはサンフランシスコだ、誰が何を言おうとサンフランシスコなんだ *1。
厳重な監視システムの唯一点の死角である重い扉の向こう側の薄暗い閉鎖空間で、奴らの「システム」に 没入すべく 端末に 氷破りをロードする待ち時間を有効活用するため、従業員専用銭湯でひと風呂浴びるべく男湯の暖簾をくぐるとそこには(ここで目が覚めた)
ということでフロイト先生、いつもの夢診断をお願いいたします。
フロイト先生「世の中暗いからなろうに憧れるのはいいとして、今時ギブスンのスプロールシリーズとか加齢臭キツ過ぎない？」
@ここからは赤黒木と白黒ショーの違いが判らない阿呆のチラシの裏のメモ書き
以前の記事でnvi-1.81用のワイド文字版regex(3)で使うために同様にワイド文字版のbm(3)風のBM法実装をクッソ雑に実装したのだが、あれをベースに簡単な性能テストを実施してみた。 やっぱりbm_comp(3)にかかるコストはそれなりに重いのだが、bm_exec(3)は不一致文字規則をソート済の配列で持ちマッチにはbsearch(3)を使うような実装であってもwcswcs(3)よりはじゅうぶんに速いので真面目に実装する価値はありそうかなこれ。
ただ以前の実装だと固定長配列で用意した不一致文字規則のテーブル長さを超える文字種がパターンに含まれるとbm_comp(3)は死ぬという制限付なので(まぁセキュリティ的にはその方がいい気もするが)そこは何とかしたいもうちょっと欲張りたいという感じ。
なのでとりあえず不一致文字規則周りを順序集合(Ordered Set)実装する時の定番である赤黒木、Nだとrbtree(3)を使って再実装してみた。
/*-
* Copyright (c) 2021 Takehiko NOZAKI,
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
#include <sys/rbtree.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>
#include "bmw.h"
struct bmw_bcr {
rb_node_t rbn;
wint_t c; /* code point */
size_t skip; /* skip delta */
};
static int
bmw_bcr_compare_key(void *ctx, const void *node, const void *key)
{
wint_t ac, bc;
ac = ((const struct bmw_bcr *)node)->c;
bc = *((const wint_t *)key);
if (ac == bc)
return 0;
else if (ac < bc)
return -1;
return 1;
}
static int
bmw_bcr_compare_nodes(void *ctx, const void *parent, const void *node)
{
return bmw_bcr_compare_key(ctx, parent,
(const void *)&((const struct bmw_bcr *)node)->c);
}
static const rb_tree_ops_t bmw_bcr_ops = {
&bmw_bcr_compare_nodes,
&bmw_bcr_compare_key,
offsetof(struct bmw_bcr, rbn),
NULL
};
struct bmw_pat {
const wchar_t *pat; /* pattern */
size_t patlen; /* length of pattern */
size_t lastp; /* last index of pattern */
rb_tree_t bcr; /* bad character rule */
size_t md2; /* mini delta */
};
bmw_pat_t
bmw_comp(const wchar_t *pat, size_t patlen)
{
bmw_pat_t b;
struct bmw_bcr *node;
size_t i, skip;
wint_t c;
b = malloc(sizeof(*b));
if (b == NULL)
return NULL;
b->pat = pat;
b->patlen = patlen;
b->lastp = b->patlen - 1;
rb_tree_init(&b->bcr, &bmw_bcr_ops);
for (i = 0; i < b->patlen; ++i) {
c = (wint_t)b->pat[i];
skip = b->lastp - i;
node = rb_tree_find_node(&b->bcr, (const void *)&c);
if (node == NULL) {
node = malloc(sizeof(*node));
if (node == NULL) {
bmw_free(b);
return NULL;
}
node->c = c;
rb_tree_insert_node(&b->bcr, node);
}
node->skip = skip;
}
for (i = b->lastp; --i > 0;) {
if (b->pat[i] == b->pat[b->lastp])
break;
}
b->md2 = b->lastp - i;
return b;
}
static inline size_t
bcr(bmw_pat_t b, wint_t c)
{
struct bmw_bcr *node;
node = rb_tree_find_node(&b->bcr, (const void *)&c);
return (node != NULL) ? node->skip : b->patlen;
}
const wchar_t *
bmw_exec(bmw_pat_t b, const wchar_t *s, size_t n)
{
const wchar_t *e;
size_t skip;
if (n < b->patlen)
return NULL;
e = s + n;
s += b->lastp;
for (;;) {
if ((skip = bcr(b, (wint_t)*s)) == 0) {
if (!wmemcmp(b->pat, s - b->lastp, b->lastp))
return s - b->lastp;
skip = b->md2;
}
if (s >= e - skip)
break;
s += skip;
}
return NULL;
}
void
bmw_free(bmw_pat_t b)
{
struct bmw_bcr *node, *next;
for (node = RB_TREE_MIN(&b->bcr); node != NULL; node = next) {
next = rb_tree_iterate(&b->bcr, node, RB_DIR_RIGHT);
rb_tree_remove_node(&b->bcr, node);
free(node);
}
free(b);
}
だたまぁ予想はしてたのだが
- ツリーのノードをいちいちmalloc(3)するコストがかなり重い
- ノード追加にかかるコストがけっこう重い
というボトルネックでbm_comp(3)にかかる時間が3倍遅くなる逆シャア状態なのでもうちょっと工夫せんとアカンなこれ、1.はまぁなんかアロケーター書きゃいいか…
つーか2.についてはそもそもrbtree(3)って他の赤黒木実装と比較しても性能悪いのだよな、Oの赤黒木実装にはtree(3)ってのがあるんだけどこいつと比較すると明かに遅い。 これもうlibcの実装を置き換えちまおうかなぁという気分、ABIの後方互換に関してはshim書くのそんなに手間ではないし。ちなみにtree(3)には他にもスプレー木が実装されてたりしてより高機能なのである。
上のコードをrbtree(3)でなくtree(3)使って書き直すとこんなん。
--- bmw.c.orig 2021-06-03 18:05:36.000000000 +0900
+++ bmw.c 2021-06-03 17:54:18.000000000 +0900
@@ -24,7 +24,7 @@
* SUCH DAMAGE.
*/
#include <sys/cdefs.h>
-#include <sys/rbtree.h>
+#include <sys/tree.h>
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
@@ -36,44 +36,29 @@
#include "bmw.h"
struct bmw_bcr {
- rb_node_t rbn;
+ RB_ENTRY(bmw_bcr) rbn;
wint_t c; /* code point */
size_t skip; /* skip delta */
};
+RB_HEAD(bmw_bcr_tree, bmw_bcr);
static int
-bmw_bcr_compare_key(void *ctx, const void *node, const void *key)
+bmw_bcr_compare_key(const struct bmw_bcr *a, const struct bmw_bcr *b)
{
- wint_t ac, bc;
-
- ac = ((const struct bmw_bcr *)node)->c;
- bc = *((const wint_t *)key);
- if (ac == bc)
+ if (a->c == b->c)
return 0;
- else if (ac < bc)
+ else if (a->c < b->c)
return -1;
return 1;
}
-
-static int
-bmw_bcr_compare_nodes(void *ctx, const void *parent, const void *node)
-{
- return bmw_bcr_compare_key(ctx, parent,
- (const void *)&((const struct bmw_bcr *)node)->c);
-}
-
-static const rb_tree_ops_t bmw_bcr_ops = {
- &bmw_bcr_compare_nodes,
- &bmw_bcr_compare_key,
- offsetof(struct bmw_bcr, rbn),
- NULL
-};
+RB_PROTOTYPE_STATIC(bmw_bcr_tree, bmw_bcr, rbn, bmw_bcr_compare_key)
+RB_GENERATE_STATIC(bmw_bcr_tree, bmw_bcr, rbn, bmw_bcr_compare_key)
struct bmw_pat {
const wchar_t *pat; /* pattern */
size_t patlen; /* length of pattern */
size_t lastp; /* last index of pattern */
- rb_tree_t bcr; /* bad character rule */
+ struct bmw_bcr_tree bcr;/* bad character rule */
size_t md2; /* mini delta */
};
@@ -81,7 +66,7 @@ bmw_pat_t
bmw_comp(const wchar_t *pat, size_t patlen)
{
bmw_pat_t b;
- struct bmw_bcr *node;
+ struct bmw_bcr *node, tmp;
size_t i, skip;
wint_t c;
@@ -91,11 +76,12 @@ bmw_comp(const wchar_t *pat, size_t patl
b->pat = pat;
b->patlen = patlen;
b->lastp = b->patlen - 1;
- rb_tree_init(&b->bcr, &bmw_bcr_ops);
+ RB_INIT(&b->bcr);
for (i = 0; i < patlen; ++i) {
c = (wint_t)pat[i];
skip = b->lastp - i;
- node = rb_tree_find_node(&b->bcr, (const void *)&c);
+ tmp.c = c;
+ node = bmw_bcr_tree_RB_FIND(&b->bcr, &tmp);
if (node == NULL) {
node = malloc(sizeof(*node));
if (node == NULL) {
@@ -103,7 +89,7 @@ bmw_comp(const wchar_t *pat, size_t patl
return NULL;
}
node->c = c;
- rb_tree_insert_node(&b->bcr, node);
+ bmw_bcr_tree_RB_INSERT(&b->bcr, node);
}
node->skip = skip;
}
@@ -118,9 +104,10 @@ bmw_comp(const wchar_t *pat, size_t patl
static inline size_t
bcr(bmw_pat_t b, wint_t c)
{
- struct bmw_bcr *node;
+ struct bmw_bcr *node, tmp;
- node = rb_tree_find_node(&b->bcr, (const void *)&c);
+ tmp.c = c;
+ node = bmw_bcr_tree_RB_FIND(&b->bcr, &tmp);
return (node != NULL) ? node->skip : b->patlen;
}
@@ -152,9 +139,8 @@ bmw_free(bmw_pat_t b)
{
struct bmw_bcr *node, *next;
- for (node = RB_TREE_MIN(&b->bcr); node != NULL; node = next) {
- next = rb_tree_iterate(&b->bcr, node, RB_DIR_RIGHT);
- rb_tree_remove_node(&b->bcr, node);
+ RB_FOREACH_SAFE(node, bmw_bcr_tree, &b->bcr, next) {
+ bmw_bcr_tree_RB_REMOVE(&b->bcr, node);
free(node);
}
free(b);
*1:なお〇ェースブックのデータセンターは過去現在においてサンフランシスコに存在したことは無い。