Patterns from Rust
Rust's standard library embodies zero-cost abstractions through its type system.
| Pattern | Where | What It Does |
|---|---|---|
| Iterator / Lazy Eval | core/iter/traits/iterator.rs | The Iterator trait — next() + composable map/filter/fold |
| Copy-on-Write | alloc/src/borrow.rs | Cow<'a, B> — clone-on-write smart pointer for zero-copy parsing |
| Arena Allocator | bumpalo lib.rs | Bump — canonical Rust arena allocator, used in wasm-bindgen and Deno |
| Work Stealing | Tokio worker.rs | Core::steal_work — multi-threaded async runtime work stealing |
| Dependency Graph | Cargo resolver/ | DAG-based dependency resolution for crate compilation order |
| Reference Counting | alloc/src/sync.rs | Arc<T> — atomic reference counting for shared ownership across threads |
| Interning | rustc symbol.rs | Symbol is a u32 index into global interner — all identifiers interned for O(1) comparison |
| Semaphore | Tokio semaphore.rs | Semaphore — async-aware bounded concurrency control |
How They Compose: Compiling a Crate
When cargo build compiles a Rust crate, the compiler and runtime use these patterns together:
cargo build▼Cargo resolves the crate dependency DAG and determines compilation order. Independent crates compile in parallel.
rustc interns all identifiers into a global table. Every variable name, type name, and keyword becomes a u32 index. Comparison is O(1) integer equality instead of string compare.
The compiler allocates AST nodes and type info in per-query arenas. When a query completes, the entire arena is freed — no per-node deallocation overhead.
Tokio's multi-thread runtime (used by async Rust programs) steals tasks from idle workers' queues to keep all cores busy.
Arc<T> enables shared ownership across threads without a GC. The compiler's type system guarantees no data races.
Rust's zero-cost abstractions philosophy means these patterns have no runtime overhead beyond what a hand-written C implementation would have. The Iterator trait compiles down to the same machine code as a manual loop. Cow<T> avoids cloning when the data is only read. Arc<T> uses atomic operations only when actually shared.