Mierzenie wydajności implementacji dzięki BenchmarkDotNet

Optymalizacja aplikacji to jeden z ważniejszych etapów tworzenia szybkich aplikacji. Praktycznie każdy algorytm można zaimplementować na więcej, niż jeden sposób^[1]Maksimum wydajności w aplikacjach .NET dzięki Hardware Intrinsics. Programiści jednak często stają przed dylematem: skąd wiedzieć, która wersja jest szybsza, albo czy zmiany, które w teorii powinny zwiększyć wydajność, nie robią przypadkiem czegoś dokładnie odwrotnego. Ręczne mierzenie czasu wykonywania implementacji wiąże się z wieloma pytaniami i wątpliwościami, jak zrobić to dobrze, aby wyniki były jak najbardziej reprezentatywne. Z odpowiedzią przychodzi BenchmarkDotNet.

Nie wystarczy zmierzyć czas?

Jednym z najprostszych sposobów, które zapewne prawie każdy programista kiedyś użył, jest zmierzenie różnicy między czasem przed i po wykonaniu operacji. Niestety nie zawsze taki pomiar będzie miarodajny – choćby z powodu w jaki współczesne procesory zarządzają zegarem. Standardowo dla oszczędności energii jest on przetaktowywany „w dół” i szybko podnoszony w sytuacji większego zapotrzebowania. Problem polega na tym, że zwiększenie częstotliwości, z jaką działa procesor wpływa na niemiarodajność wyniku czasu wykonania algorytmu. Co więcej, bieżące taktowanie może być nieprzewidywalne, kiedy nie jest wymuszone większym obciążeniem.

Można przeprowadzić operację mierzenia czasu wielokrotnego wykonania algorytmu i uśrednić go. Tu pojawiają się kolejne problemy, np. procesory Intel w trybie Boost są w stanie pracować przez ograniczony czas, a jeśli benchmark trwa dłużej, to wynik zostanie wypaczony. Na Rys. 1. widać symulację takiego zachowania. Przedstawiony program generuje tablicę z milionem elementów, a następnie sortuje ją przy pomocy LINQ. Pierwsze kilka wywołań potrzebuje wyraźnie więcej czasu niż kolejne. Na końcu uruchomiono symulację końca trybu boost poprzez ograniczenie zegara do 80% poprzedniej wartości, co dało prawie trzykrotnie dłuższy czas.

Możemy zacząć implementować obliczanie odchylenia standardowego, odrzucać skrajne 5% wyników i korzystać z innych sztuczek statystycznych… Czyli robić to, co BenchmarkDotNet od razu zrobi za nas.

Instalacja i przygotowanie

Przykłady z artykułu są dostępne na naszym GitHubie^[2]https://github.com/DawidIzydor/BenchmarkDotNetExamples.

W pierwszym kroku utwórzmy nowy projekt. BenchmarkDotNet napisany jest w .NET Standard 2.0, co oznacza, że możemy z niego korzystać zarówno w .NET Core 2.0 jak i w .NET Framework 4.6 oraz w wersjach nowszych ^[3]https://benchmarkdotnet.org/articles/overview.html.

Bibliotekę do projektu można dodać przy pomocy Menedżera pakietów Nuget szukając w nim BenchmarkDotNet lub z poziomu Konsoli menedżera pakietów wpisując do niej Install-Package BenchmarkDotNet.

Pierwszy benchmark

public class GenerateSortedArrayBenchmark
{
    [Benchmark]
    public int[] ClassicGenerateAndSortUsingLinq()
    {
        var array = new int[1_000_000];
        var rnd = new Random(42);
        for (int i = 0; i < array.Length; ++i)
        {
            array[i] = rnd.Next();
        }
        return array.OrderBy(i => i).ToArray();
    }
}

Tworzymy klasę GenerateSortedArrayBenchmark, w której umieszczamy pierwszą metodę, nazwijmy ją ClassicGenerateAndSortUsingLinq. Przed metodą dodajemy adnotację [Benchmark]. Ważne, aby zarówno klasa, jak i metoda był widoczne publicznie.

Aby uruchomić test zmodyfikujmy Main startując w nim benchmark.

private static void Main()
{
    BenchmarkRunner.Run<OddValuesSumBenchmark>();
}

Ostatnim krokiem jest skompilowanie kodu w konfiguracji Release. Jest to ważne, ponieważ w ten sposób kompilator zaaplikuje optymalizacje, a wygenerowany kod będzie taki, jak uruchamiany w środowisku produkcyjnym.

W końcu możemy uruchomić benchmark. Ważne, aby nie robić tego przez Visual Studio – dołączy on do programu debuger, który może spowalniać wykonanie. Uruchomienie pliku .exe może dać niechciany rezultat w postaci programu zamykającego się od razu po wykonaniu benchmarku – nie zdążymy obejrzeć wyników. Dodanie Console.ReadKey(); aby temu zapobiec nie zawsze jest dobrym rozwiązaniem – łatwo przypadkiem nacisnąć jakiś klawisz i stracić wyniki – co może być szczególnie dotkliwe w przypadku benchmarków, które wykonują się kilka minut i dłużej. Osobiście uruchamiam je przez PowerShell, natomiast dobrym nawykiem jest korzystanie z dowolnej konsoli – w tym wspomnianej już wcześniej Konsoli menedżera pakietów dostępnej bezpośrednio z poziomu Visual Studio.

