8 ms·
On mutex performance and WTF::Lock
- quinnftw 10y agoI'd be interested in seeing the rational behind the fairshare policy. I suppose theoretically the firstfit policy could result in starvation via one thread constantly preempting another during the lock contention, but I don't imagine that would happen very often in practise.
- alain94040 10y agoStarvation is a serious problem. Imagine two cores both trying to get a lock. The lock is held by a cache line in one of the cores. If both cores try to get the lock very often, the core further away may very well never get the lock. The synthetic benchmark results don't show that because they behave nicely: each thread waits politely in between each attempt to get the lock. Real code doesn't always do that.
- eternalban 10y agoEven if they get the lock, task latencies will be all over the place with seriously high latencies in the high percentiles.
- ajross 10y ago> Imagine two cores both trying to get a lock. The lock is held by a cache line in one of the cores. If both cores try to get the lock very often, the core further away may very well never get the lock. If that were true, then your problem is L2-cache-bound and trying to fit your solution into SMP is the Wrong Thing. In fact, the single-threaded behavior you end up with is going to be faster (by definition!) than the "fair" architecture you seem to want. No one serious thinks this behavior of the default locking primitive is a good thing. Maybe (maybe) it's a good fit for some particular problem somewhere, but I'd want to see a benchmark. It's definitely not a consensus opinion among people who do serious thought about synchronization.
- eridius 10y ago> No one serious thinks this behavior of the default locking primitive is a good thing. Clearly some people do or OS X wouldn't do it.
- 59nadir 10y agoWould it be the first badly implemented thing in OS X?
- eridius 10y agoMutexes are heavily used and get a lot of scrutiny, and work was done to speed them up when 10.11 (or was it 10.10? Whichever one added QoS) came out. I'm positive the people who maintain it are aware of the tradeoffs between fair and unfair locks and made the default fair intentionally. Or more generally, just because Linux and Windows both behave in a certain manner doesn't make that de facto correct. It's all tradeoffs, and different people value different things. Correct-by-default (i.e. fair locks) is valuable, the only question is whether it's worth the performance hit (although you can always opt in to unfair locks to get better performance).
- btschaegg 10y ago> I'm positive the people who maintain it are aware of the tradeoffs between fair and unfair locks and made the default fair intentionally. I think you're neglecting a couple of less-technical factors here. Yes, fairness was certainly made the default for reasons at some point (but still, even then, one might argue that an opt-in solution might have been better). On the other hand, there's the likely possibility that those reasons don't really hold true anymore. Think of Scene Graphs vs. Entity Component Systems in high-performance videogame design - in this example the rise of caching made a whole architecture out-dated. On the other hand, like removing the GIL in Python, such decisions are not to be taken lightly because of the things you will break. It's very likely that there are applications that would still have problems with starving threads, and just switching from opt-out to opt-in will make them break for no apparent reason in the strangest of circumstances. I know, Apple likes to break things more often than MS, but I'd guess that´s not a risk they're willing to take. Imagine you're updating your OS and a dozen apps that worked for a decade and don´t get updates anymore start behaving strangely. So, it's not unreasonable to settle for a less-than-optimal solution that still keeps things working and only makes things slower in the worst-case scenario. That doesn't mean it's not open to criticism, though.
- wbl 10y agoWhy are two threads trying to get the same lock very often? This seems like a design flaw: you want threads to mostly be uncontended, with lots of time spent outside locks.
- socmag 10y agoabsolutely, I totally agree.
- socmag 10y agoIn my personal experiences I've seen quite the opposite. Specifically, this kind of starvation mostly occurs only in synthetic lock benchmarks. In the real world, cores should be actually doing work in between spinning on cache-line locks; and the time before they get back to locking should be fairly random by quite a reasonable number of cycles - which tends to largely mitigate the starvation issue you talk about. Basically, if you have code that is structured to by default sit on spin-locks, there is likely an architectural issue in play. I'd go with the other contributor who said something along the lines of "the best policy is to go with the fastest lock possible", unless there is some very niche reason not to.
- dom0 10y agoStarvation and similar problems have plagued software using locks for a long time. A prominent example which is well documented may be the various problems of the GIL implementation when certain workloads are applied (easiest example is one I/O bound thread and one CPU bound thread, which is also a typical real world scenario - ouch!) [It should be noted that it is commonly rejected that the GIL is a scheduler, acts like a scheduler or should be a proper scheduler; all of which are untrue. Many locks are used as schedulers as well, which is especially true for a lock that controls execution of any and all code.]
- hyperpape 10y agoHe doesn't give a lot of details, but somewhere in the first 20 minutes of this talk (probably 15 minutes in), Cliff Click says that Hotspot had to create fair locks in user-space because kernel provided locks weren't adequate. https://youtu.be/Hqw57GJSrac?t=341 https://youtu.be/Hqw57GJSrac?t=341
- foepys 10y agoThank you for the video, very interesting. The time for what you mentioned is here: https://youtu.be/Hqw57GJSrac?t=1104 https://youtu.be/Hqw57GJSrac?t=1104 (from 18:24 to 24:00)
- taeric 10y agoIts funny that he throws out the "painful" learning of "don't trust the OS." I don't disagree, but it seems that the main learning should be "know your assumptions." Consider, this just moved up the stack. A good mantra for developers on the JVM is "don't trust the VM." Obviously, at some level you are trusting them, but you should also have measurements in place that would let you know which key assumption is failing. Yes, this is easier said than done.
- rogerbinns 10y agoDo remember that current CPUs can dynamically run cores/hyper-threads at different clock speeds at the same time. Not to mention significantly mismatched performance ones (eg ARM big.LITTLE). If you didn't have fairness, and the developer hadn't carefully assigned threads to cpus based on performance / priority of the work the thread is doing (and locked the CPU clock speeds), then the higher performing ones will starve out the others. Fairness at least ensures that the developers writing simple straightforward code would get simple straightforward behaviour.
- gpderetta 10y agoThen again, if you are writing simple straightforward code you shouldn't be mucking around with thread priorities. In fact probably you shouldn't be dealing with raw threads and mutices in the first place but using some higher level abstraction.
- qb45 10y agoIt's probably a very old decision, from times when most desktop computers had one CPU and threads were mostly used to keep GUI responsive while the application was churning data in the background, so there was little interaction between them.
- saagarjha 10y agoFor those wondering, WTF stands for Web Template Framework: https://webkit.org/blog/6161/locking-in-webkit/ https://webkit.org/blog/6161/locking-in-webkit/
- cperciva 10y agoMy favourite mutex name is the "sex lock" -- also known as the shared/exclusive or sx lock.
- cpeterso 10y agoWindows NT has a kernel mutex type called a "mutant" that was added for compatibility with OS/2's mutex (back when the NT team was still pretending to be building a new OS/2 kernel). Dave Cutler thought the OS/2 mutex semantics were "brain-damaged" and called NT's version "mutant". If an OS/2 thread exited while holding a mutex, the mutex would remain inaccessible forever. https://blogs.msdn.microsoft.com/larryosterman/2004/09/24/cleaning-up-shared-resources-when-a-process-is-abnormally-terminated/ https://blogs.msdn.microsoft.com/larryosterman/2004/09/24/cl...
- pjmlp 10y agoThey would have, if a Microsoft employee hadn't figured out a viable way to use extended mode in Windows 3.x.
- 0xFFC 10y agoLike i am gonna believe that ;) (I am kidding)
- pizlonator 10y agoWTF locks now use a policy we call eventual fairness. You can barge but the amount of time anyone loses due to the barging race is bounded. https://trac.webkit.org/changeset/203350/webkit https://trac.webkit.org/changeset/203350/webkit
- obstinate 10y agoHard fairness guarantees for locking are very expensive and only situationally needful, so it's hard to justify paying a high cost to have them always on. It seems like the best thing to do is to use the fastest locking primitive you can find, and implement fairness on top of that in the rare case that you need it.
- pizlonator 10y agoEventual fairness costs nothing.
- obstinate 10y agoRight, I'm referring to the idea of immediate fairness. I'm agreeing w/ your approach.
- bogomipz 10y agoMight you have any good resources about hard fairness vs eventual fairness locking?
- pizlonator 10y agoIt's all in the commit.
- ajross 10y agoSo the takeaway here is apparently that POSIX mutexes on macOS/iOS are really slow due to an oddball design decision (fairness), and the browser vendors are racing to see who can reimplment them best. Windows and Linux do this just fine AFAICT. Seems like it would be more effective for the WebKit folks to just work on their Darwin compatriots to fix the C library locks, no?
- Jweb_Guru 10y agoFairness isn't an oddball design decision, it's an important assumption that many realtime systems rely on.
- ajross 10y agoIt's oddball in the sense that literally no one else does it. So I don't know what systems you mean, since by definition they don't run on Linux (glibc or bionic) or Windows. I'm not saying there's no use case for a fair mutex anywhere (though I'll come really close and say that if you want fairness a lock is the wrong abstraction), I'm saying that stuffing a context switch into every contended call to pthread_mutex_unlock() is a terrible design decision.
- Jweb_Guru 10y agoIf you don't need fairness, don't use a fair lock. The default assumption should be fairness because it doesn't require you to think (just like the default transaction isolation level should be serializable). As the blog post points out, OS X provides unfair mutexes too. Windows locks are fair by default too, BTW (IIRC anyway). People just use the unfair version when they need performance.
- striking 10y agohttp://www.pcdoctor-community.com/wp/posts/2007/10/fairness-in-win32-lock-objects/ http://www.pcdoctor-community.com/wp/posts/2007/10/fairness-... Windows XP tried to implement some amount of fairness in its locks but did not guarantee it. Windows Vista gave up on fairness entirely. You should just be using unfair locks. Thread starvation is rare in most OSes at this point.
- ricardobeat 10y ago> I don’t know how firstfit policy locks compare to something like WTF::Lock on my Mac mini As a layperson, it would have been nice to see at least some simple benchmarks substantiating what is being said, after several paragraphs trying to explain why WTF::Lock is not a good candidate, and given it's in the title of the post.
- leksak 10y ago> But fairness is not guaranteed for all OS mutexes; in fact, fairness isn’t even guaranteed in the pthreads standard Is this true? I do not want to have to pay to read the standard