freenode/#sicl - IRC Chatlog
Search
1:55:24
no-defun-allowed
Click's choice to keep keys "pinned" in entries makes reasoning about updates much easier.
1:58:40
no-defun-allowed
For example, one thread could be updating an entry, while another removed that entry, then replaced it with an entry with a different key but the same value. Then the former thread could CAS out the value, and end up with the new key with a value intended for the old key.
2:04:27
no-defun-allowed
The "insert tombstones only when group is full" concept is also hard to apply with multiple threads, as two threads inserting could fill a group, without either having observed that it was full.
2:40:28
no-defun-allowed
In general, Click states that there's no consistent state of the table, so it is unlikely that we can determine if a group is full.
4:06:36
beach
no-defun-allowed: Some day I will understand what you just wrote. But I haven't read up yet.
4:08:26
no-defun-allowed
In short, it may not be possible to use the linear probing technique concurrently, and Click's table *depends* on a property I was trying to get rid of (that keys stick in entries without copying).
4:10:07
no-defun-allowed
So my sketch for a mostly-concurrent fast hash table is probably broken in many ways. Oh well.
4:20:47
no-defun-allowed
I thought I had an idea to avoid weird state transitions, so that (for example) an update operation and a delete operation would occur sequentially, then I realised I had re-invented the spinlock.
4:21:13
beach
Designing a good data structure can take years. It took me 30 years to design what is now Cluffer.
4:38:24
no-defun-allowed
Although, locking whenever deletion is involved is better than eventually forcing a resize, so re-inventing spinlocking isn't the worst thing one can do.
4:38:57
no-defun-allowed
(At least to me, because the throughput of my program appears to plummet while a hash table is being resized.)
4:40:46
beach
I see a multitude of hash table implementations, each one adapted to a different use case.
4:40:50
no-defun-allowed
Or, at least, that my code stores information on where to retrieve objects in concurrent hash tables, and eventually deletes an entry after the latest version was found.
4:43:43
no-defun-allowed
As mentioned yesterday, for every other use case, Cliff's table is great. But not for mine.
4:45:38
no-defun-allowed
(And any attempts to "break up" that table haven't worked, because an efficient search, in my opinion, would avoid sending requests for all but the newest versions, and the "newest version" is a global property.)