Felder auf Gleichheit überprüfen

Zhavok

Oh, da hat meine 08/15 Antwort ja noch für Gesprächsstoff gesorgt . Interessant was so über die verschiedenen Möglichkeiten geschrieben wurde. Danke, hab wieder einiges gelernt

hustbaer

@TGGC sagte in Felder auf Gleichheit überprüfen:

Ich glaube das ist nicht garantiert, weil das Kriterium der Sortierung ein Anderes als das für Identität sein könnte oder das Ergebnis von > und < komplett unbestimmt.

Und ich glaube dass du damit vollkommen richtig liegst Ich wollte auch gar nicht die Design-Entscheidung kritisieren das so zu machen. Ich wollte nur erklären warum N^2 hier "normal" ist und nicht bloss worst-case.

HarteWare

Ich meine mich daran zu erinnern, dass man für Integer in einem begrenzten Wertebereich auch schnellere Sortierverfahren hat (radix sort?). Wie würde es sich damit verhalten?

@PeterPanzer31 sagte in Felder auf Gleichheit überprüfen:

  if (v1[0] = v2[i] )

ganz böse fehlerquelle btw.

hustbaer

@HarteWare Radix-Sort ist dann aber fast schon das selbe wie die hier vorgeschlagene Map-Variante. Nur mit einer weniger effizienten Map-Implementierung, nämlich einem Radix-Tree. Dann lieber gleich (Hash)Map.

Finnegan

War neugierig und hab mir auch mal die alte Programmierer-Weisheit zu Herzen genommen (Messen!!!einself!). Gut möglich, dass ich was verbockt habe, aber ich konnte die Überlegenheit der unordered_map zumindest bis $N=2^{26}$ nicht bestätigen:

Vektoren bis $N=2^{10}$
Vektoren bis $N=2^{16}$
Vektoren bis $N=2^{26}$

Gemessen wurde mit Vektoren, die mit int-Werten von 0 bis N-1 gefüllt und dann mittels std::shuffle zufällig permutiert wurden.

Quellcode (benötigt Google Benchmark):

benchmark-vecequal.cpp
benchmark-vecequal-64k.cpp (mostly Copy&Paste)
benchmark-vecequal-1k.cpp (mostly Copy&Paste)

Vielleicht hat ja jemand von Euch eine Idee, wieso ich auf solche Messwerte komme. Ich tippe darauf, dass ich irgendwo einen Fehler gemacht oder etwas ineffizientes geschrieben habe (rehash/reserve?). Wenn sich die unordered_map nichtmal bei $N=2^{28}$ lohnt, dann fände ich das schon bemerkenswert, obwohl die schon eine stadtbekannte Cache-Sau ist

@hustbaer Wie war das noch mit deinem Code, jetzt am Abend? Den würd ich gern mal vergleichen die Tage.

Nachtrag: Vektoren von 0-1024, weil ich eh noch alles offen hatte. Seltsam schnurgerade das alles und ohne irgendwelche Cache-Hüpfer. Bestärkt mich eher darin, dass etwas nicht stimmt, obwohl es hübsch aussieht. Frage mich auch ob die CPU Time im Gegensatz zur Real Time (Wall Time) der bessere Wert ist. Intuitiv denke ich ja, weil dort weniger OS/Hardware-Aussetzer drin sein sollten.

DNKpp

@Finnegan Habs nur mal überflogen. Aber

std::unordered_map<int, int> c;
std::for_each(std::begin(a), std::end(a), [&](int v) { ++c[v]; });

scheint mir potentiell schonmal merkwürdig. Sicher dass hier mit 0 initialisiert wird?

Finnegan

@DNKpp sagte in Felder auf Gleichheit überprüfen:

scheint mir potentiell schonmal merkwürdig. Sicher dass hier mit 0 initialisiert wird?

Yep: unordered_map::operator[]:

When the default allocator is used, this results in the key being copy constructed from key and the mapped value being value-initialized.
...
value initialization
...
4) otherwise, the object is zero-initialized.

hustbaer

@Finnegan
Oops!
Gut dass du das geschrieben hast. Ich hab Mist gebaut...

std::vector<MyType> rand_vec(size_t size) {
	std::default_random_engine engine;
	engine.seed(123);
	std::uniform_int_distribution<MyType> distribution(1, 1000); // Oops

	std::vector<MyType> v;
	v.reserve(size);
	for (size_t i = 0; i < size; i++)
		v.push_back(distribution(engine));

	engine.seed(std::random_device{}());
	std::shuffle(v.begin(), v.end(), engine);
	return v;
}

Ist dann auch sehr verwunderlich dass der Break-Even bei knapp über 1000 war
Keine Ahnung warum ich da 1000 reingeschrieben hab. Vermutlich weil ich beim Schreiben bloss an die sort Variante gedacht hab, und für die is das ziemlich wörscht. (Naja, genaugenommen auch da nicht, und der Grund warum nicht erklärt dann auch genau warum ich lineare Skalierung gesehen hab statt N log N -- was jetzt auch nicht mehr der Fall ist... hachjeh.)

Wenn man das mit etwas sinnvollerem wie 10 * size ersetzt sehen die Ergebnisse auf einmal ganz anders aus.

Vollständig:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <random>
#include <chrono>
#include <stddef.h>

typedef int MyType;

std::vector<MyType> rand_vec(size_t size) {
    std::default_random_engine engine;
    engine.seed(123);
    std::uniform_int_distribution<MyType> distribution(1, static_cast<MyType>(10 * size));

    std::vector<MyType> v;
    v.reserve(size);
    for (size_t i = 0; i < size; i++)
        v.push_back(distribution(engine));

    engine.seed(std::random_device{}());
    std::shuffle(v.begin(), v.end(), engine);
    return v;
}

bool compare_via_sort(std::vector<MyType> a, std::vector<MyType> b) {
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    return a == b;
}

bool compare_via_tmap(std::vector<MyType> const& a, std::vector<MyType> const& b) {
    std::map<MyType, ptrdiff_t> tmap;
    for (auto v : a)
        tmap[v]++;
    for (auto v : b)
        tmap[v]--;

    for (auto e : tmap)
        if (e.second != 0)
            return false;

    return true;
}

bool compare_via_umap(std::vector<MyType> const& a, std::vector<MyType> const& b) {
    std::unordered_map<MyType, ptrdiff_t> umap;
    umap.reserve(a.size() * 2);
    for (auto v : a)
        umap[v]++;
    for (auto v : b)
        umap[v]--;

    for (auto e : umap)
        if (e.second != 0)
            return false;

    return true;
}

volatile bool result_dummy = false;
volatile void const* ptr_dummy = nullptr;
volatile long long t_dummy = 0;

template <class F>
long long bench(F f, size_t n) {
    auto const a = rand_vec(n);
    ptr_dummy = a.data();
    auto const b = rand_vec(n);
    ptr_dummy = b.data();

    using clock = std::chrono::high_resolution_clock;
    auto const t0 = clock::now();
    result_dummy = f(a, b);
    auto const t1 = clock::now();
    auto const dur = t1 - t0;
    auto const dur_ns = std::chrono::duration_cast<std::chrono::nanoseconds>(dur).count();
    t_dummy = dur_ns;
    return dur_ns;
}

template <class F>
void bench2(F f, size_t n, char const* name) {
    auto best = std::numeric_limits<long long>::max();
    for (size_t i = 0; i < 10; i++) {
        auto const d = bench(f, n);
        if (d < best)
            best = d;
    }

    std::cout << name << "[" << n << "]: " << best << " ns\n";
}

