Data Structures
3 engineering logs on Data Structures. Newest first.
- CPU Caches and Spatial Locality: Why an Array is 3x Faster Than a Linked List for the Exact Same Big-O Complexity
Why arrays are faster than linked lists on real CPUs: cache lines, spatial locality, hardware prefetchers, and pointer chasing.
- Cuckoo Filters: Cache-Friendly Membership Checks With Deletions
How Cuckoo filters work: fingerprints, two-bucket lookups, kick-out insertions, why they stay cache-friendly, and the real tradeoff of insertion failure.
- Bloom Filters vs Counting Bloom Filters: When Deletions Kill Performance
Why counting (deletable) Bloom filters often lose in production: cache misses, random memory access, and better alternatives like hash tables or Cuckoo filters.