Fine-Grained Analysis of SIMD-Based Hash Table Implementations

1 Introduction

• Modern implementations use compact metadata and SIMD to reduce memory accesses per probe, motivating a mathematical analysis of this hash-table design.Source: §1 · p. 2

Model of hash tables

• The analysis models open addressing with uniform hashing and random probing, measuring operation cost by the number of hops, which is linked to cache misses.Source: Model of hash tables · pp. 2–3

Using vectorization for hash tables operations

• Each bucket pairs a key array with a byte header of fingerprints; SIMD checks whether a queried key’s fingerprint is present before accessing the keys.Source: Using vectorization for hash tables… · p. 3

Related works

• Prior analyses of overflow-bit variants were incomplete or used different models; the paper adapts Wormald’s method to derive high-probability estimates for table occupancy and search costs.Source: Related works · pp. 5–6

Plan of the article and contributions

• The analysis first treats tables without overflow bits, then models overflow-bit dynamics per insertion attempt and estimates unsuccessful-search cost; insertions and successful searches are unaffected by overflow bits.Source: Plan of the article and contributions · pp. 6–7

2.1 Recurrence relations

• Each insertion moves one bucket from occupancy j to j+1, and the conditional transition probabilities yield recurrence relations for the bucket counts.The resulting expected increments produce the differential-equation system for the fluid limits.Source: §2.1 · p. 7

2.2 Wormald’s differential equation method

• Wormald’s differential-equation method converts conditional expected process increments into continuous-time equations whose solutions approximate the discrete processes with high probability.The adapted theorem allows increments bounded with high probability and supplies error bounds under its stated conditions.Source: §2.1 · p. 7, §2.2 · p. 8

2.3 Results without overflow bits

• With high probability, the number of buckets containing i elements is approximated by n u_i(k/N) + o(n), uniformly over i and k in the stated range.The functions u_i solve the system of differential equations with the specified empty-table initial condition.Source: §2.3 · p. 9
• With high probability, the total hops after k insertions are Nλ_b(k/N)/b + o(n), uniformly for k ≤ θN.The theorem identifies total hops with the construction cost from an empty table.Source: §2.3 · p. 10
• For load t = k/N bounded away from zero, successful-search cost is λ_b(t)/(bt) + o(1), while unsuccessful-search cost is (1−u_b(t))^-1 + o(1).Both estimates hold with high probability and have uniform error over their stated ranges.Source: §2.3 · pp. 10–11

3 Some properties of the number of hops function λb(t)

• λ_b(t) has logarithmic magnitude for all t, as established by Proposition 9.The supplied passage gives the proposition’s conclusion but not the inequality bounds.Source: §3 · p. 11
• Without SIMD, the classical framework uses b times as many instructions when a same-capacity table is almost full, and roughly the same number when it is almost empty.The authors note that resizing keeps the load factor above a positive threshold in practice.Source: §3 · p. 11
• An ordinary differential equation involving the upper and lower incomplete gamma functions provides an alternative characterization of λ_b(t).The text notes that these functions have efficient implementations in mathematical packages.Source: §3 · pp. 11–12

4 Analysis with overflow

• Integral-form solutions allow fast, accurate numerical estimates of the overflow-bit dynamics.The authors use these estimates to produce the paper’s curves.Source: §4 · p. 12
• With high probability, uniformly for k ≤ θN, V_j(k) = nv_j(k/N) + o(n) for each overflow-bit count j.Here V_j(k) counts full buckets with j overflow bits set.Source: §4 · p. 12
• The solutions for all overflow-bit counts can be written explicitly in terms of λ_b(t).An expression for F_b,d uses the regularized lower-incomplete Γ-function.Source: §4 · pp. 12, 14
• Recasting the process in hop time makes the bucket-count dynamics amenable to Wormald’s theorem, then maps them back to insertion time through λ_b(t).The time change is R(k) = Nbλ_b(k/N) + o(n) with high probability.Source: §4 · pp. 12–13
• For unsuccessful searches, the continuation probability is approximated by the weighted sum of full-bucket probabilities v_j(t) and bit-hit probabilities j/d.This makes the number of hops resemble a geometric law with that parameter.Source: §4 · p. 13

5 Conclusion

