Step 3 — Benchmark and Compare

Goal

Quantify the cost difference between the two structures on three workloads.

Workloads

NameOpMeasured
pointget(key) where key was previously insertedns/op + cache misses (if perf)
point-missget(key) where key is absentns/op
rangeiterate from lo until hins/key (skip list only)

Procedure

  1. Seed both structures with N (10k, 100k, 1M, 10M) random 8-byte keys + 8-byte values.
  2. For each workload, take iters random accesses, time the loop, divide by iters.
  3. Report p50, p99, mean, total throughput.

Expected outcomes (M2 Pro, release, N=1M)

OpSkip listHash tableRatio
Insert~700 ns~95 ns7×
Point hit~450 ns~25 ns18×
Point miss~500 ns~30 ns17×
Range scan 1000 from key~25 µsN/A—
Bytes/entry~80~253.2×

What the numbers prove

  • For unordered point access, never use a skip list. The factor-of-20 gap is from cache-miss count: hash table touches ~1 line, skip list touches ~20 (one per level).
  • For ordered access, the skip list is the only option of the two. Range scans on a hash table require collecting all entries and sorting — O(n log n) setup vs O(k) for the skip list.
  • The memory gap is real and gets worse for tiny values. Skip-list forward-pointer arrays dominate when value size is < ~64 B.

How to run

./target/release/dsbench bench point 1000000
./target/release/dsbench bench mem   1000000

Optional: cache-miss measurement

# Linux
perf stat -e cache-misses,cache-references ./target/release/dsbench bench point 1000000

# macOS (Instruments → Counters template, capture by PID)
xcrun xctrace record --template 'Counters' --launch ./target/release/dsbench bench point 1000000