Geschwindigkeit rekursiver Funktionen mit und ohne STL

Besten Dank, vielleicht bringts im Detail der Code.
Unterschied bleibt in Geschwindigkeit bleibt bestehen, nach zahlreichen
weiteren Untersuchungen.

Der einzige Unterschied ist in den Speicheraufrufen meiner Meinung
nach.

Wieso ist STL so langsam?

struct value
{
long valueinfo;
};

struct valuelist
{
long valuecount;
value values [200];

};

void recursivenormal (signed long flag, long depth, long maxdepth)
{
valuelist pmlist;
long start,end,anzahl,wert,empty;
long* pointer;
if (depth==maxdepth) {
return;
};
if (flag==1) {
depth+=1;
genwvalues();
pointer=&values;
start=long(pointer);
end=valuesoffset;
anzahl=(end-start)/8;
pmlist.valuecount=anzahl;
for (long i=1; i<=anzahl; i++)
{
wert=*pointer;
pointer=pointer+1;
pmlist.values[i].valueinfo=wert;
}
for (long i=1; i<=anzahl; i++)
{
pmlist.values[i]=executewvalue(pmlist.values[i]);
flag=-1;
perftnormal(flag,depth,maxdepth);
undowvalue(pmlist.values[i]);
}
} else {
depth+=1;
genbvalues();
pointer=&values;
start=long(pointer);
end=valuesoffset;
anzahl=(end-start)/8;
for (long i=1; i<=anzahl; i++)
{
wert=*pointer;
pointer=pointer+1;
pmlist.values[i].valueinfo=wert;
}
for (long i=1; i<=anzahl; i++)
{
pmlist.values[i]=executebvalue(pmlist.values[i]);
flag=1;
perftnormal(flag,depth,maxdepth);
undobvalue(pmlist.values[i]);
}
}
};

void recursivestl (signed long flag, long depth, long maxdepth)
{
value tmpvalue;
vector<value> vvaluelist;
long start,end,anzahl,wert,empty;
long* pointer;

if (depth==maxdepth) {
return;
};
if (flag==1) {
depth+=1;
genwvalues();
pointer=&values;
start=long(pointer);
end=valuesoffset;
anzahl=(end-start)/8;
nodes+=anzahl;
vvaluelist.reserve(anzahl);
for (long i=1; i<=anzahl; i++)
{
wert=*pointer;
pointer=pointer+1;
tmpvalue.valueinfo=wert;
vvaluelist.push_back(tmpvalue);
}
for (long i=0; i<anzahl; i++)
{
tmpvalue=vvaluelist[i];
tmpvalue=executewvalue(tmpvalue);
flag=-1;
perft(flag,depth,maxdepth);
undowvalue(tmpvalue);
}
} else {
depth+=1;
genbvalues();
pointer=&values;
start=long(pointer);
end=valuesoffset;
anzahl=(end-start)/8;
vvaluelist.reserve(anzahl);
for (long i=1; i<=anzahl; i++)
{
wert=*pointer;
pointer=pointer+1;
tmpvalue.valueinfo=wert;
vvaluelist.push_back(tmpvalue);
}
for (long i=0; i<anzahl; i++)
{
tmpvalue=vvaluelist[i];
tmpvalue=executebvalue(tmpvalue);
flag=1;
perft(flag,depth,maxdepth);
undobvalue(tmpvalue);
}
}
};

int main(void)
{
struct tms t,u;
long r1,r2,r3,r4;
char tchar;

maxdepths=6;
r3 = times(&t);
recursivenormal(1,0,maxdepths);
r4 = times(&u);
cout << "REKURSIV - NORMAL" << endl;
printf("user time=%f\n",((float)(u.tms_utime-t.tms_utime))/(HZ));
printf("system time=%f\n",((float)(u.tms_stime-t.tms_stime))/(HZ));
printf("real time=%f\n",((float)(r4-r3))/(HZ));

cout << endl;
showboard();
cin.get(tchar);

r1 = times(&t);
recursivestl(1,0,maxdepths);
r2 = times(&u);
cout << "REKURSIV - STL" << endl;
printf("user time=%f\n",((float)(u.tms_utime-t.tms_utime))/(HZ));
printf("system time=%f\n",((float)(u.tms_stime-t.tms_stime))/(HZ));
printf("real time=%f\n",((float)(r2-r1))/(HZ));
cout << endl;
cin.get(tchar);

}

