C++ Große Laufzeitunterschiede zwischen Windows und Linux

Hallo Leute,

heute bin ich auf eine merkwürdige Sache gestoßen und kann sie mir bisher nicht so ganz erklären. Eigentlich war meine ursprüngliche Intention nur (mal wieder) ein bisschen mit Sortieralgorithmen zu experimentieren und habe damit auf meinem Laptop (Ubuntu) begonnen.
Da mein Desktop (Windows) mehr Leistung (und Ram) besitzt wollte ich hier dann weiter testen und habe den Code einfach kopiert.

Bei den meisten Tests gab es jetzt keine Überraschungen, bis ich zum Quicksort kam. Der ist auf dieser Maschine aus irgendeinem Grund vergleichsweise absolut lahm. Das Ganze habe ich als release für 32 und 64bit kompiliert. In der Debug-Version ist alles verständlicherweise ziemlich langsam. Aber auch hier musste der Quicksort am Stärksten drunter leiden.

Die zu sortierenden Daten liegen auf dem Heap, da ich sehr große Datenmengen testen wollte. Der Quicksort ist eine rekursive Variante. Das klappt auf meinem Laptop unter Linux auch direkt. In Visual Studio musste ich jetzt erstmal noch die Größe von Stack und Heap erweitern.


Damit lief es dann auch bis zu einer gewissen Größe ohne Probleme. Nur der Quicksort ist nicht so glücklich. Der wird hier sogar langsamer als der Mergesort.

Um mal die Größenordnung deutlich zu machen:

Als Debug kompiliert:
Merge: 32,853 s
Quick: 310,949 s
Quick2:313,646 s

x64 release:
Merge: 11,778 s
Quick: 84,442 s
Quick2: 84,489 s

x32 release:
Merge: 13,774 s
Quick: 84,302 s
Quick2: 83,959 s

Auf dem Laptop(Ubuntu):
Merge: 62,885 s
Quick: 46,107 s
Quick2: 45,686 s

Also der Unterschied ist schon gigantisch. Vielleicht hat ja jemand eine Idee woher so etwas kommen kann? Schließlich ist der Code absolut identisch.
Vielleicht werde ich mal eine iterative Variante probieren, um zu schauen, ob es hier einen ähnlichen Effekt gibt.

viele Grüße
daemon

Du benutzt verschiedene Compiler und verschiedene CPUs.
Du solltest mindestens MingW oder einen anderen gcc/g++ Port unter Windows nutzen. Selbst dann sind die Ergebnisse kaum wirklich vergleichbar.

Am besten wäre vielleicht sogar Cygwin's gcc.

Dass es da zu kleinen Unterschieden kommen kann, wenn man unterschiedliche Compiler hernimmt ist ja klar. Aber wie kommt es denn zustande, dass der Mergesort zwar mehr als 5 mal so schnell ist, während der Quicksort nicht einmal mehr halb so schnell ist wie zuvor? Also von 75% Mergesortlaufzeit rauf auf 500% dieser Laufzeit.
So riesig dürften doch die Unterschiede bei Weitem nicht werden.

Je nach Compiler / Systemarchitektur können sich enorme Unterschiede ergeben. Als Beispiel hierfür viel mir folgende Frage auf Stackoverflow ein, ist zwar vielleicht nicht ganz deine Frage, aber es geht vom Ding her in die gleiche Richtung, vielleicht dacher ganz interessant für dich:
http://stackoverflow.com/questions/...-a-sorted-array-faster-than-an-unsorted-array

Soweit ich weiß, kompiliert der Microsoft-Compiler selbst bei einem Release-Build haufenweise error-checks mit in die ganzen STL-Container rein, die man mit 2 defines abschalten kann. Der Name dieser Defines ist mir im Moment entfallen, aber ich versuche mal, ob Google was findet ...

Ah nee, laut Google, ist das schon seit VS2010 per default in einem Release-Build nicht mehr aktiviert.

Es reicht schon wenn Compiler A x87 FPU nutzt und der Compiler B SSE4. Sowas passiert sehr schnell. Und eben nicht jeder Algorithmus wird durch so eine Optimierung gleich gut beschleunigt.

Wenn du den Stack vergrößern musst, klingt das nach Versagen der Tail Call Optimization. Guck mal ob und wenn ja, wie man die unter Visual Studio anmachen kann.

@Grundkurs:
Danke für den Link. Der Thread ist tatsächlich ganz interessant, da ich bisher nicht gedacht habe, dass man selber mit Branche-Predictions so spielen kann.

@HominiLupus:
Bisher habe ich nur immer gehört, dass der VC++-Compiler so toll sein soll. Da hätte ich so etwas nicht erwartet.

@ asdfman:
Die Tail Call Optimierung sollte eigentlich bei O2 oder Ox Optimierung mit dabei sein.

Danke an euch alle! Danke euch habe ich jetzt ein paar neue Anhaltspunkte zum experimentieren. Immerhin ist mein Bubblesort durch ein paar einfache Maßnahmen jetzt schon ca 50% schneller als vorher.
Beim Quicksort ist es wohl das Einfachste da erstmal zur iterativen Variante zu wechseln und hieran dann zu optimieren.

Starte den Release-Build mal außerhalb von Visual Studio (also die exe ausführen). In Visual Studio wird ein langsamerer Debug-Heap benutzt (auch im Release-Build), das kann die Laufzeit ggf. erklären. Wenn du das von außerhalb startest, wird der normale Windows-Heap genutzt, der deutlich schneller ist.

Magogan schrieb:

Starte den Release-Build mal außerhalb von Visual Studio (also die exe ausführen)

Zum Vergrößern anklicken....

Geht auch mit Strg+F5 bzw. "Debuggen -> Starten ohne Ohne Debugging" starten und führt manchmal dazu, dass de Code um ne Größenordnungen schneller läuft. Ansonsten würde ich auch eher die Rekursion als Übeltäter vermuten - ich weiß nicht, ob Vektorisierung bei sortieralgorithmen viel bringt.

VC vs GCC: Wäre mir neu, dass der Microsoft Compiler - im Vergleich zu GCC - besonder schnellen Code erzeugen würde. Eher im Gegenteil - bist du sicher, dass sich diese Kommentare nicht auf Visual Studio als IDE und den Debugger bezogen haben?

Miuwa schrieb:

Geht auch mit Strg+F5 bzw. "Debuggen -> Starten ohne Ohne Debugging" starten und führt manchmal dazu, dass de Code um ne Größenordnungen schneller läuft.

Zum Vergrößern anklicken....

Nein, auch da startet VS die *.vshost.exe, anstatt der Richtigen.

Das wäre mir neu. Gibts die nicht ohnehin nur bei c# (oder allgemein managed code)?

Hab zwar lange nix mehr mit C++ gemacht, aber afaik gibts die dort genauso.

Ich möchte nicht völlig ausschließen, dass es bei C++ Programmen irgendeinen Laufzeitunterschied zwischen dem direkten Starten der exe und dem Starten via VS gibt, aber soweit ich das sagen kann, erzeugt VS2013 für Standard C++ Projekte schlicht nur eine exe pro Konfiguration.

daemon777 schrieb:

Bisher habe ich nur immer gehört, dass der VC++-Compiler so toll sein soll. Da hätte ich so etwas nicht erwartet.

Zum Vergrößern anklicken....

Welcher ist das denn und was hast Du für ein Projekt mit welchen Einstellungen? Ist das "Managed C++" oder sowas?

Die Visual Studio Entwicklungsumgebung an sich ist meiner Meinung nach zwar immer noch unschlagbar, aber der Compiler selbst ist auch in den neusten Versionen nicht so das Gelbe vom Ei. Besonders was die Umsetzung des C++11/14-Standards angeht, hinkt Microsoft da z.B. dem GNU-Compiler immer noch meilenweit hinterher. :-(

EDIT: Hier mal eine interessante Gegenüberstellung --> http://cpprocks.com/c1114-compiler-and-library-shootout/

antred schrieb:

Die Visual Studio Entwicklungsumgebung an sich ist meiner Meinung nach zwar immer noch unschlagbar, aber der Compiler selbst ist auch in den neusten Versionen nicht so das Gelbe vom Ei.

Zum Vergrößern anklicken....

Kann ich nicht bestätigen. Ich kompiliere regelmäßig Linux-Simulationsprogramme unter Windows mit VC und stelle keine schlechtere Performance fest, die als solche nennenswert wäre. Manchmal sogar das Gegenteil.

Besonders was die Umsetzung des C++11/14-Standards angeht, hinkt Microsoft da z.B. dem GNU-Compiler immer noch meilenweit hinterher. :-(Hier mal eine interessante Gegenüberstellung --> http://cpprocks.com/c1114-compiler-and-library-shootout/)

Zum Vergrößern anklicken....

Na gut, das ist lange her. Das aktuelle VS15RC, welches ich hier am Laufen habe, kann schon eine ganze Menge mehr.

Ich sprach nicht von Performance sondern von standard compliance (und auch in der von dir verlinkten Tabelle fehlt da immer noch einiges **1). An der Performance des VS-Compilers hatte ich auch noch nie was zu meckern.

**1: Und im übrigen bin ich nicht länger gewillt, alle 15 Monate ein paar Hundert Kröten für eine neues Visual Studio abzudrücken, nur um dann festzustellen, dass Microsoft C++-technisch eigentlich wieder nur oberflächlich dran rumpoliert hat. In der Vergangenheit habe ich diesen Tanz leider zu oft mitgetanzt, aber seit neuem bin ich mit dem MingW-Compiler wesentlich zufriedener.

@antred: VS ist für Einzelpersonen Kostenlos (auch bei kommerzieller Nutzung):
https://www.visualstudio.com/en-us/products/visual-studio-community-vs.aspx

@antred: Und dabei soll doch diesmal endlich wirklich und ganz sicher bzw auf jeden Fall besser als bisher Intellisense unter C++ manchmal funktionieren!