[gelöst] Programm throws BAD_ALLOC

cni

pumuckl schrieb:

Versuch mal den Code komplett, kompilierbar, reduziert zu posten

ja das mit dem Code posten ist so ne Sache, da das ne ganze Menge Code ist und der Fehler ja nicht mal bei mir bei jeder Ausführung auftritt (Verschieden viele Eingangsknoten)

pumuckl schrieb:

ist es wahrscheinlicher dass der Heap irgendwo zerschossen wird.

Kann ich das irgendwie nachvollziehen (Debuggen oder so)? Wenn ich durch den Code debugge fliegt er halt wirklich erst an der besagten Stelle raus. Ich nutze eclipse unter linux.

krümelkacker schrieb:

Zeig doch mal die Definition von Knoten.

class Knoten {
public:
   std::vector< std::pair<double, unsigned int> > suppliedNodes;
   double threshold;
   int type;
   std::vector<unsigned int> doubleSuppliedNodes;
};

Mir ist bewusst, dass einzelne Objekte und gerade ein Vector<Knoten> sehr groß wird, allerdings klappt es mit zB. 3400 Eingangsknoten und mit 340 nicht. Die Größe sollte hier also kein Problem sein.

krümelkacker schrieb:

wobei man dann natürlich auch gleich eine Referenz statt eines Zeigers verwenden kann:
Dann könntest du sogar temporäre Objekte in die Funktion stecken. Auf solchen Dingern funktioniert ja im Allgemeinen der Adressoperator nicht.

Mach ich sogar, hab mich da vertippt.

krümelkacker schrieb:

Falls dir die Reihenfolge der Knoten-Objekte im Vektor nicht wichtig ist, könntest du das "Aufrücken" im Vektor beim Löschen eines einzelnen Elements auch sparen. Du kopierst dazu einfach den letzten Knoten auf das zu löschende Element und reduzierst die Vektorgröße um eins.

Werd das mal ausprobieren und morgen das Ergebnis posten.

Danke schon mal
cni

pumuckl

cni schrieb:

und der Fehler ja nicht mal bei mir bei jeder Ausführung auftritt (Verschieden viele Eingangsknoten)

Tritts denn wenigstens bei gleichbleibenden Eingaben zuverlässig auf? Dann solltest du das Problem natürlich immer mit dem selben Eingabesatz nachstellen und eingrenzen (und den Code reduzieren).

Zusätzlich wäre ggf. eine Analyse der Eingabesätze zielführend, die den Fehler triggern, vielleicht gibts da Gemeinsamkeiten die dich auf den Fehler stoßen.

Wenn der Fehler nicht immer auftritt (bei gleichen Eingaben), dann hört sich das nach nichtdeterministischem Verhalten an, was typischerweise bei parallelen Programmen auftaucht, die eine Race Condition oder ähnliches beinhalten.

Kann ich das irgendwie nachvollziehen (Debuggen oder so)?

Debugger und/oder Profiler können sowas oft bemerken. Die Ursachen liegen leider oft an Stellen, die nichts mit dem Code zu tun haben, in dem das Problem auftritt.

SeppJ

Ein Debugger kann dir wenigstens ganz leicht die unmittelbare Ursache nennen (vielleicht ist die angeforderte Größe fälschlicherweise sehr groß oder gar negativ). Ein Speicherdebugger wie valgrind kann dir auch Ursachen automatisch finden, die auf (technisch) fehlerhafte Programmierung zurückzuführen sind. Ein guter Compiler mit hohem Warnlevel kann dir viele solcher Fehler auch schon bei der Übersetzung des Programms finden, falls du dies noch nicht getan hast (Warnungen sollten immer angeschaltet sein).

cni

pumuckl schrieb:

Die Ursachen liegen leider oft an Stellen, die nichts mit dem Code zu tun haben, in dem das Problem auftritt.

Hattest recht. Hab mir in dem Teil, den ich hier als "[Finde beste Knoten Algorithmus]" abgetan hab, den Heap zerschossen. Hab das Programm mal mit valgrind (Danke an SeppJ) durchlaufen lassen und damit das Problem finden und beheben können.
Außerdem konnte ich noch einige andere Fehler bei der Speicherallokierung beheben.

Vielen Dank für die Hilfe.
Gruß cni

krümelkacker

