On mutex performance and WTF::Lock
blog.mozilla.org
blog.mozilla.org
https://blogs.msdn.microsoft.com/larryosterman/2004/09/24/cl...
(I am kidding)
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?
I have a simple benchmark that loses performance the more you parallelize it beyond 4-6 cores, until eventually it becomes slower than the single-threaded case [1]. And contention on that is not actually that high. That's still better than the macOS case, where performance goes to hell for even two threads, of course.
Here's the output of time for 32 threads (running on a 48-core system):
./a.out -p 32 7.72s user 75.04s system 2603% cpu 3.179 total
./a.out -p 0 1.94s user 0.00s system 99% cpu 1.942 total
In short, you do not want a high degree of contention, anyway. The macOS locks just make contention hurt much more.
[1] https://gist.github.com/rbehrends/27a1ca27ddec7016cd42428b9c...
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.
Windows locks are fair by default too, BTW (IIRC anyway). People just use the unfair version when they need performance.
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.
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.
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.
Clearly some people do or OS X wouldn't do it.
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).
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.
I think an unfair or opt-in-fair solution was deemed worse than fair-by-default for the simple reason that the most straightforward way to implement mutexes is
enter kernel mode
maybe grab a spinlock if on SMP
add yourself to the waiting list
sleep until woken up
do critical section
enter kernel mode
spinlock
wake the first waiting thread
Since we are talking about a uniprocessor desktop OS developed in the nineties, it's plausible they didn't care about mutex performance as much as today and giving this extra guarantee afforded by their simple implementation seemed reasonable at the time.
Fair point, although that still won't rule out applications that get updates (and thus still would have to be completely re-evaluated on the basis of such a case).
Also, wouldn't e.g. Homebrew also get those problems if you compile against the new SDK? (Non-Mac user here, so maybe I've got the wrong impressions on that...)
> I believe they intentionally go with fair-by-default because it's the safe choice [...]
Safety might be a big concern, but on the other hand, pthreads is a standard - if the article's right, and POSIX doesn't mandate fairness, you might still argue that this "addon" was better put into a custom solution than the other way around.
Then again, I've always suspected that strange implementations (or a total lack thereof) of POSIX must be one of the main reasons why Boost exists...
Yes, but nearly all Homebrew software is cross-platform unix software, so that software will already have to deal with having unfair mutexes on Linux.
> … pthreads is a standard - if the article's right, and POSIX doesn't mandate fairness …
It doesn't mandate fairness, but it doesn't mandate unfairness either. Apple platforms defaulting to fair is no less conforming than Linux defaulting to unfair.
Of course, but it makes it less performant in many situations, while you can't count on that feature if you're coding against the standard (i.e. if for cross platform development; hence OP's blogpost). Which - in turn - explains why people are complaining about the performance, since they need to guarantee the fairness themselves anyway if they really need it.
On the other hand: If you're only coding against OSX, having the fairness in an extension shouldn't be a problem anyway.
Of course, this then facilitates other problems, if the standard is not evolving fast enough (the whole OpenGL extension mess would be a good example).
In general, when picking defaults and choosing between "correct" or "performant", the decision is usually made in favor of "correct", because incorrectness should always be an opt-in thing. I'm actually kind of surprised Linux and Windows default to unfair locks.
POSIX is more of a common denominator than a good choice in many usecases (you'll never get far if you're dealing with complicated file handling for example[1]), but it is an essential baseline for cross-platform development. If you're changing too much about it, you're burdening cross-platform devs to do system-specific implementations anyway, so there's not much point to it.
As a flipside, you'll also get devs who see a guarantee on one system, assume the standard guarantees it, and then make statements about their library that are untrue (i.e. "WTF::Lock is fair").
Conformance with a standard doesn't just happen on a whim - if you negate the benefits that come with having a standard in the first place, any criticism you'll get as the provider of said API you brought on yourself.
Edit: Also, I have to say: I really don't like the attitude of "there are other use cases, so the one you are referring to when voicing criticisms is invalid". This has never been a constructive use of anyone's time. As I said, there are very valid reasons for why the API works as it does, but that doesn't invalidate the argument that the basic decision might not have been the best one to begin with.
> Conformance with a standard doesn't just happen on a whim
I genuinely don't understand what argument you're trying to make here. Apple is in compliance with POSIX. You seem to still be arguing from the position of "Windows and Linux behave in a certain way, therefore that way is correct", which is, quite frankly, bullshit.
The original point was: Apple uses fair mutexes by default, and that slows down any algorithm not needing that feature. Your point was: But it is still correct, and yes it is. But it's also still slow, and anyone pointing that out is as much in the right as you are when you refer to correctness.
Apple then introducing an out-of-standard solution (os_unfair_lock) for that (which is the exact duplication you talk about) is also just as suboptimal and worthy of criticism, since it torpedoes the whole reason for the existence of the standard (i.e. you still get #ifdefs or unnecessary abstractions all over the place). And - as I said - I get that no-one would ever want to change an implemented default behavior in their OS, but that doesn't make the situation any better.
Something similar happened in Microsoft's C++11-implementation of std::regex: The library uses strongly recursive function calls and might even cause stack overflows on various (not all that complicated) patterns in some scenarios. That doesn't make the implementation not correct (every regex implementation has its limits, and it never produces invalid results), but it makes it a hell of a lot less usable for non-trivial problems.
So, you can harp on on the correctness thing as long as you want, but you might consider not ignoring valid arguments before throwing words like BS around. "This implementation might be better" is not BS. Aggressively misinterpreting statements can be, though.
Given that POSIX does not define a way to select between fair and unfair locks, having any way to do that is by definition not a standard. Your argument against Apple having a way to get unfair locks is just as much an argument against Linux/Windows having a way of getting fair locks (assuming they even have that! I sure hope they do). And in any case, you don't need to #ifdef all your code everywhere to use os_unfair_lock, you just need to #ifdef a single line where you call pthread_mutexattr_setpolicy_np().
> I get that no-one would ever want to change an implemented default behavior in their OS, but that doesn't make the situation any better.
I recognize that having different behaviors on different OSes is suboptimal. The problem is you continue to imply that macOS's behavior is wrong, with the only justification being that Linux and Windows both behave differently. And I do not accept that argument. I'm also not convinced that this is really a big problem anyway. Fairness in locks is probably a little more important on Apple platforms than other platforms because of the QoS system. If you have an unfair lock that both the main thread and a "utility" thread use all the time, the utility thread will probably get starved since the main thread has a much higher QoS. So it's good that Apple platforms default to fair locks, because thread starvation is pretty bad. Personally, I think Linux and Windows platforms should default to fair locks too, with unfair-but-fast being opt-in, but that's an argument I've already made.
> but you might consider not ignoring valid arguments
Once again you are being offensive.
> Aggressively misinterpreting statements can be, though.
And even more offensive.
Seriously, if this is how you're going to argue, I don't see much point in continuing. You're providing fairly weak arguments in favor of all platforms should be the same, without recognizing that the platforms may have reasons for behaving differently, and constantly trying to imply that Apple platforms should be the ones to change while providing literally no reason whatsoever why that change should happen instead of Linux/Windows changing. This is not a compelling argument. And you keep insulting me at the same time, and I genuinely don't understand why you think that's going to change my mind.
Seems like we get the same vibes from each other; I have to point out though that I'm actually trying to be civil here. I honestly can't see where you are getting various of your implications from - I can't agree with half of what you state I'm implying here. Intended offensive statements would look different than that one.
So be it - we most likely both have more productive things to do. Maybe we'll have a more constructive discussion on something else someday.
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.
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.
[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.]
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.
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.
Is this true? I do not want to have to pay to read the standard