mhtirogla
Home
Systems
API
Pricing
About
Log in
← Back
Home
›
Systems
›
Compilers and language tooling
incremental-compiler
incremental compiler
rustc query system
System
Techniques · 7
Primitives · 21
incremental-compiler
Incremental parsing
compilers · medium: Reparse only the region an edit damaged and splice the new subtrees into the old tree, sharing everything else; O(edit) instead of O(file).
›
Language server protocol
compilers · medium: One JSON-RPC conversation over a pipe lets any editor drive any language's analysis server; the cost is keeping a live, edited document in sync and answering before it changes.
›
Type inference hindley milner
compilers · medium: Algorithm W and J: unification-based inference with let-polymorphism and generalization
Work-stealing deque
concurrency · medium: Per-worker deque: the owner pushes and pops at the bottom without contention, idle workers steal from the top; the core of Rayon, Tokio and Go.
›
Query based incremental computation
systems · medium: Memoized queries with dependency tracking and red-green revalidation (rustc, Salsa)
Lossless syntax trees
compilers · medium: Concrete syntax trees with trivia, green/red node split (Roslyn, rowan) for tools that rewrite code
Parser error recovery
compilers · medium: Recover from syntax errors via synchronization tokens and error nodes to keep a full tree
Name resolution
compilers · low: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.
›
String interning
data-structures · low: Store each distinct string once and refer to it by id
Fast hash functions
data-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.
›
Topological sort
graphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.
›
File system watching
hardware-os · low: Treat OS change notices as hints, debounce them, and rescan and diff a snapshot whenever notices overflow or may be lost.
›
mmap and the page cache
hardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.
›
Zero-copy serialization
networking · low: Wire formats laid out like in-memory structs (FlatBuffers, Cap'n Proto, SBE, rkyv) so readers access fields in place with no decode pass or allocation.
›
Arena allocator
systems · low: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.
›
Recursive-descent parsing
compilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.
›
Rope
graphics · low: A balanced tree of small string chunks with cached byte and newline counts, so seek, insert, delete and snapshot cost O(log n) instead of O(n).
›
Unification
compilers · low: First-order unification with union-find and occurs check; basis of type inference and logic programming
Union-find
graphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.
›
Epoch-based reclamation
concurrency · low: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.
›
Memory ordering
concurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.
›
Hash consing
data-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximal
Swiss table
data-structures · low: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.
›
+ 5 more primitives
System
Techniques · 7
Primitives · 21
incremental-compiler
Incremental parsing
compilers · medium: Reparse only the region an edit damaged and splice the new subtrees into the old tree, sharing everything else; O(edit) instead of O(file).
›
Language server protocol
compilers · medium: One JSON-RPC conversation over a pipe lets any editor drive any language's analysis server; the cost is keeping a live, edited document in sync and answering before it changes.
›
Type inference hindley milner
compilers · medium: Algorithm W and J: unification-based inference with let-polymorphism and generalization
Work-stealing deque
concurrency · medium: Per-worker deque: the owner pushes and pops at the bottom without contention, idle workers steal from the top; the core of Rayon, Tokio and Go.
›
Query based incremental computation
systems · medium: Memoized queries with dependency tracking and red-green revalidation (rustc, Salsa)
Lossless syntax trees
compilers · medium: Concrete syntax trees with trivia, green/red node split (Roslyn, rowan) for tools that rewrite code
Parser error recovery
compilers · medium: Recover from syntax errors via synchronization tokens and error nodes to keep a full tree
Name resolution
compilers · low: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.
›
String interning
data-structures · low: Store each distinct string once and refer to it by id
Fast hash functions
data-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.
›
Topological sort
graphs · low: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.
›
File system watching
hardware-os · low: Treat OS change notices as hints, debounce them, and rescan and diff a snapshot whenever notices overflow or may be lost.
›
mmap and the page cache
hardware-os · low: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.
›
Zero-copy serialization
networking · low: Wire formats laid out like in-memory structs (FlatBuffers, Cap'n Proto, SBE, rkyv) so readers access fields in place with no decode pass or allocation.
›
Arena allocator
systems · low: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.
›
Recursive-descent parsing
compilers · low: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.
›
Rope
graphics · low: A balanced tree of small string chunks with cached byte and newline counts, so seek, insert, delete and snapshot cost O(log n) instead of O(n).
›
Unification
compilers · low: First-order unification with union-find and occurs check; basis of type inference and logic programming
Union-find
graphs · low: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.
›
Epoch-based reclamation
concurrency · low: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.
›
Memory ordering
concurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.
›
Hash consing
data-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximal
Swiss table
data-structures · low: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.
›
Text position encoding
compilers · low: Store byte offsets, convert to (line, column) on demand with a line-start table and binary search, and count columns in the unit the peer negotiated.
›
Edit distance
search-sort · low: Levenshtein/Damerau distance by DP, bit-parallel Myers variant
BFS and DFS
graphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.
›
Virtual memory and the TLB
hardware-os · low: How page tables and TLBs translate every address, what TLB reach means, and when 2 MiB or 1 GiB huge pages pay off on Linux.
›
Sparse matrices (CSR)
numerics · low: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.
›
Copy for AI
Similar systems
Share the most building blocks with this one.
js-bundler
33 %
language-server
30 %
type-checker
29 %
formatter-linter
27 %
build-system
17 %