Why are 1000 threads faster than a few?

Question

I have a simple program that searches linearly in an array of 2D points. I do 1000 searches into an array of 1 000 000 points.

The curious thing is that if I spawn 1000 threads, the program works as fast as when I span only as much as CPU cores I have, or when I use Parallel.For. This is contrary to everything I know about creating threads. Creating and destroying threads is expensive, but obviously not in this case.

Can someone explain why?

Note: this is a methodological example; the search algorithm is deliberately not meant do to optimal. The focus is on threading.

Note 2: I tested on an 4-core i7 and 3-core AMD, the results follow the same pattern!

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

/// <summary>
/// We search for closest points.
/// For every point in array searchData, we search into inputData for the closest point, 
/// and store it at the same position into array resultData;
/// </summary>
class Program
{
    class Point
    {
        public double X { get; set; }
        public double Y { get; set; }

        public double GetDistanceFrom (Point p)
        {
            double dx, dy;
            dx = p.X - X;
            dy = p.Y - Y;
            return Math.Sqrt(dx * dx + dy * dy);
        }
    }

    const int inputDataSize = 1_000_000;
    static Point[] inputData = new Point[inputDataSize];

    const int searchDataSize = 1000;
    static Point[] searchData = new Point[searchDataSize];
    static Point[] resultData = new Point[searchDataSize];

    static void GenerateRandomData (Point[] array)
    {
        Random rand = new Random();
        for (int i = 0; i < array.Length; i++)
        {
            array[i] = new Point()
            {
                X = rand.NextDouble() * 100_000,
                Y = rand.NextDouble() * 100_000
            };
        }
    }

    private static void SearchOne(int i)
    {
        var searchPoint = searchData[i];
        foreach (var p in inputData)
        {
            if (resultData[i] == null)
            {
                resultData[i] = p;
            }
            else
            {
                double oldDistance = searchPoint.GetDistanceFrom(resultData[i]);
                double newDistance = searchPoint.GetDistanceFrom(p);
                if (newDistance < oldDistance)
                {
                    resultData[i] = p;
                }
            }
        }
    }

    static void AllThreadSearch()
    {
        List<Thread> threads = new List<Thread>();
        for (int i = 0; i < searchDataSize; i++)
        {
            var thread = new Thread(
                obj =>
                {
                    int index = (int)obj;
                    SearchOne(index);
                });
            thread.Start(i);
            threads.Add(thread);
        }
        foreach (var t in threads) t.Join();
    }

    static void FewThreadSearch()
    {
        int threadCount = Environment.ProcessorCount;
        int workSize = searchDataSize / threadCount;
        List<Thread> threads = new List<Thread>();
        for (int i = 0; i < threadCount; i++)
        {
            var thread = new Thread(
                obj =>
                {
                    int[] range = (int[])obj;
                    int from = range[0];
                    int to = range[1];
                    for (int index = from; index < to; index++)
                    {
                        SearchOne(index);
                    }
                }
                );
            int rangeFrom = workSize * i;
            int rangeTo = workSize * (i + 1);
            thread.Start(new int[]{ rangeFrom, rangeTo });
            threads.Add(thread);
        }
        foreach (var t in threads) t.Join();
    }

    static void ParallelThreadSearch()
    {
        System.Threading.Tasks.Parallel.For (0, searchDataSize, 
                index =>
                {
                    SearchOne(index);
                });
    }

    static void Main(string[] args)
    {
        Console.Write("Generatic data...  ");
        GenerateRandomData(inputData);
        GenerateRandomData(searchData);
        Console.WriteLine("Done.");
        Console.WriteLine();

        Stopwatch watch = new Stopwatch();

        Console.Write("All thread searching... ");
        watch.Restart();
        AllThreadSearch();
        watch.Stop();
        Console.WriteLine($"Done in {watch.ElapsedMilliseconds} ms.");

        Console.Write("Few thread searching... ");
        watch.Restart();
        FewThreadSearch();
        watch.Stop();
        Console.WriteLine($"Done in {watch.ElapsedMilliseconds} ms.");

        Console.Write("Parallel thread searching... ");
        watch.Restart();
        ParallelThreadSearch();
        watch.Stop();
        Console.WriteLine($"Done in {watch.ElapsedMilliseconds} ms.");

        Console.WriteLine();
        Console.WriteLine("Press ENTER to quit.");
        Console.ReadLine();
    }
}

EDIT: Please make sure to run the app outside the debugger. VS Debugger slows down the case of multiple threads.

---

EDIT 2: Some more tests.

To make it clear, here is updated code that guarantees we do have 1000 running at once:

