Tag
data-structures
- Jun 9, 2025 Piece Tables, Gap Buffers, and Ropes in Editor Buffers How editors store document text so that typing stays cheap: the gap buffer, the piece table, and the rope, plus the line index that answers offset-to-line queries over each of them. developer tools
- Apr 10, 2025 Why LRU Eviction Needs a Hash Map and a Linked List The data structure behind least-recently-used eviction, why exact recency ordering costs two pointers per entry, and what CLOCK and frequency-based policies give up to avoid that cost. backend systems
- Feb 24, 2025 Timer Wheels and the Cost of Finding the Next Expiry Why a sorted list or a heap is the wrong structure for thousands of concurrent timers, how a hashed wheel amortises the work, and what the resolution trade costs. operating systems
- Jan 11, 2024 Hierarchical Timing Wheels for Millions of Timeouts A heap of deadlines costs O(log n) per insertion and O(1) to read the next one. A hashed wheel with cascading levels makes insertion O(1) and confines expiry to one bucket, at the price of resolution and a bounded maximum interval. language runtimes