Porting a Segmented List from C to Rust
3 days ago
- #systems-programming
- #memory-management
- #performance
- Porting a segmented list from C to Rust to compare semantics, implementation, performance, and aesthetics.
- Segmented lists offer zero realloc, zero copy, lazy allocation on grow, and are backed by a bump allocator.
- Vectors (dynamic arrays) struggle with growth due to reallocation and copying, while segmented lists trade non-contiguous storage for better performance in large AST node scenarios.
- Design involves segments growing geometrically (e.g., 1.5x or 2x), reducing syscalls and enabling stable pointers.
- Indexing in segmented lists requires computing segment and offset via logarithmic calculations.
- C implementation includes a bump allocator using mmap for memory management and macros for generic list operations.
- Rust implementation leverages x86 Linux syscall ABI for mmap/munmap, a custom GlobalAlloc-compatible allocator, and precomputed block boundaries for efficiency.
- Benchmarks show Rust's segmented list outperforms std::vec::Vec on very large elements (≥1MiB), but Vec is optimized for smaller, more common workloads.
- Rust pain points include Sync/Send requirements for allocators, flaky concurrent tests, and harder-to-debug segfaults.
- Rust advantages over C include better generics, trait implementations (e.g., Drop), enums, built-in testing/benchmarking, and compile-time optimizations.