a22_acl2_02 のバックアップ(No.8)

acl2ライブラリ #2

(by K, 2022.11.24)

↑

(1) crit-bit木について #1

[1-1]
acl2ライブラリには、ACrit32L0B1などのクラスがあって、これはcrit-bit木を利用するためのクラスです。それでまずはcrit-bit木について説明します。

[1-2]
何か適当なオブジェクトの集合があって、それらを高速に検索したいとします。ソートした結果をポインタの配列で持っておくことができたら、あとは二分探索で探すだけでよくなるので、とても便利だと思います。これならO(logN)です（もしソートしてなかったら二分探索が使えないので、O(N)になってしまいます）。
ソートといえばqsort()でしょう。ということで、ひとまず解決です。
・・・でも待ってください。もし今100万件のデータがソート済みで、そこから一つだけデータを消すとしたらどうでしょうか？まず消すべきデータがどこにあるのかは二分探索ですぐにわかります。そして、そこを一番最後の要素で上書きすれば、これで一つ消したことになります。しかしこれだとソートされた状態が維持できていません。仕方ないのでqsortを呼びます。・・・これはいけません。O(NlogN)の時間がかかります。
それならmemmove()で消したい場所移行を1つ分だけ前にずらすのはどうでしょうか。これならO(N)で済みます。qsort()よりもいいです。・・・同じ問題は、データを1件だけ追加するときにも生じます。二分探索で挿入すべき場所を探して、memmove()でそこに1つ分の空きを作って入れるやり方のほうがqsort()よりも速いです。・・・結局qsort()は最初にたくさんのデータをソートするには最適なアルゴリズムですが、その後1件ずつ更新するには不向きなアルゴリズムです。

[1-3]
しかしO(N)というのはお世辞にも速いアルゴリズムだとは言えません。・・・これより速いアルゴリズムがあります。それば二分木やB木などです。これらはソートされた結果をポインタの配列で保持するのをやめて、「木」と呼ばれるデータ構造で管理します。この状態でもデータの検索はO(logN)で行えます。またデータの削除や追加はそれぞれどちらもO(logN)で、先のO(N)よりも格段に速いです。ただし、単純な配列よりもメモリは使います。たいてい単純な配列バージョンの数倍の容量を必要とします。ですから開発者はスピード重視かそれとも省メモリ重視なのかで使い分けることになります。

[1-4]
とはいえ、人類のアルゴリズムの探求は終わりません。もっと速くできないでしょうか。・・・結局、二分木やB木の処理時間のほとんどは、キーデータの比較です。そう、単純な配列であっても二分探索の際にはO(logN)回のキーの比較をやっていました。だからこの比較処理をやめることができたら、ずっと速くできそうです。・・・そんな夢みたいな方法があるのか・・・あるんです。
たとえば、キーのデータが、必ず大文字のアルファベット4文字で構成されているとしましょう。これは26^4=45.7万通りしかありません。それなら45.7万の要素を持つポインタの配列を作ればいいじゃないですか。これで、キーの値が"KAWA"のオブジェクトがどこにあるかをO(1)で検索できるようになります。データの1件ずつの追加も削除もすべてO(1)です。これはもはやハッシュ関数を使わないハッシュテーブルです。
しかしまあ、実際はそんな「キーの値は45.7万通りしかない」みたいなことはまれで、たいていはテーブル配列をメモリ上に構築できません（大きすぎて無理）。でも要点は一つ見つかりました。「ほかのキーとの比較をやめればいい」これです。
たとえばこうです。"KAWAI"と"OSASK"と"ESSEN"の3つのキーがあるのなら、1文字目だけ見ればそれだけでどこに行けばいいのかわかります。もしここで"OMAKE"も入って合計4つのキーになった場合は、1文字目が"O"の場合に限って2文字目を見て、"S"か"M"かで分岐します。こういう「木」を作ればいいのです。・・・この木をたどる際には、自分のキーだけ見ていればいいのです。他のキーとの比較は発生しません。・・・こういう木を「トライ木」と総称します。

[1-5]
先の例ではキーの文字に注目しました。文字だと分岐が多くなります。仮に1文字が1バイトだとしても256通りもあります。そんな木は管理が大変なので、キーをビット列に展開し、3ビット目が"0"ならこっち、"1"ならあっち、みたいな木を作ります。これがcrit-bit木です。crit-bitというのは「クリティカル・ビット」の略らしいです。これは私の推測ですが、臨界点（クリティカル・ポイント）という言葉があって、水と氷のさかい目の温度とか、水蒸気と水のさかい目の温度などのことを指しているのですが（というか物質は水に限らないし、温度じゃなくて圧力の場合も臨界点なのですが）、そういう、AかBかのぎりぎりのさかい目ということで、クリティカル・ビットなのかなーと。1ビットで枝分かれするのであれば、分岐はそれぞれ2つしかありません。二分木とにたような木になって理解しやすいです。木をたどるときに他のキーとの比較はないので、crit-bitはトライ木のうちの一つです。

