Hacker News Reader

Hey, same Joe from Sun? If so, howdy.

On my i7-5930K I'm seeing 7-10 usecs, quite a bit better than a millisecond. Linus cares about this stuff, I'd be very surprised if he didn't measure it regularly.

Probably thinking of my brother, Rich?

usecs are a thousand times better than a ms of course. And a ns is a thousand times better than that!

> If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?)

Not for any real world workload. It's worth reading section 6.6 of this: http://mcvoy.com/lm/bitmover/lmbench/lmbench-usenix.pdf

but I'll try and restate it here. So what's a context switch? Lots of people think it is putting one process to sleep and waking up another process. Which is sort of correct. Let's look at what that means. "Sleeping" a process means I have to take whatever hardware context there is and store it away (int/float registers are the basics). "Waking" a process is the opposite, go find the stored state, restore it, and return (sort of like longjmp()) to the awoken process.

But that is the minimal context switch, that's what you would have if you had a yield_to(pid_t pid) system call and you had a tight loop where pid A yields to pid B which yields to pid A, etc. Do that a million times, measure the total time, divide by a million.

That's not real world at all. In the real world your context is more than your registers, it is also your cache foot print. Pid A wasn't just yielding, it was doing some work. When it comes back, it has to either get lucky (with the right kind of cache that can hold more than one process's cache lines, look up physically vs virtually indexed caches, Hennessey & Patterson cover this nicely) or it has to reload state from L3 or main memory.

That's what the lmbench paper goes into a lot of detail about this. People write benchmarks and don't think about the fact that there is more to life than benchmarks. lmbench's context switch benchmarks are done as a function ctx(int N_processes, int working_set). Most people would benchmark ctx(2, 0) but that's nonsense unless you care about the silly yield/yield numbers. I dunno about you but when I'm debugging a perf problem, in ~30 years of doing that I have yet to see a perf problem around yield/yield (well, sort of. Oracle's distributed lock manager was as close as I've seen but even it had a larger context than zero bytes more than the register store/restore).

The interesting questions are:

- are your caches set up for multiple processes so you still have state when you switch back? - how many different processes can you have in the cache[s] at once? - how big is your OS path to sleep/wakeup, that uses up space in the instruction cache?

The lmbench paper talks about all this stuff, complete with crappy graphs written in troff/pic by yours truly that let you visualize when things will fit and when things will thrash.

Ok it'll never be 1 clock cycle. But it sure can be better than milliseconds!

Where are you getting milliseconds? Their results are right in line with what I'd expect, on the order of ~10-50 usecs.

Ok I only read halfway through the document.

Even knowing some measurements are 10-50usec, that's still 10000X slower than a cpu instruction. So still room for improvement.

You do realize the relative order of things, right? While a CPU instruction is around 1/4 of a ns, assuming a single cycle instruction which is not always the case, a memory load is ~60ns.

In order to really see if there is room for improvement one would need to take a look at each cache miss and see if that could be removed. On my machine, a simple context switch is 7.3us and a memory load is 57.4ns which means a total of 133 cache misses.

Could that be better? Sure, in theory. Could it be 10000x better? Not a chance. Not even if you made a zero cost context switch, you will still have cache misses getting there and coming back. Even if the context switch, the OS overhead, all of that were zero cost, if the two processes doing work have ~70 cache misses each then you are right back to where we are now.

It's 25 years later - what's changed? CPUs are 20x faster (.25ns clock instead of 5ns clock) but main memory is only ~3x faster. To the extent that things don't fit in the cache you would expect a 3x improvement in context switch time. Instead we have it almost the same speed (old was 6usec, current is 7usec). But the OS hasn't been held constant, it went from basically single threaded to scaling up to lots of CPUs. That scaling is not free, you are taking and releasing locks in your context switch code.

Personally, I doubt there is a lot of room for improvement. Some, sure. But I'd be astounded if you could figure out how to get a factor of two in Linux without losing something else.

Nice analysis.

As a last stand, I'd reiterate that different multi-thread algorithms could be practical if the minimum switch time were much, much smaller. Thread wakeup times on the order of hundreds or thousands of instructions, where the cache had not been substantially changed. E.g. Ping-Pong threads that passed buffers back and forth for staged processing. They would even benefit from the cacheing done by the other thread in the algorithm, that had processed the same data.

All impossible now, with the large thread-switch stone around our necks.

But this is sort of like saying things would be so much better if we didn't have this annoying speed of light constraint. Yeah, if memory was all L3 instead of main memory, things would be faster, but it isn't.

Don't get me wrong, I'm all for primitives being light weight, that was the whole motivation behind writing lmbench. You and I agree on the goal.

Where we part ways is what is possible. When context switches are being done in the time it takes to do ~140 cache misses I don't see how it is possible to get to "much, much smaller". Smaller, sure, much smaller? How? Which cache misses are you going to not do?

What I'm looking for is actual insight into the problem. If you've looked at the code and you know the hardware and you know each cache miss on a first name basis and you are saying "right here, these 70 misses are not needed, we can get 2x better if we lose these", that's something that I and everyone would want to know. We already agree that less is more, the point is how do you get to less? Is it even possible?

Lemme run some numbers for i686 25 years ago. Back then, we were at about 34 cache misses/context switch. Now we are at about 140. So it would seem like there is some room there. But back then we didn't have the lock traffic we have today. And who knows what else they have shoved into the kernel. Lets ignore the lock traffic and extra bloat and say we could get back to 34 misses. That would get us to 2usecs rather than 7usecs. Which is better but does it meet your definition of "much, much smaller"?

That's where I'm coming from, I'm sizing the problem. I have no idea if they can shave it down to 34 misses, I very much doubt it. But I think we can agree that given the fact that the kernel is fine grained threaded they aren't going to get to better numbers than what they had when it wasn't threaded, right? That's a lower bound in practice, agreed? So if the cache miss fairy showed up and gave us our best case scenario we're about 3x faster. Which is nice but not life changing. And I don't believe for a second that there is 3x worth of easy to remove cache misses/bloat in that code path, Linus would have to be asleep at the wheel to allow that.

Zero cache misses would be possible. If threads handed off data in a fine-grained fashion, with the cache essentially unchanged between switches.. Just like procedure call and return. In fact, maybe instead of procedure call and return. Impossible with the current model. Possible if thread switching was lightweight.

The idea is, threads are expensive (cache misses) now because they happen infrequently so the cache gets stale. But if they were as common as call-return then they'd behave at least as well. Except for this lead weight (today) of kernel switch/register reload/state reload.

Cue the comment from the 10+ year old vaporware Mill architecture's team... :)

> If the CPU made those an opcode instead of a wad of kernel code, the switch could be reduced to a clock cycle (ns?)

Uh, how do you think the kernel does it? Of course there's a CPU instruction for it - at least in modern ISAs like AArch64, but I can only assume it must have been tacked onto x86 too somehow or another.

One reason that it's implemented in the kernel is to interact well with the scheduler: it's all well and good for a user space process to spinlock (with some kind of enter-low-power-state instruction), but it's going to be spinning until the timer comes around and kicks it back to the kernel anyways unless the other side of the lock just happens to be scheduled on a different core simultaneously. Even worse, if a thread is holding a spinlock and it gets unscheduled, now everyone else who wants to acquire that lock will waste their timeslices spinning away for nothing. The only way to avoid this would be for threads to be able to tell the OS "don't unschedule me" (much like the kernel masks interrupts during critical sections), but that would allow any such process to not only DOS the rest of the system, it could allow any such process to hang the system entirely. That's not to say it can't be done properly, but the easy and perhaps even correct way to do it is OS-managed semaphores.

> not 2 or 4 hyperthreads but maybe 1000. So every thread in the system could be 'hot-staged'

And of course this is what hyperthreads are, but where exactly do you plan on putting 1MB of architectural state while you're not using it? You're lucky if you have an L2 that big, but let's think... moving architectural state to the L2, that sounds a lot like... yes, correct! OS threads!

If we want to rescue your suggestion back into the realm of feasibility, what you're saying is we should implement the OS (with features like scheduler-aware semaphores and thousands of ready threads) in hardware to make things like moving 1MB of architectural state to and from an L2 cheaper (and that we should have larger L2s so it's not incredibly wasteful to use 1MB on architectural state of non-executing threads). There's a reason we implement OSes in software, though, even with all the associated costs.

