Parallel.ForEach и ConcurrentDictionary работают медленнее чем обычный Dictionary

@evgr · Регистрация: 13.02.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте! Есть задача. Массив содержит произвольные строки. Нужно подсчитать, сколько раз каждая из строк встречается в массиве. Задачу решить в один поток и многопоточно, сравнить время выполнения.

У меня почему-то однопоточный вариант выполняется быстрее многопоточного: 90 мс против 300 мс. Как исправить многопоточный вариант, чтобы он работал быстрее однопоточного?

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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("Обычный запуск {0} мс", 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("Параллельный запуск {0} мс", stopwatch.ElapsedMilliseconds);
            foreach (var kvp in freqs)
            {
                Console.WriteLine("{0} {1}", kvp.Key, kvp.Value);
            }
        }
    }
}

@Worldmaster · 13.10.2022, 13:51

Сообщение от evgr

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

А Linq можно использовать??

C#
1
2
3
4
5
var t = strs.GroupBy(a => a).ToArray();
            foreach(var titem in t )
            {
                Console.WriteLine("val: " + titem.Key.ToString() + "; count = " + titem.Count());
            }

@evgr · 13.10.2022, 13:59 **[ТС]**

Сообщение от Worldmaster

А Linq можно использовать?

Можно, но однопоточный вариант и так работает нормально. Проблема в многопоточном.

Добавлено через 3 минуты
Вопрос именно про то, что многопоточный вариант почему-то работает медленнее однопоточного.

В качестве образца я брал пример с docs.microsoft там многопоточный работает быстрее однопоточного на аналогичной задаче с ConcurrentBag

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;
 
namespace ParallelExample
{
    class Program
    {
        static void Main()
        {
            // 2 million
            var limit = 2_000_000;
            var numbers = Enumerable.Range(0, limit).ToList();
 
            var watch = Stopwatch.StartNew();
            var primeNumbersFromForeach = GetPrimeList(numbers);
            watch.Stop();
 
            var watchForParallel = Stopwatch.StartNew();
            var primeNumbersFromParallelForeach = GetPrimeListWithParallel(numbers);
            watchForParallel.Stop();
 
            Console.WriteLine($"Classical foreach loop | Total prime numbers : {primeNumbersFromForeach.Count} | Time Taken : {watch.ElapsedMilliseconds} ms.");
            Console.WriteLine($"Parallel.ForEach loop  | Total prime numbers : {primeNumbersFromParallelForeach.Count} | Time Taken : {watchForParallel.ElapsedMilliseconds} ms.");
 
            Console.WriteLine("Press any key to exit.");
            Console.ReadLine();
        }
 
        /// <summary>
        /// GetPrimeList returns Prime numbers by using sequential ForEach
        /// </summary>
        /// <param name="inputs"></param>
        /// <returns></returns>
        private static IList<int> GetPrimeList(IList<int> numbers) => numbers.Where(IsPrime).ToList();
 
        /// <summary>
        /// GetPrimeListWithParallel returns Prime numbers by using Parallel.ForEach
        /// </summary>
        /// <param name="numbers"></param>
        /// <returns></returns>
        private static IList<int> GetPrimeListWithParallel(IList<int> numbers)
        {
            var primeNumbers = new ConcurrentBag<int>();
 
            Parallel.ForEach(numbers, number =>
            {
                if (IsPrime(number))
                {
                    primeNumbers.Add(number);
                }
            });
 
            return primeNumbers.ToList();
        }
 
        /// <summary>
        /// IsPrime returns true if number is Prime, else false.(https://en.wikipedia.org/wiki/Prime_number)
        /// </summary>
        /// <param name="number"></param>
        /// <returns></returns>
        private static bool IsPrime(int number)
        {
            if (number < 2)
            {
                return false;
            }
 
            for (var divisor = 2; divisor <= Math.Sqrt(number); divisor++)
            {
                if (number % divisor == 0)
                {
                    return false;
                }
            }
            return true;
        }
    }
}

@kolorotur · 13.10.2022, 16:09

Сообщение от evgr

Как исправить многопоточный вариант, чтобы он работал быстрее однопоточного?

Ну перво-наперво использовать проверенные и зарекомендовавшие себя инструменты для сравнения скорости, а не смотреть на секундомер.
С секундомером вы замеряете все что только можно (например, сборку мусора, оставшегося после первого теста и JIT-компиляцию кода).

