I’ve been implementing the same (or as similar as possible) trading orderbook algorithm in various languages recently and one thing I noticed with Go is that it has fewer or simpler algorithms in the standard library, for example no deques and maps cannot be ordered like the std::map/BTreeMap in C++/Rust).
I was reading about others discussing this fact somewhere and a line piqued my interest that went something like “because of the runtime cost of interface{} (aka “any”), some algorithms are implemented more simplistically”. That seemed a shame for my performance critical orderbook and so I decided to do a little experiment:
What if I take the deque library I’m using and convert it to use generics? The results are quite promising…
Benchmarks without generics
go1.18beta1 darwin/amd64
cpu: VirtualApple @ 2.50GHzBenchmarkPushFront-10 10000 25.81 ns/opBenchmarkPushBack-10 10000 40.87 ns/opBenchmarkSerial-10 10000 40.05 ns/opBenchmarkSerialReverse-10 10000 30.43 ns/opBenchmarkRotate-10 10000 30122 ns/opBenchmarkInsert-10 10000 29192 ns/opBenchmarkRemove-10 10000 13927 ns/opBenchmarkYoyo-10 10000 1801284 ns/opBenchmarkYoyoFixed-10 10000 1136005 ns/op
Benchmarks with generics
go1.18beta1 darwin/amd64
cpu: VirtualApple @ 2.50GHzBenchmarkPushFront-10 10000 9.846 ns/opBenchmarkPushBack-10 10000 10.04 ns/opBenchmarkSerial-10 10000 11.08 ns/opBenchmarkSerialReverse-10 10000 26.22 ns/opBenchmarkRotate-10 10000 11047 ns/opBenchmarkInsert-10 10000 15644 ns/opBenchmarkRemove-10 10000 5203 ns/opBenchmarkYoyo-10 10000 561729 ns/opBenchmarkYoyoFixed-10 10000 393723 ns/op
Most of the benchmarks are 2–3x faster!
This is encouraging news that performance critical data collections can get such a boost out of generics, without having to write specialized containers per type.
P.S. You can find the updated fork here and here’s the git diff.
HackerNews discussion.
Reddit discussion.
