Trzy słowa o optymalizacji LINQ

By | October 8, 2016

Kontynuując wątek LINQ, który podjąłem jakiś czas temu, poruszę dziś temat optymalizacji operacji jakie wykonujemy na kolekcjach. Na starcie muszę się przyznać, że tytuł nie jest do końca zgodny z prawdą, bo trzy słowa to o wiele za mało, by wejść w głębiej w temat optymalizacji zapytań. Są jednak 3 metody, które można wykorzystać do znacznego przyspieszenia wykonywania operacji w bardziej rozbudowanych łańcuchach przy minimalnym nakładzie pracy.

Na starcie zaznaczę, że opisane poniżej zagadnienia będą działały wyłącznie na operacjach wykonywanych na kolekcjach będących w pamięci, więc ich stosowanie w przypadku korzystania z LINQ to Entities może być możliwe, ale wyniki najprawdopodobniej będą nieprzewidywalne. Nawet w przypadku korzystania z nich w zwyczajnym LINQ zalecam ostrożność i pokrycie kodu testami lub przynajmniej dokładne, manualne sprawdzenie czy wynik na wyjściu jest zgodny z oczekiwaniami, bo w niektórych sytuacjach niestety może on być nieco inny niż to czego oczekujemy. Dlaczego? O tym powiem w dalszej części posta.

Zacznijmy od rozpisania łańcucha LINQ wykonującego kilka prostych operacji na stosunkowo dużej kolekcji, by wykonać dość dużo czynności, by było to widoczne w wynikach testu. Czas zmierzę za pomocą zwykłego Stopwatcha i wyrzucę do konsoli, będę podawał wyniki uśrednione po wykonaniu kilkudziesięciu pomiarów. Czas wykonania będzie się oczywiście różnił, ale warto zwrócić uwagę na proporcje.  Zacznijmy zatem od zbioru testowego i operacji, które będę na nim wykonywał.

static IEnumerable<int> testData { get { return Enumerable.Range(1, 10000000); } }

static void Main(string[] args)
{
    var sw1 = new Stopwatch();
    var sw2 = new Stopwatch();
    var sw3 = new Stopwatch();
    var sw4 = new Stopwatch();

    sw1.Start();
    var normalLINQTest = testData.Select(x => x.ToString())
        .Select(x => x + "1")
        .Select(x => long.Parse(x))
        .Select(x => Math.Ceiling(x / Math.PI))
        .Select(x => x * 2)
        .Select(x => x + 1)
        .Select(x => (long)Math.Floor(Math.Sqrt(x)))
        .OrderByDescending(x => x)
        .Select(x => x.ToString())
        .Select(x => int.Parse(x))
        .Select(x => (x % 5) * Math.PI)
        .Select(x => Math.Truncate(x))
        .Sum();

    Console.WriteLine(normalLINQTest);
    sw1.Stop();
    Console.WriteLine($"Normal LINQ test was running for: {sw1.Elapsed.ToString()}");
}

Jest to ciąg kilku stosunkowo prostych operacji na zbiorze 10 milionów liczb. Operacje nie są zbyt skomplikowane, więc potrzebowałem odpowiedniej ilości danych, by różnica w czasie wykonywania była w ogóle zauważalna. Średni czas wykonania zwrócony przez Stopwatch to około 11,06 sekundy. Czy możemy to odrobinę przyspieszyć?

Zacznijmy od pierwszego sposobu na optymalizację i skorzystajmy z biblioteki LINQ Optimizer, o której więcej można przeczytać pod linkiem: http://nessos.github.io/LinqOptimizer/. W telegraficznym skrócie jej działanie opiera się na konwersji zapytania LINQ do drzewa wyrażeń, optymalizacji i kompilacji do Intermediate Language, by zapewnić jak najwydajniejszy kod. W tym miejscu nie mogę nie polecić podcastu DevReview i odcinka z Pawłem Łukasikiem dotyczącego Intermediate Language właśnie, można go przesłuchać tutaj do czego gorąco zachęcam, bo temat jest bardzo ciekawy.

Jak już jesteśmy przy linkach to polecam zajrzenie do zakładki performance na stronie wspomnianej biblioteki i rzut oka na wykresy. Wynika z nich, że zapytania mogą być wykonywane nawet kilkukrotnie szybciej niż normalnie. Aby to sprawdzić należy zainstalować nugeta i dopisać do naszego LINQ dwie metody .AsQueryExpr() przed rozpoczęciem chainowania LINQ i .Run() w momencie wywołania całego zapytania, które w obecnej formie nie zacznie się wykonywać samo z siebie przy chociażby zwykłej iteracji. Kod z LINQ Optimizerem wygląda następująco:

sw3.Start();
var LINQOptimizerTest = testData.AsQueryExpr()
    .Select(x => x.ToString())
    .Select(x => x + "1")
    .Select(x => long.Parse(x))
    .Select(x => Math.Ceiling(x / Math.PI))
    .Select(x => x * 2)
    .Select(x => x + 1)
    .Select(x => (long)Math.Floor(Math.Sqrt(x)))
    .OrderByDescending(x => x)
    .Select(x => x.ToString())
    .Select(x => int.Parse(x))
    .Select(x => (x % 5) * Math.PI)
    .Select(x => Math.Truncate(x))
    .Sum();

Console.WriteLine(LINQOptimizerTest.Run());
sw3.Stop();
Console.WriteLine($"LINQ Optimizer test was running for: {sw3.Elapsed.ToString()}");

