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.
4:09:57
no-defun-allowed
I updated my description of the table <https://gist.github.com/no-defun-allowed/96070918bb433ec4219f3cec29a5844a> with these changes, and a diagram of what the vectors used look like.
4:12:14
Bike
does sbcl's SSE stuff actually work? it's exported from sb-ext but not mentioned in the manual that i could see
4:13:29
no-defun-allowed
I was able to get cl-simd to work...eventually. I forgot what patches that needed, but it also needed an older SBCL where effective addresses had sizes.
4:15:29
no-defun-allowed
heisig was also working on sb-simd, which might become a SBCL contrib package one day. Until then, it's somewhat possible to fake it with clever use of general purpose instructions; that's what the code I put in SICL does, and that is also what the "fallback" for the Abseil hash table does.
4:16:27
no-defun-allowed
(The "Probing" section has such code; which is not far off what's in SICL now.)
4:50:16
no-defun-allowed
beach: Would it be okay if I clarified that I have only implemented non-concurrent hash tables so far in the letter I am sending to university (eventually)? I can send back my changes if you'd like to check them.
4:51:22
beach
That's fine, you can do it. Just make sure the style is consistent, like US spelling and such.
4:54:03
no-defun-allowed
I say "eventually" as enrolment hasn't worked for almost a week now; even when classes start next Monday.
4:57:40
no-defun-allowed
The enrolment procedure has me pick a plan (of which there are two, I am picking the older one as the courses seem more similar to those at my old university) and then allows me to pick class times to attend.
5:00:26
no-defun-allowed
The credit form also states that the university will ensure I won't have debts from, or have fail marks for, courses I have applied for credit for, should I submit it before classes start. But that is impossible at this rate.
5:03:55
no-defun-allowed
That, and the servers got cracked. Now I read they hope to have it fixed by tomorrow.