int main() {
    for (size_t n = 10; n <= 1'000'000; n *= 10) {
        bench2([](auto a, auto b) { return compare_via_sort(a, b); }, n, "sort");
        bench2([](auto a, auto b) { return compare_via_tmap(a, b); }, n, "tmap");
        bench2([](auto a, auto b) { return compare_via_umap(a, b); }, n, "umap");
    }
}

Output:

sort[10]: 700 ns
tmap[10]: 2000 ns
umap[10]: 1800 ns
sort[100]: 6200 ns
tmap[100]: 20800 ns
umap[100]: 19400 ns
sort[1000]: 82500 ns
tmap[1000]: 244600 ns
umap[1000]: 143200 ns
sort[10000]: 1008500 ns
tmap[10000]: 3306700 ns
umap[10000]: 1435800 ns
sort[100000]: 13107800 ns
tmap[100000]: 62987400 ns
umap[100000]: 22860400 ns
sort[1000000]: 159867600 ns
tmap[1000000]: 1874229500 ns
umap[1000000]: 497277000 ns

Fazit: umap hasn't got a prayer.

Was dann auch mehr meiner ursprünglichen Vermutung entspricht. Wenigstens das.

Mechanics

Ich hab recht gute Erfahrungen mit dem integer_sort (spreadsort) aus boost gemacht, magst das noch schnell ausprobieren?

hustbaer

Bleibt noch die Frage: warum?
Grund:

map_vs_sort.exe!operator new(unsigned __int64 size)
map_vs_sort.exe!std::_Default_allocate_traits::_Allocate(const unsigned __int64 _Bytes)
map_vs_sort.exe!std::_Allocate<...>(const unsigned __int64 _Bytes)
map_vs_sort.exe!std::allocator<...>::allocate(const unsigned __int64 _Count)
map_vs_sort.exe!std::_Alloc_construct_ptr<...>::_Allocate()
map_vs_sort.exe!std::_List_node_emplace_op<...>::_Allocate<...>(...)
map_vs_sort.exe!std::_Hash<...>::emplace<...>(...)
map_vs_sort.exe!std::unordered_map<blah>::_Try_emplace<int const &>(const int & _Keyval)
map_vs_sort.exe!std::unordered_map<blah>::try_emplace<>(const int & _Keyval)
map_vs_sort.exe!std::unordered_map<blah>::operator[](const int & _Keyval)
...

1x new pro Eintrag.

Und das wiederrum muss bei std::unordered_map leider so sein wegen der Reference-Validitäts-Garantie
Wobei gut, da hätte man vermutlich noch drum-rum arbeiten können. Irgendwie. Platz für mehrere Einträge gleichzeitig anfordern, und jeden Block doppelt so gross wie den vorigen. Plus eigene Freelist damit man rausgelöschtes Zeugs wiederverwenden kann. Wobei ich nicht weiss ob unordered_map ala vector "geizig" sein darf. Ist auch fraglich wie sinnvoll das überhaupt gewesen wäre.

Und seit C++17 kann man es sich sowieso abschminken, wegen der Node Handles:
https://en.cppreference.com/w/cpp/container/unordered_map/extract
https://en.cppreference.com/w/cpp/container/unordered_map/insert

hustbaer

@Mechanics

Spreadsort ist nochmal ein gutes Stück schneller:

spreadsort[100]:            5300 ns
tmap      [100]:           24600 ns
umap      [100]:           11000 ns
std::sort [1000]:          71700 ns
spreadsort[1000]:          36700 ns
tmap      [1000]:         259300 ns
umap      [1000]:         115700 ns
std::sort [10000]:       1007000 ns
spreadsort[10000]:        403900 ns
tmap      [10000]:       3250600 ns
umap      [10000]:       1356100 ns
std::sort [100000]:     12173500 ns
spreadsort[100000]:      5739300 ns
tmap      [100000]:     51766600 ns
umap      [100000]:     19814200 ns
std::sort [1000000]:   152545500 ns
spreadsort[1000000]:    95003500 ns
tmap      [1000000]:  1624396900 ns
umap      [1000000]:   471077000 ns

