Alokacja pamięci a false sharing

Kiedyś pisałem już o false sharing. Jeśli problem nie jest znany, najpierw zachęcam do przeczytania tego wpisu, ponieważ nie będę tutaj pisał o teoretycznych zagadnieniach:

http://www.pzielinski.com/?p=1489

Oprócz wyjaśnienia podstaw, podałem przykład struktury danych składających się z dwóch Int32. Pokazałem również jakie pułapki czekają nas przy pracy z tablicami. To zadziwiające, że kolejność w jakiej przeglądamy tablicę ma tak ogromne znaczenie w wydajności (kod może być nawet kilkakrotnie wolniejszy). Oczywiście mowa tutaj tylko o wielowątkowym dostępie.

Dzisiaj kolejny przykład, na który możemy natrafić każdego dnia, pisząc kod wielowątkowy.

Alokacja pamięci w .NET jest zaawansowanym mechanizmem i bierze pod uwagę architekturę CPU. Jak napisałem (patrz powyższy post), zmienne będące blisko siebie w programie, również zostaną zaalokowane blisko siebie w pamięci (patrz przykład dwóch Int32). W większości przypadków, ma  to korzystny wpływ na wydajność. Alokacja obiektów na stercie, bierze pod uwagę wątek, z którego jest alokowana. Ma to bardzo pozytywne skutki, ponieważ dzięki temu nie mamy problemów ze wspomnianym false sharing i cache misses. Obiekty z różnych miejsc, zostaną zadeklarowane w możliwie dalekich od siebie miejscach. Napiszmy dwa programy, jeden mający problemy z false sharing:

internal class CacheLineSample
{
   public int Number { get; set; }
}

internal class Program
{
   private static void Main(string[] args)
   {
       var stopwatch = Stopwatch.StartNew();

       var data = new[] {new CacheLineSample(), new CacheLineSample(), new CacheLineSample(), new CacheLineSample()};

       Task t1 = Task.Factory.StartNew(() => Run(0, data));
       Task t2 = Task.Factory.StartNew(() => Run(1, data));
       Task t3 = Task.Factory.StartNew(() => Run(2, data));
       Task t4 = Task.Factory.StartNew(() => Run(3, data));

       Task.WaitAll(t1, t2, t3, t4);
       stopwatch.Stop();
       Console.WriteLine(stopwatch.ElapsedMilliseconds);
   }

   private static void Run(int index,CacheLineSample[] data)
   {
       CacheLineSample cacheLineSample = data[index];

       for (int i = 0; i < 10000000; i++)
       {
           cacheLineSample.Number++;
       }
   }
}

Deklarujemy tutaj pamięć w głównym wątku. A co za tym idzie, naturalne jest, że GC będzie spodziewał się, że elementy tablicy powinny być zadeklarowane koło siebie w pamięci. Następnie w różnych wątkach, zwiększamy licznik – każdy wątek operuje na osobnej klasie, której obiekt należy do wspólnej tablicy. Na swoim komputerze dostałem wynik ~550 ms.

Następnie spróbujmy zoptymalizować kod tak, że alokacja będzie dokonywana na osobnym wątkach – a co za tym idzie, logiczne jest umieszczenie obiektów w różnych miejscach w pamięci:

internal class CacheLineSample
{
    public int Number { get; set; }
}

internal class Program
{
    private static void Main(string[] args)
    {
        var stopwatch = Stopwatch.StartNew();

        var data = new CacheLineSample[4];

        Task t1 = Task.Factory.StartNew(() => Run(0, data));
        Task t2 = Task.Factory.StartNew(() => Run(1, data));
        Task t3 = Task.Factory.StartNew(() => Run(2, data));
        Task t4 = Task.Factory.StartNew(() => Run(3, data));

        Task.WaitAll(t1, t2, t3, t4);
        stopwatch.Stop();
        Console.WriteLine(stopwatch.ElapsedMilliseconds);
    }

    private static void Run(int index, CacheLineSample[] data)
    {
        CacheLineSample cacheLineSample = data[index] = new CacheLineSample();

        for (int i = 0; i < 10000000; i++)
        {
            cacheLineSample.Number++;
        }
    }
}

Otrzymany wynik to ~160 ms. Optymalizacja jest znacząca i nie należy jej bagatelizować. Każdy kto interesuje się procesorami wie jakie są trendy na rynku od wielu lat. Czasy kiedy co miesiąc wychodził procesor z szybszym zegarem już dawno minęły. Kolejną rewolucją w wydajności było doczepianie kilka dodatkowych rdzeni, co umożliwia nam realną pracę w środowisku wielowątkowym. Szybko jednak okazało się, że prawdziwą przeszkodzą jest dostęp do pamięci. Procesory były na tyle szybkie, że optymalizacje należało skierować w stronę buforowania i  unikania cache misses a nie na częstotliwość zegara czy nawet liczbę rdzeni. Problem false sharing jest znakomitym przykładem, jak dysponując szybkim procesorem, można zdegradować wydajność poprzez problemy z buforowaniem.

3 thoughts on “Alokacja pamięci a false sharing”

  1. Ciekawy temat, chociaż mam mieszane uczucia co do wyników. W trybie debug mam podobne wyniki. Po kompilacji w trybie release i uruchomieniu programu poza Visual Studio, czasy wynoszą odpowiednio 20 ms i 23 ms. Optymalizacja robi swoje 🙂 Nie chciałbym wyciągać pochopnych wniosków, że gra nie warta świeczki… Czy miałeś może przypadek, że w trybie release też była tak duża różnica jak w temacie (lub chociaż więcej niż 30%)?

  2. @Mad:
    To wszystko zależy od CPU itp.
    Podany przykład jest bardzo prosty i dlatego łatwo go zoptymalizować automatycznie (jak to najwidoczniej zrobil kompilator).

    W praktyce nie mozna liczyc, ze kompilator zrobi to za nas – to zbyt skomplikowana sprawa.

    False sharing to nie jest mikro-optymalizacja jak niektore przyklady, ktore pokazywalem na blogu. To prawdzie zagrozenie dla wydajnosci.

    Pozdrawiam,
    Piotr

Leave a Reply

Your email address will not be published.