boost :: flat_map i jego wydajność w porównaniu do map i unordered_map

W programowaniu powszechnie wiadomo, że lokalność pamięci znacznie poprawia wydajność z powodu trafień w pamięci podręcznej. Niedawno dowiedziałem się, boost::flat_mapktóra implementacja mapy jest oparta na wektorach. Wydaje się, że nie jest tak popularny jak typowy map/ unordered_mapwięc nie byłem w stanie znaleźć żadnych porównań wydajności. Jak to wygląda i jakie są dla niego najlepsze przypadki użycia?

Dzięki!

Niedawno przeprowadziłem test porównawczy różnych struktur danych w mojej firmie, więc czuję, że muszę rzucić kilka słów. Poprawne wykonanie testów porównawczych jest bardzo skomplikowane.

Benchmarking

W sieci rzadko znajdujemy (jeśli w ogóle) dobrze zaprojektowany test porównawczy. Do dziś znalazłem tylko benchmarki, które zostały zrobione w sposób dziennikarski (dość szybko i zamiatając dziesiątki zmiennych pod dywan).

1) Musisz wziąć pod uwagę ocieplenie pamięci podręcznej

Większość ludzi korzystających z testów porównawczych boi się rozbieżności timera, dlatego uruchamiają swoje rzeczy tysiące razy i zajmują cały czas, po prostu starają się wykonać te same tysiące razy dla każdej operacji, a następnie uważają to za porównywalne.

Prawda jest taka, że ​​w prawdziwym świecie nie ma to sensu, ponieważ twoja pamięć podręczna nie będzie ciepła, a twoja operacja zostanie prawdopodobnie wywołana tylko raz. Dlatego musisz testować benchmark używając RDTSC, a czas wywoływać je tylko raz. Intel opublikował artykuł opisujący, jak używać RDTSC (używając instrukcji cpuid do opróżnienia potoku i wywołując ją co najmniej 3 razy na początku programu, aby go ustabilizować).

2) Miara dokładności RDTSC

Polecam również to zrobić:

u64 g_correctionFactor;  // number of clocks to offset after each measurement to remove the overhead of the measurer itself.
u64 g_accuracy;

static u64 const errormeasure = ~((u64)0);

#ifdef _MSC_VER
#pragma intrinsic(__rdtsc)
inline u64 GetRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // flush OOO instruction pipeline
    return __rdtsc();
}

inline void WarmupRDTSC()
{
    int a[4];
    __cpuid(a, 0x80000000);  // warmup cpuid.
    __cpuid(a, 0x80000000);
    __cpuid(a, 0x80000000);

    // measure the measurer overhead with the measurer (crazy he..)
    u64 minDiff = LLONG_MAX;
    u64 maxDiff = 0;   // this is going to help calculate our PRECISION ERROR MARGIN
    for (int i = 0; i < 80; ++i)
    {
        u64 tick1 = GetRDTSC();
        u64 tick2 = GetRDTSC();
        minDiff = std::min(minDiff, tick2 - tick1);   // make many takes, take the smallest that ever come.
        maxDiff = std::max(maxDiff, tick2 - tick1);
    }
    g_correctionFactor = minDiff;

    printf("Correction factor %llu clocks\n", g_correctionFactor);

    g_accuracy = maxDiff - minDiff;
    printf("Measurement Accuracy (in clocks) : %llu\n", g_accuracy);
}
#endif

Jest to miernik rozbieżności i będzie wymagał minimum wszystkich zmierzonych wartości, aby uniknąć od czasu do czasu -10 ** 18 (64-bitowe pierwsze wartości ujemne).

Zwróć uwagę na użycie elementów wewnętrznych, a nie wbudowanego montażu. Kompilatory rzadko wspierają dziś pierwszy asembler inline, ale co gorsza, kompilator tworzy pełną barierę porządkową wokół asemblacji wbudowanej, ponieważ nie może statycznie analizować wnętrza, więc jest to problem z testowaniem rzeczy ze świata rzeczywistego, zwłaszcza przy wywoływaniu rzeczy tylko pewnego razu. Tak więc element wewnętrzny jest tutaj odpowiedni, ponieważ nie przerywa kompilatorowi swobodnej zmiany kolejności instrukcji.

3) parametry

Ostatnim problemem jest to, że ludzie zwykle testują za mało wariantów scenariusza. Na wydajność kontenera wpływają:

1. Alokator
2. wielkość zawartego typu
3. koszt wykonania operacji kopiowania, operacji cesji, operacji przenoszenia, operacji konstrukcyjnej, typu zawartego.
4. ilość elementów w kontenerze (wielkość problemu)
5. typ ma trywialne 3. operacje
6. typ to POD

Punkt 1 jest ważny, ponieważ kontenery alokują od czasu do czasu i ma duże znaczenie, jeśli przydzielają przy użyciu „nowej” CRT lub jakiejś operacji zdefiniowanej przez użytkownika, takiej jak alokacja puli, lista bezpłatna lub inna ...

( dla osób zainteresowanych punktem 1, dołącz do tajemniczego wątku na gamedev o wpływie na wydajność alokatora systemu )

Punkt 2 jest taki, że niektóre pojemniki (powiedzmy A) tracą czas na kopiowanie rzeczy dookoła, a im większy typ, tym większe obciążenie. Problem w tym, że porównując z innym pojemnikiem B, A może wygrać z B dla małych typów i przegrać dla większych.

Punkt 3 jest tym samym, co punkt 2, z wyjątkiem tego, że mnoży koszt przez pewien współczynnik wagowy.

Punkt 4 to kwestia dużego O połączonego z problemami z pamięcią podręczną. Niektóre kontenery o złej złożoności mogą w znacznym stopniu przewyższać kontenery o niskiej złożoności dla niewielkiej liczby typów (np. mapVs. vector, ponieważ ich lokalizacja pamięci podręcznej jest dobra, ale mapfragmentuje pamięć). A potem w pewnym punkcie przecięcia stracą, ponieważ zawarty całkowity rozmiar zaczyna „wyciekać” do pamięci głównej i powodować chybienia w pamięci podręcznej, a także fakt, że asymptotyczna złożoność może zacząć być odczuwalna.

Punkt 5 dotyczy kompilatorów, które są w stanie usunąć rzeczy, które są puste lub trywialne w czasie kompilacji. Może to znacznie zoptymalizować niektóre operacje, ponieważ kontenery są szablonami, dlatego każdy typ będzie miał swój własny profil wydajności.

Punkt 6, podobnie jak punkt 5, POD mogą skorzystać z faktu, że konstrukcja kopii jest tylko memcpy, a niektóre kontenery mogą mieć określoną implementację dla tych przypadków, wykorzystując częściowe specjalizacje szablonów lub SFINAE do wybierania algorytmów zgodnie z cechami T.

O płaskiej mapie

Najwyraźniej płaska mapa jest posortowanym opakowaniem wektorowym, takim jak Loki AssocVector, ale z kilkoma dodatkowymi modernizacjami związanymi z C ++ 11, wykorzystującymi semantykę ruchu do przyspieszenia wstawiania i usuwania pojedynczych elementów.

To nadal jest zamówiony kontener. Większość ludzi zwykle nie potrzebuje części do zamówienia, dlatego istnieje unordered...

Czy rozważałeś, że może potrzebujesz flat_unorderedmap? co byłoby czymś podobnym google::sparse_maplub czymś w tym rodzaju - otwartą mapą skrótów adresu.

Problem z mapami skrótów otwartych adresów polega na tym, że w tym czasie rehashmuszą one kopiować wszystko dookoła do nowego, rozszerzonego płaskiego terenu, podczas gdy standardowa mapa nieuporządkowana musi tylko odtworzyć indeks skrótu, podczas gdy przydzielone dane pozostają tam, gdzie są. Wadą jest oczywiście to, że pamięć jest pofragmentowana jak diabli.

Kryterium ponownego haszowania w otwartej mapie skrótów adresu ma miejsce, gdy pojemność przekracza rozmiar wektora kubełka pomnożony przez współczynnik obciążenia.

Typowy współczynnik obciążenia to 0.8; Dlatego musisz się o to troszczyć, jeśli możesz wstępnie dopasować swoją mapę hashującą przed jej wypełnieniem, zawsze wstępnie dopasuj rozmiar do: intended_filling * (1/0.8) + epsilonda ci to gwarancję, że nigdy nie będziesz musiał fałszywie przesuwać i kopiować wszystkiego podczas wypełniania.

Zaletą zamkniętych map adresów ( std::unordered..) jest to, że nie musisz przejmować się tymi parametrami.

Ale boost::flat_mapjest wektorem uporządkowanym; dlatego zawsze będzie miał asymptotyczną złożoność log (N), która jest mniej dobra niż mapa skrótów otwartego adresu (amortyzowany stały czas). Powinieneś to również wziąć pod uwagę.

