You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
research type_info* -> index via subtraction and division #57
The mapping asked about here (subtraction and division, prototypes A and B) works unconditionally, and its dispatch code is as good as expected: one fused load, 0.3-1.1 ns per call faster than fast_perfect_hash on GCC and Clang. It fails on memory: 5x-149x more than fast_perfect_hash with a single module, and a multi-terabyte table once a program dlopens a module that registers classes of its own.
Three other schemes were tried. None beats fast_perfect_hash as the general v-table lookup, which stays the default. But the exercise found that its randomized search is expensive on realistic type id distributions (up to 175 ms for 1000 classes), and that it gives up and aborts on large ones (all four 4000-class samples). The three schemes are alternatives for that case, and #103 added them as policies:
Prototype
Policy
Trade-off
C, minimal-cover pext
minimal_cover_hash
dispatches as fast as the default; needs BMI2
D, hash and displace
minimal_perfect_hash
one slot per type id, whatever the addresses; a second dependent load, +1.3 to +2.5 ns per call
E, two multiply-shifts
two_level_hash
D with a shift instead of a reduce: about 1 ns back on GCC, none on Clang; 1.0-2.0 slots per type id
The harness was also run on MSVC. It agrees that D costs more per call. It also found that MSVC does not inline fetching an object's type id: doing it by hand saves about half a nanosecond per dispatch, more than any difference between two of the maps.
Activity
Add minimal_perfect_hash, two_level_hash and minimal_cover_hash polic…
Add minimal_perfect_hash, two_level_hash and minimal_cover_hash polic…
Add minimal_perfect_hash, two_level_hash and minimal_cover_hash polic…
Add minimal_perfect_hash, two_level_hash and minimal_cover_hash polic…
jll63 commentedon Oct 12, 2026
(Written by Claude Code, on behalf of @jll63.)
The research is done, and its results shipped in #103. Closing.
The full note, the harness and the archived samples are in the fork, under the tag
archive/type-info-index:TYPE_ID_INDEX.mdandresearch/type_id_index/.Verdict
The mapping asked about here (subtraction and division, prototypes A and B) works unconditionally, and its dispatch code is as good as expected: one fused load, 0.3-1.1 ns per call faster than
fast_perfect_hashon GCC and Clang. It fails on memory: 5x-149x more thanfast_perfect_hashwith a single module, and a multi-terabyte table once a programdlopens a module that registers classes of its own.Three other schemes were tried. None beats
fast_perfect_hashas the general v-table lookup, which stays the default. But the exercise found that its randomized search is expensive on realistic type id distributions (up to 175 ms for 1000 classes), and that it gives up and aborts on large ones (all four 4000-class samples). The three schemes are alternatives for that case, and #103 added them as policies:pextminimal_cover_hashminimal_perfect_hashtwo_level_hashThe harness was also run on MSVC. It agrees that D costs more per call. It also found that MSVC does not inline fetching an object's type id: doing it by hand saves about half a nanosecond per dispatch, more than any difference between two of the maps.