In performance-critical environments, developers often face fundamental choices in data structure design. While pointers dominate conventional approaches, a growing contingent of systems programmers advocates for a paradigm shift: replacing pointers with integer indexes. This pattern unlocks tangible benefits across memory usage, recursion handling, and serialization – but introduces new type-safety challenges. Here's why indexes are becoming the stealth weapon for efficiency-minded developers.

The Triple Advantage of Indexes

1. Memory Efficiency:
On 64-bit architectures, a 32-bit index saves four bytes per reference. Beyond obvious memory reduction, this improves cache utilization dramatically. As one developer notes:

"Dense data structures use CPU cache more efficiently, removing prohibitive latency of memory accesses. Best case, the working set fits into the CPU cache!"

This architectural advantage permeates entire systems – each compacted structure contributes to cumulative performance gains invisible to profilers but critical at scale.

2. Cyclic & Recursive Data Safety:
Pointers inherently struggle with cycles and deep recursion, often requiring nullable types or risking stack overflows. Indexes sidestep these pitfalls:

// Zig tree node using indexes instead of pointers
const Node = enum(u32) {
    root = 0,
    invalid = std.math.maxInt(u32),
    _
};

pub fn parent(tree: *const Tree, node: Node) ?Node {
    const result = tree.get(node).parent;
    return if (result == .invalid) null else result;
}

This approach avoids recursive pointer chasing while maintaining parent/child relationships safely.

3. Zero-Cost Serialization:
Indexes shine when persisting or transmitting data. Unlike pointers, they're inherently relocatable. Bulk operations become trivial:

"You don’t need to write items one-by-one – directly memcpy arrays. But be careful to not leak data via padding."

Solving the Index Safety Problem

The elephant in the room? Accidentally using an index from one array with another. Zig's non-exhaustive enum pattern enforces type safety:

const ItemIndex = enum(u32) { _ }; // Newtype wrapper

// Compiler prevents mixing ItemIndex with other u32 values
fn process_index(idx: ItemIndex) void { ... }

This leverages Zig's enum semantics to create distinct types while retaining the raw integer's performance. The @intFromEnum and @enumFromInt builtins handle conversions explicitly.

Real-World Implementation

Consider this n-ary tree implementation:

pub const Tree = struct {
    nodes: []const Node.Data,

    pub const Node = enum(u32) { ... };
    // ... child range handling via index/count pairs
};

Key design insights:
- Store collective data (nodes array) before individual elements
- Symbolic constants (.root, .invalid) replace magic numbers
- comptime size assertions document memory layout expectations

The pattern shifts focus from individual nodes to aggregate operations – a structural change that pays dividends in cache coherence and algorithm design.

Beyond Zig

While Zig's enums provide elegant syntax, the core concept transfers to any language. As noted in prior Rust implementations, the index pattern fundamentally changes how we model relationships in data. For performance-critical systems facing memory pressure or complex data topologies, abandoning pointers for indexes might be the most impactful optimization you never benchmarked.

Source: Aleksey Kladov (matklad), Zig Newtype Index Pattern