W celu optymalizacji każdy procesor posiada swój cache. Temat jest dosyć rozbudowany bo zwykłe cache jest podzielony na kilka warstw aby przyśpieszyć dostęp do niego. W dzisiejszym w poście chciałbym wprowadzić pojęcie cache line co jest tak naprawdę po prostu wpisem w pamięci podręcznej. Jeśli procesor czyta jakieś dane to umieszcza je w cache line. Cache line to nie tylko jedna, pojedyncza zmienna a na przykład 64 bajty. Jeśli zatem czytamy pojedynczą zmienną Int32,  w rzeczywistości procesor przeczyta również zmienną przylegającą do Int32 (tak aby razem przeczytać 64).

Takie zachowanie bardzo często ma pozytywne skutki – bardzo prawdopodobne, że w praktyce będziemy chcieli skorzystać z dwóch, przylegających do siebie zmiennych jednocześnie. Wadą, mającą ogromny wpływ na wydajność, jest sytuacja kiedy wątek 1 chce przeczytać pierwszą zmienną a wątek 2, drugą.  Niestety gdy dwa rdzenie chcą mieć dostęp do tych samych danych, wtedy CPU musi więcej wykonać roboty aby przekazać tą wartość w bezpieczny sposób. Chcemy zatem unikać scenariuszy, gdzie dwie zmienne z tego samego cache line, będą potrzebne dwóm różnym rdzeniom procesora (dla operacji write). Rozważmy następującą klasę:

class CacheLineSample
{
   public Int32 Integer1;
   public Int32 Integer2;
}

Mój CPU posiada L1 równy 128KB a CacheLine 64 KB. Oznacza to, że oba pola powyższej klasy mogą znaleźć się w tym samym cache. Napiszmy teraz program, który tworzy dwa wątki (potencjalnie mogą być wykonywane na różnych rdzeniach) i każdy z nich będzie zwiększał wartość jednego z pól:

class Program
{
   private static CacheLineSample _sample=new CacheLineSample();
   static void Main(string[] args)
   {
       var stopwatch=Stopwatch.StartNew();
       Task t1 = Task.Factory.StartNew(()=>TestField(0));
       Task t2 = Task.Factory.StartNew(() => TestField(1));
       Task.WaitAll(t1, t2);
       stopwatch.Stop();
       Console.WriteLine(stopwatch.ElapsedTicks);
   }
   private static void TestField(int index)
   {
       for (int i = 0; i < 100000000; i++)
       {
           if (index == 0)
               _sample.Integer1++;
           else
               _sample.Integer2++;
       }
   }
}

Następnie odpalmy ten sam program, ale modyfikując naszą klasę następująco:

[StructLayout(LayoutKind.Explicit)]
class CacheLineSample
{
   [FieldOffset(0)]
   public Int32 Integer1;
   [FieldOffset(64)]
   public Int32 Integer2;
}

Zauważymy, że w zależności od kompilatora, procesora, różnica może być 2 lub nawet 5 krotna! W momencie gdy oba rdzenie dokonają cache wtedy aktualizacja zmiennych jest bardzo czasochłonna ponieważ należy o tym powiadomić drugi rdzeń. Powyższy mechanizm nazywa się “false sharing” ponieważ z punktu widzenia programisty, żadne zmienne nie są dzielone (czego należy unikać w programowaniu wielowątkowym) ale z punktu widzenia CPU są one niestety współdzielone. Każda operacja zapisu powoduje, że cache jest nieważny oraz czas jest marnowany na odpowiednią synchronizację. Inny przykład to pętla po tablicy dwuwymiarowej:

for (int row = 0; row < N; row++) 
{
    for (int column = 0; column < N; column++) 
    {
        array[row, column] = GetRandomValue();
    }
}

for (int column = 0; column < N; column++) 
{
    for (int row = 0; row < N; row++) 
    {
        array[row, column] = GetRandomValue();
    }
}

Pierwsza wersja może okazać się znacząco szybsza niż druga. Dlaczego? W pamięci tablicy dwuwymiarowej, dane ułożone są wierszami. Oznacza to, że w pierwszym rozwiązaniu czytając jedną wartość, umieszczamy w cache dwie wartości i nie musimy potem w następnej iteracji robić tego samego. Druga pętla z kolei, zawsze będzie aktualizować cache i wykona 2x więcej operacji na cache niż pierwsze rozwiązanie.

Należy również uważać na tablice jednowymiarowe. Rozmiar w nich jest przechowywany na początku. Każda próba dostępu do tablicy również powoduje użycie Length w celu sprawdzenia czy nie wykracza to poza zasięg. Z tego względu, gdy jeden wątek modyfikuje początek tablicy a drugi np. koniec, to pomimo, że operują na odległych od siebie miejscach w pamięci, wciąż ma miejsce false sharing.

Opisane problemy są bardzo trudne w identyfikacji.  Jeśli jednak wydajność jest krytyczna, warto monitorować (za pomocą performance counter) liczbę tzw. L1 misses, określającą ile razy trzeba było przeładować pamięć podręczną CPU.