]> git.hungrycats.org Git - bees/commit
hash: resize in one pass when no buckets merge
authorZygo Blaxell <bees@furryterror.org>
Sun, 23 Aug 2026 17:14:47 +0000 (13:14 -0400)
committerZygo Blaxell <bees@furryterror.org>
Tue, 6 Oct 2026 05:51:40 +0000 (01:51 -0400)
commit1fc8a109f84d2ebb6bf9a7d89ee41098fd40f89c
tree5d29421a2bca23cc2315a744aec717a8f3903b96
parent734485a3082e70e9fd1deb19fe5c0e5e73f8c131
hash: resize in one pass when no buckets merge

Resizing walked the old table c_cells_per_bucket (256) times, once per
cell position, so that cells from old buckets merging into one new
bucket interleave by LRU rank instead of one bucket evicting another.
That cost is only necessary when merging actually happens.

A cell is placed at hash % new_buckets and lived at hash % old_buckets.
If old_buckets divides new_buckets, hash % new_buckets == n implies
hash % old_buckets == n % old_buckets, so every cell in new bucket n
comes from exactly one old bucket and no merging occurs.  That covers
every integer-factor grow, including the doubling an operator gets from
asking for twice as much hash table.

With nothing to interleave, one sequential pass over the old table
produces bit-identical output.  Detect the divisible case and take it.

The difference is not academic.  A real 8G to 16G resize logged:

  Resizing hash table: 19423/16777216 (0%), 210.11 sec elapsed,
      181278 sec remaining

256 passes over 8G is 2 TiB of reads.  Once the old table no longer fits
in the page cache every pass after the first comes from disk, which measured
~12 MB/s and put the finish 50 hours out, with the estimate still climbing as
the 16G destination evicted what remained of the source.  One pass reads 8 GiB.

Verified end to end by resizing one populated 128M table with the
pre-change and post-change binaries and comparing beeshash.dat:
identical for a 2x grow and a 3x grow (fast path taken), and identical
for a 1.5x grow, where 49152 % 32768 != 0 keeps the merging path and
confirms it is unchanged.

Shrinks and non-divisible grows still make 256 passes.  Shrink is the
worse case, since the table being read 256 times is the larger one; it
needs a rank-aware single-pass merge, which needs somewhere to keep each
cell's LRU rank, and is left for later.

Assisted-by: Claude-Code:claude-opus-5
Signed-off-by: Zygo Blaxell <bees@furryterror.org>
src/bees-hash.cc