std::sort extrem langsam im Debug Modus?

Abend,

Ich sortiere einen Vektor mit (ca. 400) Elementen vom Typ IndexIntervalDesc mit std::sort:

void TerrainQuadTree::computeVisiblePatches(const ICamera& cam, std::vector<IndexIntervalDesc>& patches) {
   for(int i=0; i < 4; i++)
      tier1Quadrants[i]->traverse(cam, patches);

   std::sort(patches.begin(), patches.end(), sortVisiblePatchesFrontToBack);	
}

Das Prädikat sieht dabei so aus:

bool sortVisiblePatchesFrontToBack(const IndexIntervalDesc& lhs, const IndexIntervalDesc& rhs) {
   return lhs.distanceToCamSq < rhs.distanceToCamSq;
}

Und die Elemente im Vektor so:

struct IndexIntervalDesc {
   std::string	nodeID;
   float		distanceToCamSq;	// Squared distance to camera	
   UINT		indexCount, startIndex, baseVertexIndex;	
};

Das Problem: Im Release Modus läuft alles recht schnell (habe ~ 260 fps). Wenn ich den selben Code jedoch im Debug Modus laufen lasse, brechen meine fps ein auf 40 fps - nur weil ich std::sort benutze!

Zur Sicherheit habe ich mal vor und nach dem Aufruf von sort() die Zeit gemessen und dabei kam raus:
Im Release Modus dauert der Aufruf von sort ca. 0.000178794 Sekunden
Im Debug Modus dauert der Aufruf von sort ca. 0.0170315

Wegen dem sort ist mein Programm jetzt im Debug Modus unerträglich langsam, so dass ich damit fast nicht mehr rumspielen kann. Wieso ist sort im Debug Modus so unglaublich langsam?? Kann man dagegen was machen?

Debug ist nunmal nicht optimierter Code. Das ist doch auch ganz verständlich, denn zum Debuggen, braucht man zusätzliche Informationen im Code, und die machen das ganze nunmal nicht gerade schneller. Wenn man es schneller bzw. optimaler haben will, muß man ein Release erstellen. Ist doch ganz logisch. Wenn Debug genauso schnell wäre, bräuchte man kein Release.

hustbaer

Könnte sein dass im Debug Modus die Iteratoren mächtig langsam sind (wegen Iterator Debugging oder was auch immer).
Probier mal ob es was bringt wenn du den sort() Aufruf so umschreibst:

//std::sort(patches.begin(), patches.end(), sortVisiblePatchesFrontToBack);  
std::sort(&patches[0], (&patches[0])+patches.size(), sortVisiblePatchesFrontToBack);

EDIT: Nochwas: du hast einen std::string in deiner Struct. std::sort verwendet std::swap um die Elemente zu tauschen, und std::swap verwendet für Typen die es nicht kennt (also auch deine Struct) einfach Zuweisungen. String-Zuweistungen sind aber relativ teuer, da Speicher mit new() angefordert werden muss (ausser bei ganz kurzen Strings). Die "allgemein übliche" Lösung dafür ist std::swap zu spezialisieren (oder zu überladen):

namespace std
{
template <> void swap<MyStruct>(MyStruct& a, MyStruct& b)
{
    std::swap(a.Element1, b.Element1);
    std::swap(a.Element2, b.Element2);
    std::swap(a.Element3, b.Element3);
    // ...
}
}

Vielleicht wunderst du dich jetzt warum das etwas bringen soll, da es aussieht als ob hier nichts anderes passiert als was std::swap schon macht. Der Grund warum es etwas bringt ist dass jetzt nichtmehr die ganze struct geswappt wird sondern die einzelnen Member. Und die Standard-Library hat normalerweise eine swap Spezialisierung für Strings um diese viel schneller tauschen zu können als es ohne Spezialisierung ginge.
Der Effekt sollte auf jeden Fall sein dass keine Heap-Funktionen mehr zum Tauschen von Elementen gebraucht werden, und das sollte einiges bringen (im Debug wie auch im Release).

----

Versuch mal beides und schreib was es gebracht hat.

Hehe, ist ja interessant. Dein Tipp hustbaer brachte tatsächlich einen enormen Geschwindigkeitsschub (von ca 40 auf 120fps).

Mir hat gerade jemand gesagt, dass std::sort den CopyCtor aufruft und da dass das ziemlich zeitintensiv wäre, da meine Struktur einen std::string enthält. Ich habe jetzt ein bißchen debuggt, aber bei mir springt er beim Aufruf von std::sort offenbar NICHT in den CopyCtor von IndexIntervalDesc.
Ruft std::sort den Copy Ctor von IndexIntervalDesc auf? (falls ja: sollte ich dann den string zu einem string* machen?)

hustbaer