public static void AllThreadSearch()
{
    ManualResetEvent startEvent = new ManualResetEvent(false);
    List<Thread> threads = new List<Thread>();
    for (int i = 0; i < searchDataSize; i++)
    {
        var thread = new Thread(
        obj =>
        {
            startEvent.WaitOne();
            int index = (int)obj;
            SearchOne(index);
        });
        thread.Start(i);
        threads.Add(thread);
    }
    startEvent.Set();
    foreach (var t in threads) t.Join();
}

Testing with a smaller array - 100K elements, the results are:

1000 vs 8 threads

               Method |     Mean |    Error |    StdDev | Scaled |
--------------------- |---------:|---------:|----------:|-------:|
      AllThreadSearch | 323.0 ms | 7.307 ms | 21.546 ms |   1.00 |
      FewThreadSearch | 164.9 ms | 3.311 ms |  5.251 ms |   1.00 |
 ParallelThreadSearch | 141.3 ms | 1.503 ms |  1.406 ms |   1.00 |

Now, 1000 threads is much slower, as expected. Parallel.For still bests them all, which is also logical.

However, growing the array to 500K (i.e. the amount of work every thread does), things start to look weird:

1000 vs 8, 500K

               Method |     Mean |    Error |   StdDev | Scaled |
--------------------- |---------:|---------:|---------:|-------:|
      AllThreadSearch | 890.9 ms | 17.74 ms | 30.61 ms |   1.00 |
      FewThreadSearch | 712.0 ms | 13.97 ms | 20.91 ms |   1.00 |
 ParallelThreadSearch | 714.5 ms | 13.75 ms | 12.19 ms |   1.00 |

Looks like context-switching has negligible costs. Thread-creation costs are also relatively small. The only significant cost of having too many threads is loss of memory (memory addresses). Which, alone, is bad enough.

Now, are thread-creation costs that little indeed? We've been universally told that creating threads is very bad and context-switches are evil.

Answer 1

I think the real issue (other than memory use) with too many threads is that the CPU may have a hard time optimizing itself because it is switching tasks all the time. In the OP's original benchmark, the threads are all working on the same task and so you aren't seeing that much of a cost for the extra threads.

To simulate threads working on different tasks, I modified Jodrell's reformulation of the original code (labeled "Normal" in the data below) to first optimize memory access by ensuring all the threads are working in the same block of memory at the same time and such that the block fits in the cache (4mb) using the method from this cache blocking techniques article. Then I "reversed" that to ensure each set of 4 threads work in a different block of memory. The results for my machine (in ms):

Intel Core i7-5500U CPU 2.40GHz (Max: 2.39GHz) (Broadwell), 1 CPU, 4 logical and 2 physical cores)
inputDataSize = 1_000_000; searchDataSize = 1000; blocks used for O/D: 10

Threads         1       2       3       4       6       8       10      18      32      56      100     178     316     562     1000
Normal(N)       5722    3729    3599    2909    3485    3109    3422    3385    3138    3220    3196    3216    3061    3012    3121
Optimized(O)    5480    2903    2978    2791    2826    2806    2820    2796    2778    2775    2775    2805    2833    2866    2988
De-optimized(D) 5455    3373    3730    3849    3409    3350    3297    3335    3365    3406    3455    3553    3692    3719    3900

For O, all the threads worked in the same block of cacheable memory at the same time (where 1 block = 1/10 of inputData). For D, for every set of 4 threads, no thread worked in the same block of memory at the same time. So basically, in the former case access of inputData was able to make use of the cache whereas in the latter case for 4 threads access of inputData was forced to use main memory.

It's easier to see in charts. These charts have the thread-creation cost subtracted out and note the x-axis is logarithmic and y-axis is truncated to better show the shape of the data. Also, the value for 1 thread has been halved to show the theoretical best multi-threaded performance:

A quick glance above shows the optimized data (O) is indeed faster than the others. It is also more consistent (smoother) because compared to N it is not having to deal with cache-misses. As suggested by Jodrell, there appears to be a sweet spot around 100 threads, which is the number on my system which would allow a thread to complete its work within 1 time-slice. After that, the time increases linearly with number of threads (remember, the x-axis has a logarithmic scale on the chart.)

Comparing the normal and optimized data, the former is quite jagged whereas the latter is smooth. This answer suggested more threads would be more efficient from a caching point of view compared to fewer threads where the memory access could be more "random". The chart below seems to confirm this (note 4 threads is optimal for my machine as it has 4 logical cores):

The de-optimized version is most interesting. The worse case is with 4 threads as they have been forced to work in different areas of memory, preventing effective caching. As the number threads increases, the system is able to cache as threads share blocks of memory. But, as the number of threads increases presumably the context-switching makes it harder for the system to cache again and the results tend back to the worst-case:

I think this last chart is what shows the real cost of context-switching. In the original (N) version, the threads are all doing the same task. As a result there is limited competition for resources other than CPU time and the CPU is able to optimize itself for the workload (i.e. cache effectively.) If the threads are all doing different things, then the CPU isn't able to optimize itself and a severe performance hit results. So it's not directly the context switching that causes the problem, but the competition for resources.

In this case, the difference for 4 Threads between O (2909ms) and D (3849ms) is 940ms. This represents a 32% performance hit. Because my machine has a shared L3 cache, this performance hit shows up even with only 4 threads.

Answer 2

I took the liberty of rearranging your code to run using BenchmarkDotNet, it looks like this,

using System;
using System.Collections.Generic;
using System.Threading;

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace Benchmarks
{
    public class Point
    {
        public double X { get; set; }
        public double Y { get; set; }

        public double GetDistanceFrom(Point p)
        {
            double dx, dy;
            dx = p.X - X;
            dy = p.Y - Y;
            return Math.Sqrt(dx * dx + dy * dy);
        }
    }

    [ClrJob(baseline: true)]
    public class SomeVsMany
    {
        [Params(1000)]
        public static int inputDataSize = 1000;

        [Params(10)]
        public static int searchDataSize = 10;

        static Point[] inputData = new Point[inputDataSize];
        static Point[] searchData = new Point[searchDataSize];
        static Point[] resultData = new Point[searchDataSize];

        [GlobalSetup]
        public static void Setup()
        {
            GenerateRandomData(inputData);
            GenerateRandomData(searchData);
        }

        [Benchmark]
        public static void AllThreadSearch()
        {
            List<Thread> threads = new List<Thread>();
            for (int i = 0; i < searchDataSize; i++)
            {
                var thread = new Thread(
                    obj =>
                    {
                        int index = (int)obj;
                        SearchOne(index);
                    });
                thread.Start(i);
                threads.Add(thread);
            }
            foreach (var t in threads) t.Join();
        }

        [Benchmark]
        public static void FewThreadSearch()
        {
            int threadCount = Environment.ProcessorCount;
            int workSize = searchDataSize / threadCount;
            List<Thread> threads = new List<Thread>();
            for (int i = 0; i < threadCount; i++)
            {
                var thread = new Thread(
                    obj =>
                    {
                        int[] range = (int[])obj;
                        int from = range[0];
                        int to = range[1];
                        for (int index = from; index < to; index++)
                        {
                            SearchOne(index);
                        }
                    }
                    );
                int rangeFrom = workSize * i;
                int rangeTo = workSize * (i + 1);
                thread.Start(new int[] { rangeFrom, rangeTo });
                threads.Add(thread);
            }
            foreach (var t in threads) t.Join();
        }

        [Benchmark]
        public static void ParallelThreadSearch()
        {
            System.Threading.Tasks.Parallel.For(0, searchDataSize,
                    index =>
                    {
                        SearchOne(index);
                    });
        }

        private static void GenerateRandomData(Point[] array)
        {
            Random rand = new Random();
            for (int i = 0; i < array.Length; i++)
            {
                array[i] = new Point()
                {
                    X = rand.NextDouble() * 100_000,
                    Y = rand.NextDouble() * 100_000
                };
            }
        }

        private static void SearchOne(int i)
        {
            var searchPoint = searchData[i];
            foreach (var p in inputData)
            {
                if (resultData[i] == null)
                {
                    resultData[i] = p;
                }
                else
                {
                    double oldDistance = searchPoint.GetDistanceFrom(resultData[i]);
                    double newDistance = searchPoint.GetDistanceFrom(p);
                    if (newDistance < oldDistance)
                    {
                        resultData[i] = p;
                    }
                }
            }
        }
    }

    public class Program
    {
        static void Main(string[] args)
        {
            var summary = BenchmarkRunner.Run<SomeVsMany>();
        }
    }
}

When I run the benchmark I get these results,

BenchmarkDotNet=v0.11.1, OS=Windows 10.0.14393.2485 (1607/AnniversaryUpdate/Redstone1) Intel Core i7-7600U CPU 2.80GHz (Max: 2.90GHz) (Kaby Lake), 1 CPU, 4 logical and 2 physical cores Frequency=2835938 Hz, Resolution=352.6170 ns, Timer=TSC [Host] : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3163.0
Clr : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3163.0 Job=Clr Runtime=Clr

Method               inputDataSize searchDataSize Mean       Error     StdDev      
AllThreadSearch      1000          10             1,276.53us 51.0605us 142.3364us
FewThreadSearch      1000          10             547.72us   24.8199us 70.0049us
ParallelThreadSearch 1000          10             36.54us    0.6973us  0.8564us

