別スレッド - c# 処理待ち




なぜ1000スレッドが数スレッドより速いのですか? (4)

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、OS = Windows 10.0.14393.2485(1607 / AnniversaryUpdate / Redstone1)Intel Core i7-7600U CPU 2.80GHz(最大:2.90GHz)(Kaby Lake)、1 CPU、4論理コアと2物理コア周波数= 2835938 Hz、分解能= 352.6170 ns、タイマー= 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値を減らしたため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を作成すると、一定のオーバーヘッドが発生します。 作業量が多い場合、オーバーヘッドはわずかになります。

オペレーティングシステムとプロセッサのアーキテクチャは、一度に一定数のCPUスレッドしか実行できません。 コンピュータをバックグラウンドで実行し続ける多くの操作のために、ある程度のCPU時間が予約されます。 そのCPU時間の塊は、このテストとは関係なく、バックグラウンドのプロセスとサービスによって消費されます。

8コアのCPUがあり、2つのスレッドしか生成しない場合でも、両方のスレッドがプログラムをまったく同じ速度で進むことは期待できません。

スレッドが.Net ThreadPoolを介して処理されるかどうかにかかわらず、上記の点を受け入れて、有限数しか同時に処理できません。 インスタンス化されたスレッドがすべてあるセマフォに進んだとしても、それらがすべて同時にそこに到達するわけではなく、すべてが同時に進行するわけでもありません。 利用可能なコアよりも多くのスレッドがある場合、いくつかのスレッドはそれらがまったく進歩することができる前に待たなければならないでしょう。

各スレッドは特定のタイムスライスの間、またはリソースを待つまで進みます。

これは投機がinputDataSizeですが、 inputDataSizeが小さい場合、スレッドは1タイムスライス以内に作業を完了する傾向があり、コンテキストの切り替えはほとんどまたはまったく必要ありません。

inputDataSizeが十分に大きくなると、作業は1タイムスライス以内に完了できないため、コンテキストの切り替えが起こりやすくなります。

そのため、 searchDataSize大きな固定サイズを指定した場合、3つのシナリオがあります。 これらのシナリオの境界は、テストプラットフォームの特性によって異なります。

inputDataSizeが小さい

ここでは、スレッド作成のコストはかなりのものです、 AllThreadSearchは非常に遅いです。 ParallelThreadSearchはスレッド作成のコストを最小にするので勝つ傾向があります。

inputDataSizeは中です

スレッド作成のコストはわずかです。 重要なことに、作業は1つのタイムスライスで完了できます。 AllThreadSearchはOSレベルのスケジューリングを利用して、 Parallel.ForFewThreadSearchバケットループの両方の合理的ではあるが大きなオーバーヘッドを回避しFewThreadSearch 。 この領域のどこかにAllThreadSearchのスイートスポットがありますが、 AllThreadSearchが最速の選択肢である可能性があります。

inputDataSizeが大きい

重要なのは、作業を1つのタイムスライスで完了できないことです。 OSスケジューラとThreadPool両方とも、コンテキスト切り替えのコストを予測できません。 高価なヒューリスティックがなければ、どうすればよいでしょうか。 コンテキスト切り替えが回避されるため、 FewThreadSearch 。そのコストはバケットループのコストを上回ります。

これまでと同様に、パフォーマンスを重視するのであれば、代表的なシステムで、代表的な作業負荷で、代表的な構成でベンチマークを取ることが重要です。

2次元点の配列を線形に検索する簡単なプログラムがあります。 私は1000の検索を1 000 000ポイントの配列にします。

奇妙なことに、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デバッガは、マルチスレッドの場合を遅くします。

編集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対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対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 |

コンテキスト切り替えはごくわずかなコストで済むように見えます。 スレッド作成コストも比較的小さいです。 スレッド数が多すぎることによる唯一の大きなコストは、メモリ(メモリアドレス)の損失です。 それだけでは十分に悪いです。

さて、スレッド作成のコストはそれほど少ないのでしょうか。 スレッドを作成するのは非常に悪いことであり、コンテキストスイッチは悪だと広く言われてきました。


あまりにも多くのスレッドを使用した場合の(メモリ使用以外の)本当の問題は、CPUが常にタスクを切り替えているため、CPUの最適化に苦労する可能性があることです。 OPの当初のベンチマークでは、スレッドはすべて同じタスクに取り組んでいるため、余分なスレッドにそれほどのコストがかかることはありません。

さまざまなタスクを処理するスレッドをシミュレートするために、Jodrellの元のコードのreformulation (以下のデータでは「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ブロック= inputData 1/10)。 Dの場合、4つのスレッドのセットごとに、同じメモリブロック内で同時に動作するスレッドはありません。 したがって、基本的に、前者の場合にはinputDataアクセスはキャッシュを利用することができましたが、後者の場合には4スレッドではinputDataアクセスはメインメモリを使用することを強制されました。

