The thread: The structure decides the count — page 4
An old key is a crowded key
A cuckoo table that makes room by kicking each full bucket's oldest resident keeps its newest keys at home and brings a lookup asked by recency to 1.04 reads, the cheapest design measured — but only at a cap of two kicks. At a cap of 32 it leaves 6.6% of its keys in overflow where random kicks leave none, and the explanation offered was a loop: an old key kicked to its other bucket is old there too, and the next chain moves it back. Sparing every key the chain has already moved changes nothing at caps of two and eight and makes cap 32 slightly worse, 7.1%; sparing the last sixteen insertions' moves gets it to 5.0%. There was no loop. A kicked resident's other bucket has room 22% of the time when the resident is chosen at random and 7% when it is the oldest: in a table that always moves the oldest, a key grows old because both of its buckets stay full. Kicking the older of four drawn at random keeps much of the gain at a long cap, 1.055 reads by recency and 0.5% overflow, and still costs more than the oldest kick at a cap of two.
What the machine doesA bit that remembers room
A cuckoo table that kicks each full bucket's oldest resident keeps its newest keys at home, but at long caps it fails because age is a stand-in for crowding: the oldest resident's other bucket has room 7% of the time. One bit beside each resident, saying whether its other bucket had room when last read, was proposed as a way to steer by room at no cost, and predicted to leave under 1% of keys in overflow at a cap of 32 for under five reads an insertion. The bit is not free. A blind chain reads only the bucket it kicks into, so the only bit it learns is that of the key it just moved — whose other bucket is the one it was just kicked out of, and full. A bit that says room has to be bought with a read of a fresh key's second bucket, about half a read an insertion. When the bit chooses, it is right three times in five; but it chooses for 40% of kicks at a cap of two and 4% at 32, where it leaves 5.2% of keys in overflow for 6.8 reads.