Throughput–memory frontier¶

In 2001 Seward set the inverse BWT's space–time trade-off for one block: a smaller table (indexF, the byte recovered from the first column) costs more work a step than the merged one (mergedTL, the byte kept beside each link, the layout mibz2 uses). The question here is whether that trade-off still holds when several blocks decode at once and their tables share one L3 cache. A table that is slower for one block might be faster for the machine, if its smaller footprint keeps more blocks resident.

Where it stands: the mechanism is measured, and so is a first shift. On the i9 and the Wikidata corpus, the full decoder with cooperative teams dominates every worker count measured (4 to 20) on both throughput and peak RSS (series 3). Whether it also does at 1 to 3 workers, the low-memory end, is not yet measured.

The two charts¶

Both are drawn from frontier.json, the page's measured observations. Point at a mark, or Tab to it, for its values. Every value is also in the tables below.

1. Throughput against memory: each configuration's measured throughput and peak RSS, with the ones nothing beats on both ringed and joined by their step. This is the frontier. It draws series 3, the only one with measured RSS: the workers (arm mibz2), fixed teams of 2 and of 3, and the policy (v0.2.0's default). Where one plan ran at several thread counts, its marks are noise around one configuration. No worker counts below 4 were measured, so it is not yet the whole frontier.
2. Throughput against concurrent full blocks, as live table memory (blocks live × 3.6 MB, computed): where a smaller table would overtake the 32-bit one, if it does, as more blocks are live. No compact table exists yet, so it shows today's table and the knee measured in the workstation journal §9: series 1's worker counts and series 3's workers and teams, a panel each, since they are different workloads. Series 2, the inversion, is a different level: it has its own small panel and axes, never the decoder's.

The rules the charts keep:

• One machine and one workload a chart. An L3 effect on the i9 may appear at another concurrency, or not at all, on another CPU.
• Two kinds of memory, never mixed: the live tables' bytes (computed: live full blocks × 900,000 rows × 4 bytes for today's table) and the process's peak RSS (measured). Peak RSS also counts the scanner's slots, the output and every worker's buffers: at 4 threads on CI it is about 74 MB, against 14.4 MB of tables.
• Two levels, never mixed: the full decoder (a file to verified output) and the research harness's inversion (MTF, build and walk). The headline is the full decoder; the inversion shows the mechanism.
• Releases are the record. Selected pull requests and research runs appear as labelled overlays.
• Only measurements. Footprints of designs that don't exist yet, and models, stay in the text.
• The frontier is judged against the best alternative, not a convenient one. A compact table at four blocks beating today's at four blocks is a step; the frontier moves only if it beats today's best configuration at any block count.

What is measured so far¶

Three series exist, on the i9 (Intel i9-10900K, 10 cores, 20 MB L3). They are different runs at different levels, so they are separate series, never one line.

1. The full decoder, today's table, by worker count (unpinned; the bench corpus's bytes recompressed with lbzip2 -9; workstation journal §9):

Past 4 workers, more tables than the L3 holds make each block's work dearer: from 4 to 10 workers the CPU-seconds rise 3.5× and throughput falls. Peak RSS was not recorded in this run.

2. The inversion, production against cooperative teams (every thread pinned; the research harness's MTF, build and walk; coop journal §17.4):

A cooperative team shares one block's table among k cores, so N teams keep N tables live on N × k cores.

• y3x3 runs faster than p4 from fewer live tables. p4 is production's best worker count on this machine in every scaling run (series 1).
• So at this level, in throughput against live table bytes, sharing a table already does better than every production configuration measured.
• It is not yet a frontier result:
  • it is the inversion, not the decoder;
  • it is pinned;
  • its memory axis is computed table bytes, not peak RSS;
  • it uses more cores (CPU-seconds are not yet measured).

3. The full decoder, workers against cooperative teams, with measured memory (unpinned; the bench corpus, 209.7 MB decoded; 20 interleaved rounds; the decoder journal and its raw files). One point per distinct plan: where two arms ran the same plan (the policy at 8, 10 and 20 threads is 4 teams of 2 on this machine; 2 teams of 3 ran at both 6 and 8), the table gives the range of their medians, which is noise.

Peak RSS is measured (the median run's, in decimal MB). Live tables are computed. The nondominated column compares medians on throughput (higher) and peak RSS (lower) within this series.

What it shows, and what it doesn't:

• Every worker count measured is dominated. p4, the decoder's best worker count here, is beaten on both axes by 3 teams of 2 (the policy at 6 threads: 1.166× with its lower bound 1.123, at 64 MB against 76) and by 3 teams of 3.
• The nondominated set is all teams: 1×3, 2×3, 3×3 and 4×2. Measured by medians, 4×2 stays on the set by its best repeat. Its throughput is tied with 3×3's within noise (their intervals overlap almost entirely), at 13 MB more RSS and about 6% more CPU. 3×3 is a lead for refining the policy, not yet a result.
• Not a whole-frontier result. No worker counts below 4 were measured in this run. At 1 to 3 workers, today's decoder may still own the low-memory end: series 1 has 2 workers at 707 MB/s, but without RSS. Filling that in needs the same A/B at 1, 2 and 3 threads.
• One machine, one workload, one level (the full decoder). Threads above 10 share physical cores with SMT siblings.

What fills it in¶

• The low-memory end on the i9: the same A/B at 1, 2 and 3 threads, where today's workers and the smallest teams meet.
• The CI benchmark's release runs measure wall time, CPU and peak RSS at 1, 2 and 4 threads on every release, on GitHub's 4-vCPU runners. That is below the i9's knee, so it can't show a crossover, but it keeps a frontier for every release.
• Compact tables join when one exists: a 24-bit link-only table (#79) first, then others if the census and the walk's costs justify them. They are judged against the cooperative decoder now, not against the workers.

The research behind this page: Seward's trade-off revisited, verbatim (the researcher, the coordinator), and the literature study.