Indices, not Pointers
8 days ago
- #Zig
- #Data Structures
- #Performance Optimization
- Using indices instead of pointers in data structures can improve performance by reducing memory usage and speeding up accesses.
- Indices are stored in a dynamic array, making nodes reference each other via indices rather than pointers.
- Benefits include smaller nodes (4 bytes vs 8 bytes for pointers), faster access due to contiguous memory storage, and less allocation overhead.
- Freeing the entire structure is instantaneous as it requires only a single free call.
- A downside is the difficulty in freeing individual nodes without shifting elements, which can be mitigated using freelists.
- A code example in Zig demonstrates implementing a tree structure using indices for nodes.