Tag
cache-locality
- Oct 21, 2026 Singly Linked Lists: One Pointer per Node and the Cost of Unidirectional Traversal How a head pointer and a next field support O(1) splicing, why deletion needs the predecessor, and what pointer chasing costs on a modern cache hierarchy. data structures
- Jun 9, 2026 d-Ary Heaps and How Branching Factor Changes Cost Trading comparisons per level against levels per sift, why four children often beats two on real hardware, and where the arithmetic stops fitting in a register. data structures
- Apr 8, 2026 Child Representation and the Branching Factor Problem in Tries A trie costs one child lookup per key byte, so the node layout decides memory and speed. Compares dense arrays, sorted and linked child lists, bitmaps with rank, and double-array layouts. data structures
- Sep 25, 2025 Blocked and Partitioned Bloom Filters for Cache-Resident Probes Confining the k probes of a filter to one cache line, or to one slice of the array, changes the error rate by a measurable factor and the memory behaviour by an order of magnitude. data structures
- Aug 5, 2025 Swizzled Texel Layouts and the Cost of a Bilinear Fetch Why row-major storage makes a four-texel fetch hit two cache lines or more, how tiled and Morton-ordered layouts repair it, and where the repair stops paying. computer graphics
- Jun 29, 2025 SwissTable Control Bytes and Group-Wise Probing How a one-byte tag per slot lets a lookup reject fifteen candidates with one SIMD comparison, and why metadata separate from keys changes the memory hierarchy. data structures
- Jun 5, 2024 Unrolled Linked Lists and the Cost of a Cache Miss per Node Packing several elements per node cuts pointer chases by the node capacity, and the block size that minimises total cost follows from a cache line and a word. data structures