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.
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%)?
Może trochę dokładniej, 23 ms dla wariantu pierwszego i 20 ms dla drugiego.
@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