Wenn du die Standardcontainer gern und häufig einsetzt, dann kannst du auch mal deren Debug-Modus einschalten.

cni

Hallo noch mal,

dank eurer Hilfe konnte ich den ursprünglichen Fehler beheben und das Programm läuft soweit. Allerdings hab ich jetzt ein neues Problem. Wenn ich das Programm mit der Eingabemenge von ca. 34000 Knoten, für die es vorgesehen ist, im Terminal starte kommt nach 25min erneut ein BAD_ALLOC.
Wenn ich das Programm ohne Änderungen mit den gleichen Eingabedaten in eclipse starte, läuft es ohne Probleme durch.
Kann der Fehler in diesem Fall tatsächlich durch ein Speicherproblem entstehen?

Bei Eingabeparametern mit weniger Knoten läuft es sowohl im Terminal als auch in eclipse.

Ich werde jetzt erst mal versuchen das Programm für den list container umzuschreiben. Könnt ihr mir sagen ob das was bringen könnte (Nur bezogen auf Speichereffizienz)?

SeppJ

cni schrieb:

Kann der Fehler in diesem Fall tatsächlich durch ein Speicherproblem entstehen?

Ja. Das klingt sehr nach irgendeinem undefinierten Verhalten und in deiner entwicklungsumgebung läuft das Programm in irgendeiner dummen Debuglaufzeitumgebung, die den Fehler verschleppt, anstatt darauf aufmerksam zu machen.

Ich werde jetzt erst mal versuchen das Programm für den list container umzuschreiben. Könnt ihr mir sagen ob das was bringen könnte (Nur bezogen auf Speichereffizienz)?

Ganz bestimmt nicht. Die Worte "list" und "Effizienz" gehören nicht in den gleichen Satz, außer, es kommt noch ein "nicht" darin vor.

cni

SeppJ schrieb:

Ganz bestimmt nicht. Die Worte "list" und "Effizienz" gehören nicht in den gleichen Satz, außer, es kommt noch ein "nicht" darin vor.

Ok dann werd ich das wohl nicht mehr weitermachen

Ich guck dann einfach noch mal ob ich mit valgrind oder dem Debug Modus standard container was finde.

Danke schon mal

Kellerautomat

SeppJ schrieb:

Ganz bestimmt nicht. Die Worte "list" und "Effizienz" gehören nicht in den gleichen Satz, außer, es kommt noch ein "nicht" darin vor.

Ich würde es gerne etwas anders formulieren. Wer viele Objekte haben möchte (und mit viel meine ich Mengen, die an das Limit des verfügbaren RAMs kommen), der wird mit std::list/std::forward_list möglicherweise mehr Objekte abspeichern können als mit std::vector, da der Speicher nicht am Stück liegen muss. Das ist natürlich nur der Fall, solange der gespeicherte Typ ebenfalls am Stück liegt.

Grundsätzlich hast du aber vollkommen Recht, list ist einfach nur lahm, verbraucht viel Extraspeicher für Pointer und ist Cache-unfreundlich.

Edit: Um meinen Punkt etwas klarer zu machen: Es kommt darauf an, wie man Effizienz definiert.

Effizienz =
- Höhere Geschwindigkeit (natürlich auch von Operationen abhängig) -> std::vector
- Geringerer Overhead -> std::vector
- Mögliche Speicherausnutzung -> Stark abhängig vom Usecase.

SeppJ

Kellerautomat schrieb:

SeppJ schrieb:

Ganz bestimmt nicht. Die Worte "list" und "Effizienz" gehören nicht in den gleichen Satz, außer, es kommt noch ein "nicht" darin vor.

Ich würde es gerne etwas anders formulieren. Wer viele Objekte haben möchte (und mit viel meine ich Mengen, die an das Limit des verfügbaren RAMs kommen), der wird mit std::list/std::forward_list möglicherweise mehr Objekte abspeichern können als mit std::vector, da der Speicher nicht am Stück liegen muss. Das ist natürlich nur der Fall, solange der gespeicherte Typ ebenfalls am Stück liegt.

Das klingt eher nach einem Fall für eine deque.

cni

SeppJ schrieb:

Kellerautomat schrieb:

SeppJ schrieb:

Ganz bestimmt nicht. Die Worte "list" und "Effizienz" gehören nicht in den gleichen Satz, außer, es kommt noch ein "nicht" darin vor.

