5 ms·
Fascinating. I had never considered sending signals to stop all threads and check their PCs as a synchronization technique. But it works, and it brings down the
by pcwalton 11y ago
Fascinating. I had never considered sending signals to stop all threads and check their PCs as a synchronization technique. But it works, and it brings down the uncontended lock acquisition and release time down to zero in the case where no synchronization needs to be performed.
Now I'm trying to think of other places to use this trick. :)
- rayiner 11y agoClozure CL and I believe SBCL do this in their GCs to allow threads to be stopped for GC preemptively while dealing with sequences that must be atomic (like allocation). Clozure calls it PC lusering: http://ccl.clozure.com/manual/chapter17.1.html http://ccl.clozure.com/manual/chapter17.1.html
- pron 11y agoIt's a take on kernel-mode RCU.
- 1amzave 11y agoYes, this essentially just a form of RCU. Note however that RCU isn't just for the kernel anymore though: http://urcu.so/ http://urcu.so/
- pron 11y agoUserspace RCU algorithms are experimental, quite brittle, and/or have little in common with RCU. They're certainly not usable as a production-ready scalable synchronization solution.
- 1amzave 11y agoI haven't actually used it myself and am certainly willing to believe it's immature, but how do you mean it has "little in common with RCU"? Comparing personnel between that library and this set of people --> https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/MAINTAINERS#n8218 https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.... there's certainly at least some authorship in common...
- pron 11y agoRCU basically works by having a critical section only within which a reader may access the data structure. To know when to GC the old copy of the data, you wait until all readers leave the critical section. If you're in the kernel, this can be very efficient: you disable all interrupts within the CS, so you know a thread is never preempted while in it. This means that no matter how many threads there are, only those currently running on the available cores (say, there are 8 of them) can be in the CS, so no matter how many threads there are, you only need to wait for 8, and you know that that waiting period is going to be short because there are no interrupts. So the efficiency of the algorithms stems from disabling interrupts within the reader's critical section, which can only be done in kernel mode (otherwise you could do really bad things). A similar algorithm in userspace will need to find another mechanism to wait for all readers to exit the CS, which may or may not be efficient. They may share then name "RCU", but not its desirable qualities. There are, AFAIK, several different algorithms calling themselves userspace RCU. One userspace RCU algorithm I've seen essentially protects the deallocation with a read-write, which isn't known for terrific scalability, but I don't know, they may have come up with something better. Garbage collection is the Achille's heel of all nonblocking data structures. As far as I know, there is no algorithm more efficient than a general purpose GC just yet, which is both generally applicable and efficient. Common authorship, BTW, says little. Most concurrent algorithms out there were invented by a handful of people.
- sbahra 11y ago1) Efficiency of algorithms stems from disabling interrupts The efficiency stems from having little to zero synchronization cost for readers in a read-mostly workload or workload that just isn't update-intensive. In addition to that, note that a deferral interface is available so writers basically never have to block until it is actually safe to free memory. URCU and ck_epoch all share those desirable qualities. 2) "RCU algorithm I've seen ... protects with a read-write" The synchronize portion of RCU and RCU-like systems is almost always heavy-weight. Applications that adopt URCU can typically afford this. 3) "no algorithm more efficient than a general purpose GC" All the blocking schemes are magnitudes more efficient but the trade-off is that it isn't generally applicable. However, they're still applicable for plenty of workloads. We are starting to see more GC mechanisms adopt SMR-like techniques so that may change. 4) "Common authorship, BTW, says little" Not in this case. If you would like to learn more about the performance trade-off with the various mechanisms, I suggest http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf and the URCU paper as a start. I've some additional numbers on something similar at http://concurrencykit.org/presentations/ebr.pdf http://concurrencykit.org/presentations/ebr.pdf Paul also has a good introduction up at https://queue.acm.org/detail.cfm?id=2488549 https://queue.acm.org/detail.cfm?id=2488549
- sbahra 11y agoWhat makes you say this? RCU refers to a wide array of reclamation implementations and some URCU implementations do indeed have a lot in common with kernel-space RCU (which also has a myriad of implementations). Speaking of liburcu in specific, the "brittleness" is a function of your workload and your selection of the URCU implementation. The various implementations have different trade-offs, and it is definitely possible to livelock write-side or degrade read-side if you make the wrong design decisions. For example, there are major differences between signal-based URCU and QSBR URCU. No reclamation mechanism (whether one backed by RCU or something like hazard pointers) is a silver bullet and each will suck in fantastic ways with the right workload. As far as userspace RCU algorithms in general being "experimental", plenty of people are using RCU or RCU-like mechanisms in user-space for production systems as a scalable synchronization solution. For example, the Concurrency Kit library (http://concurrencykit.org http://concurrencykit.org) has an RCU-like system called ck_epoch, and it sees at least billions of transactions in production a day without fail, and even supports freestanding environments.
- sbahra 11y agoConcurrency Kit (http://concurrencykit.org http://concurrencykit.org) also has ck_epoch. Performance comparison to the URCU implementations available at http://concurrencykit.org/presentations/ebr.pdf http://concurrencykit.org/presentations/ebr.pdf
- lgg 11y agoIt isn't actually stopping the threads. The thing to understand is that you don't need to ensure that all threads are outside of a critical section at the time you free the cache, what you need is the weaker guarantee that all threads have to have exited any critical sections they were in at the time of the pointer swap before you can call free. You don't have to do anything heavy weight like stop all the threads, instead you can just pull their PCs out and check them. Sure, they may have moved on (and even back into the critical section) by the time you call free, but it doesn't matter because they'll be using the new cache buffer. The downside is that you might get false positives for the critical section, but you can either run the dealloc in a loop or defer it and try again later.
- asveikau 11y agoNo, you pretty much have to stop them. If you observe the PC of other threads at a point in time while they are running, that is no guarantee that they aren't about to enter the unsafe region immediately after you make the check. Your suggestion sounds akin to replacing a mutex acquire with an "is the lock held?" [like trylock with 0 timeout, then immediate release]. Observing that it's unheld at time t makes no guarantee it won't be held by the time of your next instruction. It therefore becomes a meaningless check, not useful at all for real synchronization. [PS: mentioned this on HN before, but my favorite "observe the PC as part of a synchronization primitive" hack was this one from Linux on armv5: http://lwn.net/Articles/314561/ http://lwn.net/Articles/314561/] [PPS: How much does objc_msgSend() do inline and how much is external calls? This PC hack seems like it could have huge holes if some of its critical work is done in a non-inlined function.]
- dilap 11y agoHmm? No I don't think you have to stop them. Basically you have: cache = <newval> if ok() { free(<oldval>) } The problem you have is if anyone is still using <oldval> at the point you free it. So: // maybe someone here gets a reference to <oldval> (1) cache = <newval> // from this point onward no one can reference <oldval> if ok() { free(<oldval>) } So ok() only has to check if threads have a reference to <oldval> that they are still using. Imagine ok() pauses all threads. It sees if any threads threads are in BAD=[PC_BAD_START, PC_BAD_END]. If yes, return false, if no, return true. Now imagine PC doesn't pause the threads. What can happen? A thread that was in BAD leaves BAD. That's fine. A thread that wasn't in BAD enters BAD. But that will use <newval>, so that's fine too. That thread that was in BAD leaves BAD, and then reenters. That's also fine. So there's no problem. (re your question, I believe objc_msgSend is hand optimized assembly that doesn't make any function calls; if it did, you'd just have to make sure to include those functions in the range of bad PC addresses.)