c++ Laufzeitsenken finden/vermeiden erster Teil

[Clemens M. (panko)]

Ich habe begonnen, mich mit c++ zu beschäftigen.Das steckt im 
Anfangsstadium von daher ist es nicht unwahrscheinlich, daß mir einige 
dämliche Fehler passieren bzw. "brain bugs" vorliegen. Da bitte ich um 
Nachsicht...

Meine Frage hier dreht sich um Experimente bzgl. Laufzeitvergleichen. 
Ich habe ja keine Ahnung bzgl. Klassen, daher kann ich auch gar nicht 
einschätzen ob/wann die Verwendung (unnötig) langsam wird und was man 
evtl. dagegen tun kann. Erscheint mir aber von Beginn an, ein ganz 
wichtiger Aspekt zu sein, den ich immer im Hinterkopf haben möchte. Sich 
in verschachtelten Klassen zu verzetteln will ich später nicht.

Ich habe begonnen etwas zu experimentieren.
Also in einer verketteten Liste 20 Elemente angelegen und recht oft 
suchen. Dabei habe ich eine rudimentäre Verkettung als quasi c-funktion 
mit der stl Lösung 'map' vergleichen. Dabei dann auch noch eine 
map<string,int> und eine map<char*, int>
(Auf die STL libraries bin ich recht schnell gestoßen und bin an sich 
begeistert - wenn nicht das folgende Fragezeichen wäre.... )
Ich stelle einen ziemlich erheblichen Laufzeitunterschied fest bei der 
stl Variante. Und zwar ist die map<string, int> noch mal eine Ecke 
länger beschäftigt, als char*...warum das?
Muss ich die map anders benutzen? Habe ich etwas grundsätzlich nicht 
verstanden, oder würde das so gar nciht funktionieren wenn ich echt 
Daten verwalte?
Denn wenn ich mir vorstelle, daß ich Daten verwende und das ist so viel 
langsamer mit einer map Lösung, dann ist das direkt unattraktiv, oder?

