5 ms·
The Concurrent 2-Trie
- aidenn0 7y agoCan someone point me to a glossary for the jargon "acquire, release, plain" access semantics? [edit] It does seem to be a general term, but given that TFA is about a Java program, see http://gee.cs.oswego.edu/dl/html/j9mm.html http://gee.cs.oswego.edu/dl/html/j9mm.html
- Avi-D-coder 7y agoI have not yet read the article, but those terms usually refer to C11 memory ordering semantics. The Rust docs on atomic orderings are pretty readable. https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html https://doc.rust-lang.org/std/sync/atomic/enum.Ordering.html
- aidenn0 7y agoThanks, that led me to: https://doc.rust-lang.org/nomicon/atomics.html#acquire-release https://doc.rust-lang.org/nomicon/atomics.html#acquire-relea... which has an even better description.
- erik_seaberg 7y agohttps://www.kernel.org/doc/Documentation/memory-barriers.txt https://www.kernel.org/doc/Documentation/memory-barriers.txt has a pretty concise explanation of acquire/release. Basically core1 core2 --------- --------- acquire x write x release x acquire x read x release x guarantees that core2 will read core1's value for x, yet is less expensive than fully flushing both caches. Without the memory barriers, the write could be moved down the timeline (queued for writeback) and the read moved up (served from cache) so that core2 doesn't see what core1 wanted to write.
- cryptonector 7y agoA few comments. First of all, this is fine for a densely packed, growable "array" of things indexed by small integers. Think of things like a file descriptor table indexed by FD number and mapping to an open file handle. But this is not a generic hash table indexable by strings. Second, the hard part here is that readers that have obtained an about-to-no-longer-be-current root need to be able to use it to completion, while writers of new roots need to be able to ensure the eventual freeing of old roots when no readers remain who have a live reference to an old root. This is particularly tricky to get right -- it's the sort of thing that in the Linux kernel gets done with RCU, but RCU in userland is not portable. That's not to say that there aren't solutions. I've implemented something like just that piece with a generic API in[0]. [0] https://github.com/cryptonector/ctp
- jsnell 7y agoThe system they're describing is written in Java, so I think they trust the GC to take care of that.
- cryptonector 7y agoAh, yes, neo4j -- the 'j' means Java, and that's fair, but a concurrent GC is an assumption worth stating!
- ot 7y ago> RCU in userland is not portable Portable implementations are possible by using thread-local integers. There's one in Folly for example.