← Back
Home › Systems › Productivity and collaboration

spreadsheet-engine

spreadsheet recalculation engine

Excel, Google Sheets

SystemTechniques · 4Primitives · 15 spreadsheet-engine Work-stealing dequeconcurrency · 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.›Operational transformationdistributed · medium: Transform concurrent edits against each other for collaborative text editingVectorized executionstorage · medium: Query operators pass batches of about 1-2K values per column instead of single tuples, amortizing interpretation overhead and enabling tight SIMD loops.›Incremental computationsystems · medium: Dependency graph of derived values recomputed only when inputs change (reactive cells, spreadsheets)Swiss tabledata-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.›Topological sortgraphs · 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.›Bytecode interpretercompilers · low: Register/stack VM dispatch loop for executing compiled plans or rules (SQLite VDBE, nftables)Pratt parsingcompilers · low: Table-driven expression parsing with one loop and a numeric binding power per operator; the compact core of precedence handling in hand-written parsers.›R-treegeometry · low: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.›Strongly connected componentsgraphs · low: Tarjan/Kosaraju SCCs for cycle detection in dependency graphsFloating-point errornumerics · low: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.›Calendar date arithmeticsystems · low: Civil dates, time zones (tzdb), DST gaps, month-end anchoring and duration mathEpoch-based reclamationconcurrency · 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 orderingconcurrency · low: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.›Message sequence numbersdistributed · low: A per-stream counter on every message lets the receiver detect loss, duplicates and reordering, ack cheaply and resume after reconnect with "send from N".›Ropegraphics · 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).›Hash consingdata-structures · low: Intern structurally equal immutable terms so equality is pointer comparison and sharing is maximalBFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›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.›

Similar systems

Share the most building blocks with this one.

office-suite 22 %