freenode/#sicl - IRC Chatlog
Search
20:36:53
no-defun-allowed
I had an idea for handling a metadata table with a concurrent hash table. When adding a new mapping, if we have to use the next group, because the first is full, we set a bit somewhere indicating the first group was full, instead of trying to observe if the group is empty when removing, and CASing entire groups.
20:41:25
no-defun-allowed
This trick is an application of the "if a tree falls in the forest..." thought experiment, as we only track when a group is observed to be full. So a group that is filled, and then has some mappings removed, without another insert operation observing that the group is filled, will not be marked as filled.
20:46:50
no-defun-allowed
Around 47:26 in the Cppcon talk, Kulukundis discusses a group which fits into a cache-line, using 7 hash bytes, 7 presence bits, and 1 "ever full?" bit.
20:51:56
no-defun-allowed
Also, in the comments, he says he didn't see a benefit from using 32 byte groups (think 256-bit, AVX2 instructions) over 16. Implementing the latter group seems hard though, both with general-purpose instructions fooled into byte-parallelism and with SIMD instructions.
21:55:32
no-defun-allowed
Maybe one can compromise, with 1 byte for "ever full?" and n - 1 metadata bytes (as usual), to make a n-byte group. We waste most of a byte, but that's cheap for fast probing for a concurrent hash table, no?