Можно ли ускорить алгоритм сортировки с помощью Parallel.ForEach?

Question

Я пытаюсь понять, как работает функция "Parallel.ForEach".Я читал об этом в MSDN, и в целом я понимаю, что чем больше вычислений вы помещаете в цикл, тем быстрее он идет по сравнению с обычным циклом foreach.

Текущий компьютер имеет 4 ядра. (я установлю свой 24-ядерный компьютер через два дня.)

Однако я думаю, что мне нужны некоторые знания в этой области.У меня есть алгоритм сортировки, который выполняет сортировку примерно за 10 секунд на 1 ядре.

Я поместил полный код, где я делаю это на одном ядре, и где я делаю это в цикле: Parallel.ForEach с 4cores.

Мне просто интересно, можно ли ускорить этот тип, используя больше ядер любым возможным способом?

Выполнение testsortFunction () дает следующий результат:

    void testsortFunction()
    {
        String resultstring1 = ""; String resultstring2 = "";
        resultstring1 = sortingtestBENCHMARKS(false);
        resultstring2 = sortingtestBENCHMARKS(true);

        MessageBox.Show(resultstring1 + "\n\n" + resultstring2);
    }
    String sortingtestBENCHMARKS(bool useParallel)
    {
        List<String> sortedLIST = new List<String>(); 
        List<String> minusLIST = new List<String>(); 
        List<String> plusLIST = new List<String>(); 
        var stopwatch = new Stopwatch();

        //Add 3 million elements
        for (double i = 0; i < 1000000; i += 1)
        {
            plusLIST.Add(i + ",awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
        }
        for (double i = 1; i < 2000000; i += 1)
        {
            minusLIST.Add("-" + i + ",awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
        }

        //Do the sorting!
        if (useParallel == false)
        {
            stopwatch.Start();
            sortedLIST = sortLIST(minusLIST, plusLIST); //11 seconds
            stopwatch.Stop();
        }
        else
        {
            stopwatch.Start();
            Parallel.ForEach("dummy", (c) =>
            {
                sortedLIST = sortLIST(minusLIST, plusLIST); //32 seconds
            });
            stopwatch.Stop();
        }
        return "Elapsed Times in seconds(Using Parallel: " + useParallel + "):\n\n" + stopwatch.Elapsed.TotalSeconds; //10.57 seconds
    }
    List<String> sortLIST(List<String> minusLIST, List<String> plusLIST)
    {
        plusLIST = plusLIST.OrderBy(i => double.Parse(i.Split(',')[0])).ToList();plusLIST.Reverse();
        minusLIST = minusLIST.OrderBy(i => double.Parse(i.Split(',')[0].TrimStart('-'))).ToList();
        plusLIST.AddRange(minusLIST);
        return plusLIST;
    }

Answer 1

Я провел несколько тестов и сумел ускорить его в 2 раза ...

public List<String> ParallelSort()
{
    var result = new List<string>(plusLIST.Count + minusLIST.Count);

    var t1 = Task.Run(() => plusLIST.AsParallel().OrderByDescending(i => int.Parse(i.Split(',')[0])));
    var t2 = Task.Run(() => minusLIST.AsParallel().OrderBy(i => int.Parse(i.Split(',')[0].TrimStart('-'))));
    Task.WaitAll(t1, t2);

    result.AddRange(t1.Result);
    result.AddRange(t2.Result);
    return result;
}

Вот тест с использованием BenchmarkDotNet.

(я уменьшил размер спискав 10 раз, потому что бенчмаркинг занимает много времени, и я хочу пойти домой сегодня вечером).

|                 Method |      Mean |    Error |    StdDev |    Median | Gen 0/1k Op | Gen 1/1k Op | Gen 2/1k Op | Allocated Memory/Op |
|----------------------- |----------:|---------:|----------:|----------:|------------:|------------:|------------:|--------------------:|
|                 OPSort | 142.35 ms | 5.150 ms | 14.693 ms | 137.40 ms |  29000.0000 |   1000.0000 |           - |           135.99 MB |
| OPSortByDescendingLazy | 118.19 ms | 2.672 ms |  7.752 ms | 117.01 ms |  29000.0000 |   1000.0000 |           - |           127.32 MB |
|   SlightlyParallelSort | 122.62 ms | 3.063 ms |  8.538 ms | 120.45 ms |  29000.0000 |   1000.0000 |           - |           127.32 MB |
|           ParallelSort |  71.37 ms | 2.190 ms |  6.389 ms |  70.30 ms |  28000.0000 |   1000.0000 |           - |           148.63 MB |
|              RegexSort | 250.80 ms | 4.887 ms |  7.315 ms | 251.70 ms |  32000.0000 |   1000.0000 |           - |           145.99 MB |

И код:

[MemoryDiagnoser]
public class Tests
{
    private List<String> minusLIST = new List<string>(100000);
    private List<String> plusLIST = new List<string>(200000);

    [IterationSetup]
    public void IterationSetup()
    {
        plusLIST.Clear();
        minusLIST.Clear();

        //Add 3 million elements
        for (double i = 0; i < 100000; i += 1)
        {
            plusLIST.Add(i + ",awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
        }
        for (double i = 1; i < 200000; i += 1)
        {
            minusLIST.Add("-" + i + ",awb/aje" + " - " + "ddfas/asa" + " - " + "asoo/qwa");
        }
    }

    [Benchmark]
    public List<String> OPSort()
    {
        plusLIST = plusLIST.OrderBy(i => double.Parse(i.Split(',')[0])).ToList(); plusLIST.Reverse();
        minusLIST = minusLIST.OrderBy(i => double.Parse(i.Split(',')[0].TrimStart('-'))).ToList();
        plusLIST.AddRange(minusLIST);
        return plusLIST;
    }

    [Benchmark]
    public List<String> OPSortByDescendingLazy()
    {
        var result = new List<string>(plusLIST.Count + minusLIST.Count);

        result.AddRange(plusLIST.OrderByDescending(i => int.Parse(i.Split(',')[0])));
        result.AddRange(minusLIST.OrderBy(i => int.Parse(i.Split(',')[0].TrimStart('-'))));
        return result;
    }

    [Benchmark]
    public List<String> SlightlyParallelSort()
    {
        var result = new List<string>(plusLIST.Count + minusLIST.Count);

        var t1 = Task.Run(() => plusLIST.OrderByDescending(i => int.Parse(i.Split(',')[0])));
        var t2 = Task.Run(() => minusLIST.OrderBy(i => int.Parse(i.Split(',')[0].TrimStart('-'))));
        Task.WaitAll(t1, t2);

        result.AddRange(t1.Result);
        result.AddRange(t2.Result);
        return result;
    }

    [Benchmark]
    public List<String> ParallelSort()
    {
        var result = new List<string>(plusLIST.Count + minusLIST.Count);

        var t1 = Task.Run(() => plusLIST.AsParallel().OrderByDescending(i => int.Parse(i.Split(',')[0])));
        var t2 = Task.Run(() => minusLIST.AsParallel().OrderBy(i => int.Parse(i.Split(',')[0].TrimStart('-'))));
        Task.WaitAll(t1, t2);

        result.AddRange(t1.Result);
        result.AddRange(t2.Result);
        return result;
    }

    private static readonly Regex splitRegex = new Regex(@"^(\d+)");
    private static readonly Regex splitWithMinusRegex = new Regex(@"^-(\d+)");

    // To test the suggestion from @PanagiotisKanavos 
    [Benchmark]
    public List<String> RegexSort()
    {
        plusLIST = plusLIST.OrderBy(i => double.Parse(splitRegex.Match(i).Groups[1].Value)).ToList(); plusLIST.Reverse();
        minusLIST = minusLIST.OrderBy(i => double.Parse(splitWithMinusRegex.Match(i).Groups[1].Value)).ToList();
        plusLIST.AddRange(minusLIST);
        return plusLIST;
    }
}

class Program
{
    static void Main(string[] args)
    {
        var summary = BenchmarkRunner.Run<Tests>();

        Console.WriteLine("========= DONE! ============");
        Console.ReadLine();
    }
}

Возможно, это можно ускоритьдалее: следующим шагом будет создание профилировщика.

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

Answer 2

Parallel.ForEach потрясающе для проблем с разделением: то есть проблем, которые можно разбить на совершенно разные подзадачи.Его первый параметр - это перечисляемая коллекция, в которой каждый элемент коллекции представляет собой раздел.

Сортировка одного списка элементов не разделима.Ваш распараллеленный код просто повторяет сортировку целую кучу раз.

Кстати, рассмотрите возможность использования метода list.Sort() dotnet для выполнения своих действий.Очень умные люди оптимизировали это.Если сортируемые элементы не являются простыми строками или скалярами, вы можете предоставить функцию сравнения.