Program po uruchomieniu wyświetli dużo informacji. Najważniejszą z nich jest tabelka widoczna na końcu wszystkich wiadomości, która pokazuje podstawowe informacje z benchmarku.

Dobrze byłoby do czegoś porównać…

Benchmarków używamy przede wszystkim do znajdowania szybszych implementacji i porównywania czasów różnych rozwiązań. Patrząc na poprzedni kod możemy pomyśleć, że zamiast tworzyć tablicę a następnie ją sortować, możemy skorzystać z mechanizmu, który od razu przy tworzeniu będzie automatycznie sortował za nas. Sprawdźmy, czy zadziała szybciej.

[Benchmark]
public int[] GenerateUsingSortedDictionary()
{
    var dictionary = new SortedDictionary<int, int>();
    var rnd = new Random(42);
    for (var i = 0; i < 1000; ++i)
    {
        var randomNr = rnd.Next();
        if (dictionary.ContainsKey(randomNr))
        {
            dictionary[randomNr]++;
        }
        else
        {
            dictionary.Add(randomNr, 1);
        }
    }
    return dictionary.Keys.ToArray();
}

Kod z ostatniego benchmarku ma kilka problemów. Przede wszystkim nie zwróci dobrej tablicy w przypadku, jeśli wylosowane wartości będą się powtarzać (w tej implementacji zobaczymy tylko unikalne wartości). Nie musimy się tym jednak przejmować, ponieważ jest zdecydowanie zbyt wolny, aby w ogóle się nim zajmować.

Dodałem „po cichu” jedną zmianę w kodzie – przy pierwszym benchmarku zmieniłem adnotację [Benchmark] na [Benchmark(Baseline = true)]. Dzięki temu wynik drugiego benchmarka jest porównywany do pierwszego – kolumna ratio to iloczyn średniego czasu danego benchmarka przez wynik porównawczy.

Spróbujmy jednak przyspieszyć kod

Sprawdzając kod przy pomocy profilera (więcej o nim wkrótce) widzimy, że wąskim gardłem kodu jest sortowanie. Spróbujmy skorzystać z klasycznego Quicksortu^[4]http://www.algorytm.org/algorytmy-sortowania/sortowanie-szybkie-quicksort/quick-1-cs.html zamiast polegać na LINQ.

[Benchmark]
public int[] GenerateAndQuickSort()
{
    var array = new int[1_000_000];
    var rnd = new Random(42);
    for (var i = 0; i < array.Length; ++i)
    {
        array[i] = rnd.Next();
    }

    QuickSort(array, 0, array.Length-1);
    return array;
}

private static void QuickSort(int[] array, int left, int right)
{
    var i = left;
    var j = right;
    var pivot = array[(left + right) / 2];
    while (i < j)
    {
        while (array[i] < pivot) ++i;
        while (array[j] > pivot) --j;
        if (i <= j)
        {
            var tmp = array[i];
            array[i++] = array[j];
            array[j--] = tmp;
        }
    }
    if(left<j) QuickSort(array, left, j);
    if(i < right) QuickSort(array, i, right);
}

Parametryzacja i refaktoryzacja benchmarków

W poprzednim akapicie udało się otrzymać sortowanie trzy razy szybsze od LINQ. BenchmarkDotNet pozwala na łatwe porównanie czasów dla różnych wielkości tablic. W tym celu zrefaktoryzujmy nasze benchmarki i wprowadźmy parametry.

Kontrola wielkości tablicy dzięki parametrowi

BenchmarkDotNet pozwala na uruchomienie każdego z naszych benchmarków dla innej wielkości tablicy. Aby to osiągnąć wprowadźmy parametr N, którego następnie użyjemy w odpowiednich miejscach kodu.

[Params(100, 10_000, 1_000_000)]
public int N;

Adnotacja Params mówi narzędziu, jaką wartość wykorzystać do kolejnych benchmarków. W ten sposób program zamiast trzech benchmarków uruchomi ich tak naprawdę dziewięć.

Refaktoryzacja i GlobalSetup

W każdym z benchmarków powtarza się jedna linijka – inicjalizacja generatora losowych liczb. W ogólnym rozrachunku takiego kodu może być więcej. Chcąc unikać niepotrzebnych powtórzeń, wyciągnijmy go do funkcji inicjalizującej kod. Dzięki temu będziemy mieć pewność, że każdy benchmark będzie korzystał z generatora zainicjalizowanego w taki sam sposób (i nie zapomnieliśmy nigdzie dodać ziarna).

private Random rnd;
[GlobalSetup]
public void Setup()
{
    rnd = new Random(42);
}

Adnotacja GlobalSetup mówi BenchmarkDotNet, aby tej metody użyć przed każdą iteracją każdego benchmarku.

Ostateczne wyniki

Kod oczywiście może być jeszcze przyspieszony, szczególnie dla większych wartości N, np. poprzez wykorzystanie więcej niż jednego wątku. W wynikach widzimy benchmark, który mimo niewielkiej zmianie w kodzie dał 75% wzrostu wydajności dla dużych tablic.

Sam BenchmarkDotNet oprócz tego umożliwia więcej możliwości konfiguracji, mierzenie ilości alokacji oraz zużycie pamięci przez algorytm. Wkrótce pojawią się kolejne artykuły opisujące tego typu scenariusze.