Warum wird mein Bottom-Up-Merge in Java so langsam sortiert?

8

Ich verbrachte die letzten paar Stunden damit, herauszufinden, warum die Java-Version meines Sortieralgorithmus doppelt so langsam war wie eine rekursive Merge-Sortierung, da die C- und C ++ - Versionen 40-50% schneller waren. Ich entfernte immer mehr Code, bis ich alles auf eine einfache Schleife reduziert und zusammengeführt hatte, aber es war immer noch doppelt so langsam . Warum ist das nur in Java so langsam?

Hier sehen Sie, wie eine Bottom-Up-Merge-Sortierung aussehen könnte:

%Vor%

Und hier ist die rekursive Version:

%Vor%

Diese werden im Grunde nur von den Algorithmen auf dieser Website kopiert. Als letzten Ausweg dachte ich, ich würde etwas aus dem Internet kopieren und einfügen, aber es ist auch doppelt so langsam wie die rekursive Version.

Gibt es etwas "Besonderes" an Java, das ich vermisse?

BEARBEITEN: Wie gewünscht, hier ein Code:

%Vor%

Und hier ist eine C ++ Version:

%Vor%

Die Unterschiede sind nicht so drastisch wie die ursprünglichen Versionen, aber die iterative C ++ - Version ist schneller, während die iterative Java-Version langsamer ist.

(und ja, ich merke, dass diese Versionen irgendwie saugen und mehr Speicher zuweisen als verwendet wird)

Update 2: Wenn ich die Bottom-Up-Merge-Sortierung auf eine Postorder-Traversierung umgestellt habe, die der Reihenfolge der Array-Zugriffe in der rekursiven Version sehr nahe kommt, lief sie schließlich um 10% schneller als die rekursive Version. Es sieht also so aus, als ob es sich um Cache-Misses und nicht um Mikro-Benchmarks oder eine unvorhersehbare JVM handelt.

Der Grund, warum es nur die Java-Version betrifft, liegt möglicherweise daran, dass Java die benutzerdefinierten Werttypen nicht enthält, die in der C ++ - Version verwendet werden. Ich werde alle Test-Klassen separat in der C ++ - Version zuweisen und sehen, was mit der Leistung passiert. Der Sortieralgorithmus, an dem ich arbeite, kann nicht einfach an diese Art von Traversal angepasst werden, aber wenn die Performance-Tanks auch in der C ++ - Version sind, habe ich vielleicht keine große Wahl.

Update 3: Nein, die Umstellung der C ++ - Version auf zugewiesene Klassen schien keine nennenswerten Auswirkungen auf die Performance zu haben. Es scheint, als ob es durch etwas speziell mit Java verursacht wurde.

    
BonzaiThePenguin 16.04.2014, 23:12
quelle

1 Antwort

2

Interessante Frage. Ich konnte nicht herausfinden, warum die BottomUp-Version langsamer als rekursiv ist, während sie bei einer Array-Stärke von zwei identisch funktioniert.

Zumindest ist BottomUp nur ein bisschen langsamer, nicht zweimal.

%Vor%

Code:

%Vor%     
leventov 17.04.2014 01:29
quelle