为什么1000个线程比几个快？

Question

我有一个简单的程序,可以在2D点阵列中进行线性搜索.我对1000万个点进行1000次搜索.

奇怪的是,如果我生成1000个线程,程序的工作速度就像我只有我的CPU核心,或者当我使用Parallel.For时一样快.这与我所知道的关于创建线程的所有内容相反.创建和销毁线程很昂贵,但显然不是这种情况.

有人可以解释原因吗？

注意:这是一个方法论的例子; 搜索算法故意不意味着做到最优.重点是线程.

注2:我测试了4核i7和3核AMD,结果遵循相同的模式!

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();
    }
}

编辑:请确保在调试器外运行应用程序.VS Debugger减慢了多线程的情况.

---

编辑2:更多测试.

要清楚,这里是更新的代码,保证我们做的有1000个运行在一次:

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();
}

使用较小的阵列(100K元素)进行测试,结果如下:

1000 vs 8个主题

               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 |

现在,正如预期的那样,1000个线程要慢得多.Parallel.For仍然是他们所有人,这也是合乎逻辑的.

但是,将数组增长到500K(即每个线程的工作量),事情开始看起来很奇怪:

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 |

看起来上下文切换的成本可以忽略不计.线程创建成本也相对较小.拥有太多线程的唯一重要成本是内存丢失(内存地址).仅此一项就足够了.

现在,线程创建成本确实不大吗？我们普遍被告知创建线程非常糟糕,上下文切换是邪恶的.

Answer 1

您可能想要考虑应用程序如何访问内存.在最大线程场景中,您有效地按顺序访问内存,从缓存的角度来看这是有效的.使用少量线程的方法更随机,导致缓存未命中.根据CPU的不同,还有一些性能计数器可用于测量L1和L2缓存命中/未命中.

Answer 2

我认为线程太多的真正问题(除了内存使用)是CPU可能很难优化自己,因为它一直在切换任务.在OP的原始基准测试中,线程都在处理相同的任务,因此您没有看到额外线程的大部分成本.

为了模拟处理不同任务的线程,我修改了Jodrell 对原始代码的重新构造(在下面的数据中标记为"Normal"),首先通过确保所有线程同时在同一块内存中工作来优化内存访问.该块使用此缓存阻止技术文章中的方法适合缓存(4mb).然后我"反转"它以确保每组4个线程在不同的内存块中工作.我的机器的结果(毫秒):

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

对于O,所有线程同时在可缓存内存的同一块中工作(其中1个块= 1/10 inputData).对于D,对于每组4个线程,没有线程同时在同一块内存中工作.所以基本上,在前一种情况下,访问inputData能够使用缓存,而在后一种情况下,4线程访问inputData被强制使用主内存.

在图表中更容易看到.这些图表减去了线程创建成本,并注意x轴是对数的,y轴被截断以更好地显示数据的形状.此外,1个线程的值已减半,以显示理论上最佳的多线程性能:

快速浏览一下就可以看出优化数据(O)确实比其他数据更快.它也更加一致(更平滑),因为与N相比,它不必处理缓存未命中.正如Jodrell所建议的那样,在100个线程附近似乎有一个最佳点,这是我的系统上允许线程在1个时间片内完成其工作的数字.之后,时间随线程数呈线性增加(请记住,x轴在图表上有对数刻度.)

比较正常和优化数据,前者是相当锯齿状的,而后者是平滑的.这个答案表明,从内存访问可能更"随机"的更少线程来看,从缓存的角度来看,更多线程会更有效.下面的图表似乎证实了这一点(注意4个线程对我的机器来说是最佳的,因为它有4个逻辑核心):

去优化版本最有趣.最糟糕的情况是有4个线程,因为它们被迫在不同的内存区域工作,阻止了有效的缓存.随着线程数量的增加,系统能够在线程共享内存块时进行缓存.但是,随着线程数量的增加,大概是上下文切换使得系统再次高速缓存并且结果趋向于最坏情况:

我认为最后一张图表显示了上下文切换的实际成本.在原始(N)版本中,线程都在执行相同的任务.因此,除了CPU时间之外,对资源的竞争有限,并且CPU能够针对工作负载优化自身(即有效地缓存).如果线程都在做不同的事情,那么CPU无法优化自身和严重的性能打击结果.因此,不是直接导致问题的上下文切换,而是资源的竞争.

在这种情况下,O(2909ms)和D(3849ms)之间的4个线程的差异是940ms.这表示性能下降了32%.因为我的机器有一个共享的L3缓存,即使只有4个线程,这个性能也会出现.