yet another code gen: specialized datastructure

[clément auger]

hi,

I recently wanted to get the juice out of some programs.

A queue consumer that transforms inputs over many routines,

then aggregates the results to re order them.

The order is defined by the input order. 

There was many variations written around it,

using a map, a slice, a regular heap, and finally,

a specialized heap (hand written).

Slice was best for its simplicity, regular heap made

with the package `container/heap` was not as good as expected.

The specialized heap was the best for performance,

but having this added complexity for only one small

library of ~100LOC did not seem a good idea.

So I wrote a template, included and rewrote the tests from

`container/heap`, et voilà, it makes sense.

It is tested, re usable, and made for perf.

The template are available at https://github.com/clementauger/jenjen-datastructure

Then you run (or add it via //go:gen..)

jenjen -template=github.com/clementauger/jenjen-datastructure/heap \

- "U => -, T => -, Heap=>MinIntHeap , MinIntHeap:U=>int, MinIntHeap:T=> minInt"

It generates for you a Heap that takes in input regular ints, output regular ints, but internally stores them as minInt.

See https://github.com/clementauger/jenjen-datastructure/blob/main/examples/heap/jenjen_heap.go#L38

So does it do any good ?

$ (cd examples/heap; go test -bench=. -benchmem -count=2)
goos: linux
goarch: amd64
pkg: github.com/clementauger/jenjen-datastructure/examples/heap
BenchmarkMinIntHeap-4            9439        108133 ns/op           8 B/op           0 allocs/op
BenchmarkMinIntHeap-4           10000        107884 ns/op           8 B/op           0 allocs/op
BenchmarkRegularHeap-4           3523        325731 ns/op          23 B/op           0 allocs/op
BenchmarkRegularHeap-4           3433        321977 ns/op          23 B/op           0 allocs/op
PASS
ok      github.com/clementauger/jenjen-datastructure/examples/heap    4.452s

(I hope i have not made a mistake writing the comparison benchmarks, i would not like to criticize the core language implementation in such fashion...)

Notes:

1/ I have to say i was surprised to not find an existing similar project using genny (a more popular code generator), did i miss something ?

Clément

[Michał Matczuk]

I invite you to take a look at [1] a bazel-free version of Google go_generics tool released with gVisor project. It is used to make [2].

[1] https://github.com/mmatczuk/go_generics 

[2] https://github.com/scylladb/go-set