Cache Lines, Not Probes: The Memory-Access Cost of Open Addressing Without Reordering
Abstract
Abstract Farach-Colton, Krapivin, and Kuszmaul determined the probe complexity of open addressing without reordering. On real hardware, however, the cost of an operation is dominated not by the number of probes but by the number of distinct cache lines (blocks of $B$ slots) it touches. We introduce the cache-line cost model for open addressing without reordering and study the optimal number of memory accesses per operation as a function of the load $1-\delta$, the block size $B$, and the table size $n$, governed by the single parameter $\delta B$ (empty slots per block). For worst-case cost we obtain a complete, unconditional law: the smallest $W$ such that every operation touches at most $W$ lines with high probability is $\Theta(1+\log\log n/\delta B)$, achieved by asymmetric ($d$-left) bucketing and matched, in the oblivious model, by V\"ocking's balanced-allocation lower bound. Asymmetry is necessary: symmetric ($d$-greedy) bucketing is a $\log n/\log\log n$ factor worse at constant slack. Hence $O(1)$ worst-case accesses are possible if and only if $\delta B=\Omega(\log\log n)$. For expected insertion cost we prove an unconditional lower bound $\Omega(1+1/\delta B)$ and matching upper bounds: $O(1+1/\delta B)$ for $\delta B=\Omega(\log\log n)$, and $O(\delta^{-1}\log\delta^{-1})$ for all $\delta,B$. The tight law $\Theta(1+1/\delta B)$ extends to small slack under one stated hypothesis, the heavily-loaded $d$-choice full-bucket tail, which we confirm empirically. A…
Read the paper
Related studies
- eggNOG 5.0: a hierarchical, functionally and phylogenetically annotated orthology resource based on 5090 organisms and 2502 viruses
- Online Survival Analysis Software to Assess the Prognostic Value of Biomarkers Using Transcriptomic Data in Non-Small-Cell Lung Cancer
- OptiType: precision HLA typing from next-generation sequencing data
- Nicotinic Cholinergic System and COVID-19: In Silico Identification of an Interaction between SARS-CoV-2 and Nicotinic Receptors with Potential Therapeutic Targeting Implications
- Saccharomyces cerevisiae cells have three Omega class glutathione S-transferases acting as 1-Cys thiol transferases
- Hemolysis at low blood flow rates: in-vitro and in-silico evaluation of a centrifugal blood pump
Go deeper in Evidence Hub
Evidence Hub adds a study data sheet (design, sample size, evidence level, key numbers), an AI summary and a chat grounded in the paper's text.