mit

bool compare_via_spreadsort(std::vector<MyType> a, std::vector<MyType> b) {
	boost::sort::spreadsort::spreadsort(a.begin(), a.end());
	boost::sort::spreadsort::spreadsort(b.begin(), b.end());
	return a == b;
}

Finnegan

@hustbaer sagte in Felder auf Gleichheit überprüfen:

@Finnegan
Oops!
Gut dass du das geschrieben hast. Ich hab Mist gebaut...

Ich muss morgen auch nochmal nach meinem Mist schauen. Irgendwie glaub ich das noch nicht so recht

> long long bench

Die Signatur find ich klasse! Das lädt auf ein Nickerchen ein, nach harter Arbeit und Tauben füttern
Ansonsten sehen deine Compare-Funktionen nahezu aus wie bei mir. Du hast allerdings ein reserve() drin - da gehe ich aber nicht davon von aus, dass das bei den Differenzen, die ich gemessen habe einen grossen Unterschied macht. Ich habe auch noch einen alternativen Hashmap-Compare, der die letzte Vergleichs-Schleife einspart und (eigentlich) korrekt sein sollte. Ist ein bisschen flotter, hab ich aber aus den Diagrammen rausgenommen, da der Unterschied nicht sehr gross ist.

Output:
sort[10]: 700 ns
tmap[10]: 2000 ns
umap[10]: 1800 ns
...
sort[1000000]: 159867600 ns
tmap[1000000]: 1874229500 ns
umap[1000000]: 497277000 ns
Fazit: umap hasn't got a prayer.

Was dann auch mehr meiner ursprünglichen Vermutung entspricht. Wenigstens das.

Was ist denn da mit der umap los? Das kann doch nicht angehen, dass man ein TiB RAM braucht, um von der zu profitieren. Ich weiss dass die Implementierung der Standardbibliothek nicht die effizenteste Hash-Map ist, aber das ist ein Ding dass man eigentlich mit $O(1)$ einkalkuliert, wenn man nicht gerade sehr ungünstige Daten hat.

Gerade bei zufälligen ints und mit reserve sollte die doch wenigstens ein bisschen glänzen (?). Muss nochmal schauen wie die implementiert werden musste, um standardkonform zu sein. Habe da nochwas von effektiv für jeden Bucket mindestens eine Pointer-Indirektion im Kopf. Auch wenn es dort nur ein Element mit diesem Hash gibt.

hustbaer

@Finnegan sagte in Felder auf Gleichheit überprüfen:

Irgendwie glaub ich das noch nicht so recht

Ich schon. Ich hab den Code ja überhaupt erst geschrieben weil ich sofort die starke Vermutung hatte dass @SeppJ hier mal ausnahmsweise nicht Recht hat - zumindest nicht wenn man auf die C++ Standardmittel ala map oder unordered_map zurückgreift. Weil die eben leider beide eine Allocation pro Eintrag machen. Blöd nur dass ich erst den Topfen mit fix 1000 drinnen hatte

Ansonsten sehen deine Compare-Funktionen nahezu aus wie bei mir.

Naja, ich hab zumindest ein Konstrukt das kompakter ist als bei dir: return a == b;

Du hast allerdings ein reserve() drin - da gehe ich aber nicht davon von aus, dass das bei den Differenzen, die ich gemessen habe einen grossen Unterschied macht.

Eh nicht. Ich wollte es nur rein schreiben weil ich mir bei unordered_map nicht mehr 100% sicher war ob die wirklich pro Eintrag eine Allocation machen muss. Und daher wollte ich fairerweise reserven

Was ist denn da mit der umap los?

Naja wie gesagt: eine Allocation pro Eintrag
Und was das "schlechter als O(N)" Scaling zwischen 10 und 1000000 angeht: Cache.

