Stack Overflow vermeiden

[snOOfy]

Ich habe ein Simulationsprogramm geschrieben, das große Arrays verwendet. Leider ist die Größe dieser Arrays eskaliert, so dass ich jetzt regelmäßig Stack Overflows produziere und den Code komplett ändern muss. Konkret geht es unter anderem um ein

int h[2][2][4][3][21][730];

Bevor ich es aber wieder schlecht löse, wollte ich fragen, wie man so etwas am besten verwaltet. Die Dimensionen sind konstant, trotzdem empfiehlt sich wohl eine dynamische Struktur, z.B. ein vector. Möglich wäre:

vector<vector<vector<vector<vector<vector<int> > > > > > h(2, 
	vector<vector<vector<vector<vector<int> > > > >(2, 
	vector<vector<vector<vector<int> > > >(4, 
	vector<vector<vector<int> > >(3, 
	vector<vector<int> >(21, 
	vector<int>(730))))));

Das sieht aber irgendwie doof aus... gibt es da noch andere Möglichkeiten?

[CStoll]

Wer kommt denn auf die Idee, sechsdimensionale Arrays anzulegen? Da solltest du dringend mal deine Datenstrukturen überarbeiten.

[snOOfy]

Das ist leider so vorgeschrieben, sonst hätte ich es auch anders gelöst. Es handelt sich um ein System Dynamics Modell.

Wenn es jemanden genauer interessiert:
http://bill.srnr.arizona.edu/classes/182/genefreqs/malaria/Flessa 1999.pdf

// Edit: mein Beispiel oben bezog sich auf das Feld mit den Menschen. Seite 186 unten: \[M_{i,r,a,s,z,d}\]

[drakon]

Man verwaltet keine 6 Dimensionale Arrays.

Ich bin überzeugt, dass man das eleganter lösen kann. (eine Variante zu nativen Arrays wäre z.B boost::array).

//EDIT
boost::array fällt natürlich aus, wenn dein Hauptproblem Stackoverflows sind. Du könntest das Array sonst auch dynamisch anlegen musst dann halt einfach die indirektionen selbst machen.

[volkard]

snOOfy schrieb:

Ich habe ein Simulationsprogramm geschrieben, das große Arrays verwendet. Leider ist die Größe dieser Arrays eskaliert, so dass ich jetzt regelmäßig Stack Overflows produziere und den Code komplett ändern muss. Konkret geht es unter anderem um ein

int h[2][2][4][3][21][730];

Ist doch hübsch.
Paßt halz nicht auf den Stack, sondern nur in den Freispeicher.

Bevor ich es aber wieder schlecht löse, wollte ich fragen, wie man so etwas am besten verwaltet. Die Dimensionen sind konstant, trotzdem empfiehlt sich wohl eine dynamische Struktur, z.B. ein vector.

Nein. Du verlierst Compileroptimierungen bei der Indexberechnung.

typedef int MenschenIfektionsFeldTyp[2][2][4][3][21][730];
MenschenIfektionsFeldTyp* h=new MenschenIfektionsFeldTyp;

Und schupps, isses im Freispeicher.
Nur ist es jetzt doof zu bedienen, weil man immer (*h) schreiben muß.

(*h)[i][r][a][s][z][d]=5;

Oder man nimmt new[] und macht den Typ nur fünfdimenional.

[volkard]

drakon schrieb:

Man verwaltet keine 6 Dimensionale Arrays.

Ich bin überzeugt, dass man das eleganter lösen kann. (eine Variante zu nativen Arrays wäre z.B boost::array).

//EDIT
boost::array fällt natürlich aus, wenn dein Hauptproblem Stackoverflows sind. Du könntest das Array sonst auch dynamisch anlegen musst dann halt einfach die indirektionen selbst machen.

Hihi. Das brint mich auf die Lösung.

vector<array<array<array<array<array<...

[snOOfy]

volkard schrieb:

typedef int MenschenIfektionsFeldTyp[2][2][4][3][21][730];
MenschenIfektionsFeldTyp* h=new MenschenIfektionsFeldTyp;

Da kommt ein Fehler:

Visual Studio schrieb:

Error: Ein Wert vom Typ ""int(*)[2][2][4][3][21][730]"" kann nicht zum Initialisieren einer Entität vom Typ ""MenschenIfektionsFeldTyp *"" verwendet werden.

