Documentation
¶
Overview ¶
Package multiproc runs rtcompare comparisons in several processes and pools their results, so that the reported interval covers the scatter between processes and not only the noise within one.
A single process fixes its memory layout for its whole lifetime, and for data larger than the caches or full of pointers that layout can move a measured difference by several points. The interval of a single rtcompare.Report cannot see this: the next process reports a different, equally narrow interval somewhere else (issue #109). The remedy is to treat one process as one observation.
Everything that takes is done here, so that none of it has to be remembered: the program is started again as child processes; each child perturbs its heap from its own seed before anything is built; the two candidates' data is built in an order that alternates between processes, since whichever is built second can be consistently a few percent faster; the reports are pooled per comparison with rtcompare.Combine; and and the first processes decide how many more every pooled interval needs to be precise enough.
A program needs nothing but the comparisons:
func main() {
multiproc.Main(multiproc.Options{}, multiproc.Pair{
Name: "lookup",
A: func() rtcompare.Candidate { return lookupIn(buildTreeA()) },
B: func() rtcompare.Candidate { return lookupIn(buildTreeB()) },
})
}
In a test, RunTest does the same and returns the results for assertions. MainSuite and RunTestSuite take a suite instead of pairs, such as the workload package's Suite for comparing data structures, and Suites combines several suites into one. Run is the general form underneath.
Two regimes ¶
By default the children run one after another, each with the machine to itself. That is the serial regime, and it answers how the candidates compare on an otherwise idle machine. Options.Parallel runs several children at the same time instead, in waves. That is a different regime, not just a faster one: the children share the last-level cache, the memory bandwidth and the clock headroom, much as a program shares them with its neighbours in production. Where the data is out of cache, the parallel regime is usually the only way to precision in reasonable time, because the variance of the pooled estimate is roughly
σ²_between/P + σ²_within/(P·R)
for P processes of R samples, and out of cache the first term dominates by far: precision improves almost only with P, and running children at the same time multiplies P per hour by the number of parallel slots. Where the question is how a structure performs with the whole cache to itself, or where a result must stand next to earlier serial ones, stay serial.
The two regimes' results are not interchangeable: all-core load lowers the clock and shrinks each process's share of the cache, which moves the point where accesses go to memory to smaller data. Never pool or compare them with each other. Results.Parallel records which one ran, and reports should state it. Within a process, A and B still run interleaved in both regimes, so neighbouring processes widen the noise but do not favour either candidate.
Index ¶
Examples ¶
Constants ¶
const ( DefaultMinProcesses = 5 DefaultMaxProcesses = 40 DefaultMaxWaves = 10 DefaultRotation = 2 DefaultAbsPrecision = 0.02 DefaultRelPrecision = 0.10 )
Defaults for Options, taken from downstream suites that pooled hundreds of comparisons this way.
Five processes were enough while the data fit in the caches. Out of cache the first suite needed 13 to 15 before every interval was within two points, which set the old serial budget of 20; later runs needed 20 to 40, and where processes scattered by 9 to 12 points the precision asked for would have needed 70 to 130 (issue #115). DefaultMaxProcesses of 40 keeps a serial run bounded while covering a scatter of about 6 points. A parallel run is budgeted in waves instead: DefaultMaxWaves of 10 costs about the wall time of 10 serial processes, since a wave takes about as long as one process, and at Parallel 12 allows 120 processes, enough for a scatter of 10 points and more.
Variables ¶
This section is empty.
Functions ¶
func Main ¶
Main runs the pairs in several processes and prints the pooled results. It is meant to be the whole of a benchmark program's main function.
Parameters: opt configures the processes, see Options; pairs are the comparisons, see Pair.
In the parent, the process the user started, Main prints a line per finished process, or per finished wave in a parallel run, to standard error and the pooled results to standard output, then returns. In a child it runs the pairs once and exits, so that nothing after Main runs there. On an error it prints it to standard error and exits with status 1, in either role.
func main() {
multiproc.Main(multiproc.Options{}, multiproc.Pair{Name: "lookup", A: buildA, B: buildB})
}
Example ¶
Main is the whole of a benchmark program: it runs the comparison in child processes, each with its own heap layout and alternating build order, and prints the pooled result. Build the data inside the builders, so that it is built in every child, after the heap is perturbed.
package main
import (
"github.com/TomTonic/rtcompare"
"github.com/TomTonic/rtcompare/multiproc"
)
// tree stands for a data structure large enough that one process is one
// observation, and lookupIn for the candidate that measures it.
type tree struct{ keys []uint64 }
func buildTree() *tree { return &tree{keys: make([]uint64, 1<<20)} }
func lookupIn(t *tree) rtcompare.Candidate {
return rtcompare.Candidate{Name: "lookup", Batch: func(n uint64) {
for i := range n {
_ = t.keys[i%uint64(len(t.keys))]
}
}}
}
func main() {
multiproc.Main(multiproc.Options{}, multiproc.Pair{
Name: "lookup",
A: func() rtcompare.Candidate { return lookupIn(buildTree()) },
B: func() rtcompare.Candidate { return lookupIn(buildTree()) },
})
}
Output:
func MainSuite ¶ added in v0.8.0
MainSuite is Main for a suite instead of pairs: it runs suite in several processes and prints the pooled results, and is meant to be the whole of a benchmark program's main function.
Parameters: opt configures the processes, see Options; suite is the measurement one process performs, see Run. Suites from other packages, such as the workload package's Suite, fit here, and Suites combines several of them, pairs included through Pairs.
It behaves like Main in every other respect, printing progress and results in the parent and exiting in a child.
func main() {
multiproc.MainSuite(multiproc.Options{},
workload.Suite("map vs Set3", 1_000_000, goMap, set3Set, workload.Options{}))
}
func Pairs ¶
Pairs returns a suite for Run that builds and compares each pair in turn, and records each report under the pair's name.
Parameters: pairs are the comparisons, see Pair.
Use it when Run's other options are needed with pairs, or to combine pairs with measurements of your own in one suite. Main and RunTest use it. The suite returns an error, naming the pair, if a comparison fails; it does not check the pairs, which Main and RunTest do before starting any process.
func Suites ¶ added in v0.8.0
Suites combines several suites into one that runs them in turn, in the order given, and stops at the first error.
Parameters: suites are the suites to run, none of them nil.
Use it to measure several kinds of comparison in the same processes, for example pairs and a workload suite:
multiproc.MainSuite(opt, multiproc.Suites(multiproc.Pairs(lookup), workload.Suite(...)))
Types ¶
type Comparison ¶
type Comparison struct {
// Name is the name the suite recorded it under.
Name string
// Reports holds one report per process that recorded it, in process order.
// They carry the estimate, confidences, noise floor, verdict, suspension
// and warnings of each process, and of the validations only the A/A
// differences in
// ValidationA.Deltas and ValidationB.Deltas; the raw samples and the rest
// of the validations stay in the child.
Reports []rtcompare.Report
// Pooled is the result of pooling Reports: [rtcompare.CombineStaged] once
// the run's first stage is complete, [rtcompare.Combine] before. It is the
// zero value until three processes have recorded the comparison.
Pooled rtcompare.Pooled
// contains filtered or unexported fields
}
Comparison collects one named comparison across processes.
type Options ¶
type Options struct {
// MinProcesses is the size of the run's first stage: the processes whose
// scatter decides how many processes the whole run needs, once, see
// AbsPrecision. Zero selects [DefaultMinProcesses]. Must be at least 3, the
// minimum [rtcompare.Combine] pools. It is rounded up to a whole Rotation,
// and in a parallel run to a whole wave. A larger first stage estimates the
// scatter better and so asks for fewer extra processes, at the price of
// never running fewer.
MinProcesses int
// MaxProcesses bounds the number of processes. Zero selects
// [DefaultMaxProcesses] for a serial run and [DefaultMaxWaves] waves for a
// parallel one. In a parallel run an explicit value is rounded up to a
// whole wave, and so is MinProcesses, since a wave runs in full anyway.
// Must not be below MinProcesses.
MaxProcesses int
// Parallel is the number of child processes that run at the same time.
// Zero or 1 selects the serial regime, one process after another. Above 1,
// processes are started in waves of Parallel, rounded up to a whole
// Rotation so that every build order is represented equally in each wave,
// and the first stage and the whole run are whole waves.
//
// Parallel runs measure a loaded machine: the children share caches,
// memory bandwidth and clock headroom, much as a program in production
// shares them with its neighbours. That is a legitimate regime, and for
// data out of cache usually the faster way to precision, but it is a
// different one: all-core load lowers the clock and shrinks each process's
// share of the last-level cache, so its results must not be pooled or
// compared with a serial run's; Results.Parallel records which one ran.
// Keep it at or below the number of physical cores. Two children on the
// SMT siblings of one core share its L1 and L2 caches and disturb each
// other far more than neighbours on other cores do.
//
// Unless the environment already sets GOMAXPROCS, each child of a parallel
// run gets GOMAXPROCS = max(2, NumCPU/Parallel), so that one child's
// garbage collector cannot take cores from its neighbours in the middle of
// their measurements.
Parallel int
// Rotation is the number of build orders the suite cycles through by
// Process.Index, such as 2 for building A's data last in even processes and
// B's in odd ones. The first stage and the whole run are rounded up to a
// whole rotation, so that every order is represented equally in the pooled
// result. Zero selects [DefaultRotation], which matches that two-way
// alternation and costs a suite that does not alternate at most one extra
// process; 1 rounds nothing.
Rotation int
// AbsPrecision and RelPrecision are the precision asked for: every
// comparison's pooled interval should have a half-width of at most
// AbsPrecision, or of at most RelPrecision times its |Delta|. After the
// first stage of MinProcesses, the run computes once how many processes
// that takes, from the scatter the first stage showed, and then runs that
// many, up to MaxProcesses, without looking at the intervals again; see
// [rtcompare.Pooled.ProcessesFor] for why. Zero selects
// [DefaultAbsPrecision] and [DefaultRelPrecision].
AbsPrecision, RelPrecision float64
// Level is the coverage level of the pooled intervals. Zero selects
// [rtcompare.DefaultConfidenceLevel].
Level float64
// Seed determines the per-process seeds, so that a whole run can be
// repeated. Zero selects a random one; Results.Seeds records what each
// process got either way.
Seed uint64
// Executable is the program to start as a child. Empty selects the running
// binary, from os.Executable.
Executable string
// Args are the arguments for the children. Nil selects os.Args[1:], which
// repeats the parent's own command line. In a test, run only the calling
// test in the children, or every test of the package runs in every child:
//
// Args: []string{"-test.run=^" + regexp.QuoteMeta(t.Name()) + "$"}
Args []string
// Stdout and Stderr receive the children's output. Nil discards stdout and
// passes stderr through to the parent's. In a parallel run the children's
// output is written in whole lines, each prefixed with its process index
// such as "[p07] ", so that concurrent children do not interleave within
// a line.
Stdout, Stderr io.Writer
// Progress, when set, is called with the results so far after each
// process of a serial run and after each complete wave of a parallel one,
// for example to print a line per call.
Progress func(Results)
}
Options configures Run. The zero value is usable and selects the documented defaults.
type Pair ¶
type Pair struct {
// Name identifies the comparison in the results. It must be unique among
// the pairs of one run.
Name string
// A and B build their candidate: they create the data the candidate works
// on and return the candidate. Build everything the measurement depends
// on here, not before, so that it is built after the heap perturbation and
// in the alternating order. Neither may be nil.
A, B func() rtcompare.Candidate
// Options are passed to [rtcompare.Compare] unchanged.
Options rtcompare.CompareOptions
}
Pair is one comparison for Main, RunTest or Pairs: how to build each candidate, and the options to compare them with.
type Process ¶
type Process struct {
// Index counts the processes of a run from zero.
Index int
// Seed is this process's seed. The heap perturbation Run applies before
// the suite and Rand are derived from it, so a process can be repeated by
// running the suite again with the same seed.
Seed uint64
// contains filtered or unexported fields
}
Process is what a child knows about itself. The suite receives it and records its results through it.
func (*Process) Rand ¶
Rand returns a generator seeded from this process's seed, independent of the heap perturbation, for shuffling the order in which many fixtures are built; see rtcompare.DPRNG.Shuffle. For two fixtures, alternate by Index instead, which balances exactly where a random draw over a few processes rarely does.
type Results ¶
type Results struct {
// Child is true in a child process, where the other fields are empty. The
// caller should return without reporting anything.
Child bool
// Processes is how many processes ran, and Seeds the seed each one got.
Processes int
Seeds []uint64
// Comparisons holds every named comparison in the order it was first
// recorded.
Comparisons []Comparison
// Precise reports whether the run reached the number of processes its
// first stage called for; false means that number exceeded MaxProcesses,
// so the run stopped there with at least one interval wider than
// requested.
Precise bool
// Parallel is the number of processes that ran at the same time, 1 for a
// serial run, so that a report can say which regime it measured. Results
// from the two regimes are not interchangeable; see Options.Parallel.
Parallel int
// ChildGOMAXPROCS is the GOMAXPROCS the children's environment set, zero
// when it set none and the children used the Go runtime's default.
ChildGOMAXPROCS int
}
Results is what Run found.
func Run ¶
Run runs suite in several child processes and pools what they record.
Parameters: opt sets how many processes to run and when to stop, see Options; suite is the measurement one process performs. It receives a Process with that process's seed, and records each comparison's report under a name with Process.Record.
Run behaves differently depending on where it is called. In the parent, the program as started by the user, it never calls suite: it starts the current binary again as a child, with the same arguments unless Options.Args says otherwise, waits for it, and repeats: one process at a time, or in waves of Options.Parallel processes at a time (see the package documentation for the two regimes). Process i always gets index i and the same seed, whichever child finishes first, and results are pooled in index order, so a run is repeatable from its seed in either regime. The first MinProcesses are the first stage: from their scatter, Run decides once how many processes every comparison's interval needs to meet the precision in Options, rounded up to a whole Rotation or wave and at most MaxProcesses, and then runs exactly that many; see Options.AbsPrecision. If a child of a wave fails, its siblings are killed and the error of the lowest failing index is returned. It returns the pooled results. In a child, Run perturbs the heap from the process's seed (see rtcompare.PerturbHeap), calls suite once, hands its records to the parent through a file, and returns Results with Child set; the caller should then return without doing anything else, since the parent does the reporting. Main and RunTest take care of that. The children find out which they are from environment variables that Run sets for them.
Use it for any comparison whose data is larger than the caches or full of pointers, where a single process's interval is known to be several times too narrow; see rtcompare.Combine for the numbers. It costs a process start and the whole suite per process, and out of cache that has taken from 13 to more than 40 processes; see DefaultMaxProcesses and Options.Parallel. Keep the machine awake while it runs: each Report notices a suspension, but the time is lost.
An error is returned for invalid options, if a child cannot be started, exits with a failure, returns an error from suite or records nothing, and if pooling fails. In a child, the error is suite's.
func RunTest ¶
RunTest runs the pairs in several processes from within a test and returns the pooled results.
Parameters: t is the calling test; opt configures the processes, see Options; pairs are the comparisons, see Pair.
It does for a test what Main does for a program. Unless opt.Args is set, the children run only the calling test, since otherwise every test of the package would run in every child. In a child, RunTest runs the pairs once and skips the rest of the test, which the parent reports; in the parent, an error fails the test. The children re-run the test function up to the call, so build the candidates' data inside the pairs' builders rather than before.
func TestLookup(t *testing.T) {
res := multiproc.RunTest(t, multiproc.Options{}, multiproc.Pair{Name: "lookup", A: buildA, B: buildB})
if p := res.Comparisons[0].Pooled; p.Resolved { ... }
}
Example ¶
RunTest does the same inside a test and returns the pooled results for assertions; the children run only the calling test.
package main
import (
"testing"
"github.com/TomTonic/rtcompare"
"github.com/TomTonic/rtcompare/multiproc"
)
// tree stands for a data structure large enough that one process is one
// observation, and lookupIn for the candidate that measures it.
type tree struct{ keys []uint64 }
func buildTree() *tree { return &tree{keys: make([]uint64, 1<<20)} }
func lookupIn(t *tree) rtcompare.Candidate {
return rtcompare.Candidate{Name: "lookup", Batch: func(n uint64) {
for i := range n {
_ = t.keys[i%uint64(len(t.keys))]
}
}}
}
func main() {
var t *testing.T // the test's own t
res := multiproc.RunTest(t, multiproc.Options{Parallel: 4}, multiproc.Pair{
Name: "lookup",
A: func() rtcompare.Candidate { return lookupIn(buildTree()) },
B: func() rtcompare.Candidate { return lookupIn(buildTree()) },
})
if p := res.Comparisons[0].Pooled; !p.Resolved {
t.Log("no difference established:", p)
}
}
Output:
func RunTestSuite ¶ added in v0.8.0
RunTestSuite is RunTest for a suite instead of pairs, such as the workload package's Suite or several suites combined with Suites.
Parameters: t is the calling test; opt configures the processes, see Options; suite is the measurement one process performs, see Run.
It behaves like RunTest in every other respect.
func TestSets(t *testing.T) {
res := multiproc.RunTestSuite(t, multiproc.Options{},
workload.Suite("map vs Set3", 100_000, goMap, set3Set, workload.Options{}))
...
}
Source Files