Pure Go generic implementation of freelist allocator.
It allows faster allocation and reuse of small objects, making some implementations of datastructures (linked lists, trees, ...) significantly more efficient.
Key features:
- Unlike many other implementations, it doesn't ruin garbage collection for pointers inside allocated objects and plays nicely with garbage collector.
- Unlike many other implementations, it doesn't depend on CGO and doesn't encumber builds.
See godoc examples.
Here is benchmarks of original container/list.List (BenchmarkContainerList.*) versus the same List, but augmented by this freelist package (BenchmarkFreelistList.*).
goos: linux
goarch: amd64
pkg: github.com/Snawoot/freelist
cpu: Intel(R) N100
BenchmarkContainerList/PushFront-4 10498634 138.6 ns/op 55 B/op 1 allocs/op
BenchmarkContainerList/PushPopFront-4 9171722 173.3 ns/op 55 B/op 1 allocs/op
BenchmarkContainerList/PushPopFrontImmediate-4 14392966 97.04 ns/op 56 B/op 1 allocs/op
BenchmarkFreelistList/PushFront-4 13464580 89.79 ns/op 56 B/op 1 allocs/op
BenchmarkFreelistList/PushPopFront-4 12886014 82.59 ns/op 56 B/op 1 allocs/op
BenchmarkFreelistList/PushPopFrontImmediate-4 30983012 38.41 ns/op 8 B/op 0 allocs/op
BenchmarkFreelistList/WarmedUpPushFront-4 36359986 32.00 ns/op 7 B/op 0 allocs/op
BenchmarkFreelistList/WarmedUpPushPopFront-4 31587457 38.25 ns/op 7 B/op 0 allocs/op
BenchmarkBuiltinNew-4 48650766 27.10 ns/op 8 B/op 1 allocs/op
BenchmarkFreelistAlloc-4 68139662 16.94 ns/op 18 B/op 0 allocs/op
BenchmarkWarmedUpFreelistAlloc-4 224581018 5.377 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/Snawoot/freelist 28.662s
As you can see it performs about twice faster than original container/list.List in worst case and performs 3-5 times faster once freelist reaches right size.