[FIXED] Parallel.ForEach und ConcurrentDictionary sind langsamer als normales Wörterbuch

Ausgabe

Es gibt eine Aufgabe. Das Array enthält beliebige Zeichenfolgen. Wir müssen zählen, wie oft jeder der Strings im Array vorkommt. Lösen Sie die Aufgabe in einem Thread und Multithreading, vergleichen Sie die Ausführungszeit.

Aus irgendeinem Grund läuft die Singlethread-Version schneller als die Multithread-Version: 90 ms gegenüber 300 ms. Wie kann man die Multithread-Version reparieren, damit sie schneller läuft als die Singlethread-Version?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections.Concurrent;
using System.Diagnostics;
using System.Threading;

namespace ParallelDictionary
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> strs = new List<string>();
            for (int i=0; i<1000000; i++)
            {
                strs.Add("qqq");
            }
            for (int i=0;i< 5000; i++)
            {
                strs.Add("aaa");
            }

            F(strs);
            ParallelF(strs);
        }

        private static void F(List<string> strs)
        {
            Dictionary<string, int> freqs = new Dictionary<string, int>();

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            for (int i=0; i<strs.Count; i++)
            {
                if (!freqs.ContainsKey(strs[i]))
                    freqs[strs[i]] = 1;
                else
                    freqs[strs[i]]++;
            }
            stopwatch.Stop();

            Console.WriteLine("single-threaded {0} ms", stopwatch.ElapsedMilliseconds);
            foreach (var kvp in freqs)
            {
                Console.WriteLine("{0} {1}", kvp.Key, kvp.Value);
            }
        }

        private static void ParallelF(List<string> strs)
        {
            ConcurrentDictionary<string, int> freqs = new ConcurrentDictionary<string, int>();

            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            Parallel.ForEach(strs, str =>
            {
                freqs.AddOrUpdate(str, 1, (key, value) => value + 1);
            });
            stopwatch.Stop();

            Console.WriteLine("multi-threaded {0} ms", stopwatch.ElapsedMilliseconds);
            foreach (var kvp in freqs)
            {
                Console.WriteLine("{0} {1}", kvp.Key, kvp.Value);
            }
        }
    }
}

Lösung

Es ist möglich, die Multithread-Version etwas schneller als die Singlethread-Version zu machen, indem Sie einen Partitionierer verwenden, um die Daten in Blöcke aufzuteilen, die Sie separat verarbeiten.

Dann kann jeder Block in ein separates, nicht gleichzeitiges Wörterbuch verarbeitet werden, ohne dass eine Sperrung erforderlich ist. Schließlich können Sie am Ende jedes Bereichs ein Wörterbuch mit nicht gleichzeitigen Ergebnissen aktualisieren (das Sie sperren müssten).

Etwas wie das:

private static void ParallelF(List<string> strs)
{
    Dictionary<string, int> result = new Dictionary<string, int>();

    Stopwatch stopwatch = new Stopwatch();
    stopwatch.Start();

    object locker = new object();

    Parallel.ForEach(Partitioner.Create(0, strs.Count), range => 
    {
        var freqs = new Dictionary<string, int>();

        for (int i = range.Item1; i < range.Item2; ++i)
        {
            if (!freqs.ContainsKey(strs[i]))
                freqs[strs[i]] = 1;
            else
                freqs[strs[i]]++;
        }

        lock (locker)
        { 
            foreach (var kvp in freqs)
            {
                if (!result.ContainsKey(kvp.Key))
                {
                    result[kvp.Key] = kvp.Value;
                }
                else
                {
                    result[kvp.Key] += kvp.Value;
                }
            }
        }
    });

    stopwatch.Stop();

    Console.WriteLine("multi-threaded {0} ms", stopwatch.ElapsedMilliseconds);
    foreach (var kvp in result)
    {
        Console.WriteLine("{0} {1}", kvp.Key, kvp.Value);
    }
}

Auf meinem System liefert das die folgenden Ergebnisse (für einen Release-Build, .NET 6):

single-threaded 50 ms
qqq 1000000
aaa 5000
multi-threaded 26 ms
qqq 1000000
aaa 5000

Es ist nur ein bisschen schneller … ob es sich lohnt, musst du entscheiden.

Beantwortet von – Matthew Watson

Antwort geprüft von – Clifford M. (FixError Volunteer)