Параллельная оптимизация запросов Linq - PullRequest
14 голосов
/ 04 февраля 2012

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

Я спрашиваю, потому что недавно я провел рефакторинг некоторого неловко параллельного кода, изменив некоторые методы и добавив AsParallel в определенные ключевые места. Время выполнения сократилось с 2 минут до 45 секунд, но из монитора производительности стало ясно, что в некоторых местах все ядра ЦП использовались не полностью. После нескольких неудачных попыток я принудительно выполнил некоторые запросы, используя ToArray, и время выполнения уменьшилось до 16 секунд. Было бы неплохо сократить время выполнения кода, но это также немного сбивало с толку, потому что было неясно, где в коде нужно вводить запросы с помощью ToArray. Ожидание до последней минуты выполнения запроса не было оптимальной стратегией, но совершенно неясно, в каких точках кода необходимо принудительно выполнить некоторые из подзапросов, чтобы использовать все ядра ЦП.

Так как я понятия не имею, как правильно перетаскивать ToArray или другие методы, которые заставляют выполнять вычисления linq для достижения максимальной загрузки ЦП. Так есть ли общие рекомендации и инструменты для оптимизации параллельных запросов linq?

Вот пример псевдокода:

var firstQuery = someDictionary.SelectMany(FirstTransformation);
var secondQuery = firstQuery.Select(SecondTransformation);
var thirdQuery = secondQuery.Select(ThirdTransformation).Where(SomeConditionCheck);
var finalQuery = thirdQuery.Select(FinalTransformation).Where(x => x != null);

FirstTransformation, SecondTransformation, ThirdTransformation все они связаны с процессором и с точки зрения сложности представляют собой несколько умножений матрицы 3x3 и некоторые ветви if. SomeConditionCheck это в значительной степени проверка null. FinalTransformation является наиболее интенсивной ЦП частью кода, потому что он выполнит целый набор пересечений на плоскости и проверит наличие полигонов для этих пересечений, а затем извлечет пересечение, которое находится ближе всего к определенной точке на линии.

Понятия не имею, почему места, куда я положил AsParallel, так же сократили время выполнения кода, как и он. Я теперь достиг локального минимума с точки зрения времени выполнения, но я понятия не имею, почему. Это была просто глупая удача, что я наткнулся на это. В случае, если вам интересно, где поставить AsParallel, это первая и последняя строки. Помещение AsParallel где-либо еще только увеличит время выполнения, иногда до 20 секунд. В первой строке скрыт ToArray.

Ответы [ 2 ]

15 голосов
/ 06 февраля 2012

Здесь происходит пара вещей:

  1. PLINQ распараллеливает коллекции более эффективно, чем неучтенные IEnumerables. Если у вас есть массив, он делит длину массива на количество ядер ЦП и распределяет их равномерно. Но если у вас есть IEnumerable с неизвестной длиной, он делает глупый экспоненциальный тип наращивания, когда задачи будут обрабатывать 1, 2, 4, 8 и т. Д. Элементы одновременно, пока не достигнет конца IEnumerable.
  2. Распараллеливая все ваши запросы, вы разбиваете работу на крошечные куски. Если у вас есть M параллельных запросов по N элементам, вы получите M * N задач. В этом есть большая нагрузка на поток, чем если бы вы просто распараллеливали последний запрос, и в этом случае вы бы получили только N задач.
  3. PLINQ работает лучше всего, когда каждая задача занимает примерно одинаковое количество времени для обработки. Таким образом, он может равномерно распределить их по ядрам. Распараллеливая каждый из ваших запросов с разным поведением производительности, вы получаете задачи M * N, которые занимают различное количество времени, и PLINQ не может планировать их оптимально (поскольку он не знает заранее, сколько времени может занять каждый ).

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

var firstQuery = someDictionary.SelectMany().ToArray().Select(FirstTransformation);
var secondQuery = firstQuery.Select(SecondTransformation);
var thirdQuery = secondQuery.Select(ThirdTransformation).AsParallel().Where(SomeConditionCheck).ToArray();
var finalQuery = thirdQuery.Select(FinalTransformation).AsParallel().Where(x => x != null);
7 голосов
/ 07 февраля 2012

Почти невозможно сказать, не увидев реальный код. Но в качестве общего руководства вы должны избегать использования P / LINQ во время обработки сложных чисел, поскольку издержки делегата и IEnumerable слишком велики. Скорость, которую вы получаете, используя потоки, вероятно, съедается удобными абстракциями, которые обеспечивает LINQ.

Вот некоторый код, который вычисляет сумму из двух целочисленных списков, выполняет некоторое сравнение с плавающей запятой, а затем вычисляет его стоимость. Довольно простые вещи, которые можно сделать с помощью LINQ, оператора .Zip ... или по старинке с циклом for.

Обновление 1 с обновленным ParallelLinq на моем ядре Haswell 8

  • Linq 0,95 с
  • Linq Parallel 0,19 с
  • Оптимизировано 0,45 с
  • Оптимизированная параллель 0,08 с

Обновление 1 Конец

  • LINQ 1,65 с
  • Оптимизировано 0,64 с
  • Оптимизированная параллель 0,40 с

Разница во времени почти в 3 раза из-за лени IEnumerable и накладных расходов при вызове методов (я использовал режим Release x32 для Windows 7, двухъядерный .NET 4). Я пытался использовать AsParallel в версии LINQ, но он действительно стал медленнее (2,3 с). Если вы работаете с данными, вы должны использовать конструкцию Parallel.For, чтобы получить хорошую масштабируемость. IEnumerable сам по себе является плохим кандидатом на распараллеливание, поскольку

  • Вы не знаете, сколько у вас работ, прежде чем перечислили до конца.
  • Вы не можете сделать нетерпеливый отрывов, потому что вы не знаете, как быстро IEnumerable будет возвращать следующий элемент (может быть вызов веб-службы или доступ индексный массив).

Ниже приведен пример кода для иллюстрации сути. Если вы хотите оптимизировать работу с голым металлом, вам нужно сначала избавиться от абстракций, которые стоят слишком дорого за единицу. Доступ к массиву намного дешевле по сравнению со встроенными вызовами методов MoveNext () и Current.

    class Program
    {
        static void Main(string[] args)
        {
            var A = new List<int>(Enumerable.Range(0, 10*1000*1000));
            var B = new List<int>(Enumerable.Range(0, 10*1000*1000));

            double[] Actual = UseLinq(A, B);
            double[] pActual = UseLinqParallel(A, B);

            var other = Optimized(A, B);
            var pother = OptimizedParallel(A, B);
        }

        private static double[] UseLinq(List<int> A, List<int> B)
        {
            var sw = Stopwatch.StartNew();
            var Merged = A.Zip(B, (a, b) => a + b);
            var Converted = A.Select(a => (float)a);

            var Result = Merged.Zip(Converted, (m, c) => Math.Cos((double)m / ((double)c + 1)));

            double[] Actual = Result.ToArray();
            sw.Stop();

            Console.WriteLine("Linq {0:F2}s", sw.Elapsed.TotalSeconds);
            return Actual;
        }

    private static double[] UseLinqParallel(List<int> A, List<int> B)
    {
        var sw = Stopwatch.StartNew();
        var x = A.AsParallel();
        var y = B.AsParallel();

        var Merged = x.Zip(y, (a, b) => a + b);
        var Converted = x.Select(a => (float)a);

        var Result = Merged.Zip(Converted, (m, c) => Math.Cos((double)m / ((double)c + 1)));

        double[] Actual = Result.ToArray();
        sw.Stop();

        Console.WriteLine("Linq Parallel {0:F2}s", sw.Elapsed.TotalSeconds);
        return Actual;
    }        

        private static double[] OptimizedParallel(List<int> A, List<int> B)
        {
            double[] result = new double[A.Count];
            var sw = Stopwatch.StartNew();
            Parallel.For(0, A.Count, (i) =>
            {
                var sum = A[i] + B[i];
                result[i] = Math.Cos((double)sum / ((double)((float)A[i]) + 1));
            });
            sw.Stop();

            Console.WriteLine("Optimized Parallel {0:F2}s", sw.Elapsed.TotalSeconds);
            return result;
        }

        private static double[] Optimized(List<int> A, List<int> B)
        {
            double[] result = new double[A.Count];
            var sw = Stopwatch.StartNew();
            for(int i=0;i<A.Count;i++)
            {
                var sum = A[i] + B[i];
                result[i] = Math.Cos((double)sum / ((double)((float)A[i]) + 1));
            }
            sw.Stop();

            Console.WriteLine("Optimized {0:F2}s", sw.Elapsed.TotalSeconds);
            return result;
        }
    }
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...