Documentation
¶
Overview ¶
Package workload generates realistic streams of insertions and deletions for benchmarking mutable data structures such as maps, sets, trees, tries, indexes, caches and queues with rtcompare.
A hand-written "insert an element, then remove the same element" loop measures a structure that never changes shape: the node splits, merges, resizes, rehashes and tombstones that dominate real workloads never happen. Getting a realistic stream right by hand runs into four traps, and this package exists to avoid them:
- Invalid operations. A deletion must target an element that is present at that point of the stream, and an insertion one that is not, or part of the timed work is a no-op. Every stream here is valid by construction, and Check proves it against a model.
- Overhead in the timed loop. Choosing a victim while timing adds cache misses and branches to every candidate and dilutes the difference between them. The streams are precomputed; the timed loop only reads the next entry, sequentially.
- State drift across batches. rtcompare calls a batch many times, and a structure that grows or shrinks without bound is a different structure at the last sample than at the first. A Cycle ends exactly in its start state, so a Replay can repeat it endlessly without an untimed rebuild.
- Shared state across comparisons. The position in a cycle belongs to the data structure instance, not to the batch closure. A Replay carries it with the structure, and Replay.Settle brings the structure back to its start state before anything else is measured on it.
Two more traps sit in the measurement itself. The first pass of a cycle is where a structure grows to its peak size, a one-time cost that must neither be spread over a steady-state measurement nor be dropped. And whichever of two structures is built last starts ahead.
Compare does all of this in one call and answers the two questions a mutation benchmark has, what an operation costs in steady state and what a build costs, separately. For structures of more than a few megabytes, or full of pointers, one process is one observation of where their memory happened to lie, and Suite runs Compare in several processes through the multiproc package and pools both answers. Cycle, Build, Replay, Cursor and Check are the parts they are made of, for setups they do not cover.
Every operation names its element twice: by an ID, which says which element it is, and by a Key, which is what to insert into or delete from the structure. IDs 0 to target-1 are the elements the structure holds at rest, and transient IDs follow from target upwards, each inserted once and deleted once. That makes the IDs sequential, and the transient ones all larger than the permanent ones, which is the one arrangement a benchmark must not use as keys: an ordered structure would see every insertion at its right edge. The keys are therefore scattered over the whole uint64 range by default, see KeyOrder. Use op.Key for integer keys, or map op.ID to keys of your own through a precomputed slice, and keep the mapping out of the timed loop.
Index ¶
- Constants
- func Check(ops []Op, start, end []uint32) error
- func Suite[SA, SB any](name string, target int, a Structure[SA], b Structure[SB], opt Options) func(*multiproc.Process) error
- type Config
- type Cursor
- type KeyOrder
- type Kind
- type Op
- type Options
- type Policy
- type Replay
- type Result
- type Structure
Examples ¶
Constants ¶
const ( BuildRepeats = 31 BuildValidationRuns = 10 )
BuildRepeats and BuildValidationRuns are the build comparison's defaults for Repeats and ValidationRuns. They are smaller than rtcompare's, because a sample is a whole build: with them a build comparison performs about 1,300 builds, some ten seconds for 100,000 elements, where rtcompare's defaults would take several minutes.
const ( SteadyStateSuffix = "/steady state" BuildSuffix = "/build" )
SteadyStateSuffix and BuildSuffix are appended to the name given to Suite to name the two comparisons it records in each process.
const DefaultMaxBurst = 16
DefaultMaxBurst is the Config.MaxBurst used when it is left at zero.
const DefaultRatio = 2.0
DefaultRatio is the Config.Ratio used when it is left at zero: twice as many insertions as elements at rest, within the 1.5 to 3 that resembles a database index.
Variables ¶
This section is empty.
Functions ¶
func Check ¶
Check replays ops against a model set that starts as start, and reports the first operation that would be invalid: an insertion of a present element, a deletion of an absent one, a Lookup of an absent one, a LookupMiss of a present one, or an unknown Kind. It also reports whether the model ends as end, ignoring order. It returns nil if the stream is valid.
Use it in a test of anything that produces or transforms a stream. For a Build stream over target elements, start is empty and end is 0 to target-1; for a Cycle, both are 0 to target-1.
func Suite ¶ added in v0.8.0
func Suite[SA, SB any](name string, target int, a Structure[SA], b Structure[SB], opt Options) func(*multiproc.Process) error
Suite returns a suite for the multiproc package that runs Compare once in each process and records both of its answers, so that they are pooled across processes.
Parameters: name identifies the comparison; the steady-state report is recorded as name+[SteadyStateSuffix] and the build report as name+[BuildSuffix], the latter only unless opt.SkipBuild is set. target, a, b and opt are those of Compare.
Use it whenever the structures hold more than a few megabytes or are full of pointers, which for the sizes this package is meant for is the usual case. There, a single process's result is one observation of where its memory happened to lie, and its interval is several times too narrow; see rtcompare.Combine. multiproc starts the processes, perturbs each one's heap and pools the reports; Suite additionally alternates which structure's build comes second between processes, A in even ones and B in odd ones, so that the small head start of the one built last averages out.
The suite returns Compare's error, naming the comparison, if a structure lacks New or Apply, the configuration is invalid or a comparison fails. Invalid structures are therefore reported by the first child process.
func main() {
multiproc.MainSuite(multiproc.Options{},
workload.Suite("map vs Set3", 1_000_000, goMap, set3Set, workload.Options{}))
}
Example ¶
Suite runs Compare in several processes through the multiproc package and pools both answers, for structures too large for one process to judge.
package main
import (
set3 "github.com/TomTonic/Set3"
"github.com/TomTonic/rtcompare/multiproc"
"github.com/TomTonic/rtcompare/workload"
)
// found counts successful lookups, so that they are not optimised away.
var found int
// goMap and set3Set describe the two sets the example compares. Both are
// created with a capacity hint for the elements at rest, as a program that
// knows its size would.
func goMap(target int) workload.Structure[map[uint64]struct{}] {
return workload.Structure[map[uint64]struct{}]{
Name: "map",
New: func() map[uint64]struct{} { return make(map[uint64]struct{}, target) },
Apply: func(m map[uint64]struct{}, run []workload.Op) {
for _, op := range run {
switch op.Kind {
case workload.Insert:
m[op.Key] = struct{}{}
case workload.Delete:
delete(m, op.Key)
default:
if _, ok := m[op.Key]; ok {
found++
}
}
}
},
}
}
func set3Set(target int) workload.Structure[*set3.Set3[uint64]] {
return workload.Structure[*set3.Set3[uint64]]{
Name: "Set3",
New: func() *set3.Set3[uint64] { return set3.EmptyWithCapacity[uint64](uint32(target)) },
Apply: func(s *set3.Set3[uint64], run []workload.Op) {
for _, op := range run {
switch op.Kind {
case workload.Insert:
s.Add(op.Key)
case workload.Delete:
s.Remove(op.Key)
default:
if s.Contains(op.Key) {
found++
}
}
}
},
}
}
func main() {
const target = 1_000_000
multiproc.MainSuite(multiproc.Options{},
workload.Suite("map vs Set3", target, goMap(target), set3Set(target), workload.Options{}))
}
Output:
Types ¶
type Config ¶
type Config struct {
// Seed makes a stream reproducible: the same seed and configuration give
// the same stream. Zero is a seed like any other.
Seed uint64
// Ratio is the number of insertions per element at rest. Build inserts
// Ratio*target elements in all, of which target remain; Cycle inserts and
// deletes (Ratio-1)*target transient elements. Zero selects DefaultRatio.
// Build requires at least 1, Cycle more than 1.
Ratio float64
// MaxBurst bounds the length of a burst of insertions, which is drawn
// uniformly from 1 to MaxBurst. Zero selects DefaultMaxBurst.
MaxBurst int
// LiveTarget is the number of transient elements the stream keeps present
// on average: the more are present, the longer the deletion bursts. Zero
// selects target/8, but no more than half the transient elements, and at
// least one.
LiveTarget int
// Victims chooses which transient element a deletion removes. The zero
// value is Uniform.
Victims Policy
// Keys chooses how IDs become keys. The zero value is Scattered, derived
// from Seed.
Keys KeyOrder
// PermanentChurn is the share of deletions, from 0 up to but excluding 1,
// that remove a permanent element rather than a transient one; the element
// is inserted again later in the same stream, so that a cycle still ends
// where it began. Zero, the default, never touches the permanent elements
// once they are in, which spares the long-lived part of a structure the
// tombstones, merges and rebalancing that real deletions cause there.
PermanentChurn float64
// Lookups is the number of lookups per insertion or deletion, spread evenly
// over the stream, and MissRate the share of them, from 0 to 1, that look
// for an element that is not present. A lookup that hits picks uniformly
// among the elements present at that point. Zero, the default, makes a
// stream of mutations only.
//
// Lookups add the kinds Lookup and LookupMiss to the stream, so an Apply
// function has to tell all four kinds apart; one written as "insert, or
// else delete" would delete where it should look up.
Lookups, MissRate float64
}
Config configures Build and Cycle. The zero value is usable and selects the documented defaults.
func (Config) Key ¶ added in v0.8.0
Key returns the key of the element with the given ID, as the streams made with this Config carry it in Op.Key.
Use it to fill a structure with the elements present at rest, IDs 0 to target-1, before replaying a Cycle on it, or to look up the elements a stream holds. It computes the key, a few nanoseconds, so read Op.Key in a timed loop rather than calling it there.
type Cursor ¶
type Cursor struct {
// contains filtered or unexported fields
}
Cursor is a position in a Cycle, and belongs to the data structure instance the cycle is replayed on.
It exists because the position is a property of the structure, not of the batch function: after half a cycle, the structure holds the transient elements of that half, and only a replay that continues from there stays valid. A new batch closure that started again at zero would insert elements that are already present. Keep one Cursor per instance, next to it, and use it for every comparison the instance takes part in.
The zero value is at the start of the cycle.
func (*Cursor) Advance ¶
Advance applies the next n operations of ops through apply, wrapping around at the end of the cycle, and moves the cursor past them. It is what the function returned by Batch does, for callers who drive the replay themselves.
func (*Cursor) Batch ¶
Batch returns an rtcompare.Batch that applies the next n operations of ops on every call, wrapping around at the end of the cycle.
Parameters: ops is a stream from Cycle, and must be the same on every call with this Cursor; apply performs the operations it is handed on the data structure. apply receives contiguous runs of the stream, so the loop over them sits in the caller's code, where the compiler can inline the data structure's methods; a run is split at the end of the cycle, so apply may be called more than once per batch.
Use it as a candidate's Batch. One operation is one unit of work: the per-operation cost rtcompare reports is the average of the insertions and deletions in the stream.
Prefer Replay, which also plays the first pass untimed; with a bare Cursor that is up to the caller, see Replay for why it matters.
cur := &workload.Cursor{}
candidate := rtcompare.Candidate{Name: "map", Batch: cur.Batch(ops, func(run []workload.Op) {
for _, op := range run {
switch op.Kind {
case workload.Insert:
m[op.Key] = struct{}{}
case workload.Delete:
delete(m, op.Key)
default: // Lookup and LookupMiss, if Config asks for lookups
_, found := m[op.Key]
hits += found
}
}
})}
An empty ops makes a batch that does nothing.
func (*Cursor) Settle ¶
Settle applies the rest of the cycle, if the cursor is not at its start, so that the structure is back in the state the cycle starts from: exactly the IDs 0 to target-1 present.
Call it outside the measured region, for instance in a Candidate's Teardown or between comparisons, before anything else is measured on the structure.
type KeyOrder ¶ added in v0.8.0
type KeyOrder int
KeyOrder chooses how IDs become keys, see Config.Keys.
const ( // Scattered maps IDs to keys by a seeded permutation of the uint64 range, // so that the keys of permanent and transient elements are interleaved // and in no particular order, as the keys of a real workload are. It is // the zero value, and the right choice for any structure that orders its // keys or hashes them. Scattered KeyOrder = iota // Sequential uses the ID itself as the key. The permanent keys are then 0 // to target-1 and every transient key lies above all of them, so an // ordered structure takes every insertion at its right edge. Choose it // only to measure exactly that, such as append-only time series keys. Sequential )
func (KeyOrder) String ¶ added in v0.8.0
String implements fmt.Stringer.
type Kind ¶
type Kind uint8
Kind is what an Op does.
const ( // Insert adds an element that is not present. Insert Kind = iota // Delete removes an element that is present. Delete // Lookup looks up an element that is present. Streams contain lookups // only when Config.Lookups asks for them. Lookup // LookupMiss looks up an element that is not present, and never was. LookupMiss )
type Op ¶
type Op struct {
// Key is the element's key, the value to insert into or delete from the
// structure under test. Keys are distinct for distinct IDs, and the same
// ID has the same key in every stream made with the same Config, so a
// [Build] and a [Cycle] fit together. See [KeyOrder] for how they are
// chosen.
Key uint64
// ID identifies the element among those of the stream: 0 to target-1 for
// the elements present at rest, target upwards for transient ones.
ID uint32
// Kind is what the operation does.
Kind Kind
}
Op is one mutation of a stream: which element, and what to do with it. It occupies 16 bytes, so a cycle of 12.7 million operations takes about 200 MB.
func Build ¶
Build returns a stream that takes a structure from empty to holding exactly the IDs 0 to target-1, the way it would have got there in real use: with transient elements inserted and deleted along the way.
Parameters: target is the number of elements at the end, at least one; c configures the stream, see Config. With Ratio r the stream holds r*target insertions, target of them permanent and the rest transient, and a deletion for each transient one. Bursts of insertions alternate with bursts of deletions, and the permanent elements are inserted in random order, spread across the whole stream.
It returns the stream, or an error for a target below one, an invalid configuration, or more elements than fit in a uint32 ID.
Use it to build a fixture with a realistic history, since a structure built by inserting its final elements in order can look quite different inside from one that has seen deletions, or to time the build itself. Replay it once, from the start; unlike a Cycle it does not return to where it began.
func Cycle ¶
Cycle returns a stream that starts with the IDs 0 to target-1 present, inserts and deletes transient elements, and ends with exactly the IDs 0 to target-1 present again, so that it can be replayed endlessly.
Parameters: target is the number of elements present at rest, at least one; c configures the stream, see Config. With Ratio r the cycle inserts and deletes (r-1)*target transient elements in alternating bursts, keeping about LiveTarget of them present at a time. The elements present at rest are never deleted.
It returns the stream, or an error for a target below one, an invalid configuration, a ratio at which no transient element would be inserted, or more elements than fit in a uint32 ID.
Use it for steady-state mutation benchmarks: build the structure with the elements of IDs 0 to target-1, from a Build stream or with the keys from Config.Key, then replay the cycle through a Replay in the batch. Because the cycle ends in its start state, a batch can wrap around to the beginning, and the structure the last sample measures is the one the first sample measured. At 1M elements and r = 2 a cycle has 2M operations and takes 32 MB.
Example ¶
Cycle and Replay replay insertions and deletions on one structure without ever rebuilding it: the cycle ends where it started, and the Replay keeps the structure's position in it. Check proves that a stream is valid.
package main
import (
"fmt"
"github.com/TomTonic/rtcompare/workload"
)
func main() {
const target = 1000
cfg := workload.Config{Seed: 1}
cycle, err := workload.Cycle(target, cfg)
if err != nil {
fmt.Println(err)
return
}
atRest := make([]uint32, target)
for i := range atRest {
atRest[i] = uint32(i)
}
fmt.Println("valid:", workload.Check(cycle, atRest, atRest) == nil)
m := make(map[uint64]struct{}, target)
for id := range uint32(target) {
m[cfg.Key(id)] = struct{}{}
}
replay := workload.NewReplay(cycle, func(run []workload.Op) {
for _, op := range run {
if op.Kind == workload.Insert {
m[op.Key] = struct{}{}
} else {
delete(m, op.Key)
}
}
})
candidate := replay.Candidate("map")
candidate.Setup() // what rtcompare does before the first batch: one untimed pass
candidate.Batch(uint64(len(cycle)) + 17)
replay.Settle()
fmt.Println("back at rest:", len(m) == target)
}
Output: valid: true back at rest: true
type Options ¶
type Options struct {
// Config configures the two streams, see [Config].
Config Config
// SteadyState are the options of the steady-state comparison, passed to
// [rtcompare.Compare] unchanged.
SteadyState rtcompare.CompareOptions
// Build are the options of the build comparison. Each of its samples is a
// whole build, which takes milliseconds rather than the microseconds of a
// calibrated batch, so a zero Collect.Repeats selects [BuildRepeats] and a
// zero ValidationRuns selects [BuildValidationRuns] rather than
// rtcompare's defaults, and Collect.GCBetween is always set, since every
// build leaves a whole structure of garbage behind that would otherwise be
// collected in the middle of the next candidate's build.
Build rtcompare.CompareOptions
// SkipBuild omits the build comparison. The steady-state result alone
// ignores what growing to size costs, and so favours structures whose
// growth is expensive; set it only when that cost is known not to matter.
SkipBuild bool
}
Options configures Compare. The zero value is usable and selects the documented defaults.
type Policy ¶
type Policy int
Policy decides which present transient element a deletion removes.
const ( // Uniform deletes a transient element drawn uniformly from those present, // so that some are deleted soon after their insertion and some long after. // It is the zero value, and what a general-purpose map or set sees. Uniform Policy = iota // FIFO deletes the oldest transient element present, as a queue, a // time-series retention window or a log compaction does. FIFO // LIFO deletes the youngest transient element present, as a stack or an // undo log does. LIFO )
type Replay ¶
type Replay struct {
// contains filtered or unexported fields
}
Replay plays a Cycle on one data structure instance. It bundles the stream, the function that applies operations to the structure, and the position in the cycle, so that they cannot be mismatched: create one Replay per structure instance, next to the structure.
It also takes care of the first pass. That pass is where the structure grows to the largest size the cycle reaches, and it costs far more than every pass after it: for a Go map of 100,000 elements at Ratio 2, stretches of the first pass cost 35 to 128 ns per operation where later passes cost 17 to 20. That growth happens once in a program's life and would otherwise be spread over the measurement, in proportions that depend on how long it ran. The candidate from Replay.Candidate therefore plays one full cycle, untimed, before its first measured batch. What the growth costs is a question of its own, which Compare answers separately with a Build stream.
func NewReplay ¶
NewReplay returns a Replay of ops, a stream from Cycle, applied to one structure through apply. apply receives contiguous runs of the stream, so that its loop over them sits where the compiler can inline the structure's methods; see Cursor.Batch.
func (*Replay) Candidate ¶
Candidate returns an rtcompare.Candidate that replays the cycle, continuing where the previous batch stopped. Its Setup primes the structure before the first batch, outside the measured region, and does nothing after that.
type Result ¶
type Result struct {
// Target is the number of elements at rest, and CycleOps and BuildOps the
// lengths of the two streams.
Target int
CycleOps, BuildOps int
// SteadyState compares the cost of one insertion or deletion in a
// structure that has been in use for a while, averaged over the cycle. Its
// per-operation figures are nanoseconds per insertion or deletion.
SteadyState rtcompare.Report
// Build compares the cost of building a structure from empty to Target
// elements, with the transient insertions and deletions a real build sees,
// including creation, every resize and the garbage it leaves. Its
// per-operation figures are nanoseconds per whole build. It is the zero
// Report when Options.SkipBuild was set.
Build rtcompare.Report
}
Result holds the two answers Compare gives, which are answers to two different questions and are deliberately not combined into one number.
func Compare ¶
Compare compares two data structures under a realistic mix of insertions and deletions, and answers two questions separately: what an operation costs once a structure is in use, and what it costs to build one.
Parameters: target is the number of elements the structures hold at rest, at least one; a and b are the two structures, see Structure; opt configures the streams and both comparisons, see Options.
It returns both reports, or an error if a structure lacks New or Apply, if the configuration is invalid (see Build and Cycle), or if a comparison fails.
Use it for any comparison of mutable data structures. It exists because doing this by hand has several traps, and each of them quietly changes the answer:
- The steady-state comparison builds one structure of each kind to target elements with a Build stream, applied to the two alternately in chunks so that neither is built last, and then replays a Cycle on each through a Replay. The first pass of the cycle is untimed: it is where the structure grows to the cycle's peak size, a one-time cost that would otherwise be spread over the measurement in proportions that depend on how long the run was.
- That growth is not dropped, it is measured where it belongs. The build comparison times whole builds, each from a structure fresh from New to target elements, so creation, capacity hints, every resize and the garbage are included. A structure that cannot be presized and has to grow pays for it here, and one that grows cheaply shows it here.
The two answers can disagree, and then that is the result: one structure can be faster to use and slower to build. Read both.
Both answers describe this one process. For structures of more than a few megabytes, or full of pointers, where the structures lie in memory moves the result by several points and differently in the next process; run the comparison through Suite with the multiproc package there.
The cost is that of two rtcompare.Compare calls, the build one dominated by the builds it performs, about 1,300 at the defaults; see BuildRepeats.
res, err := workload.Compare(100_000,
workload.Structure[map[uint64]struct{}]{Name: "map", New: newMap, Apply: applyToMap},
workload.Structure[*set3.Set3[uint64]]{Name: "Set3", New: newSet3, Apply: applyToSet3},
workload.Options{})
if err != nil { ... }
fmt.Println(res)
Example ¶
ExampleCompare compares Go's built-in map with Set3 under a realistic mix of insertions and deletions over 100,000 elements, and answers two questions: what an insertion or deletion costs once a set is in use, and what it costs to build one. Everything else, the streams, building both sets, the untimed first pass and the cursors, is done by Compare.
package main
import (
"fmt"
set3 "github.com/TomTonic/Set3"
"github.com/TomTonic/rtcompare/workload"
)
// found counts successful lookups, so that they are not optimised away.
var found int
// goMap and set3Set describe the two sets the example compares. Both are
// created with a capacity hint for the elements at rest, as a program that
// knows its size would.
func goMap(target int) workload.Structure[map[uint64]struct{}] {
return workload.Structure[map[uint64]struct{}]{
Name: "map",
New: func() map[uint64]struct{} { return make(map[uint64]struct{}, target) },
Apply: func(m map[uint64]struct{}, run []workload.Op) {
for _, op := range run {
switch op.Kind {
case workload.Insert:
m[op.Key] = struct{}{}
case workload.Delete:
delete(m, op.Key)
default:
if _, ok := m[op.Key]; ok {
found++
}
}
}
},
}
}
func set3Set(target int) workload.Structure[*set3.Set3[uint64]] {
return workload.Structure[*set3.Set3[uint64]]{
Name: "Set3",
New: func() *set3.Set3[uint64] { return set3.EmptyWithCapacity[uint64](uint32(target)) },
Apply: func(s *set3.Set3[uint64], run []workload.Op) {
for _, op := range run {
switch op.Kind {
case workload.Insert:
s.Add(op.Key)
case workload.Delete:
s.Remove(op.Key)
default:
if s.Contains(op.Key) {
found++
}
}
}
},
}
}
func main() {
const target = 100_000
res, err := workload.Compare(target, goMap(target), set3Set(target), workload.Options{})
if err != nil {
panic(err)
}
fmt.Println(res)
}
Output:
type Structure ¶
type Structure[S any] struct { // Name labels the structure in the results. Name string // New returns an empty structure, created the way the program would create // it. Whether it is given a capacity hint is part of what the build // comparison measures, so give it one exactly when the program would. New func() S // Apply performs the operations of run on s, in order. Keep the loop over // run in this function, where the compiler can inline the structure's // methods. With Config.Lookups set, run also holds Lookup and LookupMiss // operations, so switch over all four kinds rather than treating // everything but an insertion as a deletion. Apply func(s S, run []Op) }
Structure describes one data structure under test for Compare: how to create an empty one, and how to apply operations to it.
Source Files