Ich hab meinen Beitrag grad nochmal editiert, da gehts genau um die Frage
EDIT: falls du mit einem einfachen char* auskommst (z.B. weil es immer nur String-Literals sind, und daher auch kein ownership-Problem entsteht) dann wäre das natürlich die einfachste Lösung.

Hallo hustbaer,

wenn ich wie von dir vorgeschlagen deine swap Funktion benutze, dann gibt es zwar in der Tat eine leichte Geschwindigkeitssteigerung (genauer: die Zeit von sort sank von 0.17s auf 0.15s und die fps meines Programms stiegen von 44 auf 47fps), aber das Programm ist immernoch unglaublich langsam im Debug Modus.

Ich habe jetzt lange mit Parametern im VS rumgespielt, und konnte damit tatsächlich die Geschwindigkeit gewaltig steigern. Vor allem das Setzen der Präprozessorkonstanten _HAS_ITERATOR_DEBUGGING=0 sowie der Flags /Ob2 und /Zi statt /ZI brachten was. Dank diesen Flags habe ich nun (ohne Änderungen am Code!) statt 47 über 240fps

Eiszapfen schrieb:

Dein Tipp hustbaer brachte tatsächlich einen enormen Geschwindigkeitsschub (von ca 40 auf 120fps).

Eiszapfen schrieb:

(genauer: die Zeit von sort sank von 0.17s auf 0.15s und die fps meines Programms stiegen von 44 auf 47fps)

was denn nun?

ein debug-build ist zur fehlersuche da, nicht um möglichst performant zu laufen. wenn du ein schnelles programm willst, stell den compiler auf "Release".
die debugging-features so lange runter zu drehen, bis das programm genauso schnell läuft wie im release-build ist jedenfalls nicht besonders sinnvoll. dann kannst du dein programm nämlich nicht mehr vernünftig debuggen.

Tachyon

preiselbeerhörnchen hat recht. Es ist ziemlich unsinnig, ein Programm auf den Debugmodus zu optimieren. Das ist nicht mal "Premature Optimization" sondern wirklich grober Unfug. Die Leistungssteugerung erzielt der Compiler für Dich, wenn Du im Releasemode übersetzt.

drakon

die debugging-features so lange runter zu drehen, bis das programm genauso schnell läuft wie im release-build ist jedenfalls nicht besonders sinnvoll. dann kannst du dein programm nämlich nicht mehr vernünftig debuggen.

Meine Meinung. Ist zwar manchmal mühsam, aber durchaus sinnvoll.

Während in Debug Mode die STL (bei mir) Flaschenhals Nr. 1 ist, merke ich davon im Release gar nichts mehr. Dafür lässt sich das ganze recht gut Debuggen.

Fellhuhn

Man will ja keine Fehler in der STL finden, sondern im eigenen Code (an Stellen wo nicht einmal die STL verwendet wird zB). Da ist es durchaus sinnvoll. Auch verhält sich langsamer Code nicht immer genauso wie schneller Code (dank Nebenläufigkeiten etc), so daß da einiges verfälscht werden kann. Daher macht es schon durchaus Sinn.

"Wenn ich über 100 fps hab treten Grafikfehler auf..." versuch das mal mit nur 40 fps zu debuggen.

Tachyon

Fellhuhn schrieb:

Man will ja keine Fehler in der STL finden, ...

Die die "checked Iterators" überprüfen auch nicht sich selbst, sondern fehlerhafte Zugriffe seitens des Benutzers. Also z.B. falsche Ranges etc.

Fellhuhn

Fellhuhn schrieb:

(an Stellen wo nicht einmal die STL verwendet wird zB)

Shade Of Mine

Fellhuhn schrieb:

Fellhuhn schrieb:

(an Stellen wo nicht einmal die STL verwendet wird zB)

epic fail...

denn dort wo du die stl nicht verwendest, dort tun dir die STL debug helper auch kein bisschen weh.

jetzt sagst du gleich dass du ja auch keine performance einbussen von HAS_ITERATOR_DEBUGGING gemeint hast sondern von was anderem. dann sage ich dass der OP aber explizit ein STL-Debug Problem hat. Dann sagst du dass das aber nicht der punkt ist den du gemeint hast... etc. etc.

der punkt aber ist: debugging features auszuschalten weil das programm leicht träge läuft ist doof.

wenn man einen fehler entdeckt hat der im debug modus aufgrund von timing problemen nicht reproduzierbar ist, dann muss man natürlich möglichst viele debug features deaktivieren (der vorteil hier ist aber dass man dann natürlich die meisten auch nicht braucht da man ja eine ungefähre ahnung hat was das problem ist) - aber bei normalen tests sollte man soviel debug sachen anhaben wie möglich (um eben fehler frühzeitig zu finden).

deshalb: finger weg von den debug einstellungen!

Fellhuhn

*seufz*

