Skip to content

Instantly share code, notes, and snippets.

@stephenwithav
Created February 27, 2020 22:31
Show Gist options
  • Save stephenwithav/8c296df836a55a8f20fc52514f707bc8 to your computer and use it in GitHub Desktop.
Save stephenwithav/8c296df836a55a8f20fc52514f707bc8 to your computer and use it in GitHub Desktop.
AVL/Red-Black tree benchmarks for Go. The first set uses interface{} types for key/value, while the second uses an automatically generated tree with an int for key and a string for value.

Go generics remain in a galaxy far, far away.

That doesn't mean Go developers have to remain in the dark ages forever, though.

Developer tools like YASnippet allow us to reuse boilerlate code for common, repetitive tasks including priority queues and AVL Trees without the performance hit imposed by .(casting) interface{}s specific to our preferred types.

If you need or want an algorithm or a common pattern converted into a Go snippet, create an issue here and I'll get it done. (I'm currently converting some of the algorithms in this repo into snippets.)

goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/trees/avltree
BenchmarkAVLTreeGet100-4 111012 9911 ns/op 792 B/op 99 allocs/op
BenchmarkAVLTreeGet1000-4 8860 131971 ns/op 7992 B/op 999 allocs/op
BenchmarkAVLTreeGet10000-4 642 1872889 ns/op 79992 B/op 9999 allocs/op
BenchmarkAVLTreeGet100000-4 36 31355869 ns/op 799994 B/op 99999 allocs/op
BenchmarkAVLTreePut100-4 92955 12928 ns/op 792 B/op 99 allocs/op
BenchmarkAVLTreePut1000-4 5816 181437 ns/op 7992 B/op 999 allocs/op
BenchmarkAVLTreePut10000-4 459 2612332 ns/op 79992 B/op 9999 allocs/op
BenchmarkAVLTreePut100000-4 31 37961395 ns/op 799993 B/op 99999 allocs/op
BenchmarkAVLTreeRemove100-4 417405 3055 ns/op 792 B/op 99 allocs/op
BenchmarkAVLTreeRemove1000-4 41631 30990 ns/op 7992 B/op 999 allocs/op
BenchmarkAVLTreeRemove10000-4 3768 298011 ns/op 79992 B/op 9999 allocs/op
BenchmarkAVLTreeRemove100000-4 327 3144849 ns/op 799995 B/op 99999 allocs/op
PASS
ok github.com/emirpasic/gods/trees/avltree 16.673s
goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/trees/redblacktree
BenchmarkRedBlackTreeGet100-4 112082 10242 ns/op 792 B/op 99 allocs/op
BenchmarkRedBlackTreeGet1000-4 8365 145144 ns/op 7992 B/op 999 allocs/op
BenchmarkRedBlackTreeGet10000-4 589 2038133 ns/op 79992 B/op 9999 allocs/op
BenchmarkRedBlackTreeGet100000-4 38 31955082 ns/op 799993 B/op 99999 allocs/op
BenchmarkRedBlackTreePut100-4 116029 10336 ns/op 792 B/op 99 allocs/op
BenchmarkRedBlackTreePut1000-4 8336 144952 ns/op 7992 B/op 999 allocs/op
BenchmarkRedBlackTreePut10000-4 606 2016466 ns/op 79992 B/op 9999 allocs/op
BenchmarkRedBlackTreePut100000-4 39 31303663 ns/op 799993 B/op 99999 allocs/op
BenchmarkRedBlackTreeRemove100-4 328738 3482 ns/op 792 B/op 99 allocs/op
BenchmarkRedBlackTreeRemove1000-4 35464 34576 ns/op 7992 B/op 999 allocs/op
BenchmarkRedBlackTreeRemove10000-4 3122 340525 ns/op 79992 B/op 9999 allocs/op
BenchmarkRedBlackTreeRemove100000-4 340 3487268 ns/op 799994 B/op 99999 allocs/op
PASS
ok github.com/emirpasic/gods/trees/redblacktree 17.974s
goos: linux
goarch: amd64
pkg: github.com/stephenwithav/gods/avltree
BenchmarkAVLTreeGet100-4 378756 2716 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeGet1000-4 28627 41194 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeGet10000-4 1519 793758 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeGet100000-4 93 13087211 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreePut100-4 197469 5844 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreePut1000-4 12603 95326 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreePut10000-4 716 1647773 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreePut100000-4 50 24016307 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeRemove100-4 3002374 393 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeRemove1000-4 274924 3997 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeRemove10000-4 30868 38643 ns/op 0 B/op 0 allocs/op
BenchmarkAVLTreeRemove100000-4 3055 391391 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/stephenwithav/gods/avltree 17.855s
goos: linux
goarch: amd64
pkg: github.com/stephenwithav/gods/redblacktree
BenchmarkRedBlackTreeGet100-4 418836 2691 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeGet1000-4 24242 49099 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeGet10000-4 1418 829087 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeGet100000-4 90 12752928 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreePut100-4 329734 3212 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreePut1000-4 22300 53985 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreePut10000-4 1190 945810 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreePut100000-4 86 14354923 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeRemove100-4 2070156 569 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeRemove1000-4 196129 5653 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeRemove10000-4 21745 56137 ns/op 0 B/op 0 allocs/op
BenchmarkRedBlackTreeRemove100000-4 2145 568560 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/stephenwithav/gods/redblacktree 19.038s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment