Linus Torvalds (torvalds.delete@this.linux-foundation.org) on January 3, 2020 6:05 pm wrote:
> The whole post seems to be just wrong, and is measuring something completely
> different than what the author thinks and claims it is measuring.
>
> First off, spinlocks can only be used if you actually know you're not being scheduled
> while using them. But the blog post author seems to be implementing his own spinlocks
> in user space with no regard for whether the lock user might be scheduled or not. And
> the code used for the claimed "lock not held" timing is complete garbage.

Hi, original author here. First of all, I'd like to point out that I actually think we mostly agree on the spinlock vs mutex discussion. My original point of this was to try to find benchmarks that show that mutexes should be preferred over spinlocks. It then accidentally turned into an investigation into the Linux scheduler, but what can I do? If the data leads that way, I have to follow. I just had to investigate giant outliers like that.

So I think we agree about the guidance on spinlock vs mutex. (so I'll skip on responding in detail to most of your text) The problem is that people use spinlocks. In video games they're quite common. Why is that? Because most simple benchmarks will show that spinlocks are better. I linked to three of those benchmarks near the top of my blog post. So it's nice to say "you shouldn't use spinlocks" but good programmers will verify those claims, and if their benchmarks show otherwise, they'll use spinlocks. Before my blog post I had a very hard time finding guidance that actually backed up the claim "you shouldn't use spinlocks" with benchmarks. Part of my goal was to provide that.

I think the part where we disagree is in whether I showed that the Linux scheduler is problematic or not. Is this a valid benchmark?

> So now you still hold the lock, but you got scheduled away from the CPU, because you had
> used up your time slice. The "current time" you read is basically now stale, and has nothing
> to do with the (future) time when you are actually going to release the lock.

Right so this is a hard thing to measure, but this is the best thing I could come up with, so give me a chance to defend it: There are three cases where a large amount of time can pass between the "end time" and the "start time":
1. if the lock actually sits idle and nobody takes it.
2. (the one you're mentioning) the thread holding the lock takes a timestamp and then doesn't actually unlock the lock before being scheduled away.
3. a thread takes the lock and gets scheduled away before taking the initial timestamp.

To reason about whether this distorts the measurements or not, let's talk about the ticket_spinlock, because in that one the behavior is exactly defined. There is potentially a thread holding the lock, (let's call it C for "current") and there is always one thread who is next in line. (let's call it N for "next") All the other threads will call _mm_pause() and yield() in a loop.

I think we both agree that case 1 was the thing I was trying to measure so if that happens we're fine and the measurements are correct. In that case the scheduler for some reason decides to not run thread N even though all other threads are calling yield().

In case 2 thread C is not being run by the scheduler. All fifteen other threads are calling yield(). Thread N is also calling yield(), and does not look special in this situation.

Case 3 is the same situation, thread C is still not being run even though fifteen other threads are calling yield().

Once we break it down like that we realize that actually these are all the same case. In all of these cases one thread can run, all others are calling yield(). The only difference between the case that I wanted to measure and the other two accidental cases is whether the scheduler is incorrectly not running thread C or incorrectly not running thread N. In either case all other fifteen threads are just calling yield().

So your claim is that it's a problem that I try to measure how long it takes for thread N to run even though I might accidentally be measuring how long it takes for thread C to run. But I claim that that's fine because these are all equally problematic. One thread could run, all other threads are yielding, yet that one thread is not running. And we don't care whether the thread that could run is thread N or thread C.

Of course I might also be measuring any combination of the above, like maybe case 2 turns into case 1, and potentially we even run into case 3 at the same time when we get a really bad interleaving and a really big outlier. But I think any combination is fair game when comparing schedulers, because I'm measuring the same thing on all schedulers.


If we think about it like this, it's really really bad that this measurement can take multiple milliseconds. It's not something I have ever seen before. My previous experience was on Windows, Xbox One (which uses a modified version of Windows) and Playstation 4 (which uses a modified version of FreeBSD) and none of them would ever show anything like this. If all threads but one are yielding, that one thread is definitely going to run. And no way would it take a millisecond for that to happen. (of course it usually doesn't take that long on Linux either, but if the outliers are too big, we really care about them)

Thanks for responding, I really have a lot of admiration for you and your work, (and I would have wished that our first conversation wasn't this negative... but I can't change what I found)

Malte