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.

README.md

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.)

interface{}.log

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

no-interface.log

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