Во-вторых, многопоточностью нужно правильно пользоваться: например, не тратить все время на ожидание других потоков, а обрабатывать входящий список кусками, время от времени комбинируя эти куски в один словарь.

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

Вот бенчмарк:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
using System.Collections.Concurrent;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
 
BenchmarkRunner.Run<DictionaryBenchmarkk>();
 
public class DictionaryBenchmarkk
{
    private const int qCount = 1000000;
    private const int aCount = 5000;
    private const string qString = "qqq";
    private const string aString = "aaa";
 
    [ParamsSource(nameof(Args))]
    public BenchmarkArgs args;
 
    [Benchmark]
    public void SingleThreaded()
    {
        var strs = args.Values;
 
        Dictionary<string, int> freqs = new Dictionary<string, int>();
 
        for (int i = 0; i < strs.Count; i++)
        {
            if (!freqs.ContainsKey(strs[i]))
                freqs[strs[i]] = 1;
            else
                freqs[strs[i]]++;
        }
    }
 
    [Benchmark()]
    public void MultiThreadedNaive()
    {
        var strs = args.Values;
 
        ConcurrentDictionary<string, int> freqs = new ConcurrentDictionary<string, int>();
 
        Parallel.ForEach(strs, str => { freqs.AddOrUpdate(str, 1, (key, value) => value + 1); });
    }
 
    [Benchmark()]
    public void MultiThreaded()
    {
        var strs = args.Values;
 
        ConcurrentDictionary<string, int> freqs = new ConcurrentDictionary<string, int>();
 
        Parallel.ForEach(
            source: strs,
            localInit: () => new Dictionary<string, int>(),
            body: (value, state, local) =>
            {
                local.TryGetValue(value, out int count);
                local[value] = count + 1;
                return local;
            },
            localFinally: local =>
            {
                foreach (var pair in local)
                    freqs.AddOrUpdate(
                        pair.Key,
                        (key, value) => value,
                        (key, currentCount, count) => currentCount + count,
                        pair.Value);
            });
    }
 
    public IEnumerable<BenchmarkArgs> Args()
    {
        yield return new BenchmarkArgs(CreateHomogenousList(), "Homogenous");
        yield return new BenchmarkArgs(CreateRandomizedList(), "Randomized");
    }
 
    private List<string> CreateRandomizedList()
    {
        var r = new Random(42);
 
        return Enumerable.Repeat(qString, qCount)
            .Concat(Enumerable.Repeat(aString, aCount))
            .OrderBy(x => r.Next())
            .ToList();
    }
 
    private List<string> CreateHomogenousList()
    {
        return Enumerable.Repeat(qString, qCount)
            .Concat(Enumerable.Repeat(aString, aCount))
            .ToList();
    }
}
 
public class BenchmarkArgs
{
    public List<string> Values { get; }
    public string Name { get; }
 
    public BenchmarkArgs(List<string> values, string name)
    {
        Values = values;
        Name   = name;
    }
 
    public override string ToString() => Name;
}

Результат:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
BenchmarkDotNet=v0.13.2, OS=Windows 10 (10.0.19044.2006/21H2/November2021Update)
Intel Xeon Gold 6136 CPU 3.00GHz, 2 CPU, 48 logical and 24 physical cores
.NET SDK=6.0.305
  [Host]     : .NET 6.0.10 (6.0.1022.47605), X64 RyuJIT AVX2
  DefaultJob : .NET 6.0.10 (6.0.1022.47605), X64 RyuJIT AVX2
 
 
|             Method |       args |      Mean |     Error |    StdDev |    Median |
|------------------- |----------- |----------:|----------:|----------:|----------:|
|     SingleThreaded | Homogenous |  38.49 ms |  0.206 ms |  0.183 ms |  38.49 ms |
| MultiThreadedNaive | Homogenous | 519.54 ms | 16.428 ms | 48.182 ms | 534.29 ms |
|      MultiThreaded | Homogenous |  22.67 ms |  0.570 ms |  1.680 ms |  22.51 ms |
|     SingleThreaded | Randomized |  42.72 ms |  0.123 ms |  0.096 ms |  42.72 ms |
| MultiThreadedNaive | Randomized | 520.42 ms | 12.853 ms | 37.697 ms | 532.67 ms |
|      MultiThreaded | Randomized |  23.16 ms |  0.611 ms |  1.800 ms |  22.78 ms |

При "блоковой" обработке получается быстрее. Между однотипным и перемешанным списками разницы немного из-за их общей однообразности.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .