Ointers: A library for representing pointers where bits have been stolen (2021)

Original Article ↗ Hacker News Discussion ↗

Mechanics of “stolen-bit” pointers and this library

  • Some readers initially thought it only masked high bits, conflicting with typical low-bit tagging from alignment.
  • Clarification: the library packs “stealable” bits contiguously by shifting pointers by their alignment to free low bits, then re-expands on load.
  • This is seen by some as clever but complex; one guideline raised: if you’re doing more than simple masking, you risk fragility.
  • Several commenters recommend strong testing infrastructure for this kind of low-level trick.

Available bits and architecture details

  • On common 64-bit CPUs, virtual addresses are usually only 48 bits, leaving many high bits free; low bits from alignment add a few more.
  • Extensions (e.g., 5-level paging, various “ignore upper bits” and “top-byte ignore” mechanisms) expand usable virtual space and can reduce available tag bits.
  • These extensions are opt-in and kernel-mediated; on Linux, typical behavior keeps mmap in 48-bit space until a higher address is requested.
  • There’s uncertainty about practical use cases for huge (57-bit+) virtual spaces; one example given: reserving very large disjoint segments per thread.

Prevalence, benefits, and drawbacks

  • Many language runtimes and VMs use tagged pointers or NaN-boxing (Lisps, Lua-like systems, JS engines, Objective-C, OCaml, Smalltalk, game consoles).
  • Reported experience: used tactically, tagging works well and ships in major software; problems arise when it pervades whole systems without clear abstraction.
  • Tagged pointers can store types, integer vs pointer flags, refcounts, and “dirty” bits directly in the pointer.
  • Debugging becomes harder because raw pointers in memory aren’t directly dereferenceable; mitigations include wrapper types and debugger pretty-printers.

Performance and Lisp discussion

  • Debate on whether tagged pointers harmed Lisp performance:
    • One side: performance issues stem mainly from pervasive linked lists (poor cache locality), GC behavior, and low register counts on early x86.
    • Others note compacting GCs can improve locality but lists still pay overhead in links and branch/pipeline costs versus arrays/vectors.
  • Consensus: pointer tagging cost is minor compared to cache misses and indirection; data structures and overall architecture dominate.

Alternatives and related techniques

  • Relative pointers or indices plus a base pointer/arena can save more space than shaving a few bits, at the cost of allocator and architecture complexity.
  • In Rust-like settings, “NonMax” index types were proposed to get niche-optimization without sacrificing zero; workarounds use NonZero + offset/xor.
  • Unused bits can also hold pointer authentication codes; contrasted with ECC RAM, which doesn’t protect against cross-process or targeted pointer corruption.
  • OS/allocator tricks: mmap a large aligned region, constrain allocators to a range, or use special mmap flags (e.g., 32-bit-limited regions on x86-64).