グラフで見やすくなりました。 これらのチャートでは、スレッド作成コストが差し引かれ、データの形状をわかりやすくするためにx軸は対数、y軸は切り捨てられています。 また、1スレッドの値は、理論上最高のマルチスレッドパフォーマンスを示すために半分になりました。

上の概要は、最適化されたデータ( O )が他のものよりも実際に速いことを示しています。 また、 Nと比較してキャッシュミスを処理する必要がないため、より一貫性があります(よりスムーズになります)。 reformulationが示唆しているように、100スレッドの周りにスイートスポットがあるように見えます。これは私のシステムでは1つのタイムスライス内でスレッドがその作業を完了することを可能にする数です。 その後、時間はスレッドの数とともに直線的に増加します(x軸はチャート上で対数目盛を持ちます)。

通常のデータと最適化されたデータを比較すると、前者はかなりギザギザですが、後者はスムーズです。 このanswerは、メモリアクセスがより「ランダム」になる可能性がある少数のスレッドと比較して、キャッシュの観点から見るとより多くのスレッドがより効率的になることを示唆しています。 以下のチャートはこれを確認しているようです(4つのスレッドが4つの論理コアを持っているので私のマシンに最適です)。

最適化されていないバージョンが最も興味深いです。 最悪の場合、4つのスレッドが異なる領域のメモリで動作することを余儀なくされ、効果的なキャッシングが妨げられるためです。 スレッド数が増えると、スレッドがメモリブロックを共有するため、システムはキャッシュできるようになります。 しかし、スレッドの数が増えるにつれて、コンテキストの切り替えがシステムの再キャッシュを難しくし、結果は最悪の場合に戻る傾向があります。

この最後のチャートは、コンテキスト切り替えの実際のコストを示すものだと思います。 オリジナルの( N )バージョンでは、スレッドはすべて同じタスクを実行しています。 その結果、CPU時間以外のリソースに対する競争が制限され、CPUはワークロードに合わせて自分自身を最適化することができます(つまり、効果的にキャッシュすることができます)。深刻なパフォーマンスの低下が起こります。 したがって、問題を引き起こすのは直接コンテキストの切り替えではなく、リソースの競合です。

この場合、 O (2909ms)とD (3849ms)の間の4スレッドの差は940msです。 これは32%のパフォーマンスヒットを表します。 私のマシンは共有L3キャッシュを持っているので、このパフォーマンスヒットはわずか4スレッドでも現れます。


アプリケーションがどのようにメモリにアクセスしているかを検討することをお勧めします。 最大スレッド数のシナリオでは、効率的にメモリに順次アクセスしています。これは、キャッシュの観点からは効率的です。 少数のスレッドを使用するアプローチはよりランダムで、キャッシュミスを引き起こします。 CPUによっては、L1およびL2キャッシュのヒット/ミスを測定できるパフォーマンスカウンタがあります。


最初に、プロセスとスレッドの違いを理解して、並行プログラミングの利点を深く掘り下げて、逐次プログラミングよりも速い結果を達成する必要があります。

プロセス - 実行中のプログラムのインスタンスとして呼び出すことができます。 オペレーティングシステムは、アプリケーションの実行中にさまざまなプロセスを作成します。 アプリケーションは1つ以上のプロセスを持つことができます。 プロセスの作成は、メモリ、レジスタ、アクセスするシステムオブジェクトへのオープンハンドル、セキュリティコンテキストなど、作成中にいくつかのリソースを提供する必要があるため、オペレーティングシステムにとってコストのかかる作業です。

スレッド - 実行をスケジュールすることができる(コードの一部になることができる)プロセス内のエンティティです。 プロセスの作成とは異なり、スレッドの作成は仮想アドレス空間とそれが属するプロセスのシステムリソースを共有するため、コストと時間がかかりません。 作成した各スレッドにリソースを提供する必要がないため、OSのパフォーマンスが向上します。

下の図は私の言葉よりも詳しく説明します。

スレッドがリソースを共有し、それらに並行性を持たせることで、スレッドは並列実行され、改善された結果を生み出すことができます。 アプリケーションを高度に並列化する必要がある場合は、非同期コールバックを効率的に実行するためにThreadPool(ワーカースレッドのコレクション)を作成できます。

そして、あなたの最終的な仮定/質問を正すために、スレッドの作成/破棄はプロセスの作成/破棄よりもコストがかかりませんので、常に "適切に扱われたスレッドコード"を持つことはアプリケーションのパフォーマンスに利益をもたらします。







multithreading