Closed kawasin73 closed 5 years ago
kawasin73
commented
5 years ago 基数木（Patricia tree, Radix tree)
https://ja.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%9C%A8
文字列集合を格納するトライ木に基づく特殊化された集合データ構造
トライ木（trie tree）を発展させたデータ構造であり、トライ木が 1 ノードに 1 文字を割り当てるのに対して、基数木は、重複する複数の文字列（ Prefix ）を割り当てる。（参考：What is the difference between trie and radix trie data structures? ）
新しいキーの追加により、ノードの分割などが起こる。
kawasin73
commented
5 years ago https://github.com/tchap/go-patricia
Go 言語による基数木の実装。任意のバイト列と任意の型の値を保存する。
1 ノードあたりの最大プレフィックス長（MaxPrefixPerNode）と、1 ノードあたりの最大空き子ノード数（MaxChildrenPerSparseNode）を設定できる。
ノードのプレフィックスの単位は 1 バイトである。
子ノードの管理方法には sparseChildList と denseChildList の2種類があり、子ノードの数によって使い分ける。
https://github.com/tchap/go-patricia/blob/master/patricia/children.go
sparseChildList には MaxChildrenPerSparseNode の長さのノードのアドレスポインタ配列が事前にアロケートされており、ノードの検索では先頭から順にノードの走査を行う。
type sparseChildList struct {
children tries
}
func newSparseChildList(maxChildrenPerSparseNode int) childList {
return &sparseChildList{
children: make(tries, 0, maxChildrenPerSparseNode),
}
}ノードが追加されて sparseChildList の子ノードの数が MaxChildrenPerSparseNode を超えた時に、denseChildList に変換される。
type denseChildList struct {
min int
max int
numChildren int
headIndex int
children []*Trie
}denseChildList は、子ノードの先頭から末尾までの範囲の長さのノードアドレスポインタ配列を持つ。 1 バイトの全範囲を取ると 256 要素になるが、実際に挿入されたキーの値の範囲に絞ることで余分なメモリ領域を削減している。
ノードの検索では、キーの先頭 1 バイトから min を引いた値をインデックスとして 1 回の計算でノードを取得することができる。
kawasin73
commented
5 years ago https://github.com/kentik/patricia
IP/CIDR と複数のタグの関係を保存するための Go 言語による基数木の実装。
元となる実装は、template パッケージ に実装してあるが、Go 言語はジェネリクスに対応していないため、タグに利用する型によってそれぞれに最適化された（おそらく）自動生成のパッケージが用意されている。（string_tree、byte_tree、int_tree etc...）
ノードのプレフィックスの単位は 1 ビットであり、子ノードは2つのみである。
すべてのノードは連続したメモリ上にアロケートされており、あるノードの子ノードはインデックスの差分オフセットとして保存されている。 利用しているノードと空きノードはビットベクトルで管理されている。
プレフィックスもキーの最大サイズが事前に分かっているため事前にノード内に固定長で用意されている（IPv4 の場合は 32 bit であり uint32、IPv6 の場合は 128 bit であり uint64 が2つ）
// https://github.com/kentik/patricia/blob/master/template/tree_node_v4.go
type treeNodeV4 struct {
Left uint // left node index: 0 for not set
Right uint // right node index: 0 for not set
prefix uint32
prefixLength uint
TagCount int
}
// https://github.com/kentik/patricia/blob/master/template/tree_node_v6.go
type treeNodeV6 struct {
treeNode
Left uint // left node index: 0 for not set
Right uint // right node index: 0 for not set
prefixLeft uint64
prefixRight uint64
prefixLength uint
TagCount int
}1つのキーに対して複数のタグを保存できるが、すべてのタグを1つのハッシュマップに保存している。
ハッシュマップのキーは uint64 で、上位 32 bit がノードのインデックス、下位 32 bit がノード内で単調増加する ID である。
// https://github.com/kentik/patricia/blob/master/template/tree_v4.go
type TreeV4 struct {
nodes []treeNodeV4 // root is always at [1] - [0] is unused
availableIndexes []uint // a place to store node indexes that we deleted, and are available
tags map[uint64]GeneratedType
}https://github.com/armon/go-radix
任意の文字列のキーと任意の型の値を保存する Go 言語による基数木の実装。
ノードのプレフィックスの単位は 1 バイトである。
ノードの子ノードの集合はノードのアドレスポインタのスライスで表される。
新しい子ノードの追加ではスライスの末尾に追加（append）され標準ライブラリの sort パッケージを使ってプレフィックスの１文字目で並び替えられ、子ノードの検索では二分探索を行う。
子ノードのプレフィックスの先頭１バイトを、親ノードの子ノード集合スライス edges に含めることで、二分探索での空間的な局所性がでるように工夫されている。
// https://github.com/armon/go-radix/blob/master/radix.go
func (n *node) getEdge(label byte) *node {
num := len(n.edges)
idx := sort.Search(num, func(i int) bool {
return n.edges[i].label >= label
})
if idx < num && n.edges[idx].label == label {
return n.edges[idx].node
}
return nil
}
func (n *node) addEdge(e edge) {
n.edges = append(n.edges, e)
n.edges.Sort()
}
type edge struct {
label byte
node *node
}
type edges []edge
func (e edges) Sort() {
sort.Sort(e)
}https://github.com/hashicorp/go-immutable-radix
基本的なデータ構造とアルゴリズムは armon/go-radix を引き継ぎ、それにトランザクション機能を追加したパッケージ、複数のスレッドから並行にアクセスされることを想定している。
kawasin73
commented
5 years ago go-patricia と go-radix、そして比較のためにハッシュマップ（map[string][]byte）で、バイト列をキーとするときのパフォーマンスを比較した。
キーとして string のみを受け付けるパッケージ（go-radix、map[string][]byte）では、メソッド呼び出しの度にバイト列から文字列への変換を行う。
結果として、go-radix の方が go-patricia よりも値の設定と取得の両方でパフォーマンスが良くなった。
ただし、プリミティブ実装であるハッシュマップ（map[string][]byte）が一番高速であった。
$ go run bench.go
==========================
go-patricia set
total 3200000 ops, for 15.588905375s
performance : 205274 ops/s
==========================
go-patricia get
total 3200000 ops, for 10.01437886s
performance : 319540 ops/s
==========================
go-radix set
total 3200000 ops, for 9.349720069s
performance : 342256 ops/s
==========================
go-radix get
total 3200000 ops, for 6.018240636s
performance : 531716 ops/s
==========================
map[string][]byte set
total 3200000 ops, for 6.740674909s
performance : 474729 ops/s
==========================
map[string][]byte get
total 3200000 ops, for 2.385318029s
performance : 1341540 ops/s
==========================消費するメモリ量の調査も必要であるがめんどくさいので一旦パス。
基数木（Patricia tree, Radix tree）について、その Go 言語における実装も含めて調査する。