freenode/#sicl - IRC Chatlog
Search
4:07:36
no-defun-allowed
Today I found out the new university has had an outage with approximately everything, due to a phishing attack, and that Cliff Click did a nice presentation describing how to design non-blocking data structures.
4:09:21
no-defun-allowed
The latter can be found at <https://www.dropbox.com/s/agrzifhhahva4kg/2008_CodingNonBlock.pdf> and it explains how one doesn't go mad with this kind of thing.
4:13:39
no-defun-allowed
Yes, and it also describes a concurrent bit-vector set as an introduction, and then a nearly FIFO queue.
4:16:32
beach
I envy Ira Baxter who started Semantic Designs maybe 20 years ago or so, when I spent my year in Austin. I "worked" for him briefly then. His company was based on the idea that multi-processor threading was going to be huge some day. He and his company must be way ahead of everyone.
4:18:29
beach
He created PARLANSE, a parallel programming language that superficially looked like Lisp.
4:25:06
beach
I think I need to either listen to his talk or find a more complete written presentation in order to understand this stuff.
4:27:17
beach
There seems to be important information in there about CAS failure and how now to design the API for CAS.
4:37:14
no-defun-allowed
That's news to me; I thought the RISC-V specification(?) said that CAS could livelock and not LL/SC.
4:37:18
Bike
"depending on the hardware's LL-SC implementation, though" according to some random google
4:38:26
Bike
C++ exposes a CAS that can spuriously fail and one that can't. i can imagine the spurious failure one being more efficient sometimes, but it's a bit arcane
4:41:33
no-defun-allowed
Speaking of, can you compare-and-swap a byte on AMD64? I only saw instructions for 8-byte and 16-byte CAS.
4:41:57
Bike
i haven't looked at the machine level much honestly, beyond one paper on the x86 memory model
4:42:33
no-defun-allowed
Worst-case is I have to emulate CAS for just that byte somehow, which is ironically almost what I do with the non-concurrent hash table.
4:43:18
no-defun-allowed
I found a thread about byte CAS on a Java implementation on ARM, where they mention that.
4:44:08
Bike
is there a reason for a byte CAS beyond saving space? like i guess if you also want to CAS the word as a whole or something
4:45:03
no-defun-allowed
To update the compact metadata table, which is supposed to be cache-friendly and also quite SIMD-friendly (when probing).
4:45:24
no-defun-allowed
ACTION goes to see what a C++ compiler generates for std::atomic<uint8_t> or something like that.
4:50:34
Bike
https://www.felixcloutier.com/x86/cmpxchg i'm still no good at reading these tables, but
4:52:42
no-defun-allowed
(In short, the metadata table stores 7 bits of a hash for each entry, so probing only leaves the metadata table every 128 bytes, provided we have uniformly distributed hashes.)
4:53:10
no-defun-allowed
(Oh, and that's 7 and not 8 because we use the last bit to mark empty or tombstoned entries.)
4:58:57
beach
no-defun-allowed: You should be in charge of SICL concurrency in general; not only for hash tables. I would recruit Bike as well, but I think he has enough with Clasp concurrency.
5:01:00
no-defun-allowed
On the contrary, I don't think I know enough about concurrency to be "in charge" of it.
5:01:40
no-defun-allowed
Same here, I just use the "be incredibly stubborn about getting it to work somehow" strategy.
5:02:30
Bike
and, well, i don't think you need anything complicated with concurrently for most applications. make-thread, join-thread, locks is probably fine for most people
5:10:48
beach
I have tried to "prepare" the data representation for better support for concurrency, but it is all based on hunches, and I haven't thought through the details.
5:12:04
beach
And then there is the issue about keeping a reference to the rack when that is "safe" to do.
5:38:54
no-defun-allowed
Though, I did write up another test suite for concurrent hash tables, this one simulating a bad knock-off of an in-memory database (such as Redis), which retrieves and stores stuff in a concurrent hash table. Luckless scales way better than my old segmented hash table at that.
5:41:55
no-defun-allowed
I think that is closer to the scenarios Cliff Click et al put concurrent tables in, as they don't remove anything. It's a bit funny, because I got the idea from a presentation where an Amazon Web Services spokesperson complained about stop-the-world pauses while implementing such a database. Writing to the database is one big memory leak, so if you didn't have to retrieve the values, then you could just never free
5:45:50
no-defun-allowed
Said person also used a non-concurrent hash table with a lock, had unnecessary copying, so I don't think they can talk, but I digress. I saw where that table design works best, and it's really good there.