[1-6]
crit-bit木に関するリンク集です。
- https://dankogai.livedoor.blog/archives/51853853.html
- https://cr.yp.to/critbit.html

↑

(2) crit-bit木について #2

[2-1]
ここで、ベンチマーク結果を示したいと思います。・・・0から999999まで、数を数えて文字列にします。これで"0", "1", "2", "3", ... という100万件の文字列データができます。これをqsortでソートします。その際に比較関数を
```
int qscmp(const void *a, const void *b)
{
    return strcmp(*(char **) a, *(char **) b);
}
```
としてみました。すると当方の環境（Kano PC, Celeron N4000）では、初期の並びを配列に書き込んでqsort()が終わるまでに340ミリ秒かかりました。ソート結果を出力するとこうなっていました。
```
0
1
10
100
1000
10000
100000
100001
100002
100003
100004
100005
100006
100007
100008
100009
10001
100010
100011
```

いい感じに混ざり合っているのがよくわかります。次に、比較関数を改良しました。strcmp()は遅いので、使わない形に書きました。

int qscmp(const void *a, const void *b)
{
    const unsigned char *ca = *(const unsigned char **) a, *cb = *(const unsigned char **) b;
    if (ca[0] != cb[0]) return ca[0] - cb[0];
    if (ca[1] != cb[1]) return ca[1] - cb[1];
    if (ca[2] != cb[2]) return ca[2] - cb[2];
    if (ca[3] != cb[3]) return ca[3] - cb[3];
    if (ca[4] != cb[4]) return ca[4] - cb[4];
    if (ca[5] != cb[5]) return ca[5] - cb[5];
    return ca[6] - cb[6];
}

こうすると、286ミリ秒になりました。もちろん結果は同じです。ではもっと改良します。32bitのintを使って、4文字ずつ比較します。

int qscmp(const void *a, const void *b)
{
    const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
    if (ca[0] != cb[0]) return ca[0] - cb[0];
    return ca[1] - cb[1];
}

この比較を成功させるためには、文字列を加工する必要があります。x86はリトルエンディアンなので、char *s;のs[0]が上位に来てくれないのです。それでエンディアンを入れ替える処理を追加しました。するとソートに要する時間は278ミリ秒になりました（このキーの加工にかかる時間はこの278ミリ秒には含まれません）。32ビット環境ではこれくらいがqsort()での限界かなと思います。

[2-2]
では同じことをACrit32L0B1でやってみました。100万件の文字列を作って、やはりキーを都合のいい形式に加工しておきます（ビットを入れ替える）。また空っぽの木も準備しておきます。ここから処理時間を計測開始です。ACrit32L0B1_ins()でデータを1つずつ追加していきます。合計100万件です。そしてその後、qsort()と結果が同じ形式になるように配列にポインタを出力させます。この時間を計りました。100万回のinsに186ミリ秒かかって、配列への出力に20ミリ秒かかりました。合計で206秒です。qsort()での最速の278ミリ秒よりも明らかに速いです！

[2-3]
話はこれで終わりではありません。実はACrit32L0B2とACrit32L0B4というクラスもあります。使い方は同じなのですが、速さが違います。この違いは何かというと、～B1は1ビットずつのcrit-bit木なのですが、～B2は2ビットずつのCrit-bit木なのです。～B4は4ビットずつのcrit-bit木です。結果を以下にまとめておきます。
qsrot #1 340ms
qsort #2 286ms
qsort #3 278ms
ACrit32L0B1 186+20=206ms
ACrit32L0B2 145+17=162ms
ACrit32L0B4 127+15=142ms
このようにこの例ではqsort()よりも高速になりましたが、他のキーに対してはまた別の結果になるだろうと思います。またC++のSTLのsortはqsort()よりも3～4倍くらい速いという話を見聞きしたことがあるので、ACrit32はそれには負けていると思います。やっぱり高速に1件ずつ追加したり削除したりできることを優先していると、まとめて一気にソートするアルゴリズムには勝てないです、たぶん。でもその差はもうあまり大きくはないようです。

