Was ist schneller? Zuweisung oder Vergleich?

[Dirt Devil]

Hallo Leute,

wie schon im Titel dieses Threads genannt möchte ich gern wissen, was von dem Prozessor schneller abgearbeitet wird, Zuweisungen oder Vergleiche?
Ich möchte meine Programme nämlich so aufbauen, dass ich den Prozessor möglichst wenig auslaste, besonders bei Sortieralgorithmen, mit denen ich mich momentan beschäftige und bei denen Performance äußerst wichtig ist.

Ich bedanke mich schon mal für eure Antwort,
Dirt Devil

 

[SlaterB]

teste es doch einfach?
dürfte allerdings schwierig werden, vielleicht ist ja jeder Schleifenwechsel zigmal langsamer als ein Vergleich

ich glaube, auf der Ebene ist man in Java falsch,

was für ein Vergleich überhaupt? ein String oder noch komplexeres Objekt zu vergleichen ist schon was anderes als int == int

 

[Dirt Devil]

Das ist ja das Problem: Messen geht immer schlecht...sind ja noch zig andere Prozesse die im Hintergrund laufen...die einzige Methode wäre, zuweisungen und vergleiche zu zählen, aber dann kenn ich immernoch nicht den geschwindigkeitsunterschied.

Um unsere Werte sinnvoll zu vergleichen, müssen wir ja bei einem Datentyp bleiben, sonst wären die ergebnisse ja nicht korrekt. Mir geht es eher darum, wie der Prozessor Zuweisungen und Vergleiche abarbeitet...

Deshalb stelle ich meine Frage etwas genauer:
bool = true;
if(bool == true)
Was davon ist schneller??

 

[Marco13]

Auf jeden Fall würde man nicht
if (bool == true)
schreiben, sondern nur
if (bool)

Allerdings frage ich mich mehrere Dinge:
1. Warum testest du es nicht einfach?
2. Meinst du nicht, dass das auf veschiedenenen Prozessoren unterschiedlich ist?
3. Glaubst du, du könntest einen schnelleren Sortieralgorithmus entwickeln, als der von Collections.sort oder Arrays.sort?
4. Wie kannst du eine Zuweisung durch einen Vergleich "ersetzen"?

 

[Hilefoks]

Ich bin zwar nicht der Thread-Ersteller aber...

1. Warum testest du es nicht einfach?

Messen ist extrem kompliziert und fehleranfällig. Auch muss man die Messergebnisse richtig interpretieren und sicher stellen das keine Seiteneffekte das Messergebnis verfälschen. Im Allgemeinen gelingt dies nur mit erheblichen Kenntnissen der Materie.

2. Meinst du nicht, dass das auf veschiedenenen Prozessoren unterschiedlich ist?

Nicht unbedingt. Ein Beispiel: Die Shift-Operation ist auf allen Prozessoren schneller als eine arithmetische Berechnung. Allerdings sollte es keine Rolle spielen das der Programmierer in Java x*2 schreibt - den der Compiler (in anderen Fällen die Java-Runtime) kann dies optimieren. Durch die Java Runtime können hier erheblich mehr Optimierungen gemacht werden als bei klassischen Programmiersprachen. Auch kann dadurch für jeden Prozessor eine andere Optimierung gefunden und benutzt werden.

3. Glaubst du, du könntest einen schnelleren Sortieralgorithmus entwickeln, als der von Collections.sort oder Arrays.sort?

Ja. Die eingebauten Sortieralgorithmen sind nicht auf spezielle Bedürfnisse optimiert. Insbesondere wenn besonders große Datenmengen zu sortieren sind zeigen die eingebauten Sortierverfahren ein sehr schlechtes Laufzeitverhalten.

4. Wie kannst du eine Zuweisung durch einen Vergleich "ersetzen"?

Z.b. in dem man testet ob die Zuweisung nötig ist "if(b!=c) { b=c; }". Das das Sinn macht kann ich mir aber gerade nicht vorstellen. ;-)

MfG,
Hilefoks

 

[ice-breaker]

Zuweisungen sind schneller als Vergleiche
Du beschäftigst dich mit Sortieralgorithmen? Da haben doch schon schlaue Köpfe richtig gute Algorithmen (quickSort, HeapSort) die bewiesenermaßen die schnellsten Algorithmen sind

 

[para_]

4. Wie kannst du eine Zuweisung durch einen Vergleich "ersetzen"?

ersetzen vielleicht nicht, aber man kann den algorithmus ja so aufbauen dass er entsprechend weniger vergleiche oder weniger zuweisungen braucht (also das verhältnis sich ändert)

 

[SlaterB]

> die bewiesenermaßen die schnellsten Algorithmen sind

nur unter allgemeinen Annahmen,
wenn man dagegen bestimmte Randbedinungen bzl. Verteilung der Werte oder auch Aufwand des Vergleichs untereinander/ Aufwand des Ladens usw hat,
kann es ja ganz anders aussehen,

und selbst dann muss man ja nicht unbedingt vom besten Verfahren (MergeSort! ) abweichen,
sondern es vielleicht nur an bestimmten Stellen modifizieren

 

