Geschwindigkeitstest: Java, dann VB und dann C++

asdfasdf schrieb:

javadoof schrieb:

Hast du mal probiert, ob das überhaupt noch sortiert?

Ja und Ja

Lustig, bei mir wird die Eingabe 0,1,2 (verkehrt vorsortiert) zu 2,0,1 "sortiert".

Stimmt, war quatsch. Sorry for the inconvenience. Hätte nicht nur einen Lauf kontrollieren sollen

hustbaer schrieb:

Gast3 schrieb:

die Ints einfach mal in Klassen stecken und dann damit arbeiten.

und was soll dann das für die Analyse des Laufzeitunterschieds zwischen C++ und Java bringen?

Java wird haushoch verlieren? Weil es keine Value-Types kann?

Und auch noch std::string in std::vector sortieren mit RAII (weil Raw-Pointer keiner mehr macht), damit C++ haushoch verliert. Oder vielleicht einen smartpointer der den std::string hält, damit C++ wieder eine Chance haben könnte. Aber baut hier wirklich einer sowas vector< unique_ptr <string > > >?

Techel

Eher std::list<std::shared_ptrstd::string> damit java überhaupt ne chance hat

hallo123test schrieb:

Und auch noch std::string in std::vector sortieren mit RAII (weil Raw-Pointer keiner mehr macht), damit C++ haushoch verliert.

Wie was? Was soll string in vector mit RAII sein? String verwaltet doch schon seine Resourcen selbst und einen std::vector<std::string> zu sortieren dürfte dank move auch schön schnell sein.

sebi707 schrieb:

hallo123test schrieb:

Und auch noch std::string in std::vector sortieren mit RAII (weil Raw-Pointer keiner mehr macht), damit C++ haushoch verliert.

Wie was? Was soll string in vector mit RAII sein? String verwaltet doch schon seine Resourcen selbst und einen std::vector<std::string> zu sortieren dürfte dank move auch schön schnell sein.

Vergleich mal.

kurze_frage

hallo123test schrieb:

sebi707 schrieb:

hallo123test schrieb:

Und auch noch std::string in std::vector sortieren mit RAII (weil Raw-Pointer keiner mehr macht), damit C++ haushoch verliert.

Wie was? Was soll string in vector mit RAII sein? String verwaltet doch schon seine Resourcen selbst und einen std::vector<std::string> zu sortieren dürfte dank move auch schön schnell sein.

Vergleich mal.

sowieso, irgendwelche Kunst Konstrukte wie das vorgeschlagene vector<uniquer_ptr<T>> sind nicht notwendig
und selbst in alten C++ gcc hat eine, nicht ganz dem Standard entsprechende, copy on write Implementierung von std::string.die ist sicher recht flott

ich denke das, wenn man wirklich messen möchte wie sich diverse Sprachen austesten, sollte ungefähr so etwas genommen werden,

class A
{
public:
  int i ;
  float f;
};

class B {
public:
 A a ;
 string s;
};

erzeuge listen, sortiere , such , member zugriff, ....

man kann dann noch immer noch Integers und Floats vergleichen dividieren und seine Überraschungen erleben.

Wollte nur mal anmerken, dass C++ bei den meisten Benchmark-Games gegen Java gewinnt. Eben nicht bei allen, aber bei den meisten:

http://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=gpp&lang2=java

Interessant finde ich auch, dass rust in 5 von 11 Benchmarks schneller als C++ ist:

http://benchmarksgame.alioth.debian.org/u64q/compare.php?lang=rust&lang2=gpp

rust ist noch recht jung und da ist sicherlich noch einiges rauszuholen. Bin da wirklich optimistisch. rust kann wohl als einzig wahrer C++ Nachfolger betrachtet werden.

Mechanics

Aber wenn man sich die Tabelle anschaut, gibts öfter mal mehrere Implementierungen. z.B. bei dem fasta Test ist Rust #2 ganz oben, es gibt aber auch eine Rust Implementierung, die langsamer ist als C++. Ist also nicht gesagt, dass der C++ Code wirklich optimal ist.

Da man immer wieder optimierten Code einreichen kann, konvergieren die Benchmarks wohl langsam aber sicher gegen das Optimum, das mit der Sprache möglich ist.
C++ ist schon lange dabei...

hustbaer

Ich wollte gerade probieren ob ich die C++ Version des "k-nucleotide" Tests etwas schneller bekomme (kann mMn. kein Problem sein)...

Bloss sieht es so aus als ob das Test Output-File nicht zum angegebenen Test Input-File passt.

Denn sogar der aktuelle C++ Code von der Webseite wirft da andere Ergebnisse aus.

Tjoah. Doof.

EDIT: Findet jemand ne Email Adresse wo man da mal hinschreiben könnte?

Atlan

@Benchmark
Was ist mit D? D sieht auch recht vielversprechend aus, da es die starke Objektorientierung von Java mit Zeigern, Referenzen und dem schnellen Code von C++ verbindet.

@Hustbaer
Ich habe es mit mehreren Onlinediensten versucht, jedoch habe ich die Seite nur anpingen können.

