Documentation
¶
Overview ¶
Package entryheap is the committed heap-and-GC instrument for the per-key payload of the B+ tree property index (rmp sprint 353, task #2684).
Why it exists ¶
Task #2683 converted graph/index/btree to a copy-on-write snapshot whose per-key payload — the node-set plus the lock that guards it — lives behind a pointer in a separate heap object, so a path-copied snapshot and its predecessor address the SAME lock. That bought 12.37x throughput at 8 goroutines and cut resident bytes per key by 11.9%, and it spent exactly one vector to do it: one extra heap OBJECT per distinct key. At 10M keys that object count was measured to more than double GC mark time.
The harness that produced those numbers was never committed, so the claim could not be re-run. This package is that harness, rebuilt to the same discipline and committed so every number in the record is reproducible.
What it measures, and why these instruments ¶
For one live index of Keys distinct values, each carrying exactly ONE node — deliberately the case most ADVERSE to a per-key payload object, because it maximises the object count per resident byte — it reports:
- resident bytes per key, from /memory/classes/heap/objects:bytes. Chosen over an inuse_space pprof profile because that samples at 512 KB and would systematically under-count a large population of small uniform objects, which is exactly the shape under test.
- live objects per key, from /gc/heap/objects:objects.
- scannable bytes per key, from /gc/scan/heap:bytes. This separates the two candidate cost drivers: a change that cuts object COUNT while leaving scannable BYTES alone proves the mark cost is per-object, not per-byte.
- GC mark cost, by TWO independent instruments that must agree: the wall-clock of a forced runtime.GC (which blocks until the cycle completes), and the mark CPU-seconds drawn from /cpu/classes/gc/mark/{dedicated,assist,idle}. Wall clock alone is sensitive to how many workers the scheduler granted; CPU-seconds alone hides a change in parallelism. Reporting both makes a discrepancy visible instead of silently picking the flattering one.
Every counter is BRACKETED: read immediately before and immediately after the forced cycle it describes, so nothing that happens outside that window can be folded into the number.
The deletion phase, and the retention question it answers ¶
Any design that carves per-key payloads out of a shared slab trades object count for RETENTION: a slab stays reachable while any single one of its entries is still live, so a sufficiently sparse survivor set pins slabs that are almost entirely dead. Config.KeepOneIn drives exactly that worst case. Entries are handed out in insertion order, so deleting every key except every KeepOneIn-th INSERTION leaves at most one survivor per slab of that size — the maximum a slab allocator can pin. The phase reports resident bytes per SURVIVING key, which is the number the pinning question needs.
Discipline ¶
One process measures ONE configuration. The heap is cumulative and cannot be reset, so a second configuration in the same process inherits the first one's warm heap, its raised GC goal and its mapped pages. Arms are compared by running the binary repeatedly, interleaved, never by looping inside it.
Before any timing, the heap is settled with three forced collections spaced by a short sleep, and the index is pinned across the whole measurement with runtime.KeepAlive, so nothing under test can be collected early and flatter the result.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func InsertionKeys ¶
InsertionKeys returns the key inserted at each step, in order, for cfg.
It exists so the harness's OWN insertion order can be tested for bijectivity: a stride sharing a factor with the key count would silently build a smaller index than the configuration asked for, and every per-key number would then be divided by the wrong denominator. It materialises a slice and is therefore never used inside a measurement — see OrderStrided.
func Min ¶
Min returns the smallest value of s, or 0 when s is empty. The minimum is the least-contaminated sample of a repeated timing: every source of interference on a shared host — a competing process, a frequency drop, a migration to an efficiency core — can only make a sample slower, never faster.
Types ¶
type BuildMode ¶
type BuildMode string
BuildMode selects how the index under measurement is populated.
const ( // BuildInsert populates the index one key at a time through // [btree.Index.Insert], the incremental path every live write takes. BuildInsert BuildMode = "insert" // BuildBulk populates it through [btree.Index.BulkLoadSorted], the O(n) // bottom-up packer that snapshot recovery and Deserialize use. BuildBulk BuildMode = "bulk" )
type Config ¶
type Config struct {
// Keys is the number of distinct keys the index holds.
Keys int
// GCs is the number of forced collections timed after the heap settles.
GCs int
// Build selects the population path.
Build BuildMode
// Order selects the insertion order (BuildInsert only; a bulk load is
// sorted by contract).
Order KeyOrder
// KeepOneIn, when >= 2, runs the deletion phase described in the package
// documentation, keeping every KeepOneIn-th insertion and deleting the
// rest. Zero or one skips the phase.
KeepOneIn int
}
Config describes one measurement. The zero value is not usable; see [Config.normalise] for the defaults applied to unset fields.
type KeyOrder ¶
type KeyOrder string
KeyOrder selects the order in which keys are inserted. It changes the order the per-key payloads are ALLOCATED in, which is the variable a slab allocator is sensitive to; it does not change the resulting index.
const ( // OrderAscending inserts 0, 1, 2, ... so allocation order equals key order // and payloads adjacent in memory are adjacent in the tree. OrderAscending KeyOrder = "asc" // OrderStrided inserts (step * stride) mod Keys for a stride coprime with // Keys. That is a bijection, so the index ends up holding exactly the same // keys, but consecutive insertions land stride apart in key space — the // case most ADVERSE to a slab allocator, because payloads that share a slab // are then maximally far apart in the tree and share no locality with it. // // It is deliberately an affine cycle and not a materialised random // permutation: a permutation of 10M int64 is 80 MB that would still be // reachable while the heap is weighed, contaminating bytes-per-key by ~8 B. // The stride is computed, so the order costs no memory at all. OrderStrided KeyOrder = "strided" )
type Sample ¶
type Sample struct {
// Phase names the point in the measurement: "built" or "pruned".
Phase string
// LiveKeys is the number of distinct keys the index holds at this phase.
LiveKeys int
HeapObjectBytes uint64
HeapObjects uint64
ScanHeapBytes uint64
BytesPerKey float64
ObjectsPerKey float64
ScanBytesPerKey float64
// GCWallMillis holds every timed forced-collection wall clock, ascending.
GCWallMillis []float64
// MarkCPUMillis holds the mark CPU-seconds of each timed collection,
// converted to milliseconds, ascending. Index i does NOT correspond to
// GCWallMillis[i]; both are sorted independently so the minimum and median
// of each are directly readable.
MarkCPUMillis []float64
}
Sample is one bracketed observation of the live heap.
func Measure ¶
Measure builds one index to cfg and returns one Sample per phase: always "built", plus "pruned" when cfg.KeepOneIn asks for the deletion phase.
The index is kept alive across every observation, so no sample can be flattered by the collector reclaiming the very thing under measurement.
Source Files