go-datastructures icon indicating copy to clipboard operation
go-datastructures copied to clipboard

dtrie appears to be mutable (and not threadsafe)

Open BennettJames opened this issue 4 years ago • 0 comments

Tested on v1.0.50:

From the documentation, it sounds like the dtrie is intended to be an immutable, hash array mapped trie implementation:

Dtrie A persistent hash trie that dynamically expands or shrinks to provide efficient memory allocation. Being persistent, the Dtrie is immutable and any modification yields a new version of the Dtrie rather than changing the original. Bitmapped nodes allow for O(log32(n)) get, remove, and update operations. Insertions are O(n) and iteration is O(1).

However, this doesn't appear true:

t0 := dtrie.New(nil)
t1 := t0.Insert("a", "b")
t2 := t1.Insert("c", "d")

fmt.Println("trie sizes", t0.Size(), t1.Size(), t2.Size()) // yields 2, 2, 2; should be 0, 1, 2
fmt.Println(t0.Get("c")) // "d"; should be nil
fmt.Println(t1.Get("c")) // "d"; should be nil
fmt.Println(t2.Get("c")) // "d"; which is correct

It's also pretty easy to trigger a panic with concurrent access. This will reliably result in a panic on my machine -

insertLots := func() {
	for i := 0; i < 1000000; i++ {
		m0.Insert(stringEntry("v"), "value")
	}
}
	
go func() {
	insertLots()
}()
go func() {
	insertLots()
}()

Now, I know that this project hasn't seen a ton of updates in the past couple of years, and I'd understand if no-one wants to dig in to fix it properly. Nonetheless, I feel like a limitation like this would at least be worth documenting if it's not going to be fixed. I'd be happy to make a PR to that effect.

BennettJames avatar Sep 05 '19 20:09 BennettJames