[2-4]
上記の例では文字列は最長でも6バイトでした。もっと長い文字列でやったら当然遅くなると思いますが、さてどの程度遅くなるでしょうか。実験してみました。文字列はUTF8で全角文字にしました。これで1文字当たり3バイトになるので、最長18バイトになります。

qsortの比較関数はこうしました。

int qscmp(const void *a, const void *b)
{
    const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
    if (ca[0] != cb[0]) return ca[0] - cb[0];
    if (ca[1] != cb[1]) return ca[1] - cb[1];
    if (ca[2] != cb[2]) return ca[2] - cb[2];
    if (ca[3] != cb[3]) return ca[3] - cb[3];
    if (ca[4] != cb[4]) return ca[4] - cb[4];
    return ca[5] - cb[5];
}

結果は以下の通りです。
qsort 328ms
ACrit32L0B1 203+21=224ms
ACrit32L0B2 175+18=193ms
ACrit32L0B4 160+16=176ms
qsortでは328/278=1.18倍になりましたが、ACrit32L0B4では176/142=1.24倍になりました。

[2-5]
ではキーをもっと短くしたらどうでしょうか。今回は最長でも数字が6ケタなので、これをBCD（2進化10進数）という方法で表現すれば32bitに収まりそうです。BCDは簡単に言うと、数字1ケタを4ビット（＝0～15）で表現する方法です。だだし今回は必要な文字として0～9のほかにスペースもあるので、スペースを0として、0～9を1～10に対応させて変換しています。

qsortの比較関数はこうしました。

int qscmp(const void *a, const void *b)
{
    const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
    return ca[0] - cb[0];
}

一方でACrit32のほうも、キーの長さが32bitの固定長なら、より高速なモードがあります。それでいろいろ試しています。結果は次の通りです。

qsort	179ms
ACrit32L0B1	176+22=198ms	可変長モード
ACrit32L1B1	153+22=175ms	固定長32bitキー専用クラス
ACrit32L0B2	137+15=152ms	可変長モード
ACrit32L1B2	120+15=135ms	固定長32bitキー専用クラス
ACrit32L0B4	112+11=123ms	可変長モード
ACrit32L1B4	102+11=113ms	固定長32bitキー専用クラス

ちなみにACrit32L0Bxには固定長モードもありますが、結果は可変長モードとほぼ同じでした。

↑

(3) crit-bit木について #3

[3-1]

acl2ライブラリが提供するACrit32LxBxクラスは以下の機能を持ちます。

init	初期化
deinit	後始末
ins	データの追加
srch0	検索（キーを指定）：データを返す
srch1	検索（ソート順でn番目）：データを返す
srch2	検索（キーを指定）：nを返す（註1）
srch3	検索（キーを指定）：nを返す（註1）
srch4	srch0の連続指定（註2）
srch5	srch1の連続指定（註2）
del0	削除（キーを指定）：データを返す
del1	削除（ソート順でn番目）：データを返す
annl	キーの加工（アニーリング）（註3）

[註1] srch2とsrch3の違いを説明します。srch2が木の中にあるデータをキーで指定して、それが何番目かを問い合わせるためのものです。だからキーが見つからない場合、-1を返します。srch3はキーが木の中にあればsrch2と同じ挙動ですが、もしない場合は、「仮にそのキーを今木にinsしたら何番目に入るか？」を考えてそのnを返します。・・・srch3の使い道ですが、たとえば、key=1000とkey=2000でそれぞれのnを出して、1000～2000の間にいくつのデータがあるかを数えたりすることができます。
[註2] 指定されたキーから連続で複数のデータポインタを得られます。連続というのは、ソート順での連続です。srch0やsrch1を何度も呼ぶよりもはるかに高速です。
[註3] キーを検索しやすい形に加工します。主にビットを並べ替えます。これをひとまずアニーリング（焼き入れ、焼きなまし）と名付けましたが、これは一般的な用語ではなく、私が無理やり考えた呼び名です。ins/srch/delでキーを指定するときは、必ずannl済みのもので指定する必要があります。

[3-2]
世間で一般的に知られているcrit-bit木は、srch1～5, del1のようなことができません。それはそれぞれのデータがソート順で何番目なのかをO(logN)で計算するための情報を持っていないせいです。でもACrit32はそれらの情報を持っているので、これらの問い合わせに応えることができます。その代わり、各ノードのサイズは 3 * sizeof (int) ではなく、 5 * sizeof (int) になっています（ACrin32LxB1の場合）。
B1 B2 B4
pos:ビット位置 1 1 1
ptr:ポインタ 2 4 16
num:そのポインタの先にいくつデータがあるか 2 4 16
- numは実はアルゴリズムを工夫すれば、1,3,15にできることが分かっているのですが、処理を単純化して高速にするために、ポインタと同じ数だけ持たせています。
- num==1の時、対応するポインタはデータを指しています。num>=2のとき、対応するポインタはノードを指しています。

