Pre-size trigram posting list allocations to reduce GC pressure during indexing

[clemlesne]

Context

seek wraps zoekt as a local CLI for AI coding agents. Every search is a blocking tool call — the agent waits for results. On the cold-index path, shard building is the dominant cost, and over half of that cost is Go runtime memory management rather than useful work.

Problem

postingsBuilder.newSearchableString (index/shard_builder.go:90) iterates rune-by-rune through each file, extracting trigrams and appending to posting lists:

s.postings[ng] = append(s.postings[ng], buf[:m]...)

Each trigram's posting list ([]byte) grows via repeated append. Profiled on kubernetes (29k files, 23 shards, Apple M1 Max):

Flat CPU	Function	What
9.7s (38%)	runtime.memclrNoHeapPointers	Clearing newly allocated pages
1.5s (6%)	runtime.memmove	Copying on slice growth
1.8s (7%)	runtime.madvise	Kernel memory management
0.8s (3%)	runtime.mapassign_fast64	Map insertions

54% of CPU is runtime memory management. newSearchableString cumulative: 11.1s (44%), flat: 0.54s (2%) — nearly all time is in runtime calls it triggers.

Related PRs: #430 (skip trigram check for small files, 10% speedup), #522 (B+-tree for posting lists on search side), #680 (faster newLinesIndices), #838/#839 (reduce prepareNormalBuild allocations; #839 body states "we need a true rewrite"). None address newSearchableString.

Possible approaches

1. Pre-size maps (lowest effort): postings and lastOffsets are initialized as empty maps (map[ngram][]byte{} at line 82). Pre-sizing with make(map[ngram][]byte, 100_000) eliminates rehashing. The DocChecker already does this at line 596.

2. Single backing buffer: Instead of independent []byte per trigram, allocate one large []byte and sub-slice it. Eliminates per-trigram memclr/memmove. Go's arena experiment was removed in Go 1.23, but a manual arena (pre-allocated slice + offset tracking) works.

3. Pre-size posting list slices: Estimate per-trigram sizes based on corpus size, pre-allocate to reduce growth events.

4. GC tuning (immediate, no code changes): GOGC=off + GOMEMLIMIT=6GiB reduces GC overhead by 80-95% for batch workloads (Go team's recommended approach since 1.19). Could be set in the indexer entry point.

Impact

Reducing runtime memory management from 54% to ~20% yields ~1.5x speedup in shard building. On kubernetes, cold index from ~8s to ~5-6s.

[linear]

CU-2639

[keegancsmith]

Great, yes newSearchableString is indeed the biggest cost w.r.t. causing GC pressure so anything we can do to improve that would be great.

I'd very happily reviewing a PR here, this would be a great core improvement.

Impact

Reducing runtime memory management from 54% to ~20% yields ~1.5x speedup in shard building. On kubernetes, cold index from ~8s to ~5-6s.

Did you actually implement this already and these are real values?

Pre-size maps

I'd be interested to know how much of a difference this makes. I would of thought the bigger cost is the actual values in this map not the map itself.

Single backing buffer

It isn't clear to me how you would implement this. The only way I can think of is one of the following which would be interesting to compare:

instead of postings map[ngram][]byte you do something like postings []struct{ k ngram; v uint32 }. Then you just keep appending to that. To marshal you can do a stable sort on k and then do the binary.PutUVarint stuff.

GC tuning

Nice recommendation. We actually used to do some tuning of this, but it was mostly driven by zoekt-webserver. We did a little bit of tuning, but then decided probably best to just rely on defaults: #405

In particular GOGC=off seems very reasonable, but I do worry about very large monorepos (ones far larger than kubernetes). In a container environment, things that shell out to zoekt-git-index seem like they could set good values for GOMEMLIMIT.

It's probably more interesting to try improve the memory thrashing our indexer currently does before tweaking the go runtime.

[clemlesne]

Thanks for the detailed feedback @keegancsmith! I went ahead and implemented this — PR at #1020. Here's what I found:

Did you actually implement this already and these are real values?

The original numbers were estimates from profiling. Now they're real, measured values — and the actual improvement is larger than estimated. Benchmarked on kubernetes (22.9K files, 169 MB, Apple M1 Max):

Path	Before	After	Speedup
Cold (new builder)	9.3s	2.5s	3.7x
Warm (pooled reuse)	9.3s	2.3s	4.0x

Pre-size maps — I'd be interested to know how much of a difference this makes.

You were right — pre-sizing maps alone is marginal. The real wins came from two structural changes:

1. Pointer-stored map values (map[ngram]*postingList instead of map[ngram][]byte + map[ngram]uint32). This merges two maps into one and — critically — means the map is only written when a new ngram is first seen (~282K times) rather than on every trigram occurrence (~169M times). Cuts per-trigram map operations from 4 to ~1. This alone gave 1.8x.

2. Direct-indexed [2^21]*postingList array for ASCII trigrams. ASCII runes are 7 bits, so 3 runes = 21-bit index = 2M entries (16 MB). Since 99%+ of trigram occurrences in source code are pure ASCII, this eliminates nearly all hash/probe overhead. This gave an additional 2.1x on top.

Single backing buffer — It isn't clear to me how you would implement this.

I tried your flat-slice suggestion ([]struct{ k ngram; v uint32 }) first. It worked beautifully for the build phase (allocs dropped from 901K to 23K), but the write phase needed to sort 168M entries — slices.SortStableFunc took ~60s, making it a net regression. Hash-grouping at write time brought it to ~7s but was still 47x slower than the original write path.

The direct-indexed array approach turned out to be simpler and faster: zero-cost lookup during build (array index vs hash+probe), and write-time just iterates the array sequentially + sorts the small non-ASCII map (~6K entries). No sort of 168M items needed.

GC tuning — It's probably more interesting to try improve the memory thrashing our indexer currently does before tweaking the go runtime.

Agreed — that's exactly the approach I took. The PR addresses memory thrashing directly (pointer-stored values eliminate repeated map writes, pre-sized slices reduce growth events, sync.Pool reuses builders across shards). GC tuning is left for the caller to configure.

The PR includes benchmarks gated behind ZOEKT_BENCH_REPO (same pattern as seek) so these numbers are reproducible:

git clone --depth=1 https://github.com/kubernetes/kubernetes /tmp/k8s
ZOEKT_BENCH_REPO=/tmp/k8s go test ./index/ -bench=BenchmarkPostings -benchmem -count=5 -timeout=600s