[SnooP]

nein - CountingSort ist am Besten!

 

[Dirt Devil]

Danke Hilefoks, du bringst mein Gedanken genau auf den Punkt.

Ich habe im Internet noch fleissig recherchiert und bin zu dem Punkt gekommen, dass Vergleiche prinzipiell schneller ablaufen als Zuweisungen.
Beispiel mit Langzahlen: Zuweisungen hängen nämlich immer linear vom Wert ab. Vergleiche allerdings prüfen nur anhand der ersten Stelle eines Wertes; und wenn die gleich sind, rückt er eine Stelle weiter. Also kann ein Vergleich in den meisten Fällen sehr schnell verlaufen, wenn anhand der ersten Ziffer schon erkannt werden kann, ob eine Zahl größer/kleiner/gleich ist, sonst ist er allerdings auch ,im schlechtesten Fall (wenn die Zahlen also gleich sind), linear vom Wert abhängig. (Quelle: www.ma.tum.de/~kaplan/ca/spock/praktika/UrSpock/node87.html )

Ich hoffe das stimmt, was ich da zusammengetragen habe :bae:
Noch besser wäre es, wenn man wissen würde, wie der Prozessor Vergleiche und Zuweisungen abarbeiten würde (also in Assembler)

MfG,
Dirt Devil

 

[SlaterB]

falls du dich nur auf die allgemeine Logik beziehst, muss dies nicht unbedingt stimmen,

böses Beispiel:
die Zuweisung mag vielleicht von der Länge abhängen,
dauert aber nur 1-9 Zeiteinheiten für Länge 1-9

dagegen ist der Vergleich zwar schon nach einer Ziffer fertig,
dieser Vergleich der ersten Ziffer dauert aber bereits 300 Zeiteinheiten,

daher: früher Abbruch ist immer gut, ganz ohne absolute Zahlen aber recht nutzlos

 

[Ralf W. Balz]

Hallo,

Noch besser wäre es, wenn man wissen würde, wie der Prozessor Vergleiche und Zuweisungen abarbeiten würde (also in Assembler)

*InTiefVergrabenerErinnerungStaubigenBüchernHüstel* in Assembler gibt es verschiedene Vergleichsbefehle CMP CMPS, CMPSB und und und. CMP zum Beispiel ist ein arithmetischer Vergleichsbefehl, der kurz gesagt zwei Werte von einander abzieht, man kann dann die verschieden Flags wie das Carry-Flag, Zero-Flag, Overflow-Flag.... auswerten, für das was man gerade braucht. Beispiel: wenn das Zero-Flag gesetzt ist, so ist das Ergebnis der Subtraktion 0, somit besteht Gleichheit der Werte. Oder das Parity-Flag ist gesetzt, das Ergebnis ist eine gerade Anzahl von Bits und und und. Wie gesagt, es gibt verschiedene Vergleichsbefehle die auch anders arbeiten und verschieden lang brauchen.

Was ich damit sagen möchte ist, dass man auch mit dem Wissen, wie das im Assembler geht, deine Frage meiner Meinung nach nicht genauer beantworten kann, weil ja nun noch Java dazwischen liegt und ein Betriebssystem, mit dem Java ja auch kooperieren muss *wegduck*, wie auch immer.

Ich denke, die Zeit messen für jedes Sortierverfahren auf ähnlichen Daten, die du sortieren möchtest, und das mehrmals und einen Mittelwert bilden ist das beste, wie man an ein brauchbares Ergebnis kommt bzw. herausfindet, welcher Sortieralgorithmus für diese Aufgabe der schnellste ist.

Grüße Ralf

 

[Ice-Tea]

Ich vertraue mal meinem halbwissen und erhebe auch mal das Wort.

Ich kann mir kaum vorstellen, das ein vergleich schneller ist als eine Zuwesung.
Vorallen bei Datenmengen, die nicht in den L2 Cache der CPU passen- wovon ich ausgehe...

Immerhin müssen bei Vergleichen min. 2 Daten aus dem Arbeitsspeicher gelesen werden und zusätzlich verglichen werden. Das ergebniss muss danach im Speicher auch wieder abgelegt werden.

Bei einer zuweisung wird allerdings nur ein Datentranfer von der CPU zum Speicher gebraucht. OK, Generell ist speichern langsamer als lesen, aber müssen wie gesagt min. 2 Daten gelesen werden.

Ich denke, dass das sehr Platformabhäghig ist. Der beste Algorythmus bring nichts wenn die Hardware es nicht richtig umsetzen kann...

PS: Am einfachsten ist es, einen neuen T2 von SUN zu erwerben, dann ist Algorythmus nur noch zweitrangig *joke*
PSS: Wenn es wirklich so kritisch ist, dann selbst Assamblen...

@Dirk Devil: Kommt auf die länge der vergleiche an und in wie weit man davon ausgehen kann das die werte Identisch, bzw. nicht idertisch sind. Sollte sich in vielen fällen nur die letzte Ziffer ändern, könnte es durchaus sehr langsam werden.

 

