C/C++ Benchmark - Effizientes Suchen

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
udok
Beiträge: 40
Registriert: 01.02.2022, 17:34

C/C++ Benchmark - Effizientes Suchen

Beitrag von udok »

Ich habe ja vor Ewigkeiten etliche Tests zu verschiedenen Suchmethoden gemacht.

Damit die Daten nicht nur auf der Platte vergammeln, möchte ich sie hier vorstellen,
vielleicht helfen sie, die graue Theorie abzurunden...
Und wenn man ein zeitkritisches Suchproblem hat, dann geben die Zahlen einen Anhalt,
welche Methoden geeignet sind. Achtung: Die Diagramme sind doppelt logarithmisch.

--- Zufallssuche mit Integer Key ---
run4_Int_Key_Random-20211130.png
--- Zufallssuche mit strcmp ---
run5_Strings_Key_Random-20211130.png
--- Zufallssuche mit Integer Key, sehr große Felder ---
run4-20Million.png
---
Die zu suchenden Elemente sind 32 Byte Strukturen in einem grossen Feld.

Der Suchindex ist zufällig und entweder eine Integerzahl, oder ein String (strmcp).

Betriebssystem ist Win10, compiler ist VS2019, das ganze läuft auf einem Dell Laptop mit einem i7-8850H
(L1 Cache 32kByte, L2=256k, L3=1.5MByte).

Direkter-Speicherzugriff:
In manchen Fällen reden wir über < 300 Pikosekunden, moderne HW ist sauschnell!

Robin-Hood Hash Map:
Hash Suche, die den Robin-Hood Algo verwendet.
Als Hash Funktion wird die Intel HW CRC32 verwendet, die in meine Tests meist sehr gut war.
https://codecapsule.com/2013/11/11/robin-hood-hashing/

AVL Tree:
Adelson Velskii Landis (AVL) binärer Suchbaum.
Standard Methode seit 1962 aus Russland.
Unglaublich viele komplizierte Spezialfälle.
Ich würde es nicht nochmal programmieren wollen.
https://en.wikipedia.org/wiki/AVL_tree

std::map:
Wahrscheinlich ein Red-Black binärer Baum.

std::unordered_map:
C++ hash table. Keine Ahnung, was da genau verwendet wird.

Lineare Suche:
Eine einfache for Schleife.
Laut https://dirtyhandscoding.github.io/post ... earch.html
soll die bis zu 256 Einträgen ja schneller sein.
Ich habe das mit dem Code der Seite nachvollzogen, aber nicht mit meinen komplexeren Tests hier.

Gruss,
Udo
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: C/C++ Benchmark - Effizientes Suchen

Beitrag von Krishty »

Code noch da? Dann können wir selber auch benchen :D
udok hat geschrieben: 07.09.2022, 11:36Lineare Suche:
Eine einfache for Schleife.
Laut https://dirtyhandscoding.github.io/post ... earch.html
soll die bis zu 256 Einträgen ja schneller sein.
Ich habe das mit dem Code der Seite nachvollzogen, aber nicht mit meinen komplexeren Tests hier.
Interessant. Ich kann es auch in komplexen Anwendungssituationen nachvollziehen; habe deshalb viele Bubble Sorts und lineare Suchen in inneren Schleifen. Hier solltest du wirklich mal nachschauen, zumal es der einfachste Fall ist.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
udok
Beiträge: 40
Registriert: 01.02.2022, 17:34

Re: C/C++ Benchmark - Effizientes Suchen

Beitrag von udok »

Code noch da? Dann können wir selber auch benchen :D
Ist noch da, aber ist ein Wirrwarr aus Skripten. Der ist sicher nicht einfach zu verwenden. Ich schau mal was ich machen kann...

Vielleicht liegt es daran, dass mein Suchkey in einem 32 Byte struct drinnen ist, und das Memory Interface limitiert.
Das sollte dem ganzen etwas mehr Realität geben.

Auf der dirtyhandscoding Seite sind die Ergebnisse aber deutlich langsamer als meine Werte für die Hash Suche (ca 10 ns zu 1.5 ns @ 64 Elemente).
Selbst meine branchless AVL version braucht gerade mal 4 ns. Und mein Laptop ist jetzt nicht superschnell...
udok
Beiträge: 40
Registriert: 01.02.2022, 17:34

Re: C/C++ Benchmark - Effizientes Suchen

Beitrag von udok »

Ich habe den Code wieder rausgelöscht, weil der ohne Support nur schwer verwendbar ist.

Gruss,
Udo
Zuletzt geändert von udok am 12.09.2022, 15:55, insgesamt 1-mal geändert.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: C/C++ Benchmark - Effizientes Suchen

Beitrag von Krishty »

Danke! Ich konnte es auf die Schnelle nicht auf Windows ans Laufen kriegen, weil FreeBSD und Win32 SIZE_T unterschiedlich definieren, und das beim Kompilieren heftig kracht. Ich schaue die Tage nochmal rein
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Antworten