Self-Tagging Numbers
summary
Extends float self‑tagging to SML/NJ by applying a reversible bit transform — left rotate by three and XOR with 6 — to make common 64‑bit integers distinguishable from pointer/header patterns and fall back to heap allocation only for conflicts. Compiler emits wrap/unwrap at polymorphic boundaries so arithmetic stays native; preliminary benchmarks set native 64‑bit as default and report no heap allocation for most integers with up to ~30% speedup and a few pathological slow cases under investigation.
AI-written summary · about
chapters (24)
- 0:00Self-tagging numbers intro
- 1:03Integers need tagging in polymorphism
- 2:28History of number representation
- 4:12Monomorphization alternative
- 6:45Tag integers in SML/NJ
- 7:07Self-tagging floats in Scheme
- 8:52Self-tagging principle
- 10:15Advantages in ML
- 12:00Self-tagging integers
- 13:47Wrap and unwrap ops
- 15:32Wrap/unwrap performance
- 16:59Rare integer ranges
- 17:20Tagging in polymorphism only
- 18:06Type system and coercions
- 20:17Coercion generation in IR
- 21:21Lowering and type application
- 22:02Uniform representation invariants
- 23:25Optimizing type applications
- 24:09Specialization to avoid polymorphism
- 24:50Arithmetic in monomorphic
- 25:54Central message of self-tagging
- 26:15SML/NJ implementation
- 27:17Performance results
- 28:00Q&A
related talks
14mFloat Self-Tagging
16mWhat About the Integer Numbers?
34mModernizing Standard ML of New Jersey: A Status Report
31mRange-Analysis-Based Optimization for SML/NJ
32mBit-Stealing Made Legal: Compilation for Custom Memory Representations of Algebr...
58mPortable floating-point calculations
26mHow Go Avoided the Integer Promotion Footgun
43mAuto-Vectorization in HotSpot