Почему мой запрос AsOrdered PLINQ быстрее, чем мой неупорядоченный

Question

Я написал некоторый базовый пример кода, чтобы ознакомиться с PLINQ.

Я наткнулся на что-то странное. Я не знаю, является ли это ошибкой в ​​моем коде или ошибкой в ​​моем понимании PLINQ.

В документации MSDN говорится, что добавление AsOrdered() сохранит порядок вызова при возможной стоимости производительности.

Я написал несколько юнит-тестов и заметил влияние на порядок на набор результатов, как указано в документации. Но я видел обратное влияние на производительность.

Вот оба моих метода:

public IEnumerable<int> ParallelCalculatePrimesUpTo(int maxValue)
{
    return from number in Enumerable.Range(1, maxValue).AsParallel()
            where IsPrime(number)
            select number;
}

public IEnumerable<int> OrderedParallelCalculatePrimesUpTo(int maxValue)
{
    return from number in Enumerable.Range(1, maxValue).AsParallel().AsOrdered()
            where IsPrime(number)
            select number;
}

И мои очень простые тесты

    [TestMethod]
    public void SimplisticBenchmark6()
    {
        var primeNumberCalculator = new PrimeNumberCalculator();

        var startTime = DateTime.Now;

        primeNumberCalculator.ParallelCalculatePrimesUpTo(10000000).ToList();

        var totalTime = DateTime.Now - startTime;

        Console.WriteLine(totalTime);
    }

    [TestMethod]
    public void SimplisticBenchmark7()
    {
        var primeNumberCalculator = new PrimeNumberCalculator();

        var startTime = DateTime.Now;

        primeNumberCalculator.OrderedParallelCalculatePrimesUpTo(10000000).ToList();

        var totalTime = DateTime.Now - startTime;

        Console.WriteLine(totalTime);
    }

Независимо от того, как часто я запускаю этот тест, заказанная версия превосходит неупорядоченную. Я получаю около 4 секунд быстрее для заказанного на моем четырехъядерном компьютере. Я получаю около 18 секунд за заказанную и 22 секунды за неупорядоченную. Я проводил тесты десятки раз в течение двух дней (с перезагрузками между этими днями).

Если я уменьшу число от 10 000 000 до 6 000 000, различия все еще будут присутствовать, но менее заметны, и если я уменьшу его до 3 000 000, это будет примерно с той же скоростью.

Я попытался запустить тесты в порядке их выполнения, и результаты были одинаковыми.

Вот метод IsPrime, который вызывается в запросе PLINQ:

// uses inneficient trial division algorithm
private bool IsPrime(int number)
{
    if (number == 1)
        return false;

    for (int divisor = 2; divisor <= Math.Sqrt(number); divisor++)
    {
        if (number % divisor == 0)
            return false;
    }

    return true;
}

Чем это объясняется?

Answer 1

Вы всегда запускаете тесты в одном и том же порядке?

Я воссоздал ваши результаты на моей машине и обнаружил, что, независимо от того, "заказанные" результаты были быстрее. Я использовал слегка модифицированный код для бенчмаркинга:

static void Main(string[] args)
{
    const int size = 9000000;
    BenchIt("Parallel", ParallelCalculatePrimesUpTo, size);
    BenchIt("Ordered ", OrderedParallelCalculatePrimesUpTo, size);
    Console.ReadKey();
}

public static void BenchIt(string desc, Func<int, IEnumerable<int>> myFunc, int size)
{
    var sw = new Stopwatch();            
    sw.Restart();
    myFunc.Invoke(size).ToList();
    sw.Stop();
    Console.WriteLine("{0} {1}",desc, sw.Elapsed);
}

Изначально мои результаты показали, что вы были правы. Заказанный метод был быстрее. Однако, если я поменял местами порядок вызовов, я обнаружил, что неупорядоченный метод был быстрее. Другими словами, кто бы ни пошел вторым, он был быстрее. Предположительно, из-за управления пулом потоков, которое выполняет библиотека параллельных задач.

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

Как выглядит ваше оборудование?

PLINQ делает некоторые предположения о том, как выполнить быстрее всего. Я не знаю, поможет ли это вам напрямую в этом случае; но вы можете установить точку останова в середине IsPrime и остановиться на ней после нескольких сотен итераций и изучить окно потока.

Сколько потоков у вас есть при выполнении ParallelCalculatedPrimesUpTo стих OrderedParallelCalculatePrimesUpTo? Я достигаю здесь; но возможно, что решение о различных значениях на вашем компьютере создает неожиданные моменты, которые вы видите. На моей машине - я получаю восемь потоков каждый раз, - но мои времена почти одинаковы - какой бы из них ни вызывался первым, он медленнее из-за создания этих потоков. Но вам не гарантируется определенное количество потоков (вы можете установить максимум, но вы не можете принудительно использовать их).

Answer 2

Можете ли вы сказать нам, какова загрузка ЦП для 4 разных ядер? Возможно, что AsOrdered() заставляет делать больше последовательных вызовов на том же ядре. Благодаря улучшенной локализации кэширование на уровне кремния и предсказание ветвлений могут работать в вашу пользу.

Другая возможность состоит в том, что в.NET Framework есть некоторая оптимизация для случая монотонно увеличивающихся целых чисел (int.Range) при использовании проекции AsOrdered(). Я не уверен, как это будет работать, но это возможно.

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