3 ms·
This has the whiff of someone discovering the basics of high-performance locking. For e.g. other long-standing mutex implementations have spin/pause,sleep strat
by jeffbee 4y ago
This has the whiff of someone discovering the basics of high-performance locking. For e.g. other long-standing mutex implementations have spin/pause,sleep strategies. See Go's mutex, absl::Mutex, and others.
One problem with the x86 pause instruction is the number of cycles spent paused has varied dramatically from one CPU to another. Some CPU models ignore it. On others it is very short, a few or ten cycles, and on some it is hundreds of cycles. So you need a startup calibration that measures it, otherwise it will have a random outcome.
- rockdoe 4y agoThe problem is that these are the locks in the memory allocator, so they cannot allocate any memory. Most high performance implementations don't need to operate under that limitation.
- jeffbee 4y agoThat doesn't strike me as much of a constraint. TCMalloc's transfer cache and global page heap are protected by Abseil locks and this doesn't seem to have caused a circular dependency crisis.
- BeeOnRope 4y agoMany high performance locks do not, fundamentally, need to allocate memory. If they do, it is often for: 1) optional features such as statistics tracking or diagnostics (e.g., the ability to traverse all held locks in the process) 2) A space optimization to keep the lock object very small if uncontended, only allocating ancillary data structures on the heap needed to block at the OS level when contention is detected. You can easily avoid this: don't support (1) in your specific malloc lock, and don't apply the optimization (2): just put those fields in the main structure. In any case, no fancy lock is needed either: really they just want a vanilla "userspace aquire + userspace limited spin + fallback to OS blocking primitive" which is pretty much strictly better than their "userspace aquire + forever spin" existing lock. I don't think this is hard to do at all unless the OS-level locking primitives are very strange on OSX.
- FartyMcFarter 4y ago> One problem with the x86 pause instruction is the number of cycles spent paused has varied dramatically from one CPU to another. Some CPU models ignore it. On others it is very short, a few or ten cycles, and on some it is hundreds of cycles. Here's a previous HN discussion about that (in particular Skylake CPUs greatly diverging from previous behaviour): https://news.ycombinator.com/item?id=17336853 https://news.ycombinator.com/item?id=17336853 Original link: https://aloiskraus.wordpress.com/2018/06/16/why-skylakex-cpus-are-sometimes-50-slower-how-intel-has-broken-existing-code/ https://aloiskraus.wordpress.com/2018/06/16/why-skylakex-cpu...
- jeffbee 4y agoThat is good info! The very latest Intel "client" parts have UMWAIT, which allows a thread to sleep until the TSC reaches a given value, or monitored range of addresses is stored. It's the best of both worlds: a thread can arm the monitor using the address of the lock, and sleep for a defined time. If the lock is released the thread will wake immediately. If not, the thread will wake at a predictable time. This feature isn't widespread and very few libraries on github use it.
- cbsmith 4y agoI think you misunderstand the author's context. They are well of the various spin/pause/sleep strategies, and they have a specific one they need to apply to their allocator. They're just changing what OS interface to one that better matches the desired behaviour. While they are writing the article for readers who might not be as familiar with these issues, so they're doing a lot of explaining, the actual work they did, particularly exploring the semantics of os_unfair_lock_with_options (as opposed to os_unfair_lock), would potentially be informative to authors of those libraries (though likely not useful as they'd no doubt have requirements not to use private APIs that might keep an application from being made available in Apple's App Store). But the problem they're working on here isn't the calibration problem. It's about getting the spin/sleep/context switch semantics they want out of the OS.
- BeeOnRope 4y ago> This has the whiff of someone discovering the basics of high-performance locking. Came here to say this. > So you need a startup calibration that measures it, otherwise it will have a random outcome. I guess one question is if AMD or Intel plan to make any other CPUs with "fast" PAUSE. Looks like Intel has been consistently using the "slow" version since Skylake including on their little cores, while AMD has gone slow much more recently starting in Zen 2. A reasonable approach with "slow" PAUSE expected but still with large gen-to-gen variation in timing would be to base your spin on a time period, e.g., measured with RDTSC after every PAUSE, rather than a spin count, which should generally preserve the spin interval at least measured in wall clock time. This would have been a bad solution with "fast" PAUSE though since the cost of the RDTSC would have dwarfed the pause, so you might lose the "minimize load on the hardware thread" part of the PAUSE effect. Though I would question how good the "fast" PAUSE was at that anyway: perhaps RDTSC alone would be a fine substitute: it executes even slightly fewer uops/cycle than PAUSE on Haswell! It would be nice if slow PAUSE returned a cycle counter or RDTSC-like time counter to enable this kind of spinning. Or maybe UMWAIT just obsoletes all of these spinning approaches? I haven't gotten to play with it yet.