Hacker News Reader

Comment by bluetomcat | Hacker News Reader

For CPU-bound tasks, it is best to pre-create a number of threads whose count roughly corresponds to the number logical execution cores. Every thread is then a worker with a main loop and not just spawn on-demand. Pin their affinity to a specific core and you are as close as possible to the “perfect” arrangement with minimized context switches and core-local cache data being there most of the time.

View on HN

One thing to worry about is that you’re effectively taking over the job of the OS scheduler. This can be a good thing since you know more about your workload than the generic heuristics the scheduler uses, but it also means that you might need to reimplement some things.

Like only scheduling work on logical cores that share a physical core after all physical cores have a busy logical core (I.e. fill up the even cores first).

Thankfully we have very nice task-based schedulers nowadays such as https://github.com/cpp-taskflow/cpp-taskflow or TBB flowgraph

Taking over the job of the OS scheduler is explicitly the reason for doing it, there are some classes of macro-optimization that have this as a prerequisite. It is done for the same reasons that high-performance database kernels replace the I/O scheduler too.

To your point, it is a double-edged sword. Writing your own schedulers requires a much higher degree of sophistication than using the one in the OS. It is a skill that takes a long time to develop and requires a lot of first principles thinking, there is loads of subtlety, you can't just copy something you found on a blog. It also isn't just about being able to predict the behavior of your workload better than the OS, you can also adapt your workload to the schedule state since it is exposed to your application, the latter being a greatly overlooked capability.

Once you know how to design software this way, it not only generates large increases in throughput but also enables many elegant solutions to difficult software design problems that simply aren't possible any other way. While the learning curve is steep, once you are accustomed to writing software this way it becomes pretty mechanical.

Any reading recommendations?

> One thing to worry about is that you’re effectively taking over the job of the OS scheduler.

Exactly. And some apps automatically do that by default, as if they are so arrogant as to think they must be the only program running on that machine. Maybe good for a server app, terrible advice for a general desktop app.

Yep. We do this on real hardware and never preempt. There is nothing more performant than that. Using IPIs (inter-processor interrupts) you can trigger events like "more work has been added" on each CPUs queue. Additionally, when you put all interrupts of a device solely on one specific CPU you won't have to lock anything.

Some other things: pthreads generally have high cost, and that means C++ threads do too. pthreads have quite a few features that you regularly don't use, which you can skip completely using fibers and coroutines.

> never preempt

I don’t think this is a realistic expectation on Linux and, especially, Windows which runs hundreds of threads of its own you don’t want to know about. (Besides, we must remember that multithreading was invented and found quite useful in the era of ”single-core” processors.)

Linux/CFS has an isolcpus feature that can be used to tell the kernel to never schedule things on a given CPU. This is useful when latency matters.

I learned recently that even with isolcpu, and nohz, and interrupts directed elsewhere, the kernel will still pause the thread on the isolcpu if it has mmapped a file (e.g., to report stats) and the kernel decides it's time to copy the bits to disk. If you don't want stalls, only map writable files on a tmpfs volume. To snapshot the file, copy it to another file on the same volume, and then snapshot the copy.

Yes, it is called TLB shootdown and it is required to preserve the integrity of the TLB across CPUs on an umap or a dirty bit change. If latency is impprtant, don't use disk backed writeable mappings.

Edit: to clarify: any writeable mapping or any unmap will cause TLB shutdown interrupts to be broadcasted to all currently running threads of a process.

Of course one never unmaps the file, or any mapped memory, so this has nothing to do with TLB problems (which are also a thing -- another reason processes are better than threads).

These pauses happen even without unmapping. Despite that no synchronization is available, so you are right in the middle of whatever, the kernel decides a static snapshot of the pages' state must be written, so write-protects the pages first, and blocks your process until the write is done. It's just rude.

Unmapping is one case. As I said earlier, the other case is clearing the dirty bit for a page in the in the page directory. As the dirty bit is cached in the tlb (so it doesn't need to be written back every time the page is written by a cpu), the tlb need to be flushed. I do not think the kernel write protects the page is writing out, unless the architecture has no hardware dirty bit and one must be maintained by the os. Technically tlb shootdown is not a form of blocking, but it does cause periodic latency spikes.

Multi-millisecond latency spikes in a process spinning on an atomic update cannot be blamed on TLB flush, which introduces stalls measured in, at worst, microseconds.

[very late reply]

yes, that sort of spikes are definitely not due to just interrupts. As you say, it is probably a kernel io thread taking over the cpu.

On a server running heterogeneous CPU-bound tasks of various users it is hardly a realistic expectation, but on a single-user device with a single application in the foreground I would say it is realistic, since most of these running processes are blocked on something most of the time. Hundreds of mostly-idle resident processes are insignificant to a one that puts the CPU through its paces.

This thread is about the performance of threads, which we have established can be a high cost for some. In our case we don't run on Linux or Windows, but you can still do the same on Linux afaik, although you will have to write a kernel object for some things.

Mask off all those other processes to only run on core 0.

How many percent performance do you think you gain by never pre-empting?

If we're talking 50%, the complexity sounds worth it, but if it's 1% I think I'd prefer to stick with standard scheduling and know my program will 'just work' on any CPU or OS, and with any libraries I choose to use.

Probably a lot on bare metal, but we are a special case here. It really brings down the latency to respond to network events. A single context switch is in the range of 100K-1M CPU cycles.

The reason why is because we avoid all the indirect cost of context switching, which is all the various caches that has to be flushed. And also the context switching itself, of course.

However, you can still do a lot on Linux to equalize things if you really want to get down to it. For anything but special cases Linux really does a good job with scheduling. After all, you are likely not running much else other than your intended service.

That said, for me this thread was a slight wakeup-call that made me look more into fibers and co-routines. I have been wanting to use these for a long time for some things.

> A single context switch is in the range of 100K-1M CPU cycles.

1M cycles is roughly 300 microseconds (assume 3 GHz processor, so 3 cycles is 1 nanosecond). Eli’s graph from the post I referenced above, has a context switch in the 1-3 microsecond range [1] depending on taskset/core pinning. The high end (3 microseconds) is about 10000 cycles then.

Maybe you mean fork() or pthread_create for your 1M cycles?

[1] https://eli.thegreenplace.net/images/2018/plot-launch-switch...

The difference can be quite large, details are workload and software dependent. It isn't just the context-switching overhead (which is prohibitively high these days), it also significantly improves average cache locality, which is the bottleneck for many high-performance codes.

Some types of software optimizations require the ability to correctly infer local CPU cache contents, which is difficult when arbitrary processes are semi-randomly stepping all over that cache.

A valid reason to have more is IO, and particularly file IO.

File IO should be using asynchronous methods too. If your OS doesn't support asynchronous file IO then you're not using any of the big 3.

Exactly this. You want one thread pool of size ~= core count, then you want to have a completely different "max number of IO jobs" type deal that doesn't use threads at all.

C# async/await is pretty good for this (IO operations do not count towards CPU task count).

Paraphrasing the famous Greenspun’s Tenth Rule, any home-made threading library for C++ always ends up being “an ad hoc, informally-specified, bug-ridden, slow implementation of half of” Intel TBB. (Been there, done that.)

This is not about coming up with a thread library. The described scenario can be realized entirely with standard Pthread primitives and calls like pthread_setaffinity.

Well, a good library would take the issue of the “cost” into account for you.

Reply on news.ycombinator.com