(Auf die leichte Art der Zeitmessung wurde ich 
http://cplus.kompf.de/artikel/perfmess.html hier aufmerksam)

struct list{
  char* bez;
  struct list* next;
  int  val;
};

char *names[]={"bla01","bla02","bla03","bla04","bla05","bla06","bla07","bla08","bla09","bla10",
         "bla11","bla12","bla13","bla14","bla15","bla16","bla17","bla18","bla19","bla20"};

list* lst = 0;

list* find(char* s)
{
  list* pl = lst;

  for(; pl; pl=pl->next)
    if(strcmp(s, pl->bez)==0 ) return pl;
  return 0;
}

list* add(char* s)
{
  list* pl = lst;

  for(; pl; pl=pl->next)
    if(strcmp(s, pl->bez)==0 ) return pl;
  list* pll = new list;
  pll->bez  = new char[sizeof(s)+1];
  strcpy(pll->bez, s);
  pll->val  = 4711;
  pll->next = lst;
  lst = pll;
  return pll;
}

int main(void)
{
  list* pl;
  map<string, int> str_map;
  map<char* , int> chr_map;


  //dauert so 0.3 Sekunden
  {
  timer t(0);
  for(int m=0; m<100000; m++)
  for(int n=0; n<(sizeof(names)/sizeof(names[0])); n++)
  {
    if( !(pl=find(names[n])) )     
      pl = add(names[n]);
    pl->val = 42;
  }
  }

  //dauert so 4.irgendwas Sekunden
  {
  timer t(2);
  for(int m=0; m<100000; m++)
  for(int n=0; n<(sizeof(names)/sizeof(names[0])); n++)
  {
    chr_map[names[n]] = 0;
  }
  }

  //dauert so 13 Sekunden
  {
  timer t(1);
  for(int m=0; m<100000; m++)
  for(int n=0; n<(sizeof(names)/sizeof(names[0])); n++)
  {
    str_map[names[n]] = 0;
  }
  }
}

[Peter (Gast)]

erstmal eine Frage (habe den code noch nicht genau durchgesehen) - Hast 
du die optimierung eingeschatet! Die Templates ohne optimierung sind 
langsam.

[Clemens M. (panko)]

Nein, vrsuch ich aber mal, denn wenn ich eine Optimierung einschalte 
bekomme ich die Fehlermeldung:1 >cl : Befehlszeile error D8016: Die 
Befehlszeilenoptionen /ZI und /O2 sind inkompatibel.

Da muss ich also erst mal da nach suchen :-(

Aber gut zu wissen schon mal, danke

[Karl H. (kbuchegg)]

Clemens M. schrieb:

> Meine Frage hier dreht sich um Experimente bzgl. Laufzeitvergleichen.
> Ich habe ja keine Ahnung bzgl. Klassen, daher kann ich auch gar nicht
> einschätzen ob/wann die Verwendung (unnötig) langsam wird und was man
> evtl. dagegen tun kann.

Das ist nur die 'halbe' Miete.
Denn die restlichen 2/3 der Miete bestehen aus der Fragestellung: Wie 
helfen mir Klassen, meinen Code korrekt zu machen.


> Ich habe begonnen etwas zu experimentieren.
> Also in einer verketteten Liste 20 Elemente angelegen und recht oft
> suchen. Dabei habe ich eine rudimentäre Verkettung als quasi c-funktion
> mit der stl Lösung 'map' vergleichen.

und hier vergleichst du dann schon Äpfel mit Birnen.

> Dabei dann auch noch eine
> map<string,int> und eine map<char*, int>

Das sind aber auch 2 verschiedene Dinge.
Ein string Objekt passt auf seinen Speicher auf. Erzeugst du eine Kopie 
eines Objektes so handhabt das das String Objekt eigenständig. Mit einem 
char* passiert das aber nicht. Ergänzt du diese Behandlung, bist du 
wieder dort, wo du auch mit string bist. Sowohl was Funktionalität, als 
auch Korrektheit als auch Leufzeit bedeutet.

> stl Variante. Und zwar ist die map<string, int> noch mal eine Ecke
> länger beschäftigt, als char*...warum das?

Weil beim Einstellen eines Textes in die map ein String Objekt erzeugt 
wird, welches dann das Kommando über den Speicher hat, in dem es den 
Text speichert. Eine map basierend auf char* tut das naturgemäss nicht.

[Clemens M. (panko)]

Das ist mir an sich schon klar - einen Performanceverlust ist in 
Abwägung der Vorteile auch sicher das kleinere Übel, aber ich find 
Faktoren von über 40 bzgl. zwischen char* und str von 3 sind schon 
heftig.
Wobei ich da zugeben muss - der von dir beschriebene Verwaltungsaufwand 
Faktor 3 bedeuten könnte. Aber 40?

Ich bekomm die Optimierungen leider noch nciht fehlerfrei an ;-) Wenn 
ich das habe berichte ich mal - es sei denn jemand kann mit der 
Fehlermeldung ad hoc was anfangen.


@Karl Heinz: Würdest du mir denn so weit den Rücken stärken, daß blinder 
Einsatz von wild veschachtelten Klassen auch nicht der richtige Weg ist. 
Vor allem wenn man gar nicht genau weiß, WAS denn eigenltich passieren 
könnte, man es folglich richtig daneben programmieren kann?

[Edding (Gast)]

Karl heinz Buchegger schrieb:
>> stl Variante. Und zwar ist die map<string, int> noch mal eine Ecke
>> länger beschäftigt, als char*...warum das?
>
> Weil beim Einstellen eines Textes in die map ein String Objekt erzeugt
> wird, welches dann das Kommando über den Speicher hat, in dem es den
> Text speichert. Eine map basierend auf char* tut das naturgemäss nicht.

Ausserdem:
die Map ist ein Binärbaum.

Beim Einfügen müssen also viele (naja, log2(n)) Vergleiche durchgeführt 
werden.

Die Char*-Map vergleicht dabei die Speicheradressen! Nicht den 
Stringinhalt!

d.H. das sind immer 4 (oder 8) Bytes zu vergleichen, passt in ein 
Register, braucht einen Opcode.

Die String-Map vergleicht den tatsächlichen Text.

Deswegen ist die string-map nachher alphabetisch sortiert, die char-map 
ist nach den Speicheradressen sortiert.

Daraus ergibt sich auch dass die die chr-map-"Aufräum"-Schleife 
(vorletzte) Überhaupt nicht das tut, was du denkst!

[Karl H. (kbuchegg)]

Clemens M. schrieb:
> Das ist mir an sich schon klar - einen Performanceverlust ist in
> Abwägung der Vorteile auch sicher das kleinere Übel, aber ich find
> Faktoren von über 40 bzgl. zwischen char* und str von 3 sind schon
> heftig.
> Wobei ich da zugeben muss - der von dir beschriebene Verwaltungsaufwand
> Faktor 3 bedeuten könnte. Aber 40?

Die aktuellen Zahlen sind bei mir (Optimizer eingeschaltet) mit VS2005

timer 0 took 0.113 seconds
timer 2 took 0.055 seconds
timer 1 took 0.396 seconds

d.h. die char* map war am schnellsten.
deine list Lösung ungefähr doppelt so langsam
und die String map ca 3. mal so langsam wie deine Liste.

Wenn man allerdings bedenkt, dass eine map keine Liste ist (das wirst du 
spätestens beim Suchen merken), ist das gar kein schlechtes Ergebnis

[Clemens M. (panko)]

Weil ich die Fehlermeldung so nicht in den Griff bekomme, habe ich mal 
auf Release umgeschaltet in der Hoffnung, daß da dann intern 'schon was' 
konfiguriert wird.... und meine Herren.

0.156s - eigenes gefrickel
0.063s - char* map
0.218s - string map

Erstaunlich zum einen WIE schnell die char map wird und zum anderen 
spricht da auch nichts gegen die String Sicherheit. Definiv nicht...




Frage nur nach der blöden Meckerei wegen Kommandozeile ZI und O2 passt 
nicht....

[Karl H. (kbuchegg)]

Edding schrieb:

> Die String-Map vergleicht den tatsächlichen Text.
>
> Deswegen ist die string-map nachher alphabetisch sortiert, die char-map
> ist nach den Speicheradressen sortiert.

Exakt.
Das wird dann besonders lustig, wenn nach Texten gesucht wird, die nicht 
so wie hier in einem vordefinierten Array vorliegen und sich daher in 
der Adresslage nicht ändern sondern zb vom Benutzer eingegeben werden 
:-)

