Tausch (Assembler, Kopien auf Stack, Zeiger, Referenzen)

[Helium]

Du meinst die einzig sinnvolle: std::swap? Das ist ja einfach unglaublich.

Wenn man ein swap braucht verwendet man std::swap und wenn's schnell sein muss und keine Rücksicht auf Portabilität gelegt wird, vielleicht auch Assembler, aber alles andere ist Humbug. Also: verwende Dinge, die auch Sinn machen und nicht irgendwas, was sowieso niemand braucht. Und dein Assemblerbeispiel ist hundsmiserabel (siehe Bashars Post).

[entelechie]

also ich finde das tauschen mit zeigern und referenzen fuer einsteiger
interessant und wichtig. das hilft beim verstaendnis; anstatt nur irgendeine
funktion stupide aufzurufen und nicht zu wissen was dahinter steckt.

[Knuddlbaer]

Die Weicheier werden aber immer schneller damit fertig sein ihren Code auf ein anderes System zu Portieren wie die Freestyle Programmierer ;o)

Es ist im übrigen keine Scheu davor. Vielmehr ist es eine wirtschaftliche Überlegung: Knall ich da nun Assemblersource rein (wobei ich dann vllt. erst mal das Assembler lernen muss) oder überlasse ich es dem Compiler z.B. std::swap umzusetzen und nehme dabei vllt. ein klein wenig Laufzeitverlust hin ?

Betrachtet man dazu das man eventuell mal auf eine andere Plattform portieren will wäre eine Möglichkeit noch einen Profiler zu befragen ob es sinn macht den Quellcode einer starken Abhängigkeit auszusetzen.

[Shade Of Mine]

Knuddlbaer schrieb:

Es ist im übrigen keine Scheu davor. Vielmehr ist es eine wirtschaftliche Überlegung: Knall ich da nun Assemblersource rein (wobei ich dann vllt. erst mal das Assembler lernen muss) oder überlasse ich es dem Compiler z.B. std::swap umzusetzen und nehme dabei vllt. ein klein wenig Laufzeitverlust hin ?

wenn std::swap() fuer builtins nicht spezialisiert ist - wuerde ich nur diese spezialisierungen ergaenzen (und da xchg verwenden) - so kann man immer std::swap() verwenden und sich sicher sein, dass es sau schnell ist.

man beachte nur die laufzeit von

string s1("hallo du schoene grosse tolle coole einmalige welt");
string s2("!");

//teuer:
string t(s1);
s1=s2;
s2=t;

//billig:
swap(s1,s2);

//denn swap macht einfach
s1.swap(s2);
//und das kostet vielleicht 3 xchg

Templates sind geil.

[Helium]

Es geht doch offenbar nicht darum zu zeigen, auf welche weise man Variablen übergeben kann, da das Assemblerbeispiel dann nicht passt. Also scheint es darum zu gehen, wie man Variablen tauscht. Aber wieso werden dann Möglichkeiten gezeigt, die sich nur in der Übergabe unterschieden?

An deiner Didaktik musst du noch etwas feilen.

[Erhard Henkes]

Schaut euch zu diesem Thema mal Lektion 33 - 37 bei Volkard an. Der findet sogar die swap-Funktion mit den Referenzen als Parameter nicht gut, da sich a und b verändern, nur weil man sie einer Funktion übergeben hat. Ich meine, man sollte alles zeigen, dabei für die einzelnen Methoden die Themen Portabilität und Performance diskutieren. Assembler ist bezüglich Portabilität absolut problematisch (AT&T-, Intel-Syntax).

[Bashar]

Ich habe keine Scheu vor Assembler, und habe auch nichts bezüglich Portabilität gesagt. Ich sage, dass das Beispiel mit Assembler keinen didaktischen Wert hat: Ein Einsteiger wär gut beraten, da einfach drüberzulesen, und dann kannstes auch gleich weglassen. Mit Hardcore-C++ hat das nichts zu tun, schon allein weil das Beispiel so mies ist. Das schlimme ist, dass jemand, der in diesem Gebiet eher unbeleckt ist, glauben könnte, die Assembler-Lösung sei die schnellste und daher vorzuziehen.

[Walli]

EDIT: Einiges davon hatte Bashar schon erwähnt...
Das Problem ist, dass sich Anfänger auf diese Weise von vorne herein an umständliche Sachen gewöhnen könnten. Vor 2 Jahren hätte ich Erhards Code gelesen und mir gedacht: "Geil, Assembler. Sieht ja voll kompliziert aus. Dann ist es bestimmt auch schneller als das popelige swap!". Überzeugt davon das Richtige zu tun hätte ich es in vieele vieeele Programme eingebaut und würde mich heute totärgern weil ich solch einen Mist in meinen alten Sourcen rumgammeln habe aber nicht die Zeit finde es auszubessern. Ich denke man sollte in normalen Anwendungen komplett auf Assembler verzichten. Sicher, ich hatte auch schonmal einen dieser Fälle in denen ein wenig inline-asm Wunder wirkte war mir aber auch im klaren darüber was ich machte und versuchte diese Stelle so isoliert wie möglich zu halten damit ich bei der Portierung mit ein paar ifdefs (also quasi mit blauen Flecken) davonkommen könnte. Wenn man so versessen auf "Hardcoreprogrammierung" ist sollte man bei seinem TASM bleiben und C++ den "Weicheiern" überlassen.

