hash: merge in one pass when new buckets divide old
Commit "hash: resize in one pass when no buckets merge" made the
divisible grow a single sequential pass, and left the shrink on the
c_cells_per_bucket-pass loop, saying a single-pass merge "needs somewhere
to keep each cell's LRU rank". That is not so. A cell's rank is its
position in its bucket, which costs no storage at all, and recording one
rank per cell would need ~1 GiB of side table for a 16 GiB hash table --
prohibitive, and unnecessary.
The rank is only unrecoverable in a source-major traversal. Walking old
buckets in file order and pushing each into its destination interleaves
two old buckets into one new one, after which a destination cell's
position no longer says which rank it arrived with, so a third old
bucket cannot be merged correctly. That is a property of the traversal
order, not of the data.
Visit in destination order instead. Gather the merge_width old buckets
that feed one new bucket and merge them by array index: each source is
still in pure rank order, so position is the merge key and nothing has
to be stored per cell.
The gather is whole extents rather than scattered buckets. New bucket n
is fed by old buckets n + j * new_buckets, and new_buckets is a whole
number of extents because new_size is, so new extent e is fed by old
extents e + j * new_extents -- merge_width contiguous extents, with
every old extent read by exactly one new extent. The same reasoning
puts old bucket n + j * new_buckets at the same offset within its extent
as new bucket n, so one index reaches all merge_width of them.
Reads drop from c_cells_per_bucket * old_extents to old_extents. Shrink
was the worse case for the old loop, because the table it read 256 times
was the larger one.
The push order is the same subsequence the cell-pass loop produces for
each new bucket -- LRU-oldest rank first, and within a rank, descending
old extent index -- so the output is bit-identical, whatever
push_front_in_range() does with duplicates and evictions. Cells are
still addressed by hash rather than by the gathered index, so a cell
that is not in the bucket its hash names still lands in the right place.
The gather buffer is merge_width extents, so it is capped at 1024 (128
MiB, a 1024:1 shrink); a ratio past that keeps the cell-pass loop, as do
non-divisible resizes in either direction.
Verified against a pre-change binary on a 16M table seeded by real
dedupe traffic, comparing beeshash.dat byte for byte, with the
pre-change binary run twice per case to prove the comparison is
measuring the resize:
The two unchanged timings confirm the new branch does not capture cases
it should not. Timings are with the table in page cache, so they show
only the CPU cost of the extra passes; the read-count reduction is what
matters once the old table no longer fits.
projects / bees / commit