Wenn du ein Problem in zB dem Rendering von transparenten Flächen hast, diese aber mit STL-Funktionen sortiert werden, der Fehler aber dort definitiv nicht liegt, dann ist es durchaus sinnvoll Debug-Funktionen dort abzustellen.

hustbaer

Naja ich finde es kommt drauf an.
Wenn irgendwas als Debug-Version schon so arg langsam ist dass es echt nurmehr nervt, dann sehe ich auch zu dass ich die Debug-Version wenigstens so schnell bekomme dass es zumindest wieder erträglich ist.
Oft sind das 1-2 isolierte Stellen wo 80% der Zeit draufgeht. Wenn man dort zusätzliche Debug-Features deaktiviert ist das IMO nicht sehr schlimm. Vor allem wenn das Programmteile sind die bereits gut getestet wurden.

Andrerseits macht es natürlich auch keinen Sinn für das ganze Programm Schritt für Schritt Debugging-Features abzudrehen, bis nichts mehr übrig ist. Dann kann man nämlich gleich die Release Version debuggen.

EDIT: man kann das ja auch über eigene #ifdefs lösen, also z.b. ein Makro FAST_DEBUG definieren. Dann kann man immernoch hin und wieder eine Version mit allen Debug-Checks compilieren und testen.

In der (langen) Entwicklungszeit lasse ich mein Programm immer im Debug Modus laufen und dann ist es einfach absolut nicht hinnehmbar, wenn ich mich mit 20fps durchruckeln muss, nur weil er im Debug Modus tausend sachen prüft. Hatte da gerade mit paar anderen Leuten aus anderen Foren ne Diskussion und die meinten sogar, dass Debug Performance in der Grafikentwicklung sehr wohl eine Rolle spielt. SO hat zB EA eine eigene STL Lib (EASTL) entwickelt, die auch im Debug Modus gut läuft.
Also lasst das mal meine Sorge sein

Nexus

Eiszapfen schrieb:

SO hat zB EA eine eigene STL Lib (EASTL) entwickelt, die auch im Debug Modus gut läuft.

Wie toll. Sie ist sicher auch in dem Ausmasse debugfähig wie die STL der C++-Standardbibliothek.

Eiszapfen schrieb:

Also lasst das mal meine Sorge sein

Gerne, aber wieso hast du dann diesen Thread erstellt?

Eiszapfen schrieb:

In der (langen) Entwicklungszeit lasse ich mein Programm immer im Debug Modus laufen und dann ist es einfach absolut nicht hinnehmbar, wenn ich mich mit 20fps durchruckeln muss, nur weil er im Debug Modus tausend sachen prüft.

du hast offenbar immer noch nicht verstanden, wozu ein debug-build gut ist. sein sinn und zweck ist es, "tausend sachen" zwecks fehlerbehebung zu prüfen. wenn man diese prüfungen abstellt, dann ist es ein kein richtiges debug-build mehr. deswegen gibts ja auch die möglichkeit, den compiler auf release zu stellen und damit ein schnelles programm zu kompilieren.

wenn dir dein programm also zu langsam läuft, lass es im release-modus laufen. treten fehler auf, schalte zurück auf debug und behebe die fehler. so macht man das richtig.

Hatte da gerade mit paar anderen Leuten aus anderen Foren ne Diskussion und die meinten sogar, dass Debug Performance in der Grafikentwicklung sehr wohl eine Rolle spielt.

begründung für diese pauschale aussage?
wieso sollte denn bitte die debugging-geschwindigkeit bei grafiklastigen programmen eine größere (oder auch kleinere rolle) spielen als in einem x-beliebigen anderen programm, z.b. einer audio- oder netzwerkanwendung? fehler, die von der ablaufgeschwindigkeit beinflusst werden, können in jedem programm auftreten.
wenn sowas passiert, kann man sich immer noch überlegen wie man dem fehler auf die spur kommt. die lösung liegt aber eher nicht darin, die debug-optionen vom start weg auf geschwindigkeit statt auf zuverlässigkeit zu tunen.

Also lasst das mal meine Sorge sein

äh... ja. wieso fragst du dann überhaupt? bist du ein troll?

Mal davon abgesehen, dass Iteratorenchecks kein Standard-STL verhalten sondern Implementationsabhängig sind. Sowas lässt sich per Makro abstellen.

hustbaer

An ein paar wenigen Stellen diverse Debug-Checks auszuschalten damit ein Programm statt unbrauchbar langsam halt halbwegs akzeptabel läuft finde ich nicht schlimm. Und oft sind es nur ein paar wenige Stellen. Und diese paar wenigen Stellen checkt man dann indem man hin und wieder eine Version mit allen Checks baut und die dann testet. Die andauernden Testläufe mit einem Programm zu machen welches so langsam ist dass einem der Spass dran vergeht ist kontraproduktiv, da der Effekt davon bloss ist dass man weniger testet.