std::bad allocator zur Laufzeit



  • Ich habe versucht ein Programm zur Berechnung von regulären Ausdrücken zu schreiben und das compiliert auch, jetzt habe ich aber einen atd::bad allocator Fehler bekommen.Übrigens hat es vorher auch nicht das richtige Ergebnis produziert sondern nur den ersten Teil davon.

    struct Regeln{
    	std::string aus;
    	std::list<std::list<std::string>> zu;
    };
    
    
    std::vector<Regeln>*stringnachRegeln(const std::string&s){
            std::vector<Regeln>*r=new std::vector<Regeln>();
    	r->resize(1);
    	r->at(0).zu=std::list<std::list<std::string>>();
    	r->at(0).zu.push_back(std::list<std::string>());
    	r->at(0).zu.back().push_back("");
    	bool aus=true,wargleich=false;
    	int Gleiches=0;
    	for(unsigned int i=0;i<s.length();i++){
    		if(s[i]=='-')
    			r->at((wargleich?Gleiches:(r->size()-1))).zu.back().push_back("");
    		else if(s[i]<=32)
    			;
    		else if(s[i]=='|')
    			r->at((wargleich?Gleiches:(r->size()-1))).zu.push_back(std::list<std::string>());
    		else if(s[i]=='='){
    			for(unsigned int j=0;j<r->size()-1;j++)
    				if((*r)[j].aus==r->back().aus){
    					wargleich=true;
    					Gleiches=j;
    					r->resize(r->size()-1);
    					break;
    				}
    			aus=false;
    		}
    		else if(s[i]==','){
    			aus=true;
    			r->resize(r->size()+1);
    			wargleich=false;
    			r->at((wargleich?Gleiches:(r->size()-1))).zu=std::list<std::list<std::string>>();
    			r->at((wargleich?Gleiches:(r->size()-1))).zu.push_back(std::list<std::string>());
    			r->at((wargleich?Gleiches:(r->size()-1))).zu.back().push_back("");
    		}
    		else
    			switch(aus){
    				case true:
    				r->at((wargleich?Gleiches:(r->size()-1))).aus+=s[i];break;
    				default:
    				r->at((wargleich?Gleiches:(r->size()-1))).zu.back().back()+=s[i];
    			}
    		}
                  std::ofstream Datei;
                  	Datei.open("Ausgabe.txt",std::ofstream::out|std::ofstream::app);
                  	if(Datei)
                  		for(Regeln re:*r){
                  			std::cout<<re.aus+" = ";
                  			Datei<<re.aus+" = ";
                  			for(std::list<std::string>l:re.zu){
                  				for(std::string s:l){
                  					std::cout<<s+"-";
                  					Datei<<s+"-";
                  				}
                  				if(l!=re.zu.back()){
                  					std::cout<<" | ";
                  					Datei<<" | ";
                  				}
                  			}
                  			std::cout<<","<<std::endl;
                  			Datei<<","<<std::endl;
                  		}
    
    //...
    }
    
    

    Dazu kommt noch ein paar andere Methoden hinzu. Bevor ich Zeile 10-12 hinzugefügt hatte, gab es keine Fehler, allerdings wurde wahrscheinlich nur der erste Teil des Strings bearbeitet. Vielleicht kann mir ja jemand helfen...



  • @Ichwerdennsonst Gibt es einen guten Grund für das new in Zeile 8 und ist garantiert, dass die dort erstellten Vektoren auch wieder irgendwo mit delete freigegeben werden?

    Möglicherweise löst sich das Problem in Wohlgefallen auf, wenn du die Funktion so strukturierst:

    std::vector<Regeln> stringnachRegeln(const std::string& s) {
        std::vector<Regeln> r;
        ...
        return r;
    }
    

    Ansonsten hilft ein Debugger um herauszufinden, von wo aus bad_alloc geworfen wird. Diese Exception bedeutet, dass eine Speicherresverierung aus irgendeinem Grund fehlgeschlagen ist. Der häufigste Grund wohl sein, dass kein freier Speicher mehr vorhanden, oder der Speicher zu fragmentiert für Anforderung ist. Auch wenn man in Speicherbereiche schreibt, die einem nicht gehören, wäre ein bad_alloc bei folgenden Allokationen denkbar (eher unwahrscheinlicher).



  • Das mit der Speicherfragmentierung kann sein, schließlich will ich ja ein komplexes Ding auf dem Heap reservieren und das als Vector, der ja zusammenhängen soll. Aber noch weniger will ich es beim zurückgeben kopieren, also hätte ich es später in der aufrufenden Funktion gelöscht. Meinst du vielleicht es könnte daher an dem Container liegen?



  • @Ichwerdennsonst sagte in std::bad allocator zur Laufzeit:

    std::list<std::liststd::string> zu;

    Warum Liste von Liste in der Klasse? Liste ist i.d.R keine gute Idee, außer du hast spezielle Gründe für eine Liste.

    Warum gibst du nicht einen std::vector<Regeln> direkt ohne * zurück?

    Der Code sieht sehr kompliziert aus. Was tut "stringnachRegeln"?

    Wer soll das hier lesen:
    r->at((wargleich?Gleiches:(r->size()-1))).zu.back().push_back("");

    Das mit der Speicherfragmentierung kann sein, schließlich will ich ja ein komplexes Ding auf dem Heap reservieren und das als Vector, der ja zusammenhängen soll.

    Über Fragmentierung würde ich mir hier überhaupt gar keine Gedanken machen. Der vector hängt zusammen, aber die Listen sind ja das Gegenteil von zusammenhängend. Alles irrelevant, solange dein Code so kompliziert zu lesen ist.

    Aber noch weniger will ich es beim zurückgeben kopieren, also hätte ich es später in der aufrufenden Funktion gelöscht.

    War soll da wo was kopieren? Schau dir mal https://en.cppreference.com/w/cpp/language/copy_elision an.



  • @Ichwerdennsonst sagte in std::bad allocator zur Laufzeit:

    Das mit der Speicherfragmentierung kann sein, schließlich will ich ja ein komplexes Ding auf dem Heap reservieren und das als Vector, der ja zusammenhängen soll.

    Wenn "zusammenhängen" wichtig ist, solltest du vielleicht überlegen statt der verschachtelten std::list in Regeln stattdessen std::vector zu nehmen (siehe @wob).

    Ansonsten solltest du wissen, dass ein std::vector bereits vergleichbar mit einem Pointer ist, der auf einen Heap-Speicherbereich zeigt. Unter der Haube sieht der nämlich so oder ähnlich aus:

    class vector {
        ...
        T* data;
        size_t size;
        ...
        data = new T[size];
    };
    

    Mit dem new reservierst du dir also keinen Speicher für die Regeln-Objekte - das managt der vector, sondern lediglich für das vector-Objekt selbst, das wahrscheinlich nur aus einem Pointer und einer Größe besteht.

    Aber noch weniger will ich es beim zurückgeben kopieren [...],

    Schau dir mal an, was @wob dazu gesagt hat. Im besonderen auch NRVO. Im Zweifel kann man auch mit return std::move(r) ein Move forcieren. Eine Move-Operation ist letztendlich unter der Haube bezüglich Effizienz dasselbe was du hier vor hast, nur eleganter und sicherer. Alle Standard-Container unterstützen das und sind dabei mit Ausnahme flacher Container wie std::array genau so effizient wie einen Pointer zurückzugeben.

    Die Compiler-Optimierung der Copy Elision ist aber noch einen Tick effizienter - NRVO in diesem Fall.

    []... also hätte ich es später in der aufrufenden Funktion gelöscht.

    Hätte oder hast? Wenn du nur hättest und du die Funktion oft genug aufrufst, dann ist es kein Wunder, dass dir irgendwann bad_alloc entgegenfliegt.

    Meinst du vielleicht es könnte daher an dem Container liegen?

    Ziemlich sicher nicht. Das liegt mit einer Wahrscheinlichkeit 99.986% an deinem Code. Davon bin ich sogar überzeugt, ohne den Rest gesehen zu haben (siehe @wob "kompliziert zu lesen" - da sind dann auch Fehler sehr wahrscheinlich) 😉



  • @Ichwerdennsonst sagte in std::bad allocator zur Laufzeit:

    Ich habe versucht ein Programm zur Berechnung von regulären Ausdrücken zu schreiben

    Warum eigentlich? Ist das eine Übung?

    Sofern das keine Übung ist, warum nimmst du nicht die Regular expressions library?



  • @Quiche-Lorraine sagte in std::bad allocator zur Laufzeit:

    Regular expressions library?

    ...oder die hier: https://github.com/hanickadot/compile-time-regular-expressions wenn die REs zur Compilezeit feststehen.



  • @Finnegan sagte in std::bad allocator zur Laufzeit:

    oder der Speicher zu fragmentiert für Anforderung ist

    Speicherfragmentation ist kein Problem, was bei einem halbwegs aktuellen OS mit virtueller Speicherverwaltung eine Rolle spielt. Die logischen Speicherseiten können wild im physikalischen Speicher verteilt sein, die Applikation sieht davon nichts. Es kann nur dann zu einem Problem werden, wenn die OS interne Verwaltungsstruktur über zu laufen droht. Dann wird eine Defragmentatierung gemacht, wovon die Applikation nichts mitbekommt. Sie wird kurz angehalten und die physikalischen Speicherseiten umgelagert, so dass weniger Seiten verwaltet werden müssen.

    Probleme mit Fragmentation sieht man heute eigentlich nur noch bei embedded Laufzeitumgebungen, oder man programmiert für ein Retrosystem.



  • @john-0 sagte in std::bad allocator zur Laufzeit:

    @Finnegan sagte in std::bad allocator zur Laufzeit:

    oder der Speicher zu fragmentiert für Anforderung ist

    Speicherfragmentation ist kein Problem, was bei einem halbwegs aktuellen OS mit virtueller Speicherverwaltung eine Rolle spielt.

    Das wohl, aber ich denke da hat die Malloc-Implementierung der verwendeten C-Runtime auch noch ein Wörtchen mitzureden. Dort könnte ebenfalls eine feingranularere Fragmentierung auftreten (unterhalb der Page-Ebene), die dazu führt, dass das Programm übermässig viele Seiten vom OS anfordert, ohne diese wieder zurückzugeben. Da könnte dann ein OS auch nicht viel gegen tun.

    Wie relevant das letztendlich ist, kann ich aber nicht sagen. Ich wollte hier nur ein paar Gründe auflisten, weshalb es zu einem bad_alloc kommen kann. Ich vermute stark @Ichwerdennsonst läuft hier einfach in eine klassische OOM-Situation.



  • @Finnegan sagte in std::bad allocator zur Laufzeit:

    Das wohl, aber ich denke da hat die Malloc-Implementierung der verwendeten C-Runtime auch noch ein Wörtchen mitzureden. Dort könnte ebenfalls eine feingranularere Fragmentierung auftreten (unterhalb der Page-Ebene), die dazu führt, dass das Programm übermässig viele Seiten vom OS anfordert, ohne diese wieder zurückzugeben. Da könnte dann ein OS auch nicht viel gegen tun.

    Aus Performancegründen wird mittlerweile exzessiv Gebrauch von Memory Overcommitment gemacht. D.h. wenn man wirklich ein Problem mit dem Speicher bekommt, wird mit Sicherheit kein bad_alloc mehr geworfen, sondern das OS kickt das Programm aus dem System.

    Wie relevant das letztendlich ist, kann ich aber nicht sagen. Ich wollte hier nur ein paar Gründe auflisten, weshalb es zu einem bad_alloc kommen kann. Ich vermute stark @Ichwerdennsonst läuft hier einfach in eine klassische OOM-Situation.

    Danach sieht es aus.



  • @john-0
    oom ist schwierig, da ich dem Programm nicht wirklich viel übergeben habe, grob geschätzt müsste es 100 byte ram verbraucht haben und es sollte ja wohl problemlos tausendmal so viel verbrauchen dürfen. An der For-Schleife kann es nicht liegen, die hört nach der Länge des Strings sicher auf. Wie gesagt ist es erst nach Hinzufügen in Zeile 10-12 dazu gekommen. Vielleicht ist das auch logisch immerhin versuche ich ein zusammenhängendes Stück Speicher mittendrin aufzublähen. Andererseits sollte ich mir als Programmierer selbst bei C++ darüber keine Gedanken machen müssen, das ist Aufgabe der stdlib. Vielleicht ist auch irgendwo eine Schleife kaputt und das Programm hört gar nicht auf Speicher zu beschlagnamen, aber wie gesagt die For-Schleife ist eigentlich wasserdicht.
    Ob der Speicher zusammenhängt ist mir letzendlich egal, ich weiß nur das er es bei Vector tut. Windows zerschießt den Performance-Vorteil wahrscheinlich durch Paging. Vielleicht erkennt Windows aber auch die Chance. Wieweit ich Assembler kenne, sind zusammenhängende Bereiche u.a. wegen rep/repz/repnz (jedenfalls bei x86) und weil man Adressen nicht aus dem Speicher laden muss effizienter. Also folgt, dass es guter Programmierstil ist, das wenn möglich so zu machen. Übrigens ist die Funktion dafür gedacht, die Eingabe zu ordnen. Später wird sehr viel darauf zugegriffen.
    @Finnegan
    Statt list vector zu nehmen ist eine gute Idee. Das hab ich schließlich auch gemacht und jetzt kommt kein bad::allocator mehr 🙂 Also danke schonmal für die Hilfe



  • Du denkst über völlig falsche Dinge nach. Sag ja nur. VERGISS SOFORT alle Gedanken über Fragmentierung, Assembler, möglicherweise problematische Stdlib und anderen Kram.

    Stattdessen hinterfrage in deinem Programm:

    • die Loops
    • jedes new und delete (es sollte keines geben)

    Was soll deine Funktion stringnachRegeln tun? Beschreibe das mal exakt. Und dann schreibe Tests dazu. Was soll rauskommen, wenn du sie mit einem leeren String aufrufst? Was wenn du "123abc" oder "\w+" eingibst? Allein schon der Rückgabetyp ist doch völlig unklar - ein String und eine Liste von Liste von String - aber was soll da semantisch drinstehen?

    Ansonsten: aktiviere Address- und Memory-Sanitizer.



  • ich weiß jetzt woran es liegt es ist diese Zeile:

    
    r->at((wargleich?Gleiches:(r->size()-1))).zu.push_back(std::vector<std::string>());
    

    Offenbar wird dadurch alles gelöscht

    Absurderweise aber nur, wenn ich es in einer If-Schleife ausführe
    Jedenfalls nochmal danke
    jetzt funktionierts



  • @Ichwerdennsonst sagte in std::bad allocator zur Laufzeit:

    ich weiß jetzt woran es liegt es ist diese Zeile:

    
    r->at((wargleich?Gleiches:(r->size()-1))).zu.push_back(std::vector<std::string>());
    

    Offenbar wird dadurch alles gelöscht

    Absurderweise aber nur, wenn ich es in einer If-Schleife ausführe
    Jedenfalls nochmal danke
    jetzt funktionierts

    If ist keine Schleife und gelöscht wird da gar nix.



  • @Ichwerdennsonst sagte in std::bad allocator zur Laufzeit:

    Ob der Speicher zusammenhängt ist mir letzendlich egal, ich weiß nur das er es bei Vector tut. Windows zerschießt den Performance-Vorteil wahrscheinlich durch Paging. Vielleicht erkennt Windows aber auch die Chance.

    Sollte dein Thema eher nicht Parser oder Automaten sein?

    Ich habe da mal einen schönen Link gefunden: Regular Expression Matching Can Be Simple And Fast



  • @Quiche-Lorraine sagte in std::bad allocator zur Laufzeit:

    Sollte dein Thema eher nicht Parser oder Automaten sein?

    Ich habe da mal einen schönen Link gefunden: Regular Expression Matching Can Be Simple And Fast

    Ja, ich denke auch dass sich die Diskussion hier zu sehr um Folgeprobleme dreht, die wahrscheinlich durch - gelinde ausgedrückt - etwas holprigen Code selbst geschaffen sind. Nicht vergessen: Man will eigentlich meistens keine Bohrer, sondern Löcher 😉


Anmelden zum Antworten