aber das ist ein Ding dass man eigentlich mit $O(1)$ einkalkuliert, wenn man nicht gerade sehr ungünstige Daten hat.

Der Teil (Lookup) haut eh hin. Das Einfügen ist das Langsame. Und sogar das ist O(1) -- bloss sehr langsames O(1).

Muss nochmal schauen wie die implementiert werden musste, um standardkonform zu sein. Habe da nochwas von effektiv für jeden Bucket mindestens eine Pointer-Indirektion im Kopf. Auch wenn es dort nur ein Element mit diesem Hash gibt.

Schlimmer. Siehe meinen anderen Beitrag mit den Links zu extract und insert(node_type&&).

Finnegan

@hustbaer sagte in Felder auf Gleichheit überprüfen:

@Finnegan sagte in Felder auf Gleichheit überprüfen:

Irgendwie glaub ich das noch nicht so recht

Ich schon. Ich hab den Code ja überhaupt erst geschrieben weil ich sofort die starke Vermutung hatte dass @SeppJ hier mal ausnahmsweise nicht Recht hat ...

Dachte ich auch, allerdings bis vielleicht 1 Million oder so. Irgendwann muss da der Break-Even kommen - wahrscheinlich erst bei Datenmengen, mit denen man eigentlich eher im HPC-Bereich zu tun hat. Aber die werden sehr wahrscheinlich keine std::unordered_map nehmen

Ansonsten sehen deine Compare-Funktionen nahezu aus wie bei mir.

Naja, ich hab zumindest ein Konstrukt das kompakter ist als bei dir: return a == b;

Ich erachte solche handgeschnitzen Schleifen als äquivalent, da sie sehr wahrscheinlich zu annähernd identischem Maschinencode zerfallen. Ich meinte damit eher "algorithmisch" nahezu gleich.

Der Teil (Lookup) haut eh hin. Das Einfügen ist das Langsame. Und sogar das ist O(1) -- bloss sehr langsames O(1).

Würd echt mal gerne wissen, ob 64 GiB RAM und 2 Wochen Zeit überhaupt reichen um experimentell zu sehen, dass das Ding linear ist. Wahrscheinlich eher nicht ... ausserdem gibts wichtigeres zu rechnen ... dass das Ding Kacke ist, sieht man auch so

Schlimmer. Siehe meinen anderen Beitrag mit den Links zu extract und insert(node_type&&).

Ah, damit kann man Elemente "moven" ohne "move". Ich habe Zweifel, ob es viele Anwendungsfälle gibt, wo man von so einem Feature tatsächlich profitiert. Zumal man noch mit einer dauerhaft ineffizienten Datenstruktur bezahlt, auch wenn man das gar nicht braucht - eigentlich wider die C++-Philosophie.

Hab heute übrigens nochmal ein paar Benchmarks laufen lassen, vor allem weil ich mal Googles dense_hash_map testen wollte. Bin mit der nicht bis ins Detail vertraut, sie arbeitet aber auf einem zusammenhängenden Speicherbereich mit offener Adressierung (klingt schonmal etwas cache-freundlicher).

Sieht aus als sei die Ehre der Hash-Maps wiederhergestellt, auch wenn sich die dense_hash_map ein Kopf-an-Kopf-Rennen mit Boost spreadsort liefert und sich stellenweise sogar überholen lässt - besonders bei den seltsamen Sprüngen in der $2^{26}$ -Skala. Gegen spreadsort kommt sie aber auch nur in der meiner schnelleren Compare-Variante an, die den letzen Loop über die Hash Map und oft auch einen Großteil des "Subtraktions-Loops" einspart:

Vektoren bis $N=2^8$
Vektoren bis $N=2^{10}$
Vektoren bis $N=2^{16}$
Vektoren bis $N=2^{26}$

Quellcode (benötigt Google Benchmark, sparsehash und Boost):

benchmark-vecequal.cpp

