|
Everett
|
The useful comparison is whole-search throughput against growth in complete file size. Elias–Fano can be much smaller than a direct directory while that difference is still a small fraction of the encoded table. I measure both.
The space-versus-throughput plot shows every workload median in the primary comparisons. The PNG copy and plot provenance are retained too.
Absolute offsets improve the whole lookup on this host. Packed offsets keep most of the direct directory's gain with less space; denser sampling inside Elias–Fano gives no useful aggregate whole-query gain in these fixtures.
| Offset choice | Byte throughput | Byte whole-file growth | Bit throughput | Bit whole-file growth |
|---|---|---|---|---|
| Existing Elias–Fano | \(1.000\times\) | Baseline | \(1.000\times\) | Baseline |
| EF with 32-one subentries | \(1.002\times\) | 0.003–0.067% | \(0.997\times\) | 0.003–0.071% |
| Packed absolute | \(1.094\times\) | 0.016–0.237% | \(1.041\times\) | 0.016–0.245% |
| Direct 32-bit | \(1.110\times\) | 0.079–0.473% | \(1.055\times\) | 0.064–0.529% |
| Direct 64-bit | \(1.105\times\) | 0.246–1.214% | \(1.047\times\) | 0.229–1.309% |
Throughput is the geometric mean of 48 ratios of median query times per profile. Space is the range over the corresponding fixtures. Each candidate uses its own interleaved, contemporaneous baseline; the first phase tests sub32/direct32, and the second tests packed/direct64. Small differences between candidates from different phases should not be treated as a ranking.
All 96 direct32, 96 packed and 96 direct64 case medians beat their baseline. Their process-median ranges are disjoint in the candidate's favor in 89, 78 and 86 cases respectively. Sub32 has only one disjoint favorable case and four disjoint unfavorable cases; the rest overlap. These observations describe repeatability across three processes, not statistical significance guarantees.
For one concrete example, byte storage with 131,072 base records and structured 16-byte keys occupies 6,762,352 bytes across its complete files with the existing EF directory. Direct32 occupies 6,794,352 bytes: 32,000 extra bytes, or 0.473%. The offset arrays themselves grow from 18,160 to 50,160 bytes. Reporting only their \(2.76\times\) increase would obscure the useful tradeoff.
The primary summary and alternative summary retain every query kind, key shape, process range, absolute time and complete-file denominator. The separate geometric-size panel increases both record count and query working set; its results should be consulted before choosing a cutoff.
The separate size panel checks six geometric sizes, with two fresh processes per variant and three trials of both random and sorted order of the same hit set. It increases the query count with \(N\) up to 65,536. These are two distinct workloads: byte files with structured 16-byte keys, and bit files with hash-like 128-byte keys. Their size columns do not measure byte-versus-bit compression for identical input.
| Base records | Byte fixture bytes | Bit fixture bytes | Query count | Distinct query keys |
|---|---|---|---|---|
| 1,024 | 57,664 | 246,248 | 1,024 | 660 |
| 8,192 | 427,096 | 1,926,400 | 8,192 | 5,179 |
| 32,768 | 1,694,672 | 7,679,128 | 32,768 | 20,754 |
| 131,072 | 6,762,352 | 30,651,952 | 65,536 | 51,598 |
| 524,288 | 27,033,696 | 122,404,168 | 65,536 | 61,621 |
| 2,097,152 | 108,116,624 | 488,848,920 | 65,536 | 64,544 |
At the largest sizes, query records contain 3,145,728 logical key/value bytes for the byte fixture and 10,485,760 for the bit fixture. Each query vector has 3,670,016 bytes of C++ query objects; its ordering vector occupies another 524,288 bytes. Logical contents and object storage are reported separately: inline string contents may overlap object storage, and allocator overhead and spare string capacity are not counted. File size alone does not establish a cache boundary. These are warmed resident lookups with a growing query set, without hardware cache-miss counters or cold-page measurements.
The complete-file growth at 2,097,152 records remains small:
| Offset choice | Byte whole-file growth | Bit whole-file growth |
|---|---|---|
| EF with 32-one subentries | 0.0118% | 0.0026% |
| Packed absolute | 0.3342% | 0.0749% |
| Direct 32-bit | 0.4776% | 0.0797% |
| Direct 64-bit | 1.2180% | 0.2435% |
The initial 524K/2M timing collection is diagnostic, not a settled performance result. All queries and file accounting pass, but the raw wall-clock times show large transient variation despite an exclusive lane for owned build/test jobs. For example, the two 524K byte baseline random process medians are about 8.09 and 3.86 microseconds; 2M bit direct32 sorted medians are about 15.54 and 7.89 microseconds. Twenty of the eighty large-size process/access groups have a largest trial more than 20% above their smallest trial. Such variation can create apparent large gains or regressions. I retain every observation and make no cutoff recommendation from those large-size ratios. The data does not identify the source of the variation.
The size summary includes all six sizes and both access orders, with process-median ranges. The timing-quality table marks the entire initial large-size collection as diagnostic, rather than selectively removing slow trials. The stable smaller-size panel and primary matrix are separate collections. Raw size queries and complete-file/query-buffer accounting are retained for reanalysis. I made one separate follow-up with scheduling diagnostics; it does not overwrite or selectively filter this collection.
I repeated three sizes in a separate collection: 131,072 as a control, then 524,288 and 2,097,152. Each of the five variants has three fresh processes and three trials per access order: 90 processes and 540 retained observations. The benchmark requests and verifies USER_INITIATED QoS on its own Apple thread and records thread CPU time alongside wall time for each complete trial. It changes no global scheduling setting and adds no timer inside the lookup loop. The smaller baseline-only pilot, original collection and this follow-up remain separate. The improved repeatability does not establish that QoS alone caused the difference.
Each cell below is whole-query throughput / extra complete-file space for random hits. All file sizes, encoded-stream fingerprints and query buffers match the original size panel exactly. The byte and bit rows still use different key workloads.
| Workload | Base records | EF sub32 | Packed | Direct32 | Direct64 |
|---|---|---|---|---|---|
| Byte / structured 16 | 131,072 | 1.016× / +0.0151% | 1.101× / +0.2366% | 1.131× / +0.4732% | 1.124× / +1.2140% |
| Byte / structured 16 | 524,288 | 1.006× / +0.0125% | 1.111× / +0.2868% | 1.132× / +0.4767% | 1.131× / +1.2172% |
| Byte / structured 16 | 2,097,152 | 1.013× / +0.0118% | 1.089× / +0.3342% | 1.108× / +0.4776% | 1.097× / +1.2180% |
| Bit / hash 128 | 131,072 | 1.008× / +0.0033% | 1.041× / +0.0531% | 1.079× / +0.0785% | 1.055× / +0.2419% |
| Bit / hash 128 | 524,288 | 1.005× / +0.0028% | 1.042× / +0.0643% | 1.053× / +0.0794% | 1.041× / +0.2429% |
| Bit / hash 128 | 2,097,152 | 0.964× / +0.0026% | 1.004× / +0.0749% | 1.019× / +0.0797% | 1.029× / +0.2435% |
For byte keys, all 18 packed/direct32/direct64 comparisons across both random and sorted access have process-median ranges disjoint in the candidate's favor. At 2M, direct32 gives 10.8% more random-hit throughput for 0.4776% extra complete-file space; packed gives 8.9% for 0.3342%. Sorted-hit speedups there are 1.115× and 1.089× respectively.
The largest bit fixture has a less decisive outcome. Packed, direct32 and direct64 give random-hit median ratios of 1.004×, 1.019× and 1.029×, with overlapping process ranges. Sorted ratios are 1.002×, 1.036× and 1.047×, also with overlapping ranges. Those small differences do not establish a winner. Sub32 is 0.964× random and 0.966× sorted there; the sorted process ranges are disjoint in the slower direction. Denser EF sampling still does not support a broad whole-search improvement.
| Base records | Largest trial max/min within a process | Largest process-median max/min | Median CPU/wall | Minimum CPU/wall |
|---|---|---|---|---|
| 131,072 | 1.083 | 1.087 | 99.46% | 99.02% |
| 524,288 | 1.096 | 1.074 | 99.49% | 99.24% |
| 2,097,152 | 1.304 | 1.091 | 99.71% | 92.02% |
The CPU/wall median is taken over process/access medians; the minimum is over individual trials. Variation is still visible. The worst wall-time excursion is a 2M byte/sub32 sorted process; its CPU-time trial ratio is also 1.203×. All trials remain in the analysis. CPU/wall time can expose descheduling but does not identify core placement, clock frequency or cache misses. Process ranges describe repeatability, not confidence intervals. I do not derive an automatic size cutoff from this one host and these two workloads.
The scheduled summary retains both access orders and all absolute query times. Its CPU/wall diagnostics, raw trials, complete-file accounting and source/validation provenance are retained separately from the original six-size panel.
All measurements use an Apple M2 Max and Apple Clang 21.0.0, with C++20, -O3 -g -DNDEBUG -Wall -Wextra -Werror. The production header baseline is cb2b029a657d2bbcd7135265cb3060b2b11cd961. Candidate overlays change the offset codec only. The source and binary hashes are retained alongside the results. The runner and reproduction instructions describe the variants. The measured count decoder is stateless; these profiles do not include the subsequent reservoir reader change.
Each fixture maps real KV02 or KV03 files and IX03 fractional indexes. It has four main native runs of \(N\), \(N/4\), \(N/16\) and \(N/64\) records, a terminal secondary of \(N/128\) records, and enough empty-native routing catalogs to bound the head by \(K=15\). Records have 16- or 128-byte keys and 32-byte values. Keys are either a long shared prefix followed by an ordered integer or a deterministic hash-like prefix with a unique integer suffix. Newer runs repeat subsets of the base keys. Replacement reads use the existing first_value implementation, including query encoding, exact cascade routing, record parsing, comparisons, value decoding, allocation and destruction. Every generation stores the same value for a given key. This catches wrong-key selection, but does not independently test choosing the newest of unequal replacement values. A separate untimed mapped-query check adds unequal newer values and tombstones, described below.
The primary matrix uses 8,192 and 131,072 base records, both key shapes and lengths, both byte/bit profiles, and hit/miss/mixed queries. The independent order uses a precomputed pseudorandom query list. In the dependent order, the previous returned value chooses the next query. Queries are precomputed before timing; query encoding remains inside each lookup. The fixture checks exact returned strings against the logical generator before timing, then checks every timed aggregate against an independent oracle using the same recurrence.
Each primary comparison uses three fresh processes per variant and fixture, with three trials of 2,048 lookups per query/access combination. I first take the median within each process, then the median across process medians. The process-median ranges show repeatability; they are not confidence intervals. Warm queries reuse 1,024 query keys. They do not establish cold-file or large-working-set behavior; the separate size panel increases the query set.
The denominator for space is the sum of unique complete serialized .kv and .index file lengths, including headers, descriptors and alignment. It excludes filesystem block allocation, directory entries and fixture memory. Offset payload and auxiliary bytes are also reported separately. All variants have identical record-stream lengths and fingerprints and return identical logical values. The direct representations replace Elias–Fano; sub32 changes only the select directory. No faster in-word select result is presented as a replacement-representation result.
I sampled four baseline query loops with Instruments Time Profiler at a 1-ms sampling interval. The profiler launched only the benchmark process. Each fixture repeats 2,048 mixed dependent queries for ten seconds; the retained samples come from the main thread's final eight seconds of query execution. The final sample at the frozen lookup call site excludes later teardown. Setup, mapped-file construction and the initial oracle pass finish before this interval. These profiled executions are separate from the throughput measurements.
| Baseline workload, \(N=131,072\) | EF navigation | Rank projection | Frame decoding | Key comparison | Other |
|---|---|---|---|---|---|
| Byte, structured 16-byte keys | 9.47% | 2.40% | 19.30% | 22.75% | 46.08% |
| Byte, hash-like 128-byte keys | 8.15% | 2.06% | 24.11% | 18.89% | 46.80% |
| Bit, structured 16-byte keys | 4.65% | 0.97% | 66.59% | 10.84% | 16.95% |
| Bit, hash-like 128-byte keys | 4.63% | 1.05% | 68.59% | 9.50% | 16.24% |
These are exclusive sampled categories, rounded independently. EF navigation includes low-bit decoding and validation, not just selecting a high one. Framing includes parsing skipped records, not just the final compared window. Other includes routing/context management, query encoding, value materialization, allocation, the small harness cost and unresolved linker-folded frames. The sanitized evidence retains resolved value/query categories separately; tiny values there are not precise measurements of all value-copy costs.
Inclusive categories in the raw summaries can overlap. For example, a bit frame parser calls a comparison helper; its inclusive frame-decoding fraction is about 70–72%, while the exclusive frame fraction above is about 67–69%. I do not add overlapping inclusive percentages. Sampling uncertainty, inlining and symbol folding limit finer attribution; no timer is added to each select.
A separately compiled counter audit performs the primary 1,024-query lists without using its elapsed times as performance data. For these large mixed/dependent cases, byte queries average 11.29 offset selections, 11.55 rank calls and about 102 ordinary frame parses. Bit queries average about 12.4 selections, the same rank count, about 46 ordinary borrowed-frame parses and 56 sort-owned native frame parses. Both perform about 0.59 value materializations per query; the dependent recurrence changes the mix from the original half-hit list. Those counts help explain why improvements to one small selector do not translate directly into its microbenchmark speedup.
The retained space rows include native and index preparation times. They cover encoding, directory construction, record-stream fingerprinting, checksums, temporary file writes and metadata-only mapping. They exclude durability barriers, and are not isolated offset-builder measurements. The select-only report separately measures offset construction on extracted real directories.
The files are resident and reused. These measurements do not cover storage faults, durable publication, merge throughput, range initialization, arbitrary arrow composition, x86 or GPU selection. The primary and size panels record their different process counts explicitly. Throughput speedup is \(t_{\mathrm{baseline}}/t_{\mathrm{candidate}}\); for example, \(1.10\times\) is 10% greater throughput and about 9.1% less elapsed time.
A production per-file choice needs a tagged offset directory, independent of the sort registry. Its common interface needs size, universe, select and a forward cursor. Native and each borrowed stream may choose independently; unit conversion and fixed-value stride restoration stay in the caller. Opening checks the tag and section shape without scanning every offset; explicit recovery checks order, bounds and endpoints. direct32 eligibility concerns the residual universe in the stream's byte or bit units, not total file length. Wider universes need another representation. The experimental overlays are evidence for that choice, not a production wire-format proposal. Each measured binary specializes all streams to one representation. Runtime tag dispatch in a mixed-representation reader has not been measured here. Metadata opening/shape checks finish before lookup timing and are included only in the broader preparation figures.
The five selectors pass 213,460 sequential/random oracle selections each under ASan/UBSan, including empty/repeated inputs, 32/256-one boundaries, clustered offsets and sparse exceptions. Each variant also passes 16,384 mapped changed-value, tombstone and neighboring-miss checks under ASan/UBSan, across both byte/bit profiles and short structured/long hash-like keys. This separate untimed check verifies newest-value selection without changing the measured fixtures. Its source and binary hashes are retained. Complete query fixtures check exact values, then timed checksums. The analysis checks matching record-stream fingerprints, result checksums and space across processes. Raw observations, source/header hashes, binary hashes, operation counts and sanitized profiler samples are in the retained artifact manifest.
1.9.8