Почему 1000 потоков быстрее, чем несколько?

Ответ 1

Я думаю, что реальная проблема (кроме использования памяти) со слишком большим количеством потоков состоит в том, что ЦП может быть трудно оптимизировать себя, потому что он постоянно переключает задачи. В исходном бенчмарке OP все потоки работают над одной и той же задачей, поэтому вы не столкнетесь с большими расходами на дополнительные потоки.

Чтобы смоделировать потоки, работающие над различными задачами, я изменил переформулировку исходного кода Джодреллом (помеченную как "Нормальная" в данных ниже), чтобы сначала оптимизировать доступ к памяти, гарантируя, что все потоки работают в одном и том же блоке памяти одновременно и так далее. что блок помещается в кэш (4 МБ), используя метод из этой статьи о методах блокировки кеша. Затем я "изменил", чтобы каждый набор из 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 ему не приходится иметь дело с промахами в кеше. Как предположил Джодрелл, около 100 потоков, по-видимому, есть "сладкое пятно", то есть число в моей системе, которое позволит потоку завершить свою работу в течение 1 интервала времени. После этого время линейно увеличивается с числом потоков (помните, что ось X имеет логарифмический масштаб на графике.)

Сравнивая нормальные и оптимизированные данные, первый довольно неровный, а второй гладкий. Этот ответ предполагает, что больше потоков будет более эффективным с точки зрения кэширования по сравнению с меньшим количеством потоков, где доступ к памяти может быть более "случайным". Таблица ниже, кажется, подтверждает это (обратите внимание, что 4 потока являются оптимальными для моей машины, поскольку она имеет 4 логических ядра):

Де-оптимизированная версия наиболее интересна. В худшем случае 4 потока были вынуждены работать в разных областях памяти, что препятствует эффективному кешированию. По мере увеличения числа потоков система может кэшироваться, поскольку потоки разделяют блоки памяти. Но, поскольку число потоков увеличивается, предположительно, переключение контекста усложняет повторное кэширование системы, и результаты возвращаются к худшему случаю:

Я думаю, что этот последний график показывает реальную стоимость переключения контекста. В исходной (N) версии все потоки выполняют одну и ту же задачу. В результате существует ограниченная конкуренция за ресурсы, отличные от времени ЦП, и ЦП может оптимизировать себя под рабочую нагрузку (т.е. эффективно кешировать). Если все потоки делают разные вещи, то ЦП не может оптимизировать себя и серьезная производительность ударил результаты. Так что проблема заключается не в непосредственном переключении контекста, а в конкуренции за ресурсы.

В этом случае разница для 4 потоков между O (2909ms) и D (3849ms) составляет 940 мс. Это составляет 32% снижения производительности. Поскольку моя машина имеет общий кэш L3, это снижение производительности проявляется даже при наличии только 4 потоков.

Ответ 2

Вы можете рассмотреть, как приложение обращается к памяти. В сценарии с максимальным количеством потоков вы эффективно обращаетесь к памяти последовательно, что эффективно с точки зрения кэширования. Подход с использованием небольшого количества потоков является более случайным, что приводит к отсутствию кэша. В зависимости от ЦП существуют счетчики производительности, которые позволяют измерять попадания в кеш L1 и L2.

Ответ 3

Я позволил себе перестроить ваш код для запуска с использованием BenchmarkDotNet, похоже,

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

Когда я запускаю тест, я получаю эти результаты,

BenchmarkDotNet = v0.11.1, ОС = Windows 10.0.14393.2485 (1607/AnniversaryUpdate/Redstone1) Процессор Intel Core i7-7600U 2,80 ГГц (макс: 2,90 ГГц) (Kaby Lake), 1 ЦП, 4 логических и 2 физических ядра Частота = 2835938 Гц, разрешение = 352,6170 нс, таймер = TSC [хост]:.NET Framework 4.7.2 (CLR 4.0.30319.42000), 64-разрядная версия RyuJIT-v4.7.3163.0
Clr:.NET Framework 4.7.2 (CLR 4.0.30319.42000), 64-битный 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

Это те результаты, которые я ожидаю и которые отличаются от того, на что вы претендуете в этом вопросе. Однако, как вы правильно указали в комментарии, это потому, что я уменьшил значения inputDataSize и searchDataSize.

Если я перезапущу тест с исходными значениями, я получу такие результаты,

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

Эти результаты подтверждают ваш вопрос.

FWIW Я сделал еще один тестовый прогон,

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

Это может помочь отличить стоимость переключения контекста от создания потока, но, в конечном счете, должен присутствовать элемент того и другого.

Есть немного предположений, но вот несколько утверждений и вывод, основанный на наших агрегированных результатах.