[seldon]

Es gibt da noch Boost.Multi-Array:

boost::multi_array<int, 6> h(boost::extents[2][2][4][3][21][730]);

...danach benutzbar wie ein normales Array.

[hustbaer]

snOOfy schrieb:

volkard schrieb:

typedef int MenschenIfektionsFeldTyp[2][2][4][3][21][730];
MenschenIfektionsFeldTyp* h=new MenschenIfektionsFeldTyp;

Da kommt ein Fehler:

Visual Studio schrieb:

Error: Ein Wert vom Typ ""int(*)[2][2][4][3][21][730]"" kann nicht zum Initialisieren einer Entität vom Typ ""MenschenIfektionsFeldTyp *"" verwendet werden.

Dann stülp ne struct drüber.

struct teh_dada
{
    int dada[2][2][4][3][21][730];
};

void foo()
{
    std::auto_ptr<teh_dada> d(new teh_dada());
}

[volkard]

snOOfy schrieb:

volkard schrieb:

typedef int MenschenIfektionsFeldTyp[2][2][4][3][21][730];
MenschenIfektionsFeldTyp* h=new MenschenIfektionsFeldTyp;

Da kommt ein Fehler:

Visual Studio schrieb:

Error: Ein Wert vom Typ ""int(*)[2][2][4][3][21][730]"" kann nicht zum Initialisieren einer Entität vom Typ ""MenschenIfektionsFeldTyp *"" verwendet werden.

Ärgerlich.
Warum kommt er? Ich dachte bisher, das [] bei new[] sei Teil des new[] und nicht Teils des Typs. Ich hab new benutzt und nicht new[]. Das hat dem new doch egal zu sein, ob mein Typ zufällig ein Array ist.
*verwirrt bin*

[seldon]

Es gibt einen eigenen operator new[], aber die new-expression wählt ihn abhängig vom Typ aus. Das kann im Zusammenhang mit typedefs und Arrays auch dazu führen, dass scheinbar new und delete[] gemischt werden müssen:

typedef int foo_t[3];
int *p = new foo_t; // --> new[]
delete[] p; // !

Ich hab das auch erst aus Effective C++ (Item 17) gelernt.

[snOOfy]

Schön dass es offenbar eine Lösung gibt, aber sorry, ich verstehe nur noch Bahnhof. Wie muss ich das jetzt anwenden, um mein 6-dimensionales Array zu erhalten?

[drakon]

Am einfachsten so, wie es hustbaer gezeigt hat.

Beachte, dass auto_ptr ein Smart Pointer ist und den Speicher, den du mit new angelegt hast wieder frei gibt.

[seldon]

Ganz direkt geht Folgendes:

int (*h)[2][4][3][21][730] = new int[2][2][4][3][21][730];

// ...

delete[] h;

Aber ich bin wirklich der Ansicht, dass Boost.Multi-Array die einfachste Möglichkeit ist - hauptsächlich aus Gründen der Exception-Sicherheit. Einen Block Speicher dieser Größe willst du wirklich nicht verlieren.

[snOOfy]

Ok, ich fasse mal zusammen. Man macht es entweder mit boost, was ich aber nicht so gerne machen möchte, da dann alle, die an dem Projekt mitarbeiten, das erst mal installieren müssen. Oder man benutzt eine der folgenden drei Möglichkeiten:

#include <vector>;
#include <iostream>;
using namespace std;

int main(char* argv[]) {
	// Möglichkeit 1 mit vector
	vector<vector<vector<vector<vector<vector<int> > > > > > h1(2, 
			vector<vector<vector<vector<vector<int> > > > >(2, 
			vector<vector<vector<vector<int> > > >(4, 
			vector<vector<vector<int> > >(3, 
			vector<vector<int> >(21, 
			vector<int>(730))))));
	h1[1][1][1][1][1][1] = 42;
	cout << h1[1][1][1][1][1][1] << endl;

	// Möglichkeit 2 mit struct
	struct InfRegAgeHeaInfDay {
			int data[2][2][4][3][21][730];
	};
	auto_ptr<InfRegAgeHeaInfDay> h2(new InfRegAgeHeaInfDay());
	(*h2).data[1][1][1][1][1][1] = 43;
	cout << (*h2).data[1][1][1][1][1][1] << endl;

	// Möglichkeit 3 mit pointer
	int (*h3)[2][4][3][21][730] = new int[2][2][4][3][21][730];
	h3[1][1][1][1][1][1] = 44;
	cout << h3[1][1][1][1][1][1] << endl;
	delete[] h3; 

	system("PAUSE");
}

