Почему Parallel.ForEach работает медленее со списком строк чем foreach?

Question

Есть код для поиска слов в списке, начинающихся с введённых символов с использованием foreach и Parallel.ForEach. При этом при использовании обычного foreach поиск выполняется быстрее. В чём может быть причина? Может ли это быть связано с накладыванием дополнительных расходов ресурсов и времени на организацию параллельных потоков?

foreach (var word in words)
{
     if (word.StartsWith(searchString))
        {
            matchingWords.Add(word);
        }
 }

И Parallel.ForEach

   Parallel.ForEach(words, word =>
   {
       if (word.StartsWith("b"))
         {
           lock (matchingWords)
           {
              matchingWords.Add(word);
           }
         }
   });

Answer 1

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

Плюс к вышесказанному тормозов добавляет lock, так как подмораживает каждую из итераций, ради того чтобы не повредить результирующую коллекуцию. Как вариант, можно использовать потокобезопасную коллекцию, типа ConcurrentBag<T>.

Если вам хочется вывести вычисления в отдельный поток. Сделайте просто так.

Task<List<string>> task = Task.Run(() =>
{
    List<string> result = new();
    foreach (var word in words)
    {
        if (word.StartsWith(searchString))
        {
            result.Add(word);
        }
    }
    return result;
});
// здесь можно нарисовать в интерфейсе, что поиск начался
List<string> filteredWords = await task;
// здесь можно отобразить результат

И lock в таком случае не потребуется.

Кстати, если так важна производительность, то foreach по массиву работает быстрее, чем по списку.

Answer 2

Update: поступили замечания по тесту. Мои комментарии:

1. Сборка в релизе не дает никакой прибавки к скорости
2. Убирание lock (он тут не нужен) дает минимальную прибавку к скорости
3. .NET 7 на тесте работает на порядок медленнее, чем .NET 4.8

---

Написал свой тест, который показал, что ваше предположение о медленной работе в несколько потоков неверно. Результаты работы программы опубликованной ниже:

simple: 00:00:04.2730974, parallel: 00:00:01.6736944, aepot: 00:00:04.3022718

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
namespace ConsoleApp2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            var swSimple = new Stopwatch();
            var swParallel = new Stopwatch();
            var swAepot = new Stopwatch();
            var random = new Random();
            string searchString = new string('0', 100);
            var words = new List<string>();
            for (int i = 0; i < 5e3; i++)
            {
                char randomNum = "0123456789"[random.Next(10)];
                string sampleString = new string(randomNum, random.Next(100 * i));
                words.Add(sampleString);
            swSimple.Start();
            var list1 = RunSimple(words, searchString);
            swSimple.Stop();

            swParallel.Start();
            var list2 = RunParallel(words, searchString);
            swParallel.Stop();

            swAepot.Start();
            var list3 = RunAepot(words, searchString);
            swAepot.Stop();

            if (list1.Count != list2.Count || list3.Count != list1.Count)
            {
                Console.WriteLine($&quot;Функции не идентичны: words={words.Count}, searchString={searchString.Length}, RunSimple: {list1.Count}, RunParallel: {list2.Count}, RunAepot: {list3.Count}&quot;);
            }
        }

        Console.WriteLine($&quot;simple: {swSimple.Elapsed}, parallel: {swParallel.Elapsed}, aepot: {swAepot.Elapsed}&quot;);

    }

    static List&lt;string&gt; RunSimple(List&lt;string&gt; words, string searchString)
    {
        var matchingWords = new List&lt;string&gt;();
        foreach (var word in words)
        {
            if (word.StartsWith(searchString))
            {
                matchingWords.Add(word);
            }
        }
        return matchingWords;
    }

    static List&lt;string&gt; RunParallel(List&lt;string&gt; words, string searchString)
    {
        var matchingWords = new ConcurrentBag&lt;string&gt;();
        Parallel.ForEach(words, word =&gt;
        {
            if (word.StartsWith(searchString))
            {
                lock (matchingWords)
                {
                    matchingWords.Add(word);
                }
            }
        });
        return matchingWords.ToList();
    }

    static List&lt;string&gt; RunAepot(List&lt;string&gt; words, string searchString)
    {
        Task&lt;List&lt;string&gt;&gt; task = Task.Run(() =&gt;
        {
            List&lt;string&gt; result = new List&lt;string&gt;();
            foreach (var word in words)
            {
                if (word.StartsWith(searchString))
                {
                    result.Add(word);
                }
            }
            return result;
        });
        // здесь можно нарисовать в интерфейсе, что поиск начался
        //List&lt;string&gt; filteredWords = await task;
        // здесь можно отобразить результат
        task.Wait();
        return task.Result;
    }
}

}