Is a Ternary Search Tree really better?

Question

Is a Ternary Search Tree really better?

erikdubbelboer opened this issue 5 years ago · 4 comments

I'm curious about the choice for a Ternary Search Tree instead of just a normal map. I wrote a quick benchmark an no matter how I configure it the map always uses 90% less memory and is 10% to 500% faster depending on the hit rate. Do you have some benchmark to show why it is better for your case?

package main

import (
	"container/list"
	"math/rand"
	"runtime"
	"testing"
)

// Basic Implementation for Ternary Search Tree (TST)

// tst returns Ternary Search Tree
type tst interface {
	Set(word []byte, value interface{})
	Get(word []byte) interface{}
	GetString(word string) interface{}
}

// Ternary Search Tree node that holds a single character and value if there is
type tstNode struct {
	lower  *tstNode
	higher *tstNode
	equal  *tstNode
	char   byte
	value  interface{}
}

// newTST returns Ternary Search Tree
func newTST() tst {
	return &tstNode{}
}

// Set adds a value to provided key
func (t *tstNode) Set(key []byte, value interface{}) {
	if len(key) < 1 {
		return
	}

	t.insert(t, key, 0, value)
}

// Get gets the value of provided key if it's existing, otherwise returns nil
func (t *tstNode) Get(key []byte) interface{} {
	length := len(key)
	if length < 1 || t == nil {
		return nil
	}
	lastElm := length - 1

	n := t
	idx := 0
	char := key[idx]
	for n != nil {
		if char < n.char {
			n = n.lower
		} else if char > n.char {
			n = n.higher
		} else {
			if idx == lastElm {
				return n.value
			}

			idx++
			n = n.equal
			char = key[idx]
		}
	}
	return nil
}

// Get gets the value of provided key (string) if it's existing, otherwise returns nil
func (t *tstNode) GetString(key string) interface{} {
	return t.Get([]byte(key))
}

// insert is an internal method for inserting a []byte with value in TST
func (t *tstNode) insert(n *tstNode, key []byte, index int, value interface{}) *tstNode {
	char := key[index]
	lastElm := len(key) - 1

	if n == nil {
		n = &tstNode{char: char}
	}

	if char < n.char {
		n.lower = t.insert(n.lower, key, index, value)
	} else if char > n.char {
		n.higher = t.insert(n.higher, key, index, value)
	} else {
		if index == lastElm {
			n.value = value
		} else {
			n.equal = t.insert(n.equal, key, index+1, value)
		}
	}

	return n
}

// RandBytes generates random string from English letters
func RandBytes() []byte {
	const letterBytes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	b := make([]byte, rand.Intn(100))
	for i := range b {
		b[i] = letterBytes[rand.Intn(len(letterBytes))]
	}
	return b
}

var (
	keys = make([][]byte, 1000)
	T    tst
	M    = make(map[string]interface{})

	Sink interface{}
)

func init() {
	T = newTST()
	rand.Seed(0)

	for i := 0; i < len(keys); i++ {
		keys[i] = RandBytes()
	}

	rand.Seed(0)
	var b, a runtime.MemStats
	runtime.ReadMemStats(&b)
	for i := 0; i < 500; i++ { // Only fill half of the keys so we get a 50% hit rate.
		T.Set(keys[i], &list.Element{})
	}
	runtime.ReadMemStats(&a)
	println(a.Alloc - b.Alloc)

	rand.Seed(0)
	runtime.ReadMemStats(&b)
	for i := 0; i < 500; i++ { // Only fill half of the keys so we get a 50% hit rate.
		M[string(keys[i])] = &list.Element{}
	}
	runtime.ReadMemStats(&a)
	println(a.Alloc - b.Alloc)
}

func BenchmarkTST(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Sink = T.Get(keys[(n*31)%len(keys)]) // Lookup a semi random key (using rand.Intn is too heavy here compared to the operation we are benchmarking).
	}
}

func BenchmarkMap(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Sink = M[string(keys[(n*31)%len(keys)])] // Lookup a semi random key (using rand.Intn is too heavy here compared to the operation we are benchmarking).
	}
}

Answer 1 · 2020-06-15T16:43:56.000Z

Issue-Label Bot is automatically applying the label question to this issue, with a confidence of 0.93. Please mark this comment with 👍 or 👎 to give our bot feedback!

Links: app homepage, dashboard and code for this bot.

Answer 2 · 2020-06-16T16:29:34.000Z

Hello Erik,

I’m totally agree with you that map is better than TST in general, but these our assumptions (that may not be perfect for all case, but we think they are practical)

We use radix tree for each part (static) in path for routing, so all path parts are not stored in one TST and most probably each part is an English word(s) and may be common prefixes between keys (not too long key)
A Micro service will not have many routes registered (e.g 1000+ route) and after building radix tree with common prefixes, keys will be distributed in radix nodes

