News for hackers. Stuff that matters.

sporadicity

Re:Optimizing Open Addressing on Sunday April 02, 2023 @10:47PM (#35417943)
Thanks for the great write-up! I have one quibble with your implementation of quadratic probing though: the usual index function used for quadratic probing is start_index + (i + i^2) / 2. This is the sequence you get by adding one to your start index, then adding two the next time, then adding three, etc., so you can avoid performing any actual multiplication by just adding one to the stride on every failed probe. Furthermore, this sequence has the useful property of visiting every index once before returning to the start, if your table size is a power of 2, so you could remove a check from your inner loop.
Re:Optimizing Open Addressing on Sunday April 02, 2023 @02:40PM (#35413749)
Have you tried absl::flat_map? It uses simd in a different way than described in this article, and Google claims that it saves them a lot of memory because it still works pretty well at 90-95% occupancy.