Ich würde es gerne etwas anders formulieren. Wer viele Objekte haben möchte (und mit viel meine ich Mengen, die an das Limit des verfügbaren RAMs kommen), der wird mit std::list/std::forward_list möglicherweise mehr Objekte abspeichern können als mit std::vector, da der Speicher nicht am Stück liegen muss. Das ist natürlich nur der Fall, solange der gespeicherte Typ ebenfalls am Stück liegt.

Das klingt eher nach einem Fall für eine deque.

Macht es denn dann Sinn eine deque (oder list) zu benutzen statt eines vectors, wenn das Problem wirklich auf zu wenig verfügbarem Speicher beruht?

Es kann natürlich gut sein, dass da noch einige andere Fehler in meinem Programm sind. Allerdings dauert es jedes mal ne gute halbe Stunde bis der Fehler auftritt. Da ist das Debuggen relativ zeitaufwendig.
Bei der Verwendung von valgrind dauert es dann wahrscheinlich einige Stunden bis der Fehler auftritt...
Gibts da ne schnellere Möglichkeit?

SeppJ

cni schrieb:

Macht es denn dann Sinn eine deque (oder list) zu benutzen statt eines vectors, wenn das Problem wirklich auf zu wenig verfügbarem Speicher beruht?

Nur wenn es wirklich an zu wenig Speicher liegt, was extrem unwahrscheinlich ist.

Es kann natürlich gut sein, dass da noch einige andere Fehler in meinem Programm sind.

Dies wird vermutlich der Fall sein.

Allerdings dauert es jedes mal ne gute halbe Stunde bis der Fehler auftritt. Da ist das Debuggen relativ zeitaufwendig.

Lass dir doch einfach mal ein Coredump machen, dann siehst du wenigstens die unmittelbare Ursache. Vielleicht läuft irgendwo etwas über und du forderst eine negative Menge Speicher an oder ähnliches.

Bei der Verwendung von valgrind dauert es dann wahrscheinlich einige Stunden bis der Fehler auftritt...

Einfach mal valgrind in den strengsten Einstellungen auf eine kleinere Datenmenge ansetzen, vielleicht ist der Fehler schon da, aber wirkt noch nicht fatal. Ich benutze für valgrind immer

valgrind --tool=memcheck --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes ./executable

und im Falle von uninitialisierten Werten noch zusätzlich --track-origins=yes . Letzteres ist wirklich sehr langsam, daher nur, wenn die anderen Checks schon was werfen, um die Ursache zu finden.

cni

SeppJ schrieb:

Ich benutze für valgrind immer
valgrind --tool=memcheck --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes ./executable
und im Falle von uninitialisierten Werten noch zusätzlich --track-origins=yes . Letzteres ist wirklich sehr langsam, daher nur, wenn die anderen Checks schon was werfen, um die Ursache zu finden.

Hab das jetzt gerade mit den Parametern laufen lassen. "Leider" sind keine Fehler aufgetreten und der Durchgang hat auch mal eben ne knappe Stunde gedauert.

Werd das jetzt mal mit der deque probieren, schaden kanns ja nicht ist auch nicht so viel Aufwand.

SeppJ

Erwarte keine Wunder von deque. Wenn vector bei Eingabemenge 34000 an zu wenig zusammenhängendem Speicher scheitert, dann wird deque auch nicht wesentlich weiter kommen. Ist dein Programm denn wirklich so speicherintensiv, dass dein Rechner voll ausgenutzt wird? Und ist dies für den Algorithmus wirklich nötig?

cni

Das Problem bei der ganzen Sache ist, dass der Algorithmus schon länger existiert und mit der Zeit einfach immer erweitert wurde. Wahrscheinlich gibt es schon einen Weg das ganze effizienter zu Programmieren, allerdings müsste man dann auch komplett neu Anfangen.
Also bei dem letzten Versuch ist der Algorithmus komplett durch gelaufen (mit deque). Hoffe mal das war jetzt kein Zufall...

Da ich dem ganzen Programm allerdings auch nicht mehr so viel Zeit widmen wollte, werd ich dem Problem nicht mehr genauer auf den Grund gehen, wenn es denn dann jetzt läuft.
Von da her schon mal vielen Dank für die Hilfe an alle!