Создание Thread связано с некоторыми фиксированными издержками. Когда работа большая, накладные расходы становятся незначительными.

Операционная система и архитектура процессора могут одновременно запускать только определенное количество потоков ЦП. Некоторое количество процессорного времени будет зарезервировано для многих операций, которые поддерживают работу компьютера за кадром. Часть этого процессорного времени будет использоваться фоновыми процессами и службами, не связанными с этим тестом.

Даже если у нас 8-ядерный процессор и порождают только 2 потока, мы не можем ожидать, что оба потока будут проходить через программу с одинаковой скоростью.

Принимая во внимание вышеприведенные пункты, независимо от того, обслуживаются ли потоки через .Net ThreadPool, одновременно может обслуживаться только конечное число. Даже если все созданные экземпляры потоков преобразуются в какой-то семафор, они не все попали туда сразу и не будут продолжать все сразу. Если у нас больше потоков, чем доступных ядер, некоторым потокам придется ждать, прежде чем они вообще смогут прогрессировать.

Каждый поток будет продолжаться в течение определенного промежутка времени или до тех пор, пока не будет ожидать ресурс.

Это то место, где приходят предположения, но когда inputDataSize невелик, потоки будут стремиться завершить свою работу за один промежуток времени, требуя меньше или вообще не переключая контекст.

Когда inputDataSize становится достаточно большим, работа не может быть завершена за один промежуток времени, это повышает вероятность переключения контекста.

Итак, учитывая большой фиксированный размер для searchDataSize у нас есть три сценария. Границы этих сценариев будут зависеть от характеристик тестовой платформы.

inputDataSize маленький

Здесь стоимость создания потоков значительна, а AllThreadSearch значительно медленнее. ParallelThreadSearch имеет тенденцию к победе, поскольку сводит к минимуму стоимость создания потоков.

inputDataSize - средний

Стоимость создания потока незначительна. Важно, что работа может быть завершена за один отрезок времени. AllThreadSearch использует планирование на уровне ОС и избегает разумных, но значительных накладных расходов как Parallel.For и циклического FewThreadSearch в FewThreadSearch. Где-то в этой области самое приятное место для AllThreadSearch, возможно, что для некоторых комбинаций AllThreadSearch - самый быстрый вариант.

inputDataSize большой

Важно отметить, что работа не может быть завершена за один отрезок времени. Планировщик ОС и ThreadPool не могут предвидеть стоимость переключения контекста. Без какой-то дорогой эвристики, как они могли? FewThreadSearch выигрывает, потому что избегает переключения контекста, стоимость которого перевешивает стоимость циклов сегмента.

Как и всегда, если вы заботитесь о производительности, стоит сравнить ее с репрезентативной системой, репрезентативной рабочей нагрузкой и репрезентативной конфигурацией.

Ответ 4

Сначала вы должны понять разницу между Process и Thread, чтобы глубже погрузиться в преимущества параллелизма, чтобы добиться более быстрых результатов по сравнению с последовательным программированием.

Процесс - мы можем назвать это как экземпляр программы в процессе выполнения. Операционная система создает различные процессы при выполнении приложения. Приложение может иметь один или несколько процессов. Создание процесса - это то, что является дорогостоящей задачей для операционной системы, поскольку для ее создания необходимо предоставить несколько ресурсов, таких как память, регистры, открытые дескрипторы для доступа к системным объектам, контекст безопасности и т.д.,

Поток - это сущность внутри процесса, которую можно запланировать для выполнения (может быть частью вашего кода). В отличие от создания процесса, создание потока не требует больших затрат и времени, поскольку потоки совместно используют виртуальное адресное пространство и системные ресурсы процесса, к которому он относится. Это повышает производительность ОС, поскольку нет необходимости предоставлять ресурсы для каждого потока, который она создает.

Ниже на диаграмме будут подробно изложены мои слова.

Поскольку потоки совместно используют ресурсы и имеют в них природу параллелизма, они могут работать параллельно и давать улучшенные результаты. Если ваше приложение должно быть высокопараллельным, вы можете создать ThreadPool (набор рабочих потоков) для эффективного выполнения асинхронных обратных вызовов.

И чтобы исправить ваше окончательное предположение/вопрос, создание/уничтожение потоков не обходится дороже, чем создание/уничтожение процесса, поэтому всегда наличие "правильно обработанного кода потоков" повысит производительность приложения.

Ответ 5

Это просто потому, что вы не можете создавать потоки, превышающие возможности вашего процессора... поэтому на самом деле в обоих случаях вы создаете одинаковое количество потоков; ваш процессор макс...