Ich habe denselben Test nun nocheinmal mit den passenden API-Funktionen in Java und C++ laufen gelassen.
Java hat beim ersten Durchlauf 95.000 Mikrosekunden gebraucht, es wird jedoch mit jedem Durchlauf weniger und das Geringste, was es bei 300 Durchläufen gebraucht hat, sind ca. 7.500 Mikrosekunden.
C++ kann mit weniger, als 2.000 Mikrosekunden locker dagegenhalten.
Java benutzt den Quicksort, C++ einen unbekannten Algorithmus mit O(n log n) im Worst Case, während der Quicksort O(n2) im Worstcase hat.
Es ist aber fast sicher, dass C++ nicht den Quicksort verwendet, da O(n log n) als Worstcase gefordert wird und nicht als Durchschnitt. Vielleicht verwendet C++ Introsort.

SeppJ

Atlan schrieb:

Java benutzt den Quicksort, C++ einen unbekannten Algorithmus mit O(n log n) im Worst Case, während der Quicksort O(n2) im Worstcase hat.
Es ist aber fast sicher, dass C++ nicht den Quicksort verwendet, da O(n log n) als Worstcase gefordert wird und nicht als Durchschnitt. Vielleicht verwendet C++ Introsort.

C++ macht keine spezielle Vorgabe an die Sortieralgorithmen, nur an die Komplexität. Ich weiß aus dem Stand nicht, ob Java einen speziellen Algorithmus verlangt oder auch nur Komplexitätsvorgaben macht, aber Quicksort wird in Java schon lange nicht mehr benutzt. Der Worst-Case ist einfach inakzeptabel.

Aktuelle Implementierungen in Standardbibliotheken benutzen diverse Algorithmen mit O(n*log n) als Worst-Case. Beispiele, die tatsächlich praktisch genutzt werden, sind Timsort (Java, Python, andere) und Introsort (diverse C++-Standardbibliotheken). Die tun sich alle gegenseitig nicht viel. Der Unterschied, den du hier siehst, sind höchstwahrscheinlich die fundamentalen Unterschiede, wie Daten in den verschiedenen Sprachen gehandhabt werden.

hustbaer

Atlan schrieb:

Es ist aber fast sicher, dass C++ nicht den Quicksort verwendet, da O(n log n) als Worstcase gefordert wird und nicht als Durchschnitt. Vielleicht verwendet C++ Introsort.

Wobei Introsort ja auch nur ein Quicksort ist der ab einer bestimmten Verschachtelungstiefe die Reissleine zieht und auf Mergesort umschaltet.
Bei nem sortierten Input kann das also keinen grossen Unterschied machen, da hier Introsort niemals mergen wird. Was bleibt ist lediglich der minimale Aufwand die Verschachtelungstiefe mitzuführen und mit einem Grenzwert zu vergleichen.

Ihr trefft aussagen über Java, die man so nicht stehen lassen kann. Mag auch ein wenig an wenig vertrauenswürdigen Nicks liegen. Eine Art Vorsortierung, modifizierter Quicksort und MergeSort finden dort Anwendung. Sortierte Listen n, alle anderen Fälle n*log_2(n). Wenn man sich nicht gerade etwas konstruiert, was schwer zu konstruieren ist, würde n^2 in der Praxis auch bei Qs nie erreicht. Möchte man testen, muss man schon mit einer zufallszahlengeneratorverteilen Liste testen. C++ wird nicht durch seine Geschwindigkeit langsamer sein.

SeppJ

EinGastredner schrieb:

Wenn man sich nicht gerade etwas konstruiert, was schwer zu konstruieren ist, würde n^2 in der Praxis auch bei Qs nie erreicht.

Das Problem ist aber, dass ein böser Hacker eben genau das tut und damit deinen Server DOSt, wenn du Quicksort benutzt. Daher kannst du in der Praxis kein naives Quicksort einsetzen. Die anderen Algorithmen sind ja auch nicht wirklich schlechter. Viele davon setzen schließlich auf Quicksort auf.

kurze_frage

wie wertlos ein publizierter Benchmarks ist kann man daran sehen um wie viel schneller C als C++ bei einzelnen Tests ist.
Denk ich mir mal, denn entweder muss C++ genauso schnell sein weil ich den gleichen Code verwenden kann der den selben Output erzeugen müsste, oder schneller weil ich an stellen wo C void* nutzt Typen benutzen kann.

benchmarksgame.alioth.debian vergleicht ja auch nicht Sprachen sondern Sprache und Implementierung da die Implementierungen doch sehr unterschiedlich sind.

siehe zB binary tree C und C++ Implementierungen, da bekommt man ja hier im Forum bessere C++ Versionen.

hustbaer schrieb:

EDIT: Findet jemand ne Email Adresse wo man da mal hinschreiben könnte?

Evtl. darüber:

http://benchmarksgame.alioth.debian.org/play.html

@atlan: Mag sein, dass D nicht schlecht ist. Bietet aber nicht dieselbe Sicherheit wie rust und ist außerdem nicht offen.

Atlan

@SeppJ
Ich benutze die Oracle Implementierung der Java Standardbibliothek. Dort wird eine Methode mit DoublePivotQuicksort im Namen aufgerufen. Vielleicht ist das eine Optimierung vom Quicksort oder einfach der Name der Methode.

@Benchmark
Das mag sein. Es ist aber womöglich ausgereifter, weil älter und der Wechsel von C++ ist sehr einfach, weil die Syntax sehr ähnlich ist.

Mechanics

Wär mir neu, dass D ausgereift sein soll.