...and yet OSs do thread switches on the order of usec or even msec. So I repeat, there's much room for improvement.

Um, you need to think more deeply about this. Yes, you can switch a "thread" (says the guy who wrote a user level thread package) very, very quickly but that's meaningless. Unless your application is one where all it does is context switch and does no other work.

"Context" is more than just the registers. You could make an instruction that did the context switch in zero time and a real context switch will take much more than zero time. Because there is more context than just the registers.

Yes all that is very, very clear. But adding 10,000ns to the switch time is going to torpedo any chance of a quick turnaround on a queue wait or IO completion. That's a huge timewad compared to a procedural solution that doesn't use multiple threads or locked queues. Thus the initial comment that using threads adds unpredictable issues that are hard to diagnose. And the suggestion that removing this delay will definitely reduce latency of event handling at all levels.

Including, returning to a thread 10,000ns quicker can help with cache utility - there's that much less cache washout occurring 'while you were away'. Tightening this up can allow, for the first time in any architecture, truly transparent multi-thread implementations of ordinary tasks without penalty. Imagine each thread executes a handful of instructions and then signals the other thread to continue. No cache issues (its only been nanoseconds).

Sure, 'nobody does that'. But that's because, threads are so godawful expensive now. We'd be in a whole different headspace if that changed.

You seem to be living in an imaginary world where main memory is much, much closer to the CPU than it is in real life. 10,000ns is 174 cache misses on my machine. That's not a lot of room when you are popping something off a queue or finishing an IO.

The presumption of large cache misses is where our intuitions diverge. Algorithms where threads operated on the same data, for instance, would not actually have many cache misses or even zero cache misses.

btw Lets take it down a notch, and back off on the personal aspersions? ok?

Sorry if it sounds personal, it's not intended to be so. I get weird when I see people not seeing all of the picture. To me, the picture includes main memory, I've spent way too much time with a logic analyzer watching stuff go across the bus (actually did a lot of this while tuning some hashing code for performance).

Memory misses are a fact of life. If you look at my comments elsewhere, I noted that

    CPU: 20x faster
    Main memory: 3x faster
    Context switch: about the same

If memory wasn't the main part of the equation, shouldn't the context switches be faster? Yes, as I pointed out, the OS is now fine grained multi threaded but that doesn't explain a 20x difference.

As for the comment that some stuff is going to have zero cache misses, sure, in theory. Can you show any real world examples of that? I would think that anything that takes a lock on more than one cpu/cache is going to have lock traffic that is going to cause a cache miss like stall. Has cache coherency changed such that locks are "free"? That would be (interesting) news to me.

The question is, would multiple threads have any essential difference from another embodiment e.g. procedural. If not, then the (only) gain is being able to recast the problem as threads, for whatever that's worth. If thinking about an algorithm as synchronization-of-data is helpful, then the low-or-zero-latency-added thread model is helpful.