Czas wykonania jest zauważalnie niższy, bo wynosi około 7,58s. Różnica nie jest tak widoczna jak na niektórych wykresach, którymi chwalą się autorzy LINQ Optimizera, ale wyniki są w dużej mierze zależne od wykonywanych przez nas metod. Niektóre funkcjonalności LINQ nie zostały zaimplementowane i sądząc po ostatnim braku aktywności twórców wątpię, by miało się to zmienić.

Jeśli zajrzeliście na wspomniane wykresy to być może zauważyliście, że LINQ Optimizer wcale nie osiąga najlepszych wyników i jest coś, co dosyć mocno go wyprzedza. Tym czymś jest dotnetowy Parallel LINQ (PLINQ), który po wywołaniu metody .AsParallel() dzieli cały łańcuch na oddzielne wątki, a my nie musimy się niczym martwić. Przynajmniej teoretycznie, bo w niektórych przypadkach zdarza mu się odrobinę pomieszać kolejność wykonywania operacji i zwrócić zupełnie inny niż oczekiwany wynik. Dlatego też dobrze jest takie zapytanie obłożyć testami i dodać .AsParallel(), w momencie gdy będziemy pewni, że zwraca to czego oczekujemy. Używając następującego kodu sprawdźmy czy gra jest w ogóle warta świeczki:

sw2.Start();
var parallelLINQTest = testData.AsParallel()
    .Select(x => x.ToString())
    .Select(x => x + "1")
    .Select(x => long.Parse(x))
    .Select(x => Math.Ceiling(x / Math.PI))
    .Select(x => x * 2)
    .Select(x => x + 1)
    .Select(x => (long)Math.Floor(Math.Sqrt(x)))
    .OrderByDescending(x => x)
    .Select(x => x.ToString())
    .Select(x => int.Parse(x))
    .Select(x => (x % 5) * Math.PI)
    .Select(x => Math.Truncate(x))
    .Sum();

Console.WriteLine(parallelLINQTest);
sw2.Stop();
Console.WriteLine($"Parallel LINQ test was running for: {sw2.Elapsed.ToString()}");

Wynik jest bardzo zadowalający bo średnia wynosi około 2,3s, jest to około pięciokrotnie szybciej niż zwyczajne, sekwencyjne LINQ i mimo, że PLINQ nie zawsze da się zastosować, to w niektórych przypadkach warto spróbować, bo możemy całkiem sporo zyskać.

A czy dwie przedstawione metody można ze sobą połączyć? Oczywiście. LINQ Optimizer w pełni wspiera PLINQ i byłoby głupio nie sprawdzić co się stanie gdy to zrobimy. Biorąc pod uwagę to, że poprzednie wyniki były bardzo zadowalające, to przy takim połączeniu sił nasze zapytanie powinno się wykonać jeszcze przed uruchomieniem aplikacji ;). 

sw4.Start();
var parallelLINQOptimizerTest = testData.AsParallel().AsQueryExpr()
    .Select(x => x.ToString())
    .Select(x => x + "1")
    .Select(x => long.Parse(x))
    .Select(x => Math.Ceiling(x / Math.PI))
    .Select(x => x * 2)
    .Select(x => x + 1)
    .Select(x => (long)Math.Floor(Math.Sqrt(x)))
    .OrderByDescending(x => x)
    .Select(x => x.ToString())
    .Select(x => int.Parse(x))
    .Select(x => (x % 5) * Math.PI)
    .Select(x => Math.Truncate(x))
    .Sum();

Console.WriteLine(parallelLINQOptimizerTest.Run());
sw4.Stop();
Console.WriteLine($"Parallel LINQ Optimizer test was running for: {sw4.Elapsed.ToString()}");

Wynik w tym wypadku jest nieco rozczarowujący, bo czas wykonania wynosi średnio 7,34s czyli niewiele krócej niż przy wykorzystaniu samego LINQ Optimizera i kilkukrotnie dłużej niż w przypadku korzystania jedynie z PLINQ. W tej sytuacji proporcje potrafią się zmieniać bardzo mocno i są przypadki gdy taki połączenie działa niemal tak samo szybko jak samo PLINQ, ale nigdy nie udało mi się osiągnąć lepszego wyniku niż samotnym .AsPararrel().

Kończąc ten wpis wspomnę o jeszcze jednym pomiarze, który ma trochę wspólnego z tym postem, ale bliżej mu do posta o metodzie .ToList(), który planuję opublikować w następnej kolejności. Trochę o tym jak działa LINQ mogliście przeczytać w poście dotyczącym deferred execution i powinniście już wiedzieć, że nie ma sensu ewaluowaniazapytania jeśli nie jest to konieczne. Jak więc myślicie, o ile wzrośnie czas wykonania powyższego łańcucha jeśli w co drugiej linii wstawię metodę .ToList() (Bo jeśli zrobię to w każdej linii, to otrzymam wyjątek System.OutOfMemoryException :() 

var normalLINQTest = testData.ToList()
    .Select(x => x.ToString())
    .Select(x => x + "1").ToList()
    .Select(x => long.Parse(x))
    .Select(x => Math.Ceiling(x / Math.PI)).ToList()
    .Select(x => x * 2)
    .Select(x => x + 1).ToList()
    .Select(x => (long)Math.Floor(Math.Sqrt(x)))
    .OrderByDescending(x => x).ToList()
    .Select(x => x.ToString())
    .Select(x => int.Parse(x)).ToList()
    .Select(x => (x % 5) * Math.PI)
    .Select(x => Math.Truncate(x)).ToList()
    .Sum();

Powyższy kod wykonuje się około 18,38s, te samo zapytanie bez używania .ToList() wykonywało się 11,06s. Dlatego też jeśli korzystamy z LINQ i mamy możliwość operowania na IEnumerable, ale ten temat poruszę w kolejnym poście.