According to these assumptions, we think that TST would be better since it does not need to calculate hash and handle collisions like hash map. Just it will match in O(n) (surely if n is large, map would be better for constant calculations). We know the difference between performance is not large with TST (for small n), but building things up may give a better performance (we didn't know how this will affect the whole performance till building necessary things up and it seems it does not add too much according to our assumptions so, we are intending to use maps)

Just wanted to note that we keep trying to tune different ways and algorithms not only limited to key-value stores to improve gearbox performance while adding features (your feedback and ideas are very welcome)

Answer 3 · 2020-06-16T16:38:34.000Z

Good points. But when I register 500 keys with just the letters "a" and "b", which results in a lot of common prefixes the map still outperforms the TST by almost twice. I guess a benchmark with realistic paths is required.

Answer 4 · 2020-06-16T23:45:05.000Z

I guess a benchmark with realistic paths is required.

I attached here a file contains 235886 English words and results show map is better than TST (even with assumptions mentioned in comment above), so we are going to use maps instead of TST

Benchmark results

214224
106672
goos: darwin
goarch: amd64
BenchmarkTST-4          12687427                90.6 ns/op
BenchmarkMap-4          32308705                35.4 ns/op

package main

import (
	"bytes"
	"container/list"
	"io/ioutil"
	"math/rand"
	"os"
	"runtime"
	"testing"
)

// Basic Implementation for Ternary Search Tree (TST)

// tst returns Ternary Search Tree
type tst interface {
	Set(word []byte, value interface{})
	Get(word []byte) interface{}
	GetString(word string) interface{}
}

// Ternary Search Tree node that holds a single character and value if there is
type tstNode struct {
	lower  *tstNode
	higher *tstNode
	equal  *tstNode
	char   byte
	value  interface{}
}

// newTST returns Ternary Search Tree
func newTST() tst {
	return &tstNode{}
}

// Set adds a value to provided key
func (t *tstNode) Set(key []byte, value interface{}) {
	if len(key) < 1 {
		return
	}

	t.insert(t, key, 0, value)
}

// Get gets the value of provided key if it's existing, otherwise returns nil
func (t *tstNode) Get(key []byte) interface{} {
	length := len(key)
	if length < 1 || t == nil {
		return nil
	}
	lastElm := length - 1

	n := t
	idx := 0
	char := key[idx]
	for n != nil {
		if char < n.char {
			n = n.lower
		} else if char > n.char {
			n = n.higher
		} else {
			if idx == lastElm {
				return n.value
			}

			idx++
			n = n.equal
			char = key[idx]
		}
	}
	return nil
}

// Get gets the value of provided key (string) if it's existing, otherwise returns nil
func (t *tstNode) GetString(key string) interface{} {
	return t.Get([]byte(key))
}

// insert is an internal method for inserting a []byte with value in TST
func (t *tstNode) insert(n *tstNode, key []byte, index int, value interface{}) *tstNode {
	char := key[index]
	lastElm := len(key) - 1

	if n == nil {
		n = &tstNode{char: char}
	}

	if char < n.char {
		n.lower = t.insert(n.lower, key, index, value)
	} else if char > n.char {
		n.higher = t.insert(n.higher, key, index, value)
	} else {
		if index == lastElm {
			n.value = value
		} else {
			n.equal = t.insert(n.equal, key, index+1, value)
		}
	}

	return n
}

var (
	keys = make([][]byte, 500)
	T    tst
	M    = make(map[string]interface{})

	Sink interface{}
)

func readAvailableDictionary() (words [][]byte) {
	file, err := os.Open("words.txt")
	if err != nil {
		panic(err)
	}

	b, err := ioutil.ReadAll(file)
	if err != nil {
		panic(err)
	}

	return bytes.Split(b, []byte("\n"))
}

func init() {
	T = newTST()
	rand.Seed(0)

	words := readAvailableDictionary()
	for i := 0; i < len(keys); i++ {
		keys[i] = words[rand.Int()%len(words)]
	}

	rand.Seed(0)
	var b, a runtime.MemStats
	runtime.ReadMemStats(&b)
	for i := 0; i < 250; i++ { // Only fill half of the keys so we get a 50% hit rate.
		T.Set(keys[i], &list.Element{})
	}
	runtime.ReadMemStats(&a)
	println(a.Alloc - b.Alloc)

	rand.Seed(0)
	runtime.ReadMemStats(&b)
	for i := 0; i < 250; i++ { // Only fill half of the keys so we get a 50% hit rate.
		M[string(keys[i])] = &list.Element{}
	}
	runtime.ReadMemStats(&a)
	println(a.Alloc - b.Alloc)
}

func BenchmarkTST(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Sink = T.Get(keys[(n*31)%len(keys)]) // Lookup a semi random key (using rand.Intn is too heavy here compared to the operation we are benchmarking).
	}
}

func BenchmarkMap(b *testing.B) {
	for n := 0; n < b.N; n++ {
		Sink = M[string(keys[(n*31)%len(keys)])] // Lookup a semi random key (using rand.Intn is too heavy here compared to the operation we are benchmarking).
	}
}

words.txt