pixie::experimental Namespace Reference

Classes
class	ByteSlotOrder
	Byte-index control for the split-bit slot-order experiment. More...
struct	ExcessByteLut
class	GroupedSlotOrder256
	Experimental ordering of 256 pointer slots in one 16x16 node. More...
class	PermutedBitBlock
	Bounded owning experiment, independent of sequence split/merge policy. More...
class	PowerOfTwoPermutableSequence
	Experimental owning packed sequence with power-of-two leaf capacity. More...
class	PowerOfTwoValueBlock
	Packed unsigned leaf with a power-of-two element capacity. More...
class	RmMBTree
	Cache-aligned btree implementation of the range min-max index. More...
struct	SelectByteLut
class	SlotOrder16
	Experimental logical ordering of sixteen stable physical slots. More...
class	SplitSlotOrder
	Experimental 32/64-slot order with separate low nibbles and high bits. More...

Functions
template<bool Zero>
std::optional< detail::compressed::PackedPrefixLocation >	packed_prefix_search_multishift (const std::uint64_t *record, std::uint64_t target, std::size_t valid_bits)
	Experimental AVX-512 VBMI multishift search of packed rank prefixes.

Variables
constexpr ExcessByteLut	kExcessByteLut
constexpr SelectByteLut	kSelectByteLut
constexpr auto	kPrefixGroupBytes

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

Function Documentation

packed_prefix_search_multishift()

template<bool Zero>

std::optional< detail::compressed::PackedPrefixLocation > pixie::experimental::packed_prefix_search_multishift ( const std::uint64_t * record, std::uint64_t target, std::size_t valid_bits )

inline

Experimental AVX-512 VBMI multishift search of packed rank prefixes.

Uses the production record layout and preconditions: a nonhomogeneous superblock, a valid one-based local target, and its valid bit count. Returns no result on unsupported targets. This kernel is not selected by RankSelectSupportCompressed.

Variable Documentation

kPrefixGroupBytes

auto pixie::experimental::kPrefixGroupBytes

inlineconstexpr

Initial value:

= [] {
  std::array<std::uint8_t, 64> indexes{};
  for (std::size_t i = 0; i < 64; ++i) {
    indexes[i] = (8 + (i / 8) * 7 + i % 8) & 63;
  }
  return indexes;
}()