asc

Kopfzerbrechen schrieb:

Wieso ist STL so langsam?

Ich tippe mal auf falsche Benutzung. Die STL ist an sich recht schnell (wobei in einzelnen Bereichen unterschiedliche STL-Implementierungen langsam sind, beispielsweise wurde vor einiger Zeit hier im Forum etwas über Streams und MSVC geschrieben - Am Schluß mit einer Lösung).

Könntest du aber bitte mal die C/C++ Tags verwenden, dein Code lässt sich so, gelinde gesagt nicht sinnvoll lesen. Ganz davon abgesehen das du C und C++ recht wild mischst.
Und: Da ich den Code nicht ausgeführt bekomme (ist unvollständig), werde ich jetzte nicht versuchen dein Codekauderwelsch zu interpretieren.

cu André

schon mal im Release modus kompiliert oder nur debug?

Debug oder Release Modus zeigen keinen signifikanten Unterschied.

C/C++ ist nicht meine "Heimatsprache" ( ) , sonst würde mein Code nicht
"gemischt" sein, was immer das bedeuten mag (Hinweis, wo ich denn
"gemischt" habe?).

Dennoch, so schlecht scheint es nicht zu sein:
der Compiler g++ beschwert sich auch im WALL-Mode nicht (keine Meldungen!).

Noch einmal der Hinweis, der Code ist gleich bis auf die Speicherallokierung.

Wo könnte denn der STL-Container Vector nicht korrekt angesprochen sein
(z.B. C konform, aber nicht C++ konform ?) ?

Einen Vergleich allein mit "INT" als Speicherwert brachte in der Tat eine
gleiche Performance. Die Reihenfolge in der ich den Code ausführe (zuerst
STL-Code und dann Normal oder anders herum) brachte das gleiche Ergebnis.
(Hypothese von wegen Cache, etc. + interessanterweise ein Unterschied vom
Faktor 2, was immer verdächtig ist).

Habe hier aber keine Lösung gefunden, warum es ausgerechnet ein Faktor zwei
ist. Auch der Code zeigt keinen Hinweis darauf. In beiden Fällen wird die
Schleife gleich oft durchlaufen (Überprüfung durch Zähler).

LordJaxom

Trotzdem nutze doch bitte endlich mal die C/C++-Tags. Dazu schaust Du Dir am besten mal ein paar der anderen Beiträge an, wunderst Dich, wieso der Code dort immer so schön eingerückt in einem weissen Kasten steht, und beachtest dann mal die Knöpfe unterhalb des Editors, wenn Du einen Beitrag schrteibst.

Danke für die Anregungen, wie schon gesagt, der gezeigte Code war vollkommen
ausreichend um einen Lösungsansatz aufzuzeigen / Problemursache erläutern.

Habe die "Lösung" gefunden:

http://www.tutorials.de/forum/c-c/208260-c-stl-vector-push_back-ist-sehr-langsam-schleife.html

Mal wider das übliche Problem von C/C++. Kaum einer kennt die genauen
Abläufe hinter den Kulissen und permanent treten "Bugs" auf.
Z.B. was mir noch eine Menge Zeit gekostet hat:

64 Bit Zahl ausgeben mit printf(%x,varname) geht nicht (nur 32 Bit)
Bit Shifts gehen auch nicht sinnvoll ohne Recherche
1 << 45 geht voll in die Hose (1L << 45 geht, aber woher wissen?)

Da bleibe ich lieber bei meinem Assembler, wenn das nicht langsam besser wird.

Nexus