These are the kind of results I'd expect and different to what you are claiming in the question. However, as you correctly identify in the comment, this is because I have reduced the values of inputDataSize and searchDataSize.

If I rerun the test with the original values I get results like this,

Method               inputDataSize searchDataSize Mean    Error    StdDev
AllThreadSearch      1000000       1000           2.872s  0.0554s  0.0701s
FewThreadSearch      1000000       1000           2.384s  0.0471s  0.0612s
ParallelThreadSearch 1000000       1000           2.449s  0.0368s  0.0344s

These results support your question.

---

FWIW I did another test run,

Method               inputDataSize searchDataSize Mean    Error    StdDev
AllThreadSearch      20000000      40             1.972s  0.0392s  0.1045s
FewThreadSearch      20000000      40             1.718s  0.0501s  0.1477s
ParallelThreadSearch 20000000      40             1.978s  0.0454s  0.0523s

This may help distinguish the cost of context switching versus thread creation but ultimately, there must be an element of both.

---

There is a little speculation but, here are a few assertions and, a conclusion, based on our aggregated results.

Creating a Thread incurs some fixed overhead. When the work is large, the overhead becomes insignificant.

The operating system and processor architecture can only run a certain number of CPU threads at a time. Some amount of CPU time will be reserved for the many operations that keep the computer running behind the scenes. A chunk of that CPU time will be consumed by the background processes and services, not related to this test.

Even if we have a 8 core CPU and spawn just 2 threads we cannot expect both threads to progress through the program at exactly the same rate.

Accepting the points above, whether or not the threads are serviced via a .Net ThreadPool, only a finite number can be serviced concurrently. Even if all instantiated threads are progressed to some semaphore, they did not all get there at once and they will not all proceed at once. If we have more threads than available cores, some threads will have to wait before they can progress at all.

Each thread will proceed for a certain time-slice or until it is waiting for a resource.

This is where the speculation comes in but, when inputDataSize is small, the threads will tend to complete their work within one time-slice, requiring less or no context switching.

When inputDataSize becomes sufficiently large, the work cannot be completed within one time-slice, this makes context switching more likely.

So, given a large fixed size for searchDataSize we have three scenarios. The boundaries of these scenarios will depend on the characteristics of the test platform.

inputDataSize is small

Here, the cost of thread creation is significant, AllThreadSearch is massively slower. ParallelThreadSearch tends to win because it minimizes the cost of thread creation.

inputDataSize is medium

The cost of thread creation is insignificant. Crucially, the work can be completed in one time slice. AllThreadSearch makes use of OS level scheduling and avoids the reasonable but significant overhead of both the Parallel.For and the bucket looping in FewThreadSearch. Somewhere in this area is the sweet spot for AllThreadSearch, it may be possible that for some combinations AllThreadSearch is the fastest option.

inputDataSize is large

Crucially, the work cannot be completed in one time slice. Both the OS scheduler and the ThreadPool fail to anticipate the cost of context switching. Without some expensive heuristics how could they? FewThreadSearch wins out because it avoids the context switching, the cost of which outweighs the cost of bucket looping.

---

As ever, if you care about performance it pays to benchmark, on a representative system, with a representative workload, with a representative configuration.

Answer 3

First you have to understand the difference between Process and Thread to deep dive into the benefits of concurrency to achieve faster results over sequential programming.

Process - We can call it as an instance of a program in execution. Operating System creates different processes while executing an application. An application can have one or more processes. Process creation is some what costly job to the operating system as it needs to provide several resources while creating, such as Memory, Registers, open handles to system objects to access, security context etc.,

Thread - it is the entity within a process that can be scheduled for execution(can be a part of your code). Unlike Process creation, thread creation is not costly/time consuming as threads share virtual address space and system resources of the process where it belongs. It's improving the performance of the OS as it no need to provide resources for each thread it creates.

Below diagram will elaborate more than my words.

As threads are sharing the resources and having the concurrency nature in them they can run parallel and produce improved results. If your application needs to be highly parallel then you can create ThreadPool(collection of worker threads) to achieve efficiently execute asynchronous callbacks.

And to correct your final assumption/question, creating/destroying threads is not costly than creating/destroying process so always having a "properly handled threading code" would benefit the performance of the application.

Answer 4

You may want to consider how the application is accessing memory. In the maximum threads scenario you are effectively accessing memory sequentially, which is efficient from a caching point of view. The approach using a small number of threads is more random, causing cache misses. Depending on the CPU there are performance counters that allow you to measure L1 and L2 cache hits/misses.

Answer 5

It is simply because you can't create threads more than the capacity of your cpu ... so actually in both cases you are creating the same number of threads; your CPU max ...