Skip to content

dtrie appears to be mutable (and not threadsafe) #206

Open
@BennettJames

Description

@BennettJames

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions