Benchmark: C/C++ Effiziente Methoden zum Suchen

Also ist Direct Access immer schneller lt. deinen Diagrammen.

Ja, da wird ja ohne Suche auf das Element zugegriffen.

Ist auf der x-Achse die "Anzahl" der gesuchten oder durchsuchten 
Elemente dargestellt?

Wie sieht es mit binärer Suche aus?

mh schrieb:
> Ist auf der x-Achse die "Anzahl" der gesuchten oder durchsuchten
> Elemente dargestellt?
>
> Wie sieht es mit binärer Suche aus?

Die X-Achse ist die Grösse der durchsuchten Elemente in Bytes
(Anzahl * Grösse).
Da sieht man schön die Cache Effekte.

Binäre Suche kommt hoffentlich noch.

Pandur S. schrieb:
> Eigentlich sind die Wuerfel schon laengst gefallen. Falls man sich's
> leisten kann nimmt man Binaersuche.

Kannst du das etwas genauer erklären?

mh schrieb:
>> Eigentlich sind die Wuerfel schon laengst gefallen. Falls man sich's
>> leisten kann nimmt man Binaersuche.

Im Anhang ein Update mit Binärsuche.
Die X Achse ist jetzt mit der Anzahl der Elemente skaliert (32 
Bytes/Element).

Einmal mit der libc bsearch Funktion, und dann noch mit
einer inline Version, die aus den Sourcen von BSD 4.3 abgekupfert ist.
Gerade bei der hier sehr einfachen Compare Funktion kann die
libc bsearch nicht mithalten.

Wie macht man in C++ eine binäre Suche, wo man nicht nur gefunden oder
nicht gefunden zurückbekommt, sondern den Index des gefundenen Elements
(bzw. wer hat sich die kranke std::binary_search einfallen lassen...)?

Grüsse,
Udo

udok schrieb:
> Wie macht man in C++ eine binäre Suche, wo man nicht nur gefunden oder
> nicht gefunden zurückbekommt, sondern den Index des gefundenen Elements
> (bzw. wer hat sich die kranke std::binary_search einfallen lassen...)?

std::lower_bound bzw upper_bound.

Falls du lower/upper_bound testest, kannst du dann zufällig auch teste, 
ob sich std::find von deiner linearen Suche unterscheidet? (std::find 
hat das gleiche Interface).

mh schrieb:
> Falls du lower/upper_bound testest, kannst du dann zufällig auch teste,
> ob sich std::find von deiner linearen Suche unterscheidet? (std::find
> hat das gleiche Interface)

Ist identisch zur linearen Suche (überdeckt sich mit der for() 
Schleife).
Bild ist im Anhang.

udok schrieb:
>> Falls du lower/upper_bound testest

Habe ich eingebaut.  lower_bound() verhält sich ca. wie bsearch.
Bei kleinen Datensätzen ist lower_bound klar im Vorteil.

Ich habe noch ein Update des Benchmarks gemacht.
Bilder sind wieder im Anhang.

Das erste Bild zeigt die Suche nach zufälligen Integer Keys.

Hier habe ich einige "branchless" Versionen ausprobiert.

Bei den Branchless Versionen wird ein "if-else" durch
ein "Conditional-move" ersetzt.

Teilweise branchless sind AVL-Baum und bsearch-inline.
bsearch-branchless ist komplett branchless, da wird
die Suche immer erst nach log2(N) Vergleichen terminiert.

Speziell bei den binären Suchmethoden sind die Sprünge recht
zufällig und der CPU-Branchprediktor funktioniert damit nicht.
Die Conditional-Move Befehle haben das Problem nicht, weil
immer derselbe Codepfad ausgeführt wird, und damit die CPU-Pipeline
voll bleibt.
Das bringt einen beachtlichen Geschwindigkeitsvorteil, sofern
die Daten in den L2 Cache passen.  Passen die Daten da nicht
mehr rein, kann das ein Nachteil werden, weil "spekulative RAM-Read"
der CPU auch nicht mehr funktioniert.  Das habe ich hier aber
nicht gesehen.

Das zweite Bild zeigt die Suche nach zufälligen Strings.

Da sieht man sehr schön, das in der Praxis die Unterschiede zwischen
den Suchverfahren sehr viel kleiner ausfallen, weil die relativ
langsame strcmp() Funktion die Zeit dominiert.
Einzig die Hash Suchverfahren heben sich positiv heraus, weil die 
strcmp()
Funktion da nur ein einziges Mal ausgeführt wird.