Repository navigation
Probe the slot array in groups with SIMD #178
Description
Activity
- added a commit that references this issue
on Sep 1, 2026 The control run is in, and the answer is more interesting than a straight no.
The problem with the first measurement was that it changed two things at once. The group probe branch sized the slot array exactly at three quarters load, and main rounds up to a power of two, so at a million members main allocates 2.09 million slots and runs at 0.48 while the branch ran at 0.75. Measuring those together measured neither.
elem-group-probe-pow2is the group probe withnext_power_of_two()put back, which works because the group probe scales homes rather than masking, so it runs at any array size. That leaves the group probe as the only difference.Three interleaved passes on gamingpc, taken as medians, and every row below is reproducible in the same direction on all three.
The read path is worse.
probe_hitat a million is +12 to +14 percent,probe_miss+21 to +24 percent,write_over+8.5 to +9.2 percent, andwalk+10 percent. That is consistent with what the group probe actually does: it loads a whole group of eight and does SIMD work on it, where a linear probe on a table at 0.48 load usually finds what it wants on the first slot it touches. Paying for eight to look at one is not a trade that pays when one is nearly always enough.The bulk paths are better, and by a lot.
fillat a million is 12 to 19 percent faster andpopis 19 to 24 percent faster, on all three passes. That makes sense too: an insert is looking for a free slot rather than a specific one, and a group of eight either has a free slot or it does not, which is one load and a mask instead of walking slots one at a time.So the group probe is not slow, it is aimed at the wrong operation. The gate rows are the read rows, and those are the ones that lose, so this does not go in as it stands and #175 stays where it is.
What the split points at is the untested alternative, which is a separate byte wide tag array rather than tags packed into the slots. Sixteen tags in one 128 bit load, and the slot itself untouched, so a hit costs one tag load plus one slot load and a miss costs one tag load and nothing else. That keeps the group win on the paths that scan without making a single lookup pay for eight slots it did not want. It also costs less memory: 5 bytes a slot against main s measured 8.39 bytes a member.
Leaving this open, retargeted at the tag array rather than at the packed group probe. The branch and the numbers stay so the next attempt has a baseline that already separates load from probe shape.
Measured, on two machines, and it does not work. The branch is
elem-groupsat 5fc2ca1, kept for reference rather than opened as a pull request, because the number this was for says no.What was built
Groups of eight slots, aligned to a multiple of eight so a group never straddles a cache line and never wraps.
find_hashed,put_slot,clear_slot,slot_ofand the placement loop ingrow_toall ask their question of a whole group at once, through one primitive,mask_eq(group, keep, want), which answersslot & keep == wantfor eight slots and returns a bitmask. The four questions the table asks are that one primitive with different constants: a tag match iskeep0xFF000000, a row match iskeepROW, an empty iskeepEMPTY, and a free slot iskeepROWagainstROW. Written by hand for SSE2 and NEON, with a portable loop for everything else and for Miri, and a test that runs random groups through both and checks they agree.The first version was written portably in the hope that LLVM would vectorise it. It does not. The disassembly on aarch64 was eight scalar compares, eight selects and a chain of ors, which is strictly more work than the short linear probe it replaced, and the measurement agreed before the disassembly was read. The numbers below are the hand written version, whose assembly does contain
cmeq.4s,ldr q,and.16bandaddv.4s.The numbers
Six alternating rounds per machine, minimum of the six taken per benchmark, since noise only ever adds time.
drawis the control: it indexes the row array and reads, and never touches the probe, so it says whether the machine held still.Apple M series, aarch64, NEON:
bench before, ns after, ns change probe_hit/1000 10.446 10.292 -1.5% probe_hit/100000 15.258 16.453 +7.8% probe_hit/1000000 13.821 15.126 +9.4% probe_miss/1000 7.670 9.319 +21.5% probe_miss/100000 7.645 9.056 +18.4% probe_miss/1000000 7.685 9.968 +29.7% draw/1000 4.177 4.065 -2.7% draw/100000 4.095 4.085 -0.2% draw/1000000 4.219 4.256 +0.9% i9-13900K, x86_64, SSE2:
bench before, ns after, ns change probe_hit/1000 9.283 9.826 +5.8% probe_hit/100000 12.900 13.272 +2.9% probe_hit/1000000 23.937 26.341 +10.0% probe_miss/1000 5.937 7.130 +20.1% probe_miss/100000 6.455 7.992 +23.8% probe_miss/1000000 6.821 8.296 +21.6% draw/1000 3.480 3.495 +0.4% draw/100000 3.557 3.586 +0.8% draw/1000000 5.379 5.528 +2.8% Two architectures, two vector instruction sets, the same sign and roughly the same size, with a control that moved by a few percent at most. This is not noise.
Why the premise was backwards
The issue said the tag already sitting in the top eight bits of the slot makes this free, because nothing has to be added to the layout. That is exactly what makes it not work.
A Swiss table's group is sixteen control bytes, one per slot, in one sixteen byte load, and one instruction turns that into a mask. Here a slot is four bytes, so eight slots are thirty two bytes, which is two loads, two ands, two compares and two masks that then have to be stitched together. Four times the bytes for half the slots is eight times the metadata traffic per slot examined. The win in a Swiss table comes from the control bytes being a separate dense array, not from the tag existing.
On aarch64 it is worse again, because NEON has no movemask. Each half needs an and against a vector of bit weights and then an
addv, which is a horizontal reduce, and both of those sit on the critical path between the load and the branch.And the thing being replaced was already about one step long. At a ceiling of three quarters with a tag byte, a linear probe looks at roughly one and a half slots on a hit and two and a half on a miss, and those slots are almost always in the same cache line. The module already claimed a probe is one load and it was telling the truth. Group probing does not shorten a probe that is already about one. It widens the one step and pays more for it.
Where the miss number comes from
probe_miss is the largest and most consistent column, at plus twenty to plus thirty on both machines, and it is not the compare. It is removal. One slot at a time, a removal can hand the slot straight back whenever the slot after it is empty, because then no probe ever ran past it. A group has to see an empty somewhere in the whole group before it can do the same, so a group that filled up leaves a marker behind, the array carries tombstones it did not carry before, and every miss walks them. The compare got a little worse and the array got dirtier, and the second one costs more than the first.
What to do instead
The memory this issue is really after is 1.8 bytes a member, and about 1.3 of it is the growth factor rather than the ceiling. The argument for doing groups first was that a growth factor under two makes the slot count not a power of two, a non power of two cannot mask its probe, and the fastrange multiply that replaces the mask is only affordable amortised over eight slots.
That argument needs redoing now, because it was resting on groups being a win. A fastrange is one sixty four by sixty four multiply and a shift, which is a few cycles, on a path that measures between six and twenty four nanoseconds. It is not obviously unaffordable one slot at a time, and the way to find out is to measure it one slot at a time rather than to assume it needs a group.
So there are two things worth trying, in this order. First, the growth factor on its own, with fastrange and a linear probe, which is where nearly all the memory is. Second, if the compare is ever worth revisiting, a separate control byte array, one byte a slot, sixteen slots a load, which is what a Swiss table actually has. That costs a byte a slot on top of the four already there, which is a memory regression in a change whose whole purpose is memory, so it has to earn it, and given what is above it starts a long way behind.
The element table's slot array is one
u32a slot, open addressed with linear probing, and #175 tried to make it cheaper by shrinking it. That does not work, because the memory a slot array costs and the length of a probe through it are the same number seen twice. Slots per member is one over the load factor, and an unsuccessful linear probe costs about half of one plus one over the square of one minus the load. You cannot spend less on the array without running hotter, and you cannot run hotter without probing further. The A/B on #175 is that sentence in numbers: a quarter of the memory back, and probe_miss up between fifty and ninety percent, fill up fifty six and pop up a hundred and forty five.The way out is to stop making the probe more expensive as the load rises, which is what group probing does.
What is already there
A slot is not a bare index. It is a tag in the top eight bits and a row index in the low twenty four, which is what #174 landed. So the tag byte a Swiss table needs is already sitting in the slot, in the right place, at no extra cost. Nothing has to be added to the layout to do this.
The shape
Load eight consecutive slots into one 256 bit register, mask with
0xFF000000broadcast, compare against the wanted tag broadcast, and take the movemask. That is one load, one and, one compare and one movemask for eight slots, against eight dependent loads and eight branches today. An empty slot is its own sentinel and falls out of the same compare, so the stop condition comes free with the match.At a load of seven eighths, the expected number of groups touched on a miss is a little over one. Which is to say the probe gets shorter as the array gets smaller, which is the exact opposite of what happens now, and it is why a Swiss table can run where a linear probed one cannot.
What it is worth
Correcting the arithmetic this issue was opened with. It said 4.6 bytes a member at a load of 0.85, which is the number at the ceiling, and a table is only at its ceiling for an instant before it doubles. What matters is the average over the life of the table. Under doubling the load runs over half the ceiling to the ceiling, and the average cost works out at four times two ln two over the ceiling, which is 5.55 divided by the ceiling.
So today, at a ceiling of three quarters, the array costs 7.39 bytes a member on average. Raising the ceiling to four fifths takes that to 6.93. That is half a byte, not three, and it is worth saying plainly: raising the ceiling on its own is nearly free and buys nearly nothing.
The memory is in the growth factor, not the ceiling. With a growth factor of g the average is four g ln g over the ceiling times g minus one. At a ceiling of four fifths that is 6.08 bytes a member at g equal to one and a half, and 5.58 at g equal to a quarter more. Against 7.39 today the whole win is 1.8 bytes a member, and about 1.3 of it comes from the growth factor rather than from the ceiling.
The reason it has to be done in this order anyway is that a growth factor under two means the slot count is not a power of two, and a table that is not a power of two cannot mask its probe. Group probing is what makes that affordable: the group is picked by a fastrange multiply instead of a mask, and the probe steps a group at a time with a compare against the group count instead of an and. Under one slot at a time that multiply would sit on the hot path of every lookup for nothing. Under group probing it is amortised over eight slots.
1.8 bytes a member is not most of what M3's memory row is short by. The gate says forty and a half bytes a member on the SADD shape against a bar in the low thirties, #174 took four off and #177 took two off the hash shape, and this is worth under two more. The rest has to come from somewhere else.
What has to be worked out
Portability. The engine builds for x86-64 and aarch64 and the CI matrix has all three platforms, so this needs a scalar fallback that is at minimum no worse than what is there today, and the group width has to be a constant the fallback also honours. Runtime detection on x86-64 rather than a build flag, because the release binaries are not built per microarchitecture.
The tag is eight bits, which means one match in two hundred and fifty six is a false positive that costs a row read to reject. That is the same rate a Swiss table lives with and it is fine, but the tag has to be derived from a different part of the hash than the bucket index or the two correlate and the false positive rate goes up in exactly the buckets that are already full.
Deletion. Backshift deletion is what keeps a linear probed table's runs short and it does not survive group probing, so this needs tombstones, and tombstones need a rebuild trigger of their own or a table that is churned in place degrades. That is the part of this with real design in it.
Growth. The fastrange mapping from #175 comes back on top of this rather than on its own, as a second change measured on its own, because that is the one that actually carries the memory. Wrapping has to change with it: a linear step over groups with a compare against the group count, because the triangular sequence only covers every group when the group count is a power of two. The home group a row remembers has to move too, since it can no longer be recovered by masking, and the tag has to move off the top of the hash to somewhere the group index does not read.
Part of M3 (#4).