algorithms
21 articles tagged algorithms.
-
Property-Based Testing and Shrinking
Learn how property-based testing generates structured inputs and shrinks failures into small, reproducible counterexamples.
-
Git Packfiles and Delta Compression
How Git packs objects, resolves delta chains, and uses garbage collection and repacking to balance repository size against read and write speed.
-
How Compiler Register Allocation Uses Interference and Spilling
Register allocation assigns live intermediate values to CPU registers, building interference constraints and spilling selected values to memory when registers run out.
-
TCP Slow Start and Congestion Avoidance
How TCP grows its sending rate, reacts to acknowledgements and loss, and discovers how much capacity a network path can support.
-
Consistent Hashing and Virtual Nodes
See how a hash ring assigns keys to members, and why membership changes remap only a small, predictable portion of the data.
-
Bloom Filters: Bit Arrays, Hash Probes, and False Positives
Learn how Bloom filters use hashed bit positions for cheap membership checks, and why sizing and probe count control false positives.
-
How Work-Stealing Deques Reduce Scheduler Contention
A work-stealing deque gives each worker fast local task operations while letting idle workers take tasks from the opposite end.
-
Raft Leader Election and Majority Voting
How Raft uses terms, randomized timeouts, and majority votes to elect one leader and keep conflicting log entries from being committed.
-
TCP Retransmission Timeout Estimation
How TCP combines measured round-trip time and its variability to choose a timeout that avoids duplicate retransmissions and slow loss recovery.
-
Hybrid Logical Clocks
How hybrid logical clocks combine wall-clock readings and counters to preserve causality across distributed systems despite clock skew.
-
Skip Lists and Expected Logarithmic Index Operations
Layered linked lists let skip lists search, insert, and delete ordered data in expected logarithmic time through randomized node heights.
-
Git Packfiles and Delta Compression
How Git packfiles combine objects, store deltas and chains, and change repository size and lookup behavior during repacking.
-
Consistent Hashing Rings and Virtual Nodes
Learn how hash rings and virtual nodes assign cache keys so adding or removing a host remaps only a fraction of the keyspace.
-
Property-Based Testing Shrinkers
How a property-based test turns a complex generated failure into a smaller counterexample while checking that each reduction still fails.
-
Static Single-Assignment Form and Phi Nodes
SSA gives each intermediate value one definition, while φ-nodes merge values from different control-flow paths for simpler data-flow optimization.
-
How Raft Leader Elections Work
Raft uses numbered terms, randomized timeouts, majority votes, and log checks to elect one safe leader and recover from split votes.
-
Bloom Filters and Probabilistic Set Membership
Learn how Bloom filters use a bit array and multiple hashes to save memory while allowing false positives but not false negatives.
-
Consistent Hashing on a Ring
How consistent hashing assigns keys around a ring, uses virtual nodes to balance load, and limits key movement during membership changes.
-
Speculative Decoding with Draft and Target Models
How a small model proposes token sequences for a large model to verify, reducing generation latency while preserving the large model’s distribution.
-
Database B-Tree Page Splits and Separator Keys
How B-tree pages split at capacity, propagate separator keys, and preserve fast, logarithmic index lookups.
-
Property-Based Testing and Shrinking Counterexamples
Learn how property-based testing generates varied inputs, detects invariant violations, and shrinks failures into small reproducible counterexamples.