Parallel pipeline measurements

Historical measurements; see Profiling the compiler for the profiling guide.

Parallel pipelines

scripts/bench_par_pipelines.py compares a serial pipeline, the equivalent pool.map/reduce_tree calls, and the same pipeline after .par(&pool) (B75 stage 4). Cases are map+collect, filter+count, sum over i64 lists, i64 ranges and f64 lists, and reduce. The cheap callback is x * 3 + 1; the expensive one runs 100 rounds of a linear congruential step. The pool column for filter+count maps the predicate to 0/1 and sums serially; for the sums and reduce it is reduce_tree over pool.map. Run:

taskset -c 0,2,4,6,8,10,12,14 python3 -B scripts/bench_par_pipelines.py target/release/plenty

The taskset mask keeps the eight-worker pool on the eight physical cores of this laptop; more than ten busy threads drop its clock to about 1.1 GHz. Each program builds its input outside the timed region, times one terminal with the monotonic clock per repetition, discards the first repetition and prints a checksum; every variant of a case must agree. The script interleaves the variants over three rounds of four timed repetitions and reports medians in milliseconds. The machine was not otherwise idle (load average 2 to 5 from other work), so differences under about 10% are noise.

Screening. Before timing, --dump asm of the chunk workers showed the same per-item calls as the serial loop (plenty_list_scalar_get and, when collecting, plenty_collection for the append) for map, filter and count. The signed-sum worker folded into a seven-field tuple and called signed_step per item, with two memmove calls for the tuple state; a serial microbenchmark of that fold over ten million items took 400 ms against 20 ms for the same arithmetic in local variables and 6 ms for sum. The worker now runs the chunk in a loop over locals, tracking the exact running total as a wrapping i64 plus a wrap count. Combining collected chunks now appends each chunk’s storage with extend instead of moving items one at a time.

The first round of measurements found two losses: splitting a list moved each item on the calling thread with a list append (about 37 ns per item), and .par reduce collected every item, then ran reduce_tree, which submitted one job per pair. Three changes followed:

• A list source was split by an internal list operation that copied each chunk’s contiguous rows in one bulk copy. Issue #455 replaced this with borrowed chunks, described in this report.
• pool.reduce_tree gives one job an aligned run of adjacent inputs, a power of two chosen so there is about one run per worker, and the job reduces it serially through the same rounds. The remaining run results are combined by pair jobs. Because each round maps index i to i / 2, an aligned run is exactly a subtree of the fixed tree, so the grouping is unchanged; a test compares it with a serial level-by-level evaluation for lengths 0 to 70 and larger odd and even lengths, with 1, 2, 3 and 8 workers.
• .par reduce now groups like sum: each chunk reduces its items left to right in its worker, and the chunk results are reduced in input order. No list of all items is collected. The worker’s loop makes the same direct calls per item as the serial pipeline (plenty_list_scalar_get, the callback and f).

Borrowed chunks (issue #455). A list chunk is now a span of the source’s rows: the job receives the first row’s address, the row size and the item count, and reads (or, for owned affine items, takes) items in place. The calling thread copies nothing; it allocates one small list of chunk bounds. This relies on every terminal draining its jobs before it returns. --dump asm of the filter+count worker showed the per-item loop with no calls (an imul and a load per row, then the inlined predicate); before, it called plenty_list_scalar_get per item, and the split called the runtime copy.

The first measurement after that change regressed filter+count and the sums at 100,000 items (0.46 to 1.24 times serial): the owned source was now dropped on the calling thread, and dropping a list walked and cleared every row even when the items own nothing (about 3.4 ns per row). A list of items that own no heap storage now frees its buffer without the walk. That also makes the serial pipelines, which consume the list, faster.

Results on an AMD Ryzen 7 7840HS, eight workers, with borrowed chunks and the drop change (load average 5 to 6 from other work):

Before, at main 9e3970d5 with the bulk-copy split, measured just before in the same conditions (load average 4 to 6):

Findings.

• With cheap callbacks over ten million list items, .par now takes 0.38 to 0.58 times the serial time (1.7 to 1.9 before). At 100,000 items it takes 0.08 to 0.16 times serial for filter+count, the sums and reduce, and 0.64 for map+collect, which still appends each result.
• With expensive callbacks, .par runs at 0.13 to 0.26 times the serial time from 100,000 items, as before.
• At 1,000 cheap items the job overhead still exceeds the work (1.8 to 2.3 times serial). A range source over cheap items is unchanged.
• reduce keeps per-chunk grouping; pool.reduce_tree keeps aligned runs.

Remaining work. Early stop for parallel any/all; user-facing scoped pool jobs (a deferred B22 extension) could reuse the drain-before-return guarantee.