Why running threaded algorithms with exact number of cores the machine has, is faster than anything else?

Question

I made some basic multi-threading tests here, and noticed that the speed increase when using the exact is bigger than I expected.

I assumed that speed would increase linearly until I hit the limit of cores, and then either stop increasing, or even slow down.

Instead speed increases linearly, and then JUMPS upward, but on the next amount of thread (1+ than the machine have cores), it "continues" from where it was before.

A graph for example looked like a long linear function, with a gigantic spike in the middle, where I had same number of threads as cores.

So, why is that?

PS: before someone point out the obvious (that using the number of cores of the CPU mean using the maximum of the CPU), I already know the obvious, I am asking about the non-obvious.

EDIT: graph made in R, it is how many "turns" the simulator can run per MS.

The algorithm there is running through an array of agents, then doing some floating-point math, doing some comparisons with turn number, and then calling a function that do more floating-point math, on the test of the graph the function wasn't inlined.

EDIT2:

Same program, but with "release" build.

Also, I would like to note that "threads" here refer to worker threads, there is also an UI+Boss thread that updates as fast as OpenGL allows, seemly this became important on the MacMini, since the graph looks like "off by one"

Here is the MacMini performance alone, its CPU is a i5-2415M 2.3Ghz (with 2.9Ghz boost) 2 cores + HT.

Here is Zephyr's performance + MacMini on the bottom of the graph, its CPU is a i5-4690K with Intel's stock behaviour, it has 4 cores, but doesn't have HT.

Answer 1

Some of the many things that may or may not be relevant include:

• if the threads use all CPU time they're given, or are constantly blocking/unblocking (e.g. for file IO, time delays, mutexes, ...)

• what the CPU/s are. A NUMA system (with a pair of dual core chips) is very different to "single quad-core chip with SMT/hyper-threading".

• if the CPUs have some sort of "turbo-boost" (e.g. where single-core might gets full boost, 2-core might get partial boost, etc)

• if the threads use some kind or resource part of the time, where the CPU might turn that off to save power, and where "more threads" might keep that resource busy enough to prevent it from being turned off (e.g. AVX in modern Intel gets turned off to save power, so if it's used temporarily you get "turning it back on latency").

• which caches are shared by which cores

• if there's any possibility of cache thrashing (e.g. each core modifies the same cache line, causing that cache line to be constantly bouncing between cores).

• what the bottleneck is (e.g. if it's limited by RAM bandwidth at 4+ cores, then throwing more than 4 cores at it won't help much).

• what the OS is (or what strategy it uses to schedule threads), and the thread's policy and priority; and if there's other threads that could be running in the background.

• if there's any kind of heavy (possibly asynchronous/non-blocking) IO involved.

Answer 2

Interesting case. If you had no dependencies on other threads, you would get a peak at the number of cpu's (or double with Hyper Threading) and then a slight decrease due to excessive context switching.

The large jump aspect is a mystery for now, you may be hitting a "resonation point" where callback requests and context switching occur in an optimal sequence or frequency, but since the same is reproducible on other hardware that remains a bit mysterious.

The other aspect however, increasing performance after the number of CPU's, can have many known causes. It is due to how your worker threads lock common resources (for example how they interact with the main thread).

If you have a thread-pool that gets work assigned by the main thread, then you are probably not really utilizing the given number of threads all the time since your main thread may be busy while some workers are waiting for new work.

Try to implement it this way, where the main thread (or another thread) first prepares chunks of work and stuffs them into a queue. Then let your worker threads loop around picking up a chunk, processing it and dropping it into another queue that your main thread (or another thread) will process. That way the worker threads will never have to wait on your main thread. Check out my blog-post "Fully utilise all bottlenecks" where I elaborate on this idea (with an open source C# example).

If you are updating the UI after each result comes in, then that will certainly be a bottleneck (especially the OpenGL stuff). See my answer to the question "Why is my C# program faster in a profiler?" Using a timer to render a frame of the current status would in that case increase your performance dramatically. I don't think this applies to your case though, since you do see an increase with more threads.

No exact answer is possible without knowing the implementation, but I hope I'm poking you into the right direction :-)

Answer 3

The amount of time a task takes is the maximum amount that it takes each core to do its work. With 4 threads each thread does 1/4 of the work and each core has 1 thread, so each core has the same amount of work. With 5 threads then each thread does 1/5 of the work but one core must handle 2 threads, taking 2/5 of the time, which is greater than 1/4. More generally, the cores do equal work when the number of threads is a multiple of 4, which the graph reflects.

Note that context switching for CPU-bound tasks has very little effect on performance until you reach a huge (likely thousands) number of threads. That is certainly not your problem with such small numbers of threads.