Rust data structures with circular references (2021)

Original Article ↗ Hacker News Discussion ↗

Indices, arenas, and “laundered” pointers

  • Several comments critique “manual memory is fine, just use arenas + handles,” arguing it often just hides pointer arithmetic behind vector indices.
  • Others reply that indices are still safer than raw pointers due to bounds checks and defined panic behavior.
  • Memory savings from using small integer indices instead of pointers are highlighted as substantial in pointer-heavy structures.
  • Using indices is seen as good for locality and serialization, but also as easy to misuse (“handle confusion,” logical bugs, leaks).

What counts as memory safety

  • Long subthread debates whether bugs in index-based structures are “memory safety” issues.
  • One side: out-of-bounds or “use index after free” in safe Rust yields panics or logic errors, not UB or RCE, so still memory-safe in Rust’s sense.
  • Other side: you can still get two “owners” of the same logical object and serious semantic bugs, even if not UB.
  • Participants stress that Rust equates memory safety with absence of UB; disagreement arises when people use broader notions.

Encapsulating unsafe: Rust vs C/C++ and older languages

  • Strong view: C/C++ cannot enforce encapsulation of unsafe code; “if you know what you’re doing” is not a safety boundary.
  • Counterpoint: with discipline and libraries, you can approximate this, but the language doesn’t help.
  • Rust’s unsafe and the requirement to explicitly mark unsafe calls are seen as culturally and technically important.
  • Historical notes mention earlier languages with explicit unsafe/checked modules and tainted binaries.

Techniques for circular references in Rust

  • Besides the article’s vector-of-nodes-with-indices, people mention:
    • The “Too Many Linked Lists” guide.
    • Rc/Weak + RefCell.
    • Gc<T>-style pointers and third-party GC runtimes.
    • GhostCell / qcell patterns using higher-rank lifetimes and tokens.
  • Some note that index-based deletion in a Vec<T> can leak or require extra machinery (e.g., Option<T>, free lists).

Are parent links / cyclic structures needed?

  • One camp: avoid parent pointers and cycles when possible; many algorithms don’t truly need them, and cycles are hard to reason about.
  • Others respond that some algorithms genuinely require parent or bidirectional links; if a language blocks that, it’s a limitation, not a virtue.
  • There is a sense that Rust’s friction here reveals when cycles are actually necessary vs habitual.

GC vs Rust-style ownership

  • Some argue a modern GC would suffice for most Rust use cases; Rust’s contortions around graphs show the cost of no GC.
  • Others counter that:
    • Many Rust users already know GC’d languages and chose Rust for predictability, performance, and no runtime.
    • Even low-latency GCs still hurt determinism and cache behavior in high-performance or real-time-ish code.
  • Discussion notes that many projects probably could tolerate GC, but developers value Rust’s other properties (type system, deterministic destruction, ownership-based concurrency).

Isoheaps and alternative memory models

  • Isoheaps (per-type isolated heaps) are proposed as an alternative: similar guarantees to indices/arenas but faster and more ergonomic.
  • Claims: isoheaps and index-based schemes both prevent RCE, though they don’t prevent all logical misuse.
  • Some suggest that borrow-checker-style systems may be overkill compared to isoheap-based manual management.

Ergonomics, lifetimes, and language mix

  • Complaints about Rust ergonomics: adding lifetimes is painful; patterns like &'a Node<'a> are easy mistakes.
  • Some prefer using two languages (e.g., C for low-level, Go/Python for high-level) instead of bending Rust to all roles.
  • Others enjoy Rust as a single language spanning high- and low-level code, citing its expressiveness, safety culture, and performance.