↑

(4) crit-bit木について #4

[4-1]
これだけいろいろできれば、例えばこんなことができます。
malloc/free処理を考えます。・・・mallocするときに、要求サイズにできるだけ近い空きブロックを高速に見つけたいです。それはACrit32を使えば簡単にできそうです。

それでは性能を比べてみたいと思います。まずこんなプログラムを作りました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
    int i, sz = 16 * 1024, n = 10;
    void **p = malloc(1024 * 1024 * sizeof (void *)), *q;
    free(malloc(1026 * 1024 * 1024)); // 1GBくらいを確保して解放(意図しない断片化を防ぐため).
    for (i = 0; i < n; i++)
        p[i] = malloc(sz);
    q = malloc(sz * 2);
    for (i = 1; i < n; i += 2)
        free(p[i]);

    clock_t t0 = clock();
    for (i = 0; i < 1000000; i++) {
        free(q);
        free(p[0]);
        p[0] = malloc(sz);
        q = malloc(sz * 2);
    }
    clock_t t1 = clock();
    printf("%f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
    return 0;
}

最初に16KBのメモリ領域をn個確保します。次に32KBのメモリ領域を1個確保します。そしてn/2個の16KBのメモリ領域を解放します。このときにメモリの空きがとびとびになるようにします。これで準備完了です。
ここで free(q); free(p[0]); p[0] = malloc(16KB); q = malloc(32KB); を実行します。これは解放してから確保し直すという、かなり無意味なことをやっています。でもこの処理をK&R型のmalloc()はかなり苦手としています。一番時間がかかるのは q = malloc(32KB); のところです。n/2個の16KBしかない空き領域を読み飛ばして、やっと32KB以上の空きメモリを見つけることができるのです。ここでは n=10 なので大したことはないのですが、nが大きくなると結構な負担になります。
ただし、それでも1回やったくらいでは大して時間はかからないので、100万回繰り返して、かかった時間を計ります。

次にACrit32版のほうについてです。以下のようなクラスを作り、initして、本家のmalloc()で1GBくらいを取ってきて、MemManの管理下に組み入れます。あとはすべてMemManに対するmalloc/freeに書き換えるだけです（条件を同じにしないと比較にならないので）。
```
AClass(MemMan) {
    ACrit32L0B1 idxSiz; // 空きメモリブロック情報オブジェクトの、sizメンバをキーとするインデックス.
};
```
mallocではidxSizを使って最適な空きメモリブロックをO(logN)で見つけてきます。見つけて必要なメモリを切り取った後に余りが出れば、それはidxSizに登録します。・・・freeでは、前後の領域とマージできるときはマージして、それからidxSizに登録します。
n=10 n=65536
オリジナル（msvcrt.dllのmalloc/freeを使用) 613ms 4178ms
ACrit32L0B1 306ms 573ms
ACrit32L0B2 320ms 600ms
ACrit32L0B4 459ms 559ms
これを見ると、ACrit32L0B1がシンプルで一番よさそうに思います。n=10の時点で、すでに標準のmalloc/freeの2倍の速度が出ています。これで、ACrit32L0B1の基本的なオーバヘッド（Nによらないオーバーヘッド）は十分に小さいことが分かります。n=65536では性能の差は圧倒的になっています。
高性能なmallocとしてはdlmallocが知られていますが、このMemMan-mallocはサイズごとに処理を分けるようなこともなく、ごく単純にK&R型のmallocを速くしたような感じになっています。
なお、言うまでもないですが、メモリ消費量の観点では、crit-bit木の分も必要になるため、K&R型と比べれば劣っています。

qsrot #1	340ms
qsort #2	286ms
qsort #3	278ms
ACrit32L0B1	186+20=206ms
ACrit32L0B2	145+17=162ms
ACrit32L0B4	127+15=142ms

qsort	328ms
ACrit32L0B1	203+21=224ms
ACrit32L0B2	175+18=193ms
ACrit32L0B4	160+16=176ms

	B1	B2	B4
pos:ビット位置	1	1	1
ptr:ポインタ	2	4	16
num:そのポインタの先にいくつデータがあるか	2	4	16

	n=10	n=65536
オリジナル（msvcrt.dllのmalloc/freeを使用)	613ms	4178ms
ACrit32L0B1	306ms	573ms
ACrit32L0B2	320ms	600ms
ACrit32L0B4	459ms	559ms