Habe jetzt auch die random(1, 10 * size)-Konstruktion verwendet und initialisiere den Zufallsgenerator mit festem Seed für bessere Reproduzier- und Vergleichbarkeit.

SeppJ

@hustbaer sagte in Felder auf Gleichheit überprüfen:

Ich schon. Ich hab den Code ja überhaupt erst geschrieben weil ich sofort die starke Vermutung hatte dass @SeppJ hier mal ausnahmsweise nicht Recht hat - zumindest nicht wenn man auf die C++ Standardmittel ala map oder unordered_map zurückgreift.

Ja, ich bin echt schwer enttäuscht. unordered_map war der Hype als sie neu war, aber das hier ist doch Mist.

Mechanics

Ich hatte in der Arbeit mal alles mögliche ausprobiert. Es gibt schon deutlich bessere Hash Maps, z.B. früher die dense_hashmap oder so von Google. Mittlerweile haben die was in der absl Bibliothek. Und dann findet man auch paar andere Implementierungen, wenn man etwas googelt. Wir benutzen mittlerweile mehrere unterschiedliche Implementierungen.
Ob das hier viel rausreißen würde, weiß ich nicht.

hustbaer

@Finnegan sagte in Felder auf Gleichheit überprüfen:

Ah, damit kann man Elemente "moven" ohne "move". Ich habe Zweifel, ob es viele Anwendungsfälle gibt, wo man von so einem Feature tatsächlich profitiert. Zumal man noch mit einer dauerhaft ineffizienten Datenstruktur bezahlt, auch wenn man das gar nicht braucht - eigentlich wider die C++-Philosophie.

Ich glaube der Zug war schon vor den Node Handles abgefahren. Die garantierte Adress-Stabilität verhindert schonmal eine wirklich performante open-addressing Variante. Und auch jede "nicht beknackte" open-addressing Variante. Weil man dazu halt Pool-Allokatoren für die KVPs bräuchte und der open-addressing Table würde dann bloss Pointer enthalten -- wäre alles recht komisch.

Was der Grund für die Adress-Stabilitäts Garantie angeht kann ich nur vermuten: es war dem Committee wichtig damit unordered_map oft als 1:1 replacement für map dienen kann. Und natürlich wäre es auch gefährlich eine unordered_map mit leicht unterschiedlichem Interface anzubieten die dann keine Adress-Stabilität garantiert. Weil dass sich ein Programm auf stabile Adressen verlässt, das kann der Compiler nicht erkennen und keinen Fehler dafür werfen. Und beim Programmierer kann es dann allzuleicht sein dass er nicht dran denkt oder es nicht weiss, bzw. u.U. nichtmal weiss dass das Programm das er da modifiziert sich überhaupt darauf verlässt.

Und zumindest was Lookup angeht ist die unordered_map ja durchaus schneller - gerade bei Keys die teuer zu vergleichen sind.

ps: Und genau das, also dass der Zug eh schon lange abgefahren war, war dann soweit ich weiss der Grund warum die Node-Handles und das Bucket-Interface noch dazugebastelt wurden. Weil wenn man sowieso schon die ollen einzeln angeforderten Nodes hat, dann macht es durchaus Sinn zu versuchen den maximalen Nutzen zu bekommen indem man weitere Funktionen anbietet. Auch wenn diese Funktionen nur in wenigen Projekten nützlich sind.

Mechanics

@hustbaer sagte in Felder auf Gleichheit überprüfen:

Und zumindest was Lookup angeht ist die unordered_map ja durchaus schneller - gerade bei Keys die teuer zu vergleichen sind.

Auch da hatte ich mit den alternativen Implementierungen deutlich bessere Erfahrungen gemacht. Da kann man schon noch was rausholen.

hustbaer

@Mechanics Ja sorry, ich meinte schneller als std::map. Dass es nochmal schneller geht ist klar, wegen der besseren Cache-Locality und weniger Pointer-Chasing bei Open-Addressing.