[Edding (Gast)]

Clemens M. schrieb:
> Erstaunlich zum einen WIE schnell die char map wird und zum anderen
> spricht da auch nichts gegen die String Sicherheit. Definiv nicht...

Mach mal statt 20 Einträge in Liste/Map lieber so 2000. Und Staune.

Und lass die char-Map weg, die funktioniert so nicht. (siehe oben, 
Vergleich der Pointer-Adressen statt des Textes)

[Clemens M. (panko)]

Ich danke euch vielmals. Mühsam ernährt sich das Eichhörnchen.

edit: ich hab schon bei 50 gestaunt :-o

[Karl H. (kbuchegg)]

Clemens M. schrieb:

> Frage nur nach der blöden Meckerei wegen Kommandozeile ZI und O2 passt
> nicht....

Mit 'Optimizer einschalten' ist im Visual Studio normalerweise immer das 
Umschalten auf 'Release' gemeint.

[Klaus W. (mfgkw)]

Nur am Rande:
Die Container in der STL arbeiten immer mit Kopien der übergebenen
Daten, deshalb ist nicht nur der Vergleich langsamer, sondern
schon das Einfügen.
Auch deshalb ist ein Vergleich std::string mit char* nicht
sinnvoll.
Realistisch wäre ein Vergleich char* gegen std::string*.

[IsobarX (Gast)]

Hallo Clemens,

anhand des Topics (Betonung auf Laufzeit) vermute ich, dass Du das STL 
Feature in Mikrocontrollern einsetzen möchtest. Da dieses Feature sehr 
resourcenhungrig ist, kann ich Dir den Einsatz von STL nicht empfehlen. 
Auch die dynamische Speicherverwaltung ist ein Performancekiller und 
deren Nutzen im uC-Bereich mit seinen mickrigen 6Kbs RAM nicht 
erkennbar.
Vererbung und Polymorphie, also das hantieren von Klassen (=Strukturen 
mit Kapselung), würde ich möglichst vermeiden (Overhead).


Was ich momentan in C++ verwende sind folgende Features:

- Klassen (enstpräche in C: Strukturen mit Kapselung) mit Kon-& 
Destruktor
- Instanzieren (z.B. Einsatz von 2 LCDs)
- virtuelle Methoden/Klassen (nicht übertreiben, sonst Overhead)
- Namensräume
- Funktionsüberladung
- Referenzen und Alias (mit Alias kann man sich viele Variablen 
einsparen und trotzdem einen Übersichtlichen Code schreiben)
- Templates

Mein Tipp fürs Programmieren: Die Verwendung des Typs "CONS" (bei 
Deklaration oder Werteübergabe). Das erspart einem einige Fehler beim 
Kompilieren.

MfG
IsobarX

[IsobarX (Gast)]

Nachtrag:

ich meine Fehler im Programmverhalten (meine nicht syntaktische Fehler) 
vermeiden(würde man beim Kompilieren sehen, insbesondere bei Verwendung 
von Referenzen, die man bei der Funktionsübergabe schützen möchte).

MfG
IsobarX