Kopfzerbrechen schrieb:

Danke für die Anregungen, wie schon gesagt, der gezeigte Code war vollkommen
ausreichend um einen Lösungsansatz aufzuzeigen / Problemursache erläutern.

LordJaxom sagte das auch eher wegen derer, die den Post lesen. Für dich ist es jedoch auch von Vorteil, wenn sich dank schöner Formatierung mehr Leute deinen Post anschauen.

Kopfzerbrechen schrieb:

Da bleibe ich lieber bei meinem Assembler, wenn das nicht langsam besser wird.

Wenn du damit fehlerfreier programmieren kannst, dann viel Spass damit.

LordJaxom

Kopfzerbrechen schrieb:

64 Bit Zahl ausgeben mit printf(%x,varname) geht nicht (nur 32 Bit)

Mal im Ernst, falsch benutzen kann man jede Bibliothek in jeder Sprache. "%x" ist für den Datentyp int, kein Wunder dass Du da keine 64 bit Zahl mit rausbekommst.

asc

Kopfzerbrechen schrieb:

Mal wider das übliche Problem von C/C++. Kaum einer kennt die genauen Abläufe hinter den Kulissen und permanent treten "Bugs" auf.
...
Da bleibe ich lieber bei meinem Assembler, wenn das nicht langsam besser wird.

1. Kann keiner die bei dir verwendete Umsetzung der C++ Standardbibliothek kennen, da der Standard nur Rahmenbedingungen festlegt, nicht aber WIE die Implementierung zu erfolgen hat.
2. Magst du vielleicht der Meinung sein das dein Codeschnipsel reicht, nur wenn man diesen nicht ausführen kann, wird man dir kaum sagen können was besser zu machen ist.
3. Dein Code ist gelinde gesagt bescheiden zu lesen, die fehlenden Tags verschlimmern das noch. Und nein, mindestens ich werde jetzt deinen Code nicht analysieren.
4. Bugs habe ich bislang in der C++ Implementierung nahezu 0 erlebt. In der Regel sitzt das Problem vor dem Rechner (da nehme ich auch mich nicht aus). Viel Spaß mit Assembler, spätestens für große Projekte - C++ programmiert man nunmal anders als Assembler.
5. [Nachtrag] Wer sich nicht mit einer Sprache auseinander setzt brauch sich auch nicht zu wundern wenn ihm einige "Bugs" auffallen...

cu André

asc

So, und um jetzt den Irrglauben gegen langsame vectoren etwas auszumerzen, sei neben meinen Post in diesem Thread hier, auch noch folgendes Beispiel zu nehmen.

Getestet unter MSVC 2008, unter Verwendung von push_back, und verglichen mit einmal einen initialisierten und einmal einen uninitialisierten Array:

1. Fall: ca. 0,36 Sekunden (Uninitialisiertes Array)
2. Fall: ca. 0,55 Sekunden (Initialisiertes Array)
3. Fall: ca. 0,45 Sekunden (vector mit reserve und push_back)

Also ich sehe da keinen Faktor 1:3, sondern wenn schon 1:1,25... Also träum weiter.

#define _SECURE_SCL 0

#include <vector>
#include <boost/progress.hpp>

int main()
{
    for(int i=0; i<5; ++i)
    {
        boost::progress_timer t;
        {
            long* list = new long[100000000]; // Ohne Elementinitialisierung
			for(int i=0; i<100000000; ++i)
				list[i] = i;
            delete[] list;
        }
    }
    for(int i=0; i<5; ++i)
    {
        boost::progress_timer t;
        {
            long* list = new long[100000000](); // Mit Elementinitialisierung
			for(int i=0; i<100000000; ++i)
				list[i] = i;
            delete[] list;
        }
    }
    for(int i=0; i<5; ++i)
    {
        boost::progress_timer t;
        {
            std::vector<long> list;
			list.reserve(100000000);
			for(int i=0; i<100000000; ++i)
				list.push_back(i);
        }
    }
    return 0;
}