[elise]

die darstellung von
call by value
und
call by reference

ist ein typisches lehrbeispiel, soll übrigens nicht "std::swap" ersetzen ;), sondern muss zwischen dem erlernen von zeigern und referenzen und klassen angesiedelt werden, um zu zeigen, daß es billiger ist, mit referenzen objekte zu übergeben, als per wert.

und natürlich auch: was passiert da. (mal wieder im speicher rumkriechen, ein wenig den überblick kriegen, zeiger festigen...)

assembler gehört da nicht rein. ! ausrufungszeichen.
entweder ich unterrichte c++ oder ich unterrichte assembler.

um assemblercode einzubinden, hätte ich den anspruch, daß die leute wissen was sie tun, wäre dann was für "c++ für leute mit assemblervorkenntnissen".

aber an der stelle vollkommen unbrauchbar.

[Erhard Henkes]

o.k., überzeugt. Assembler bleibt weg. XCHG würde die Sache auch nicht verbessern, da man hierbei ebenfalls über die Register (die man eigentlich vorher pushen und nachher poppen müsste) gehen muss. Die STL-Methode std::swap gehört selbstverständlich dazu und ist die Methode der Wahl.

Wäre das so akzeptabel?

#include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

//globale Variablen
int a = 1; 
int b = 2;

void ausgabe()
{
    cout << &a << ": " << a << "\t " << &b << ": " << b  << endl << endl;
}

void erfolgloser_swap(int x, int y)
{
  cout << endl << "Kopien auf dem Stack: " << endl;
  cout << &x << ": " << x << "\t " << &y << ": " << y << endl;

  int temp = x;
  x = y;
  y = temp;

  cout << &x << ": " << x << "\t " << &y << ": " << y << endl;
  cout <<  endl;
}

