Summary: using a custom allocator I was able to speed up an allocation heavy program (
binary-trees benchmark) ~4x.
These are historical measurements from the original binary-trees experiment, not a comparison of current Go and Java releases. Allocation and garbage-collection costs depend on the runtime, object lifetimes, and workload. Rebenchmark before applying this design to a new program.
Go 1.26 enabled the
Green Tea garbage collector by default, improving how small objects are marked and scanned. Reducing allocations and pointer-rich data can still help, but the speedups below should not be assumed to carry over unchanged.
The benchmark builds a large binary tree composed of nodes:
type Node struct {
item int
left, right *Node
}
To allocate a new node we use &Node{item, left, right}.
Improving allocation-heavy code
Allocation cost deserves a closer look.
Allocation has both an immediate cost and an effect on later garbage collection. Go can place some values on the stack through escape analysis; heap allocation involves the runtime allocator. The amount of live data and the allocation rate influence how much GC work is needed.
The collector starts with roots such as globals and goroutine stacks and follows pointers to mark reachable heap objects. Unreachable objects can then be reclaimed. Pointer-free backing arrays do not need their contents scanned for pointers. The
Go garbage collector guide explains these costs in detail.
Two useful observations follow:
- more live objects can mean more work for the collector
- more pointers can mean more scanning work
That suggests two possible optimizations:
- allocate fewer objects (e.g. by allocating them in bulk or reusing previously allocated objects)
- replace pointers with indices when that suits the data model
As it happens, the majority of the 4x speedup I got in this particular benchmark came from replacing pointers with integer indices.
Speeding up the binary-trees benchmark
For this benchmark, we can replace child pointers with integer indices. The new Node definition is:
type NodeID int
type Node struct {
item int
left, right NodeID
}
We changed left and right fields from *Node to a defined type NodeID, which is just a unique integer representing a node.
An ID identifies a node in the backing store. In a single-slice version, we could append a node and return its index, then retrieve it with &nodes[id].
Our implementation is a bit more sophisticated. In Go it’s easy to grow a slice with append(), but growth beyond its capacity copies the existing elements. We avoid that by pre-allocating nodes in buckets and using a slice of slices for storage. The code is still relatively simple:
const nodesPerBucket = 1024 * 1024
var (
allNodes [][]Node
nodesLeft int
currentNodeID int
)
func NodeFromID(id NodeID) *Node {
n := int(id) - 1
bucket := n / nodesPerBucket
el := n % nodesPerBucket
return &allNodes[bucket][el]
}
func allocNode(item int, left, right NodeID) NodeID {
if nodesLeft == 0 {
newNodes := make([]Node, nodesPerBucket)
allNodes = append(allNodes, newNodes)
nodesLeft = nodesPerBucket
}
nodesLeft--
node := NodeFromID(NodeID(currentNodeID + 1))
node.item = item
node.left = left
node.right = right
currentNodeID++
return NodeID(currentNodeID)
}
This bucketed version uses IDs starting at 1, reserving 0 for a missing child. Only pass an allocated, nonzero ID to NodeFromID. The remaining changes add NodeFromID calls where the original code dereferenced child pointers.
An int is 64 bits on a 64-bit Go target, so replacing a pointer with NodeID int does not reduce the field size there. A uint32 index could use four bytes, but would require a capacity limit and overflow checks; struct alignment also affects the final size.
Drawbacks of custom allocators
This implementation cannot reclaim individual nodes. Its global allNodes slice retains every bucket until the program exits. An allocator scoped to a task could release all its buckets by dropping every reference to them, after which Go could reclaim the memory; returning memory to the OS is a separate runtime decision. The allocator is also not safe for concurrent use without synchronization.
It’s not a problem in this case, since the tree only grows and the program ends when it’s done.
In a long-running program, this retention could be a much bigger issue. Reclaiming individual slots adds bookkeeping and can evolve into implementing a garbage collector of your own. At that point, ordinary Go allocations may be the simpler choice.
Measure on the current runtime
The original Java comparison motivated this experiment, but different Java collectors and newer Go runtimes make it unsuitable as a current language ranking.
Before adding a custom allocator, measure with go test -bench=. -benchmem and inspect allocation profiles with go tool pprof. Look for simpler ways to reduce allocation, such as preallocating a slice or reusing a buffer. Integer indices are useful when a group of objects has a shared lifetime, but retaining a large backing store can cost more memory than it saves.
A win in C++ as well
Optimizing by reducing the number of allocations or making allocations faster is applicable to languages without garbage collection as well, like C and C++, because malloc() and free() are relatively slow functions.
Back in the day when I was working on Poppler, I achieved a significant ~19% speedup by
improving a string class to avoid an additional allocation in 90% of the cases. I also used this trick in my C++ code, including SumatraPDF.
I also managed to improve Poppler by another ~25% by using a simple,
custom allocator.
It’s a good trick to know.