• The asymptotic analysis describes modern SIMD hash-table behavior precisely, and its high-probability state estimates support a single experimental trial.The authors use Theorem 13 to compare unsuccessful-search hops across overflow-bit choices.Source: §5 · p. 14
• The error term and convergence speed trade off: smaller error terms come with slower convergence in probability.The stated o(n) terms are O(n^(1/2+ε)) with probability tending to one, for any fixed ε > 0.Source: §5 · p. 14
• Figure 5 compares expected additional unsuccessful-search hops across b and d at constant header size, with capacities varying slightly.The caption identifies the comparison but supplies no outcome values.Source: Figure 5 · p. 14, §5 · p. 14
• The analysis does not cover every implementation, and overlapping groups of b elements introduce dependencies between buckets that require new ideas.The authors suggest the method may extend to counting element comparisons by adding fingerprint collisions to the equations.Source: §5 · p. 14
• Deletions are not analyzed because hash tables lack a commonly accepted deletion-use model, and proposed scenarios lack practical validation.The authors say some simple probabilistic models may be analyzable, though their systems may be difficult to solve.Source: §5 · p. 15
• A proposed insertion-deletion model yields a larger system of ordinary differential equations that is numerically evaluable but lacks a simple solution here.The example constrains time to when the table first reaches maximal load factor θ with high probability.Source: §5 · p. 15

A.1 Wormald’s Theorem

• For Theorem 2, the authors could have used a result of Wormald’s in almost its original form, but later results such as Theorem 6 require a stronger result presented in Section A.2.Their main tool, Theorem 1, is derived from Theorem 14.Source: §A.1 · p. 17
• The theorem assumes bounded process values, controlled increments and drift, and an initial vector close to a fixed scaled vector.Its ODE functions are continuous and Lipschitz on an open, connected domain.Source: §A.1 · p. 17
• Under the theorem’s conditions, each process is approximated uniformly up to θN by the corresponding scaled ODE solution, with probability tending to one.The theorem requires θ to lie below the solution’s boundary time σ.Source: §A.1 · p. 17
• The stated version both extends and restricts Wormald’s original result, while variants allow growing increment bounds and random initial conditions.The authors note that the θ < σ condition simplifies the statement.Source: §A.1 · p. 17

A.2 Proof of Theorem 1

• Whenever δ ≥ R/N, the approximation deviation |Y_j(k) − Ny_j(k/N)| is at most 3e^(Lθ)δN, with probability at least 1 − 2ℓexp(−Nδ²/(8θβ²)), for every j in [ℓ] and k ≤ min(m, θN).Source: §A.2 · p. 18
• A lemma permits the theorem’s conditions to be checked only on events E_i, bounding the probability that their intersection holds while the conclusion fails.The bound is 2ℓexp(−Nδ²/(8θβ²)).Source: §A.2 · p. 18
• The proof combines the concentration bound with a union bound for increment-bound failures to establish Theorem 1.It bounds the probability of any such failure by ℓθNγ(N).Source: §A.2 · p. 18

• With high probability, U_i(k) = n u_i(k/N) + o(n), uniformly in i and k for k ≤ θN, where the u_i solve the stated ODE system.The ODE initial condition is u_0(0)=1 and u_1(0)=...=u_b(0)=0.Source: §B.1 · p. 18
• The ODE solution has u_i(t) > 0 for i > 0, u_i(t) ≤ 1, and u_b(t) ≤ t wherever it can be extended.These bounds are used to control the denominators and establish existence on [0, 1).Source: §B.1 · pp. 18–19
• Uniqueness of the initial-value problem reduces verification of the proposed u_i formulas to checking that they satisfy the ODE system.The proof uses the implicit definition of λ_b(t) and verifies the equations for the proposed functions.Source: §B.1 · pp. 19–20

C Proofs from Section 3

• Proposition 9 establishes its stated logarithmic inequalities for all t in [0, 1).Source: C Proofs from Section 3 · p. 20

D.1 Proving the formula

• Lemma 20’s integral identity is proved by integrating both sides and reversing the order of integration with Fubini’s theorem.The stated conditions require continuity of F and almost-everywhere continuous differentiability in y.Source: §D.1 · p. 21

Proof of the formula

• The formula for v_j is established inductively, using the product rule for the base case and Lemma 20 in the induction step.The same result can be derived in hop-time and then composed with λ_b(t)/b.Source: Proof of the formula · pp. 21–22

• F_{b,d}(λ) = P(b, λ) − (1 − 1/d)^−b e^−λ/d P(b, λ · (1 − 1/d)), with P the regularized lower-incomplete Γ-function.Source: §D.2 · p. 22
• After k insertions, an unsuccessful search is geometric with parameter P(k), and its expected-hop expression is approximated using p(t) for k ≤ θN.The approximation uses that P(k) and p(t) are at most θ, where x ↦ 1/(1−x) has bounded derivative.Source: §D.2 · p. 22