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

Original Article ↗ Hacker News Discussion ↗

A Rust library for “stealing” unused bits from pointers to store extra data prompts a deep look at tagged pointers and related techniques. Commenters weigh the practicality and safety of shifting or masking pointer bits versus alternatives like indices, arenas, or constrained address spaces, noting both long-standing use in Lisps, VMs, and Apple’s runtimes and the potential for debugging complexity or future hardware incompatibilities. The exchange highlights how modern 64‑bit architectures leave significant headroom in virtual addresses, enabling clever memory optimizations that trade simplicity for density and performance.

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).