6

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.

debug test, 4690K

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.

MacMini

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.

Zephyr

| improve this question | |
  • @speeder So what happens when you continue increasing the number of threads? I would expect an upward spike in the graph every time the number of threads is evenly divided by the number of cores (here: 4, 8, 12), leading to the best possible work balance between the cores. – njuffa Dec 17 '16 at 15:46
  • that is an interesting question, I will do more tests later. The tests on a MacMini with 2 cores also sort of had this behaviour that you predicted (2 threads were faster than 3, but 4 threads were the fastest). I have to leave now, but later I will test around other interesting thread numbers on more machines and make more graphs. – speeder Dec 17 '16 at 15:51
  • 3
    Context switching has overhead, both direct, and indirect in warming up the caches. – Erik Eidt Dec 17 '16 at 16:20
  • 1
    There are many possible reasons, and without seeing the actual code there's no way that anyone can give you a good answer. Voting to close. – kdgregory Dec 17 '16 at 16:44
  • 1
    @speeder Did you also read/know about threading model of an Operating system? – overexchange Dec 17 '16 at 17:40
7

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.

| improve this answer | |
3

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 :-)

| improve this answer | |
  • One thing I've noticed is that if I am running an intensive computation (i.e. no IO waits) on all the CPUs on my desktop, the system UI (windows) can become somewhat unresponsive. Could it be that running at the exact number prevents 'hogs' the CPUs more effectively. Likewise, running at multiples of the CPUs evenly loads all of them such that 'jumping on to the merry-go-round' is harder. This implies that there is some sort of common contention on the threads or something trying to distribute load evenly across them. – JimmyJames Dec 19 '16 at 15:24
  • @JimmyJames It depends on your OS if the system becomes unresponsive. Try running PovRay on all CPU's. They will max out, but your computer should remain responsive. You can give the rendering process max priority (using process explorer) to hog your system (not much benefit). You may be right on trying to distribute load evenly. I guess that if we find out what causes the sawtooth we'll all say, "oh off course!". It would be a challenge to produce a program with these exact characteristics :-) – Louis Somers Dec 19 '16 at 20:16
  • @LouisSomers my algorithm: the "boss" thread, tell workers to all of them work on the same problem at the same time, and each worker then proceeds looping through a part of the array, for example with 50k elements, and 3 threads, thread 0 would loop from elements 0 to 16665, thread 1 from 16666 to 33332, and thread 2 would do the rest (thus would process 2 elements more than the others, to account for the division remainder). – speeder Dec 20 '16 at 18:42
  • @speeder is the array is the only common resource between threads? If it is fixed-length in general, and read-only from the perspective of a worker thread, it should not cause any locking (depending on the language or technology). If it is a dynamic "array" (List or other collection), it may have some "thread safety" locking mechanism in its properties. So the next question is what language / runtime or libraries are you using, and how do you define that common array? – Louis Somers Dec 21 '16 at 8:09
  • I made the program in C, I am referring to a C array. Each thread has its own mutex, but used to know when all threads are done with their part before starting over, and to avoid race that would happen while updating the task variable (without mutex they would start working before I even finished writing the pointer to the array they will work on) – speeder Dec 21 '16 at 15:19
1

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.

| improve this answer | |
  • While I suspect this is what is likely causing the spikes in the asker's experiments (see my earlier comment on the question itself), an OS could migrate the "extra" thread between the four cores with fine granularity to even out the load on each core. – njuffa Dec 20 '16 at 16:43
  • That would violate the unwritten rule that you not impose so many unforced context switches that they impact performance. Or, to put it another way, that would cause good code to perform badly just to let bad code perform a bit less badly. (Consider sane code that has 5 threads and 8 jobs for them to do. You don't want all 5 threads ping-ponging across cores to then have 3 things left to do on four cores!) – David Schwartz Jan 26 '17 at 3:54
  • @DavidSchwartz Context switches only become a problem when there are tons of them. On the other hand, spreading out work can be beneficial to, say, help heat dissipation, which might actually allow cores to "clock up". – Reinstate Monica Jan 27 '17 at 15:40
  • @Solomonoff'sSecret Right, exactly. You can't have so many unforced context switches that they affect performance. But even if this could be implemented with a smaller number of context switches, it would still be awful. See my last sentence in the comment above. – David Schwartz Jan 27 '17 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.