void zeiger_swap(int* x, int* y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

void referenzen_swap(int& x, int& y)
{
  int temp = x;
  x = y;
  y = temp;
}

int main()
{ 
    cout << "Ausgangssituation: " << endl;
    ausgabe();

    cout << "Tausch mittels std::swap(x,y): " << endl;            
    std::swap(a,b); // Methode der Wahl aus der STL
    ausgabe();

    cout << "Tausch mittels Referenzen: " << endl;            
    referenzen_swap(a,b);
    ausgabe();

    cout << "Tausch mittels Zeiger: " << endl;            
    zeiger_swap(&a, &b);
    ausgabe();

    cout << "Erfolgloser Tausch, da nur lokale Kopien getauscht werden:" << endl;            
    erfolgloser_swap(a,b);
    ausgabe();

    getch();
}

[Shade Of Mine]

jetzt stoeren nur noch die funktion ausgabe() und die globalen variablen.

[Erhard Henkes]

Mir hat das mit den globalen Variablen gut gefallen, da man dann den Unterschied bezüglich Speicheradresse leichter erkennt (global/lokal).
Aber das geht auch anders, man kann ja beides zeigen:

#include <iostream>
#include <conio.h>
using std::cout;
using std::endl;

void ausgabe(int x, int y)
{
    cout << &x << ": " << x << "\t " << &y << ": " << y  << endl << endl;
}

void erfolgloser_swap(int x, int y)
{
  cout << endl << "Kopien auf dem Stack: " << endl;
  ausgabe(x,y);

  int temp = x;
  x = y;
  y = temp;

  ausgabe(x,y);
  cout <<  endl;
}

void zeiger_swap(int* x, int* y)
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

void referenzen_swap(int& x, int& y)
{
  int temp = x;
  x = y;
  y = temp;
}

void referenzen_swap_Variante(int& x, int& y)  
{  
  x^=y;  
  y^=x;  
  x^=y;  
} 

int main()
{ 
    //lokale Variablen
    int a = 1; 
    int b = 2;

    cout << "Ausgangssituation: " << endl;
    ausgabe(a,b);

    cout << "Tausch mittels std::swap(x,y): " << endl;            
    std::swap(a,b); // Methode der Wahl aus der STL
    ausgabe(a,b);

    cout << "Tausch mittels Referenzen: " << endl;            
    referenzen_swap(a,b);
    ausgabe(a,b);

    cout << "Tausch mittels Referenzen (Variante): " << endl;            
    referenzen_swap_Variante(a,b);
    ausgabe(a,b);

    cout << "Tausch mittels Zeiger: " << endl;            
    zeiger_swap(&a, &b);
    ausgabe(a,b);

    cout << "Erfolgloser Tausch, da nur lokale Kopien getauscht werden:" << endl;            
    erfolgloser_swap(a,b);
    ausgabe(a,b);

    getch();
}

referenzen_swap_Variante(...) ist ein Vorschlag von HumeSikkins (s.u.).

[HumeSikkins]

Hallo,
warum zeigt man Anfängern eigentlich nur den Dreieckstausch? Eine so schöne Situation würde ich nicht verstreichen lassen und gleich boolesche Logik (oder heißt das dann Algebra?) motivieren. Schließlich muss das sowieso *jeder* Programmierer können.

[Shade Of Mine]

HumeSikkins schrieb:

Eine so schöne Situation würde ich nicht verstreichen lassen und gleich boolesche Logik (oder heißt das dann Algebra?) motivieren. Schließlich muss das sowieso *jeder* Programmierer können.

aeh... was meinst du?

[HumeSikkins]

void swap(int& a, int& b)
{
a^=b;
b^=a;
a^=b;
}

[Erhard Henkes]

Danke! Sehr gute Idee. Ich habe es gleich oben in den Code editiert. Da kann es gleich jeder ausprobieren.
Jetzt fehlt eigentlich nur noch ein Geschwindigkeitsvergleich aller Methoden (da nehmen wir Assembler testweise wieder mit ins Boot!), z.B. jeweils x Mio. Tauschoperationen. Frage: was sollte bei Massenanwendung der schnellste Algo sein? Setzt ihr auf std::swap(x,y) ?

Verloren! std::swap(x,y) ist hinter meiner "ach so miesen" Assemblervariante. Mit xchg war es deutlich langsamer, mov ist besser. Zur Zeitmessung bin ich wegen der Assembler-Variante auf globale Variablen umgestiegen. HumeSikkins boolsche-Tauschvariante ist leider langsamer als der Dreieckstausch. Sieht man von Assembler ab, so ist std::swap(...) vergleichbar schnell wie die eigene Zeiger- oder Referenz-Variante.

Ergebnis: (60000000 Aufrufe)
1. Assembler (die obige mov-Variante) 2.6 sec
2. std::swap(...) 2.9 sec
3. ref und zeiger (fast gleich) 2.9 sec
4. ref (boolsche Variante) // Schönheit siegt nicht immer. 3.2 sec

(gerundete Mittelwerte aus Messungen)

[davie]

std::iter_swap nicht vergessen

[elise]

Erhard Henkes schrieb:

Verloren! std::swap(x,y) ist hinter meiner "ach so miesen" Assemblervariante. Mit xchg war es deutlich langsamer, mov ist besser. Zur Zeitmessung bin ich wegen der Assembler-Variante auf globale Variablen umgestiegen. HumeSikkins boolsche-Tauschvariante ist leider langsamer als der Dreieckstausch. Sieht man von Assembler ab, so ist std::swap(...) vergleichbar schnell wie die eigene Zeiger- oder Referenz-Variante.

Ergebnis: (60000000 Aufrufe)
1. Assembler (die obige mov-Variante) 2.6 sec
2. std::swap(...) 2.9 sec
3. ref und zeiger (fast gleich) 2.9 sec
4. ref (boolsche Variante) // Schönheit siegt nicht immer. 3.2 sec

(gerundete Mittelwerte aus Messungen)

hallo??

ich dachte, dir geht es hier darum, deinen schülerInnen didaktisch aufbereitet c++ zu unterrichten, und nicht, um geschwindigkeitshöchstgrenzen zu überschreiten.
dann nimm gleich assembler pur, und lass c++ oder code in maschinensprache.

die einheit call by value, call by reference soll was erklären. eigentlich die wichtige einheit, die funktionsweise von referencen (und zeigern) zu erläutern.

humes idee finde ich darüber hinaus witzig, da schlägt man zwei fliegen mit einer klappe und zeigt mal eine nette anwendungsmöglichkeit von xor.

hat didaktischen, nicht real life progger sinn.

beim unterrichten muss man manchmal schritte gehen, hinführen.. bis man dann wo angelangt ist, und da sind auch oft nicht ganz optimierte lösungen dabei, aber es geht ums lernen.
in der schule fängt man ja auch nicht gleich mit integralrechnung in der ersten klasse an, oder hat einer von euch das äpfel rechnen übersprungen?

[.b7f7]

der XOR swap kommt ohne temp-variable aus und deswegen ist er so "cool"

[Helium]

Ich fand den auch mal "Cool", aber da war ich 15 und hab in Basic programmiert. Na egal.