pixie::experimental Namespace Reference

Classes
struct	ExcessByteLut
class	RmMBTree
	Cache-aligned btree implementation of the range min-max index. More...

Variables
constexpr ExcessByteLut	kExcessByteLut

Detailed Description

Benchmark note:

This header keeps experimental and historical excess_min/excess_positions variants for comparison benchmarks. Production excess code lives in pixie/bits.h; a benchmark win here should be treated as a candidate to port, not evidence that callers use this variant already.

excess_min_128 method comparison, 2026-06-17: taskset -c 0 ./build/release/excess_positions_benchmarks –benchmark_filter='^(BM_ExcessMin128/(left:0/right:(128|16|32)|left:1/right:17|left:3/right:35|left:5/right:37|left:56/right:72|left:60/right:68|left:63/right:64|left:17/right:17)|BM_ExcessMin128_(ByteLUT|NibbleLUT|DeinterleavedSSE|Lane64SSE|Split64SSE)/(left:0/right:(128|16|32)|left:1/right:17|left:3/right:35|left:5/right:37|left:56/right:72|left:60/right:68|left:63/right:64|left:17/right:17)|BM_ExcessMin128_RandomRange$|BM_ExcessMin128_(ByteLUT|NibbleLUT|DeinterleavedSSE|Lane64SSE|Split64SSE)_RandomRange$)' –benchmark_min_time=0.5s –benchmark_repetitions=5 –benchmark_report_aggregates_only=true

Tables report median CPU time across 5 repetitions. Each numeric cell is nanoseconds per excess_min_128 call. Columns named A-B are the inclusive prefix-offset arguments [left, right]; Random is the benchmark's reproducible mixed-range workload.

excess_min_128 CPU time:

method	0-128	0-16	0-32	1-17	3-35	5-37
Production	5.17	3.54	5.88	7.97	7.58	8.17
ByteLUT	17.82	2.97	5.04	11.51	11.96	10.85
NibbleLUT	40.00	4.78	8.14	8.59	10.72	10.81
DeinterleavedSSE	5.44	6.08	6.24	8.28	7.84	8.90
Lane64SSE	6.53	7.26	7.27	10.25	10.26	10.30
Split64SSE	9.67	6.22	6.30	9.63	9.52	9.48

method	56-72	60-68	63-64	17-17	Random
Production	4.01	5.89	2.12	1.55	10.07
ByteLUT	3.60	8.74	2.34	1.55	13.14
NibbleLUT	5.27	3.52	2.33	1.55	17.48
DeinterleavedSSE	6.30	6.38	2.07	1.55	9.10
Lane64SSE	4.27	7.23	3.84	2.25	11.36
Split64SSE	9.86	9.75	3.17	1.55	11.02

Diagnostic run, 2026-05-30: taskset -c 0 build/benchmarks-profile_local/excess_positions_benchmarks –benchmark_filter='BM_ExcessPositions512' –benchmark_repetitions=3 –benchmark_perf_counters=CYCLES,INSTRUCTIONS,CACHE-MISSES –benchmark_counters_tabular=true

Counter table for excess_positions_512 with a random target in [-128, 128]. CPU is nanoseconds per call. cycles, instructions, and cache misses are hardware-counter events per call.

method	CPU (ns)	cycles	instructions	cache misses
Production	11.4	50.8	188.9	0.001
LUTAVX512	12.8	56.8	195.5	0.002
BranchingLUT	16.7	73.4	261.4	0.003
ExpandAVX512	21.0	93.6	266.6	0.003
Expand8	24.6	109.9	449.7	0.002
Expand	46.8	207.7	784.8	0.006
ByteLUT	49.7	221.4	754.5	0.008
Scalar	374.2	1656.0	7716.6	0.041

CPU time for excess_positions_512 fixed-target rows. Numeric cells are nanoseconds per call. Columns are target excess values.

method	-64	-8	0	8	64
Production	11.6	18.0	18.3	19.1	12.3
LUTAVX512	13.4	17.9	19.2	21.3	13.2
BranchingLUT	19.1	28.9	28.7	28.3	16.8
ExpandAVX512	22.7	36.6	36.3	36.2	22.5
Expand8	17.6	52.7	47.5	46.9	17.7
Expand	51.0	85.9	86.1	85.5	53.9
ByteLUT	34.7	77.4	76.9	79.0	34.3
Scalar	367.2	433.5	466.3	428.1	364.6