[gelöst] Programm throws BAD_ALLOC

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!