Add Generics Support, More Idiomatic Go #31

adrianosela · 2025-01-25T18:25:20Z

Add Generics Support, More Idiomatic Go

Simplifies code for users of this package (avoids type assertions at runtime) and helps prevent runtime panics due to wrong type-assertions
Made lookup function e.g. Get() more idiomatic by returning true/false for whether item was found
Makes the individual trie types private e.g. PathTrie --> pathTrie, RuneTrie --> runeTrie and has constructors return the interface (better encapsulation)
Makes the following NOT true anymore for either implementation: Internal nodes have nil values so stored nil values cannot be distinguished and are excluded from walks., nil values can now be stored and distinguished from empty nodes.
Other misc. cosmetic changes.

Note that if existing users want to maintain the ability to store multiple different types of data in the trie they can still use the constructors with type any. e.g. before NewPathTrie(), now NewPathTrie[any](). While most users of this library will now be able to do NewPathTrie[string]() when they only ever expect to store strings, or NewPathTrie[*customStruct](), and so on...

UX

Before:

trie := NewPathTrie()

trie.Put("/hello/world", 27)

value := trie.Get("/hello/world")

// must do a type assertion before using value (cumbersome)
if intValue, ok := value.(int); ok {
    sum += intValue
}

// or risk a runtime panic by skipping the check part
otherSum += value.(int)

After:

trie := NewPathTrie[int]()

trie.Put("/hello/world", 27)

// value returned from lookup can be used directly
if value, ok := trie.Get("/hello/world"); ok {
    sum += value
}

Benchmark (TL;DR; No Changes)

Before:

✔ ~/go/src/github.com/dghubble/trie [main|✔]
10:15 $ go test -bench=.
goos: darwin
goarch: arm64
pkg: github.com/dghubble/trie
cpu: Apple M1 Pro
BenchmarkRuneTriePutStringKey-8   	 3474247	       323.8 ns/op	       9 B/op	       1 allocs/op
BenchmarkRuneTrieGetStringKey-8   	 3813277	       317.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkRuneTriePutPathKey-8     	 3481916	       337.2 ns/op	       9 B/op	       1 allocs/op
BenchmarkRuneTrieGetPathKey-8     	 3644137	       331.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkPathTriePutStringKey-8   	28855054	        40.92 ns/op	       8 B/op	       1 allocs/op
BenchmarkPathTrieGetStringKey-8   	39185912	        30.34 ns/op	       0 B/op	       0 allocs/op
BenchmarkPathTriePutPathKey-8     	16460866	        71.89 ns/op	       8 B/op	       1 allocs/op
BenchmarkPathTrieGetPathKey-8     	19688133	        60.69 ns/op	       0 B/op	       0 allocs/op
BenchmarkPathSegmenter-8          	45136537	        26.25 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/dghubble/trie	18.762s

After

✔ ~/go/src/github.com/adrianosela/trie [main|✔]
10:17 $ go test -bench=.
goos: darwin
goarch: arm64
pkg: github.com/dghubble/trie
cpu: Apple M1 Pro
BenchmarkRuneTriePutStringKey-8   	 3492538	       324.1 ns/op	       9 B/op	       1 allocs/op
BenchmarkRuneTrieGetStringKey-8   	 3845990	       306.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkRuneTriePutPathKey-8     	 3444878	       341.2 ns/op	       9 B/op	       1 allocs/op
BenchmarkRuneTrie
8000
GetPathKey-8     	 3705607	       322.3 ns/op	       0 B/op	       0 allocs/op
BenchmarkPathTriePutStringKey-8   	30349173	        38.81 ns/op	       8 B/op	       1 allocs/op
BenchmarkPathTrieGetStringKey-8   	39880358	        29.80 ns/op	       0 B/op	       0 allocs/op
BenchmarkPathTriePutPathKey-8     	17097781	        69.07 ns/op	       8 B/op	       1 allocs/op
BenchmarkPathTrieGetPathKey-8     	19641246	        61.73 ns/op	       0 B/op	       0 allocs/op
BenchmarkPathSegmenter-8          	44727998	        26.20 ns/op	       0 B/op	       0 allocs/op
PASS
ok  	github.com/dghubble/trie	18.609s

adrianosela · 2025-02-04T17:29:03Z

Any thoughts on this @dghubble? Wondering if there is interest in this change or if I should close the PR. Feel free to close it if not.

adrianosela force-pushed the main branch from 8c510ba to 7d9de8c Compare January 25, 2025 18:33

adrianosela changed the title ~~Add Generics Support, More Idiomatic Get()~~ Add Generics Support, More Idiomatic Go Jan 25, 2025

adrianosela force-pushed the main branch from 7d9de8c to d3b4aba Compare January 25, 2025 18:35

Add Generics Support, More Idiomatic Go

6363281

adrianosela force-pushed the main branch from d3b4aba to 6363281 Compare January 25, 2025 18:49

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add Generics Support, More Idiomatic Go #31

Add Generics Support, More Idiomatic Go #31

Add Generics Support, More Idiomatic Go #31

Are you sure you want to change the base?

Add Generics Support, More Idiomatic Go #31

Conversation