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?
1:07:22
no-defun-allowed
As I can't rely on keys not to change without double-CAS, how terrible would it be to put a key and value in a CONS and then CAS those out of storage vectors?
1:09:44
no-defun-allowed
The main issues are that any metadata match incurs a "random" memory read, and it allocates a cons per update. But that may be preferable to eventually having to resize to remove tombstones.
1:12:04
no-defun-allowed
It could be done without that additional read with double CAS (or at least CMPXCHG16B, which can CAS two adjacent words), but may be a bit much to ask for.