Felder auf Gleichheit überprüfen

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.

Finnegan

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

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.

Danke für die Info. Hatte sowas schon gesucht. dense_hash_map war das erste, was ich auf die Schnelle gefunden habe und das Vorstellung von einer halbwegs effizienten Implementierung entsprach. Das die etwas angestaubt ist, ist mir auch aufgefallen (2005).

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

Ich glaube der Zug war schon vor den Node Handles abgefahren. Die garantierte Adress-Stabilität verhindert schonmal eine wirklich performante open-addressing Variante.

Ja, da sagst du was. Selbst so ein vermeintlich unschuldiger wie No-Brainer wie std::vector hat dieses Problem:

After container move construction (overload (7)), references, pointers, and iterators (other than the end iterator) to other remain valid, but refer to elements that are now in *this. The current standard makes this guarantee via the blanket statement in [container.requirements.general]/12, and a more direct guarantee is under consideration via LWG 2321.

Das verhindert effektiv Small Size Optimization wie bei std::string, da bei einem Move natürich Elemente, die sich im Inline-Puffer des SSO-vector befinden die Adresse ändern und Iteratoren invalidiert werden müssen.

Auch interessant:

std::basic_string<CharT,Traits,Allocator>::swap:

Exchanges the contents of the string with those of other. All iterators and references may be invalidated.

std::vector<T,Allocator>::swap:

All iterators and references remain valid. The past-the-end iterator is invalidated.

Schon schade. Es wär ja durchaus nicht verkehrt gewesen, den std::string damals als class string : public vector<CharT> {}; zu stricken und den Standard darauf aufzubauen. Inklusive Raum für SSO.

Vielleicht sehen wir ja irgendwann mal sowas wie std2, wo man sich mit den Garantien etwas zurückhält um den Implementierungen möglichst viel Freiheiten zu lassen. Ich sehe z.b. kein grosses Problem darin, wenn jegliche nicht-const-Operation auf einem Container Iteratoren und Element-Addressen invalidiert. Man muss das eben wissen und entsprechend programmieren. Zusätzlich können einen die Container noch unterstützen, so dass es für übliche Verwendungen nicht zu umständlich oder ineffizient wird, wie z.B. map::erase() -> iterator.

Dass man sich bei der aktuellen std festgenagelt hat, ist natürlich auch klar. Ich behaupte auch nicht, dass man da noch viel tun könnte.

Fazit ist aber auch, dass man sich nicht schämen muss, einen Grossteil der std links liegen zu lassen oder sogar sowas banales wie std::vector selbst zu implementieren (siehe LLVM), wenn man weiss man tut und Performance wichtig ist.

P.S.: Tip an übugsaufgabengeplagte Schüler und Studenten: Wenn ihr eure Fragen in ein interessantes Problem wie dieses hier verpackt, machen wir hier eure Hausaufgaben mit Kusshand. Das drölfzigste "Hilfe!!! Ich muss einen Taschenrechner proggen, aber die IF-Schleife ist kaputt." ist da nur bedingt geeignet. SCNR

HarteWare

Ich bin jetzt verwirrt... Es ist also doch am schnellsten mit std::sort (wenn man std::sort, std::map und std::unordered_map betrachtet)?

P.S.: @hustbaer In Deinem Post fehlt glaub noch oben (aber ist ja nicht so wichtig...)

std::sort[100]

integer_sort is a fast templated in-place hybrid radix/comparison algorithm

Spreadsort - integer sort

Finnegan

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

Ich bin jetzt verwirrt... Es ist also doch am schnellsten mit std::sort (wenn man std::sort, std::map und std::unordered_map betrachtet)?

Für Vektoren bis etwa 68 Millionen ( $2^{26}$ ) ints definitiv ja. Weiter nicht getestet, da die unordered_mapdafür schon etwa 2 Minuten brauchte (vs. 10 Sekunden mit std::sort).

Zumindest in der Theorie sollten die sich aber irgendwann treffen bei $n = 2^c$ ( $\Leftrightarrow cn=n\log_2 n$ ) für irgendein konstantes $c$ . Wenn ich raten müsste, würde ich das $c$ irgendwo in der Größenordnung von 300 verorten ( $2^{26}c /120\text{ Sekunden}=2^{26} \log_2 2^{26}/10\text{ Sekunden}\Leftrightarrow c=312$ ).

Sollte das tatsächlich stimmen, braucht man viel Zeit, eine Menge RAM und ne neue CPU-Architektur die den adressieren kann.
... kann aber auch sein, dass ich grad halbgaren Bullshit phantasiere

hustbaer

@HarteWare

Es ist also doch am schnellsten mit std::sort (wenn man std::sort, std::map und std::unordered_map betrachtet)?

Korrekt.

In Deinem Post fehlt glaub noch oben (aber ist ja nicht so wichtig...)

std::sort[100]

Ebenso korrekt. Ich hab' beim Kopieren wohl nicht weit genug hinaufgescrollt und zu wenig kopiert. Es fehlen auch noch alle 4 Einträge mit [10]. Aber ja, sollte reichlich egal sein, denn auch da schlagen beide Sorts beide Maps.