[Guest]

Zum Thema Performance:

It works, it run, it fast.

Sprich zuerst entwickeln, dann mal schauen ob Performance ausreicht, wenn nicht ueber neue Hardware nachdenken, wenn das nicht hilft ueber Codeoptimierung nachdenken (z.B Caching, etc.).. Spaetestens dann sollten alle Probleme weg sein ausser bei RealTime Anwendungen vielleicht...

Sprich schreib bloss nicht son scheiss wie

if (a!=b) {
    a=b
}

Denn dass kann doch kein schwein mehr lesen. Der Programmcode ist die Schnittstelle zum Menschen NICHT zur Machine....

 

[para_]

Sprich zuerst entwickeln, dann mal schauen ob Performance ausreicht, wenn nicht ueber neue Hardware nachdenken, wenn das nicht hilft ueber Codeoptimierung nachdenken (z.B Caching, etc.)..

Ich hoffe doch das ist nicht ernst gemeint... ???:L :?

 

[Dirt Devil]

@para: Hoff ich auch hehe:

@Ice-Tea: Deine Argumentation klingt für mich bisher am schlüssigsten. Ich denke, ich werde dies erst mal so übernehmen.

 

[schalentier]

It works, it run, it fast.

Recht hat er! Ein schneller, fehlerhafter Algorithmus ist tausend Mal schlechter, als ein langsamerer dafuer fehlerfreier und wartbarer.

Zum Testen: Schreib den Algo doch in 2 Versionen, einmal mit Vergleichen, einmal mit Zuweisungen (wie auch immer) und vergleich dann die Performance. Nimm am besten ein Profiler.
Aber ganz im Ernst, ich glaub kaum, dass du mit Vergleich/Zuweisung in Java irgendwas rausholen kannst. Viel wichtiger sind da die ueblichen Performancebremsen (Strings, ueberfluessige new XYZ(), unnoetige BigInteger, etc.).

Demnach sagt der Satz da oben nur, mach zuerst dein Algo fertig, so dass er funktioniert, weil der Code einfach, lesbar und wartbar ist. Danach kannste optimieren, wobei wenns wirklich auf die letzten 5% ankommt, sicher C/ASM die bessere Wahl waere.

 

[Saxony]

[...]wenn nicht ueber neue Hardware nachdenken[...]

Hehe der Nichtschwimmer schiebt es auch immer auf die Badehose.

Naja in ASM würde ich entweder CMP oder XOR für Vergleiche verwenden.

XOR ax, bx
jnz ungleich // jump not zero
    hier gehts weiter wenn se gleich sind
jmp weitergehts
ungleich :
    mache irgendwas bei Ungleichheit
weitergehts :
    weiter im programm

Zuweisungen kommen dagegen ohne bedingte und unbedingte Sprünge aus

mov ax, bx

und müssten auf Maschinenebene ein paar Takte schneller sein.

In wie weit sich das alles auf komplexe Objekte ein paar Level nach oben auf Java übertragen lässt, bleibt allerdings offen.

bye Saxony

 

[happy_robot]

[...]wenn nicht ueber neue Hardware nachdenken[...]

Hehe der Nichtschwimmer schiebt es auch immer auf die Badehose.

Naja in ASM würde ich entweder CMP oder XOR für Vergleiche verwenden.

XOR ax, bx
jnz ungleich // jump not zero
    hier gehts weiter wenn se gleich sind
jmp weitergehts
ungleich :
    mache irgendwas bei Ungleichheit
weitergehts :
    weiter im programm

Zuweisungen kommen dagegen ohne bedingte und unbedingte Sprünge aus

mov ax, bx

und müssten auf Maschinenebene ein paar Takte schneller sein.

In wie weit sich das alles auf komplexe Objekte ein paar Level nach oben auf Java übertragen lässt, bleibt allerdings offen.

bye Saxony

leider nicht ganz richtig ....

ein

mov ax,bx

entspricht wohl kaum einer zuweisung im gemeinten sinne. das würde nur stimmen wenn alle werte grundsätzlich in registern gehalten werden, was durch deren beschränktes vorkommen wohl auszuschliessen ist. . :lol:

bei einem vergleich werden eventuell mehrere 8- bis 64-bit - werte zwischen verschiedenen segmenten hin- und her transferiert. das dauert deutlich länger als ein XOR und der sprung mit jnz oder jne (hier gibts sogar minimale laufzeitunterschiede zwischen je und jne!)

ich vermute daß man davon ausgehen kann daß der vergleich schneller ist, da dort die wahrscheinlichkeit grösser ist daß zumindest einer der zu vergleichenden werte in einem register vorliegt. bei einer zuweisung kann man sich fast sicher sein daß dies nicht der fall ist, da diese in der regel im SS, DS oder ES gehalten werden. Bei einem Clone von grossen Datenmengen kommt dann wahrscheinlich zu Verschiebungen vom DS nach ES...und das ist nicht sonderlich performant gegenüber einem Vergleich.

mfg