Mam binarne drzewo decyzyjne krytyczne dla wydajności i chciałbym skupić się na tym pytaniu na pojedynczej linii kodu. Poniżej znajduje się kod iteratora drzewa binarnego wraz z wynikami przeprowadzonej na nim analizy wydajności.
public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
{
0.2% ScTreeNode node = RootNodes[rootIndex].TreeNode;
24.6% while (node.BranchData != null)
{
0.2% BranchNodeData b = node.BranchData;
0.5% node = b.Child2;
12.8% if (inputs[b.SplitInputIndex] <= b.SplitValue)
0.8% node = b.Child1;
}
0.4% return node;
}BranchData to pole, a nie właściwość. Zrobiłem to, aby zapobiec ryzyku, że nie zostanie on umieszczony.
Klasa BranchNodeData jest następująca:
public sealed class BranchNodeData
{
/// <summary>
/// The index of the data item in the input array on which we need to split
/// </summary>
internal int SplitInputIndex = 0;
/// <summary>
/// The value that we should split on
/// </summary>
internal float SplitValue = 0;
/// <summary>
/// The nodes children
/// </summary>
internal ScTreeNode Child1;
internal ScTreeNode Child2;
}Jak widać, pętla while / kontrola zerowa jest ogromnym hitem w wydajności. Drzewo jest masywne, więc spodziewałbym się, że poszukiwanie liścia zajmie trochę czasu, ale chciałbym zrozumieć nieproporcjonalną ilość czasu spędzonego na tej jednej linii.
Próbowałem:
- Oddzielenie czeku zerowego od chwili while - to test zerowy jest trafieniem.
- Dodanie pola boolowskiego do obiektu i sprawdzenie tego nie zrobiło różnicy. Nie ma znaczenia, co jest porównywane, chodzi o porównanie.
Czy to problem z prognozowaniem gałęzi? Jeśli tak, co mogę z tym zrobić? Jeśli cokolwiek?
Nie będę udawać, że rozumiem CIL , ale opublikuję go, aby każdy mógł spróbować wydobyć z niego informacje.
.method public hidebysig
instance class OptimalTreeSearch.ScTreeNode GetNodeForState (
int32 rootIndex,
float32[] inputs
) cil managed
{
// Method begins at RVA 0x2dc8
// Code size 67 (0x43)
.maxstack 2
.locals init (
[0] class OptimalTreeSearch.ScTreeNode node,
[1] class OptimalTreeSearch.BranchNodeData b
)
IL_0000: ldarg.0
IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode> OptimalTreeSearch.ScSearchTree::RootNodes
IL_0006: ldarg.1
IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode>::get_Item(int32)
IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode
IL_0011: stloc.0
IL_0012: br.s IL_0039
// loop start (head: IL_0039)
IL_0014: ldloc.0
IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
IL_001a: stloc.1
IL_001b: ldloc.1
IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2
IL_0021: stloc.0
IL_0022: ldarg.2
IL_0023: ldloc.1
IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex
IL_0029: ldelem.r4
IL_002a: ldloc.1
IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue
IL_0030: bgt.un.s IL_0039
IL_0032: ldloc.1
IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1
IL_0038: stloc.0
IL_0039: ldloc.0
IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
IL_003f: brtrue.s IL_0014
// end loop
IL_0041: ldloc.0
IL_0042: ret
} // end of method ScSearchTree::GetNodeForStateEdycja: Postanowiłem zrobić test przewidywania gałęzi, dodałem identyczny, jeśli w czasie, więc mamy
while (node.BranchData != null)i
if (node.BranchData != null)wewnątrz tego. Następnie przeprowadziłem analizę wydajności w porównaniu z tym i wykonanie pierwszego porównania zajęło sześć razy więcej czasu niż wykonanie drugiego porównania, które zawsze zwracało prawdę. Wygląda więc na to, że jest to rzeczywiście problem z przewidywaniem gałęzi - i domyślam się, że nic nie mogę na to poradzić ?!
Kolejna edycja
Powyższy wynik wystąpiłby również, gdyby node.BranchData musiał zostać załadowany z pamięci RAM w celu sprawdzenia while - zostałby wówczas zapisany w pamięci podręcznej dla instrukcji if.
To moje trzecie pytanie na podobny temat. Tym razem skupiam się na pojedynczym wierszu kodu. Moje inne pytania na ten temat to:
źródło
BranchNodenieruchomości. Spróbuj wymienićnode.BranchData != nullReferenceEquals(node.BranchData, null). Czy to ma znaczenie?while(true) { /* current body */ if(node.BranchData == null) return node; }. Czy to coś zmienia?while(true) { BranchNodeData b = node.BranchData; if(ReferenceEquals(b, null)) return node; node = b.Child2; if (inputs[b.SplitInputIndex] <= b.SplitValue) node = b.Child1; }pobranienode. BranchDatatylko raz.Odpowiedzi:
Zdecydowanie najdroższą rzeczą, jaką kiedykolwiek wykonuje procesor, jest brak wykonywania instrukcji, jest to dostęp do pamięci. Rdzeń wykonanie nowoczesnego procesora jest wiele razy szybciej niż magistrali pamięci. Problem związany z odległością : im dalej musi przebyć sygnał elektryczny, tym trudniej jest uzyskać sygnał dostarczony na drugi koniec przewodu bez jego uszkodzenia. Jedynym lekarstwem na ten problem jest spowolnienie. Duży problem z przewodami łączącymi procesor z pamięcią RAM w komputerze, możesz otworzyć obudowę i zobaczyć przewody.
Procesory mają środek zaradczy dla tego problemu, używają pamięci podręcznych , buforów, które przechowują kopię bajtów w pamięci RAM. Ważnym jest pamięć podręczna L1 , zwykle 16 kilobajtów dla danych i 16 kilobajtów dla instrukcji. Mały, dzięki czemu znajduje się blisko silnika wykonawczego. Odczytywanie bajtów z pamięci podręcznej L1 zwykle zajmuje 2 lub 3 cykle procesora. Dalej jest pamięć podręczna L2, większa i wolniejsza. Ekskluzywne procesory mają również pamięć podręczną L3, większą i wolniejszą jeszcze. Wraz z rozwojem technologii procesowej te bufory zajmują mniej miejsca i automatycznie stają się szybsze, gdy zbliżają się do rdzenia, co jest głównym powodem, dla którego nowsze procesory są lepsze i jak udaje im się używać coraz większej liczby tranzystorów.
Te skrytki nie są jednak idealnym rozwiązaniem. Procesor nadal będzie blokować dostęp do pamięci, jeśli dane nie są dostępne w jednej z pamięci podręcznych. Nie może być kontynuowane, dopóki bardzo wolna magistrala pamięci nie dostarczy danych. Pojedyncza instrukcja może spowodować utratę setek cykli procesora.
Struktury drzewiaste są problemem są nie cache obsłudze. Ich węzły są zwykle rozproszone w całej przestrzeni adresowej. Najszybszym sposobem uzyskania dostępu do pamięci jest odczyt adresów sekwencyjnych. Jednostką pamięci podręcznej L1 są 64 bajty. Innymi słowy, gdy procesor odczyta jeden bajt, następne 63 są bardzo szybkie, ponieważ będą obecne w pamięci podręcznej.
Co sprawia, że tablica jest zdecydowanie najbardziej wydajną strukturą danych. Również dlatego, że klasa .NET List <> w ogóle nie jest listą, używa tablicy do przechowywania. To samo w przypadku innych typów kolekcji, takich jak Dictionary, strukturalnie nie jest zdalnie podobny do tablicy, ale wewnętrznie zaimplementowany z tablicami.
Dlatego też instrukcja while () najprawdopodobniej będzie cierpieć z powodu blokad procesora, ponieważ wyłuskuje wskaźnik w celu uzyskania dostępu do pola BranchData. Następna instrukcja jest bardzo tania, ponieważ instrukcja while () już przeszła ciężką operację pobierania wartości z pamięci. Przypisanie zmiennej lokalnej jest tanie, procesor używa bufora do zapisu.
W innym przypadku nie jest to prosty problem do rozwiązania, spłaszczenie drzewa w tablice prawdopodobnie nie będzie praktyczne. W każdym razie nie dlatego, że zazwyczaj nie można przewidzieć, w jakiej kolejności będą odwiedzane węzły drzewa. Pomóc może czerwono-czarne drzewo, nie wynika to jasno z pytania. Tak więc prosty wniosek do wyciągnięcia jest taki, że już działa tak szybko, jak można mieć nadzieję. A jeśli chcesz, aby działał szybciej, potrzebujesz lepszego sprzętu z szybszą magistralą pamięci. W tym roku DDR4 wejdzie do głównego nurtu.
źródło
Aby uzupełnić wspaniałą odpowiedź Hansa na temat efektów pamięci podręcznej pamięci, dodaję omówienie pamięci wirtualnej do translacji pamięci fizycznej i efektów NUMA.
W przypadku komputera z pamięcią wirtualną (wszystkich komputerów bieżących) podczas uzyskiwania dostępu do pamięci każdy adres pamięci wirtualnej musi zostać przetłumaczony na adres pamięci fizycznej. Odbywa się to przez sprzęt zarządzający pamięcią za pomocą tabeli translacji. Ta tabela jest zarządzana przez system operacyjny dla każdego procesu i sama jest przechowywana w pamięci RAM. Dla każdej strony pamięci wirtualnej istnieje wpis w tej tablicy tłumaczeń odwzorowujący stronę wirtualną na fizyczną. Przypomnij sobie dyskusję Hansa na temat drogich dostępów do pamięci: jeśli każde tłumaczenie wirtualne na fizyczne wymaga przeszukania pamięci, cały dostęp do pamięci kosztowałby dwa razy więcej. Rozwiązaniem jest posiadanie pamięci podręcznej dla tabeli tłumaczeń, która jest nazywana buforem podglądu tłumaczenia(W skrócie TLB). TLB nie są duże (od 12 do 4096 wpisów), a typowy rozmiar strony w architekturze x86-64 to tylko 4 KB, co oznacza, że jest maksymalnie 16 MB dostępnych bezpośrednio w przypadku trafień z TLB (prawdopodobnie jest to nawet mniej, ale Sandy Most o rozmiarze TLB 512 elementów ). Aby zmniejszyć liczbę braków TLB, możesz sprawić, by system operacyjny i aplikacja współpracowały ze sobą w celu wykorzystania większego rozmiaru strony, na przykład 2 MB, co prowadzi do znacznie większej przestrzeni pamięci dostępnej przy trafieniach TLB. Ta strona wyjaśnia, jak używać dużych stron w Javie, co może znacznie przyspieszyć dostęp do pamięci .
Jeśli twój komputer ma wiele gniazd, prawdopodobnie jest to architektura NUMA . NUMA oznacza niejednolity dostęp do pamięci. W tych architekturach niektóre dostępy do pamięci kosztują więcej niż inne. Przykładowo, przy komputerze z 2 gniazdami i 32 GB pamięci RAM, każde gniazdo prawdopodobnie ma 16 GB pamięci RAM. Na tym przykładowym komputerze dostęp do pamięci lokalnej jest tańszy niż dostęp do pamięci innego gniazda (dostęp zdalny jest od 20 do 100% wolniejszy, a może nawet więcej). Jeśli na takim komputerze Twoje drzewo używa 20 GB pamięci RAM, co najmniej 4 GB danych znajduje się w drugim węźle NUMA, a jeśli dostęp do pamięci zdalnej jest o 50% wolniejszy, dostęp NUMA spowalnia dostęp do pamięci o 10%. Ponadto, jeśli masz wolną pamięć tylko w jednym węźle NUMA, wszystkie procesy wymagające pamięci w zagłodzonym węźle zostaną przydzielone pamięci z innego węzła, do którego dostęp jest droższy. Co gorsza, system operacyjny może pomyśleć, że dobrym pomysłem jest wymiana części pamięci zagłodzonego węzła,co spowodowałoby jeszcze droższe dostępy do pamięci . Jest to wyjaśnione bardziej szczegółowo w Problemie „szaleństwa wymiany” MySQL i skutkach architektury NUMA, gdzie podano pewne rozwiązania dla Linuksa (rozprzestrzenianie dostępu do pamięci na wszystkie węzły NUMA, przegryzanie punktora przy zdalnych dostępach NUMA, aby uniknąć zamiany). Mogę też pomyśleć o przydzieleniu większej ilości pamięci RAM do gniazda (24 i 8 GB zamiast 16 i 16 GB) i upewnieniu się, że program jest zaplanowany na większym węźle NUMA, ale wymaga to fizycznego dostępu do komputera i śrubokręta ;-) .
źródło
Nie jest to odpowiedź sama w sobie, a raczej podkreślenie tego, co Hans Passant napisał o opóźnieniach w systemie pamięci.
Naprawdę wysokowydajne oprogramowanie - takie jak gry komputerowe - jest nie tylko napisane w celu implementacji samej gry, ale jest również przystosowane w taki sposób, że kod i struktury danych maksymalnie wykorzystują pamięć podręczną i systemy pamięci, tj. Traktują je jako ograniczone zasoby. Kiedy mam do czynienia z problemami z pamięcią podręczną, zwykle zakładam, że L1 dostarczy w 3 cyklach, jeśli są tam dane. Jeśli tak nie jest i muszę jechać na L2, zakładam 10 cykli. Dla L3 30 cykli i dla pamięci RAM 100.
Istnieje dodatkowa akcja związana z pamięcią, która - jeśli musisz jej użyć - nakłada jeszcze większą karę i jest nią blokada magistrali. Blokady magistrali nazywane są sekcjami krytycznymi, jeśli używasz funkcji systemu Windows NT. Jeśli używasz odmiany domowej, możesz nazwać ją szpinakiem. Niezależnie od nazwy, synchronizuje się z najwolniejszym urządzeniem zarządzającym magistralą w systemie, zanim blokada zostanie założona. Najwolniejszym urządzeniem zarządzającym magistralą może być klasyczna 32-bitowa karta PCI podłączona przy 33 MHz. 33 MHz to jedna setna częstotliwości typowego procesora x86 (@ 3,3 GHz). Zakładam nie mniej niż 300 cykli na wykonanie blokady, ale wiem, że może to zająć wiele razy tyle, więc jeśli zobaczę 3000 cykli, nie zdziwię się.
Początkujący programiści wielowątkowości będą używać blokad magistrali w każdym miejscu, a następnie będą się zastanawiać, dlaczego ich kod jest wolny. Sztuczka - podobnie jak w przypadku wszystkiego, co ma związek z pamięcią - polega na oszczędzaniu na dostępach.
źródło