Davon ist die erste wohl die schlechteste, da für jedes Array ein riesen Schreibaufwand entsteht und Compileroptimierungen bei der Indexberechnung verloren gehen.
Die zweite hat eine etwas unübersichtliche Syntax und ich sehe keinen konkreten Vorteil zur Möglichkeit 3.
Ich werde also trotz der Exception-Unsicherheit (ist das tatsächlich ein Problem?) die dritte verwenden, da ich dann fast nichts am bestehenden Code ändern muss.

[ipsec]

Wie wäre es damit:

struct MyBigArray
{
    int (*data)[2][4][3][21][730];

    MyBigArray()
    {
         data = new int[2][2][4][3][21][730];
    }

    ~MyBigArray()
    {
        delete[] data;
    }

    int (*operator [])(std::size_t idx)[2][4][3][21][730]
    {
        return (*data)[idx];
    }
};

...

MyBigArray a;
a[1][1][1][1][1][1] = 45;

(ungetestet, möglicherweise mit Schreibfehlern)

[seldon]

Naja, der Punkt ist, dass du darauf achten musst, dass der Speicher auch aufgeräumt wird, wenn eine Exception geworfen wird - etwa führt

int (*h3)[2][4][3][21][730] = new int[2][2][4][3][21][730];

throw std::logic_error("Ups, Fehler!");

delete[] h3;

zu einem Speicherleck. boost::multi_array löst das Problem per RAII, wie es in C++ zur Ressourcenverwaltung üblich ist.

Man kann das relativ einfach ranpatchen:

template<typename array_t>
class array_memory_guard {
public:
  array_memory_guard(array_t *data): data_(data) { }
  ~array_memory_guard() { delete[] data_; }
private:
  array_t *data_;
};

// ...

{
  int (*h3)[2][4][3][21][730] = new int[2][2][4][3][21][730];
  array_memory_guard<int[2][4][3][21][730]> memguard(h);

  throw std::logic_error("Ups, Fehler!");
} // Speicher wird hier aufgeräumt

..worin der Destruktor des "Speicherwächters" beim Verlassen des Scopes auch durch eine Exception den Speicher aufräumt. Wenn du Boost wirklich nicht benutzen willst, ist das eine Option, aber die Eigenschaftsverhältnisse sind hier natürlich deutlich weniger sauber.

[hustbaer]

// Möglichkeit 2.5 mit struct und pointer
    struct InfRegAgeHeaInfDay {
            int data[2][2][4][3][21][730];
    };
    auto_ptr<InfRegAgeHeaInfDay> guard(new InfRegAgeHeaInfDay());

    int (*const h25)[2][4][3][21][730] = guard->data;
    h25[1][1][1][1][1][1] = 44;
    cout << h25[1][1][1][1][1][1] << endl;
    // freigeben tut der guard, wir müssen nur drauf achten h25 nimmer zu verwenden nachdem guard gestorben ist

EDIT
@seldon: dein Guard sollte noch noncopyable sein

[snOOfy]

Wunderbar, dann nehm ich 2.5
Danke für all die Antworten.

[seldon]

Hustbaers Ansatz gefällt mir für diesen Anwendungsfall. Bestechend einfach, und die ganze Arbeit wird von Standardmechanismen übernommen - wenig Gefahr, etwas zu übersehen (wie die Kopierbarkeit des Speicherwächters) und wenig Arbeit. Die Rückgabe aus Funktionen ist damit auch einfach möglich.

ipsecs Ansatz ist natürlich sehr luxuriös, wenn man sich die Arbeit macht, das Interface zu vervollständigen. Je öfter derartiger Code öfter im Programm benutzt wird, desto sinnvoller wird diese Variante - das bewegt sich vom Grundgedanken her ja schon in die Richtung des genannten Multi-Arrays.

Ich ziehe also meinen Vorschlag zurück. Bessere sind gemacht worden.