Cache procesora - jak najlepiej wykorzystać pamięć podręczną
Możliwości, jakie daje pamięć podręczna procesora, często nie są optymalnie wykorzystywane przez twórców aplikacji. Tymczasem wprowadzenie dobrych praktyk odnośnie zarządzania cache może znacząco zoptymalizować wykonywanie kodu i przyśpieszyć ogólne działanie aplikacji. Przyjrzyjmy się zatem bliżej temu, czym jest pamięć podręczna i jaką ma strukturę oraz prześledźmy sposoby efektywnego jej wykorzystania.
Po co nam cache?
Zanim jednak przejdziemy do konkretów, warto odpowiedzieć na elementarne pytania – po co nam właściwie pamięć podręczna procesora i dlaczego w ogóle pojawiła się ona w procesorach? Przecież równie dobrze moglibyśmy wykorzystywać wyłącznie pamięć operacyjną, prawda?
W teorii tak, ale w praktyce byłoby to rozwiązanie dalece nieefektywne. Kluczową rolę odgrywa szybkość, z jaką procesor może uzyskiwać dostęp do cache. Jest ona bowiem znacznie większa niż DRAM, ale też skutkuje to większymi kosztami produkcji. To właśnie dlatego wielkość cache nawet w najlepszych procesorach jest rzędy wielkości mniejsza niż ma, to miejsce w przypadku pamięci operacyjnej.
Pod względem technicznym przewaga wykorzystywanego w cache rodzaju pamięci (SRAM) wynika z braku konieczności jej odświeżania w celu dłuższego utrzymywania danych w dostępności. SRAM działa bardziej pasywnie (czy też, jak wskazuje sama nazwa, statycznie) niż DRAM, które wymaga odświeżania, a zatem także energii. Każdorazowy jej pobór niezbędny do działania jest czynnikiem spowalniającym.
W efekcie, biorąc pod uwagę wydajność procesorów rosnącą jeszcze do niedawna zgodnie z Prawem Moore’a, dostrzeżono konieczność zapewnienia CPU szybszej pamięci specjalnego przeznaczenia, nawet jeśli jej wielkość wynosiłaby zaledwie kilka-kilkadziesiąt megabajtów. Poleganie na DRAM tworzyłoby bowiem wąskie gardło i wpływało na spowolnienie wykonywania instrukcji.
Struktura pamięci podręcznej
Z czasem możliwości pamięci podręcznej zaczęto eksplorować śmielej, w rezultacie czego dziś rozróżniamy trzy warstwy cache: L1, L2 i L3. W takiej też kolejności dostęp do zawartości cache uzyskuje procesor.
Różnice pomiędzy warstwami wynikają ze wspomnianych kosztów produkcji – im szybsza pamięć, tym wyższa warstwa i tym mniej mamy jej do dyspozycji. W rezultacie w najnowszych procesorach (rzecz jasna zależy to od modelu i klasy) stosuje się dziś już 1-megabajtową warstwę L1 wykonaną w najszybszej technologii SRAM, ale już nawet 64 MB najwolniejszej pamięci SRAM warstwy L3.
Warto przy tym zaznaczyć, że L1 rozbija się jeszcze na dwie części. Pierwszą z nich jest L1 Data Cache, dzięki której dane są utrzymywane po to, aby na powrót zapisać je w głównej pamięci DRAM. Drugi składnik to L1 Instruction Cache, która przechowuje między innymi instrukcje wykonywanie następnie przez procesor. Można zatem w uproszczeniu powiedzieć, że Instruction Cache to wejściowa pamięć podręczna, zaś Data Cache odpowiada za output.
Omawiając strukturę pamięci podręcznej, warto prześledzić przepływ danych pomiędzy poszczególnymi warstwami. Różni się to bowiem w zależności od tego, jaki komponent poszukuje zapisanych w cache danych. Jak już to wspomniano, jeśli jest to procesor, to w pierwszej kolejności odwołuje się on do najszybszej warstwy L1. Sytuacja przybiera jednak inny obrót, gdy danych poszukuje pamięć DRAM – wówczas rozpoczyna się to od największej i najwolniejszej warstwy L3.
Jak optymalnie korzystać z cache?
Skoro mamy już pewien ogląd tego, jak działa pamięć podręczna we współczesnych procesorach, warto zastanowić się, jak w sposób najbardziej efektywny wykorzystać jej możliwości.
Przede wszystkim, nie ma możliwości zaadresowania w kodzie konkretnej warstwy pamięci, gdyż odpowiada za to sprzęt. W sytuacji, kiedy dane nie zostaną odnalezione, mowa o zjawisku chybienia pamięci podręcznej (cache miss). To z kolei wpływa na opóźnienia w dostępie i całościowo przekłada się na wydajność kodu. Możemy jednak tak zoptymalizować kod, aby możliwie jak najbardziej zniwelować wszelkie opóźnienia w odnajdywaniu danych zapisanych w pamięci podręcznej.
Jedną z metod jest eliminacja konieczności korzystania z garbage collectorów. Przy wykorzystaniu stert zawsze pojawiać się będą spadki wydajności związane z koniecznością zbierania obiektów. Jednym za sposobów na optymalizację jest zatem wyeliminowanie stert i zastąpienie ich strukturami, w których przechowywane będą obiekty. Oto przykładowy fragment kodu, który priorytetyzuje tablice struktur ponad tablice klas proponowany przez Joydipa Kanjilala, MVP Microsoftu w obszarze ASP.NET:
struct RectangleStruct
{
public int breadth;
public int height;
}
class RectangleClass
{
public int breadth;
public int height;
}
Następnie różnice w przepływie danych można zaobserwować na przykładzie prostego programu, którego celem jest stworzenie miliona obiektów dla danych przechowywanych w tablicach struktur oraz kolejnego miliona dla danych w tablicach klas, oraz zwrócenie informacji o czasie potrzebnym na wykonanie obu operacji.
static void Main(string[] args)
{
const int size = 1000000;
var structs = new RectangleStruct[size];
var classes = new RectangleClass[size];
var sw = new Stopwatch();
sw.Start();
for (var i = 0; i < size; ++i)
{
structs[i] = new RectangleStruct();
structs[i].breadth = 0
structs[i].height = 0;
}
var structTime = sw.ElapsedMilliseconds;
sw.Reset();
sw.Start();
for (var i = 0; i < size; ++i)
{
classes[i] = new RectangleClass();
classes[i].breadth = 0;
classes[i].height = 0;
}
var classTime = sw.ElapsedMilliseconds;
sw.Stop();
Console.WriteLine("Czas dla tablic klas: "+ classTime.ToString() + " milliseconds.");
Console.WriteLine("Czas dla tablic struktur: " + structTime.ToString() + " milliseconds.");
Console.Read();
}
W tym przykładzie dobrze widoczne jest, że pamięć podręczna „lubi się” z sekwencyjnymi strukturami danych. Pozwala to wykorzystać między innymi takie mechanizmy współczesnych procesorów, jak spekulatywne wykonywanie kodu. Sekwencyjny dostęp do pamięci zawsze będzie rozwiązaniem bardziej wydajnym, niż miałoby to miejsce w przypadku uzyskiwania dostępu do pamięci w losowej kolejności.
Dobre praktyki
Ważną koncepcją w tworzeniu kodu, który będzie efektywnie wykorzystywał pamięć operacyjną, jest „bliskość” lokowania danych w cache. W uproszczeniu można powiedzieć, że optymalizacja może przebiegać w dwóch wymiarach: w czasie i miejscu. Jeśli chodzi o czas, to warto pamiętać, o tym, że skoro już raz uzyskany został dostęp do jakiejś lokalizacji w pamięci, to najprawdopodobniej stanie się tak drugi raz w niedalekiej przyszłości, gdyż informacja o tym będzie jeszcze zapisana w pamięci podręcznej.
Jeśli zaś chodzi o miejsce, to chodzi tu o możliwie jak najbliższe alokowanie w pamięci powiązanych ze sobą danych. Dotyczy to zresztą nie tylko procesorów, ale także pamięci operacyjnej, a nawet masowej. Jeśli bowiem odczytujemy jakieś dane z DRAM, to pobierany jest ich zawsze jakiś większy wycinek, a nie tylko precyzyjnie żądany fragment. W rezultacie, dzięki bliskiemu alokowaniu danych, kolejny ich fragment może być już pobrany automatycznie w jednym cyklu i nie będzie konieczności sięgania po niego ponownie.
Dobrą praktyką jest także unikanie pisania takich algorytmów i struktur, które będą skutkować nieregularnymi wzorcami dostępu do pamięci – polecane są natomiast liniowe struktury danych, np. rzeczone tablice struktur. Dobra orientacja w strukturze pamięci podręcznej i jej blokach, a także zwracanie uwagi na sposoby przechowywania danych z pewnością przełożą się na wydajniejszy kod, który korzysta z pełni możliwości cache.