Wyniki testów porównawczych

To jest test obejmujący różne mapy (z intkluczem i __int64/ somestructjako wartością) i std::vector.

informacje o testowanych typach:

typeid=__int64 .  sizeof=8 . ispod=yes
typeid=struct MediumTypePod .  sizeof=184 . ispod=yes

Wprowadzenie

EDYTOWAĆ:

Moje poprzednie wyniki obejmowały błąd: faktycznie testowali uporządkowane wstawianie, które wykazywało bardzo szybkie zachowanie dla płaskich map.
Zostawiłem te wyniki później na tej stronie, ponieważ są interesujące.
To jest poprawny test:

Sprawdziłem implementację, nie ma tu czegoś takiego jak odroczony sort zaimplementowany w płaskich mapach. Każde wstawienie sortuje się w locie, dlatego ten wzorzec wykazuje asymptotyczne tendencje:

map: O (N * log (N))
hashmaps: O (N)
vector i flatmaps: O (N * N)

Ostrzeżenie : poniżej 2 testy dla std::mapi oba flat_mapsą błędne i faktycznie testują zamówione wstawianie (w porównaniu z przypadkowym wstawianiem dla innych kontenerów. Tak, to jest mylące, przepraszam):

Widzimy, że uporządkowane wkładanie powoduje cofanie się i jest niezwykle szybkie. Jednak z nieopublikowanych na wykresach wyników mojego testu porównawczego mogę również powiedzieć, że nie jest to bliskie absolutnej optymalności dla wstawienia wstecznego. Przy 10k elementach uzyskuje się idealną optymalność wstawiania wstecznego na wcześniej zarezerwowanym wektorze. Co daje nam 3 miliony cykli; obserwujemy tutaj 4,8 mln dla zamówionego wstawienia do flat_map(czyli 160% optymalnego).

Analiza: pamiętaj, że jest to „losowe wstawianie” dla wektora, więc ogromny 1 miliard cykli wynika z konieczności przesuwania połowy (średnio) danych w górę (jeden element na jeden element) przy każdym wstawieniu.

Losowe wyszukiwanie 3 elementów (zegary znormalizowane do 1)

w rozmiarze = 100

w rozmiarze = 10000

Iteracja

powyżej rozmiaru 100 (tylko typ MediumPod)

powyżej 10000 (tylko typ MediumPod)

Ostateczne ziarno soli

Na koniec chciałem wrócić do „Benchmarkingu §3 Pt1” (podzielnik systemowy). W niedawnym eksperymencie, który przeprowadzam wokół wydajności opracowanej przeze mnie mapy skrótów otwartego adresu, w niektórych std::unordered_mapprzypadkach użycia ( omówionych tutaj ) zmierzyłem lukę wydajności wynoszącą ponad 3000% między Windows 7 i Windows 8 .
Co sprawia, że ​​chcę ostrzec czytelnika o powyższych wynikach (zostały wykonane na Win7): Twój przebieg może się różnić.

Z poważaniem

Z dokumentacji wynika, że ​​jest to analogiczne do tego, Loki::AssocVectorktórego jestem dość ciężkim użytkownikiem. Ponieważ jest oparty na wektorze, ma cechy wektora, to znaczy:

• Iteratory są unieważniane, gdy sizewykraczają poza capacity.
• Kiedy przekracza capacityto, należy ponownie przydzielić i przenieść obiekty, tj. Wstawienie nie jest gwarantowane w stałym czasie, z wyjątkiem specjalnego przypadku wstawiania w endmomenciecapacity > size
• Wyszukiwanie jest szybsze niż std::mapdzięki lokalizacji pamięci podręcznej, wyszukiwaniu binarnemu, które ma taką samą charakterystykę wydajności jak w std::mapinnych przypadkach
• Zużywa mniej pamięci, ponieważ nie jest to połączone drzewo binarne
• Nigdy się nie kurczy, chyba że wymusisz to (ponieważ powoduje to realokację)

Najlepsze zastosowanie jest wtedy, gdy znasz z góry liczbę elementów (więc możesz reservez góry) lub gdy wstawianie / usuwanie jest rzadkie, ale wyszukiwanie jest częste. Unieważnienie iteratora sprawia, że ​​jest to nieco kłopotliwe w niektórych przypadkach użycia, więc nie można ich stosować zamiennie pod względem poprawności programu.