False sharing

Jestem w trakcie czytania Patterns for Parallel Programming. Jest tam wiele anty-wzorców programowania współbieżnego, a pośród nich False sharing (nawet nie próbuję tego tłumaczyć na polski).

Ze względu na wydajność, systemy zarządzania pamięcią wykorzystują cache’owane bloki pamięci najczęściej po 64 lub 128 bajty. Pobieranie w takich większych kawałkach (zamiast po bajcie) jest sensowne, ponieważ najczęściej dane które potrzebujemy są obok siebie (na stosie, jak i na zarządzanej stercie). Dzięki temu pobieramy je za jednym razem.

Współbieżnie

Jest to jednak niekorzystne gdy różne procesory operują na różnych danych, które jednak są umiejscowione blisko siebie w pamięci. Wspomniany cache’owany blok pamięci jest tutaj najmniejszą jednostką jaką możemy pobrać i nie może być wykorzystany przez różne procesory w tym samym momencie.

Złe podejście

Przykład z książki inicjalizuje dwie instancje klasy Random. Każdy wątek operuje tylko na jednej z nich (brak konfliktu). Niestety są umieszczone obok siebie w pamięci. Każde odwołanie do Next modyfikuje wewnętrzny stan instancji Random, więc będzie zakładany jakby hardwarowy lock, którego nie widać bezpośrednio w kodzie.

        public void WithFalseSharing()
        {
            Random rand1 = new Random(), rand2 = new Random();
            int[] results1 = new int[20000000], results2 = new int[20000000];
            Parallel.Invoke(
                () =>
                {
                    for (int i = 0; i < results1.Length; i++)
                        results1[i] = rand1.Next();
                },
                () =>
                {
                    for (int i = 0; i < results2.Length; i++)
                        results2[i] = rand2.Next();
                });
        }

Powyższy kod wykonuje się u mnie w ok. 2,2 sekundy. Jeśli porównać to z 2 sekundami w których wykonuje się synchroniczna wersja, widać tutaj wymieniony problem dostępu do pamięci.

Rozwiązanie

Druga wersja rozwiązuje ten problem. Obiekty na zarządzanej stercie powinny zostać utworzone w kolejności rand1, results1, rand2, results2 (inna prawdopodobna to: rand2, results2, rand1, results1), gdzie results1 wystarczająco dobrze rozdziela instancje Random. Kod wykonuje się zdecydowanie bardziej równolegle w ok. 1,2 sekundy (na dwu rdzeniowej maszynie).

        public void WithoutFalseSharing()
        {
            int[] results1, results2;
            Parallel.Invoke(
                () =>
                {
                    Random rand1 = new Random();
                    results1 = new int[20000000];
                    for (int i = 0; i < results1.Length; i++)
                        results1[i] = rand1.Next();
                },
                () =>
                {
                    Random rand2 = new Random();
                    results2 = new int[20000000];
                    for (int i = 0; i < results2.Length; i++)
                        results2[i] = rand2.Next();
                });
        }

Jest tutaj co prawda możliwość, że results1 nie rozdzieli rand1 i rand2, ale to już jest pomijalny hazard o ile nie niemożliwy na procesorach, które pobierają kilka rozkazów na raz.

Podsumowanie

Bardzo trudne do wytropienia gdy się o tym nie słyszało. Czasem trzeba celowo obiekty oddzielać, niestety z czasem podczas kolejnych Garbage Collection mogę się one znowu przybliżać.

Z góry przepraszam za niektóre tłumaczenia. Uwagi mile widziane.

Źródła

Patterns for Parallel Programming, strona 44.
Obrazek z artykułu na codeproject.

Advertisements
Ten wpis został opublikowany w kategorii Programowanie i oznaczony tagami , , , , . Dodaj zakładkę do bezpośredniego odnośnika.