Repository navigation
Conversation
The gate's SADD row lands on the worst case of power of two rounding and it is not a small one. Eight hundred and ten thousand members want one million and eighty thousand slots at the load factor. A masked table gives them two million and ninety seven thousand, so the array sits at a load of 0.39 and spends 10.4 bytes a member where 5.3 would do. That was the second largest thing in the structure after the names themselves.
A slot array is now exactly as large as the table needs. The index is a multiply and a shift over the twenty four hash bits a row already carries rather than a mask, which is the standard trick for mapping a hash into an arbitrary range, and it is what makes any size available. The three cycles it costs over an and go in front of a load that misses cache, which is the only reason the trade is there to take.
Growing follows the same policy the rows and the name blob already follow, which is doubling while the array is small and a quarter more once it is large. So the load runs between three fifths and three quarters instead of between three eighths and three quarters, and the array is rebuilt more often for a smaller step each time. A rebuild reads two flat arrays and hashes nothing, so it is the cheap half of a growth.
The twenty four bits also get simpler. They used to be enough only while the mask was narrower than they were, with a fall back that rehashed the name above sixteen million slots, and now they are enough at every size because the multiply scales them across the table rather than cutting them down to it. Every placement in the file goes through the one function, so the answer is always the one the insert gave. Past sixteen million slots some slots stop being anybody's home, which costs a little clustering on a table holding twelve million elements and nothing below it.
A sorted set promoting out of its listpack was rounding its own presize up to a power of two before handing it over. It does not need to any more.
Per member, on sixteen byte members, against main and against the row packing that went in ahead of this:
members main rows slots
1,000 36.96 32.83 30.18
100,000 43.53 38.72 34.84
1,000,000 42.11 37.23 35.09
On the gate's own shape, eight hundred and ten thousand members with memtier style names, a set went from 40.5 bytes a member to 30.8.
dc91a77 to
dde3720
Compare
|
Peak resident memory on server3, glibc, building a set of eight hundred and ten thousand members with memtier style names, which is the shape the gate's SADD row builds:
The structure is nearly four megabytes smaller, which is what the change was for, and the peak is nearly seven megabytes smaller, which is a second thing worth having. The gate scores the peak, not the structure, so the second number is the one that moves the row. The extra came from how the slot array grows rather than from how large it ends up. A doubling holds the old array and the new one at the same time, so the moment of the rebuild costs three times the old array. Growing by a quarter costs two and a quarter times, and it happens at a point where the array is smaller. That is the whole gap between a peak eleven percent over the structure and a peak one percent over it. Presizing the set instead of growing into it gives 24.12 MB of structure and a 24.19 MB peak, so a table that never grows at all is only three percent better than one that grows the whole way. There is not much left in this direction. |
|
The throughput A/B on gamingpc is in and it says do not merge this as it stands. Everything below is against
The walk rows disagree with each other in a way nothing in this change can explain, so read those two as noise. Everything else is real and the shape of it is clear once you look at what actually changed. I had this backwards in the description. The memory did not come from the multiply. A masked table and an exactly sized one both run at a load between three eighths and three quarters if they both double, because doubling an exact size starting from a power of two gives you powers of two again. The multiply buys nothing on its own. What buys the memory is growing by a quarter instead of doubling, which lifts the load to between three fifths and three quarters, and the multiply is only what makes a factor other than two possible. So the memory and the slowdown are the same fact seen twice. The mean load went from about 0.52 to about 0.67. An unsuccessful linear probe costs half of one plus one over the square of one minus the load, which is 2.3 slots at the first and 5.4 at the second, and that is the probe_miss column almost exactly. Insert walks the same run, which is half of fill, and the other half is rebuilding the array four times as often. Removal backshifts the run behind the hole, which is pop. Eight hundred and ten thousand members is a bad n for doubling and that is why the gate's SADD row looked so fat. It is not the average case, it is the worst point of the same distribution. The reason this matters more than usual is which rows it hits. From the last full gate run, SADD is 1.09x at memtier P16 and 1.25x at redis-benchmark P16, against a ten times target, and the CPU column says 85 percent. It is the thinnest throughput margin we have. A fill that is half again as expensive is not something to spend there.
The change that gets both rather than trading one for the other is probing the slot array in groups with SIMD, which is what a Swiss table does. Sixteen tags in one register, one compare, one movemask, and a load of seven eighths costs about one group probe. That would put the array at 4.6 bytes a member and make the probe faster than it is today rather than slower. Opening it as its own issue. |
The measurement first, because this is a memory change and the number is the point. On a set of a million sixteen byte members it goes from 37.23 bytes a member to 34.83, and on a hundred thousand from 38.72 to 37.03. That is 2.40 bytes a member at a million, which is more than the entire slot array plan in #178 is worth, out of a one word change to a growth factor. The reason it was a quarter and not an eighth was an argument about copies. An element is copied about five times over the life of an array that grows by a quarter and about nine times for one that grows by an eighth, so an eighth looked like it was buying memory with throughput. That count is wrong for exactly the arrays this policy applies to. A growing array is grown with realloc, and past the system allocator's mmap threshold the block is its own mapping, so growing it is a page table edit and not a walk over the bytes. glibc does that with mremap and macOS remaps the object. The cost stops scaling with the contents of the array and starts scaling with its pages. That is a claim about an allocator, so benches/grow.rs is here to check it rather than let it sit in a doc comment. It fills an array an element at a time through the policy at three sizes, one under the threshold and two over it, and beside each one a presized control that pays for a single allocation and no growth at all. The gap between a fill and its control is the whole cost of the policy. It also prints what the array is holding at the end, because quoting one side of a trade is how #175 went wrong. Set grew three accessors on the way, slot_bytes, row_bytes and name_bytes, and measure_bytes_per_member prints them. Elements and Parts already had the breakdown and Set did not, which meant the set measurement could say twenty one bytes a member of overhead without being able to say where any of it went. With the breakdown it can: at a million members the slot array is 8.39 of it, the row array 8.73 and the name blob 1.71 over the members themselves. Before this change the last two were 9.77 and 3.07, and that difference is the whole commit.
The gate's SADD row lands on the worst case of power of two rounding and it is not a small one. Eight hundred and ten thousand members want one million and eighty thousand slots at the load factor. A masked table gives them two million and ninety seven thousand, so the array sits at a load of 0.39 and spends 10.4 bytes a member where 5.3 would do. That was the second largest thing in the structure after the names themselves.
A slot array is now exactly as large as the table needs. The index is a multiply and a shift over the twenty four hash bits a row already carries rather than a mask, which is the standard trick for mapping a hash into an arbitrary range, and it is what makes any size available. The three cycles it costs over an and go in front of a load that misses cache, which is the only reason the trade is there to take.
Growing follows the same policy the rows and the name blob already follow, which is doubling while the array is small and a quarter more once it is large. So the load runs between three fifths and three quarters instead of between three eighths and three quarters, and the array is rebuilt more often for a smaller step each time. A rebuild reads two flat arrays and hashes nothing, so it is the cheap half of a growth.
The twenty four bits also get simpler. They used to be enough only while the mask was narrower than they were, with a fall back that rehashed the name above sixteen million slots, and now they are enough at every size because the multiply scales them across the table rather than cutting them down to it. Every placement in the file goes through the one function, so the answer is always the one the insert gave. Past sixteen million slots some slots stop being anybody's home, which costs a little clustering on a table holding twelve million elements and nothing below it.
A sorted set promoting out of its listpack was rounding its own presize up to a power of two before handing it over. It does not need to any more.
Per member, on sixteen byte members, against main and against the row packing in #174 that goes in ahead of this:
On the gate's own shape, eight hundred and ten thousand members with memtier style names, a set went from 40.5 bytes a member to 30.8. That is a twenty four percent cut and it puts a set level with valkey, whose implied number on the same row is 29.3.
Stacks on #174 and should go in after it.