Zur Laufzeit festgelegte Feldgrößen in komplexen Datentypen



  • Auf den ersten Blick sollte sich aus std::vector die Lösung ableiten lassen: Die Klasse garantiert, dass alle Elemente in einem zusammenhängenden Speicherblock abgelegt werden und es wird explizit darauf hingewiesen, dass bei Erschöpfung dieses Speicherblockes alle Elemente umgelagert werden.
    ... Nur leider sagt das nichts darüber aus, wo dieser zusammenhängende Speicherbereich angelegt wird - das Ziel ist aber gerade, denselben direkt anliegend an den übrigen Variablen des Structs zu haben.
    Genauer nutzt std::vector einen std::allocator und derselbe diese Methode, also explizit den new-Operator, was bedeutet, dass der Speicherbereich irgendwo im Heap zu liegen kommt.

    Kein Glück damit.

    Dasselbe Spiel mit std::map - allokiert Schlüssel/Wert-Paare, aber dieselben irgendwo und sogar reichlich sicher nicht beieinander.

    Diese Erkenntnisse lassen zumindest eine Generalisierung der Aufgabenstellung zu:

    1. Wie reserviere ich einen arbiträr großen Speicherbereich auf dem Stack?
    2. Wie strukturiere ich pseudo-Struct/Member-mäßig einen arbiträr großen Speicherbereich?

    Damit ließen sich die ursprünglichen speziellen Probleme bequem lösen.

    Zu 1) - Es gibt wohl eine nicht-standardisierte Funktion alloca, die genau das tut. Es gibt reichlich Grund, diese nicht zu benutzen... Aber ist das denn wirklich der einzige Weg? Kann doch nicht angehen!
    Zu 2) - const Funktionen für die Offsets (gäben Zeiger zurück) sind eine mögliche Lösung. Einfacher?

    @anti-freak b:
    Tut diese Klasse nicht nichts anderes als die normale Eigenschaft einer Union zu kapseln? Ich sehe aber, wie Union vonnutzen sein kann:

    typedef union Element
    {
      <Elementtypen>
    } Element;
    
    vector<Element> Nest = new vector();
    vector.resize(<Gesamtgröße>/sizeof(Element));
    

    Damit hätte ich gegenüber meinem Struct-Beispiel nichts gewonnen - ich müsste immernoch die Offsets aufrechnen. Natürlich kann ich das tun, aber das konnte ich auch schon bei der "Oldschool"-Variante mit malloc.
    ... Vorteil ist natürlich, dass ich hier keine überlappenden Indizes mehr habe, also ist es zumindest schon einmal besser benutzbar als mein Entwurf
    - lässt aber dafür Lücken, sobald die Elementtypen nicht mehr alle gleich groß sind!

    Nachtrag:
    Habe Folgendes versucht:

    typedef struct Nest
    {
      double wert;
      double koordinaten[];
      double * wertigkeiten;
    } Nest;
    
    Nest * LeeresNest(const unsigned int & dimension, const unsigned int & bewohner)
    {
      Nest * ausgabe = (Nest *)malloc((1 + dimension + bewohner) * sizeof(double));
    
      ausgabe->wertigkeiten = ausgabe->koordinaten + dimension;
    
      return ausgabe;
    }
    

    Hätte gegenüber einer Funktion den Vorteil, dass man die Feld-Syntax beibehalten könnte.
    - Funktioniert aber nicht. Wenn das nicht Ursache eines dummen Fehlers ist, den ich aufgrund der fortgeschrittenen Stunde gerade nicht erkenne, kann ich nicht einmal sagen, warum.

    Nachtrag 2:

    Upps, ich muss an den "Doof"-Knopf gekommen sein. Kann ja nicht gehen!
    So funktioniert's:

    typedef struct Nest
    {
      double wert;
      double * koordinaten;
      double * wertigkeiten;
    } Nest;
    
    Nest * LeeresNest(const unsigned int & dimension, const unsigned int & bewohner)
    {
      Nest * ausgabe = (Nest *)malloc(2 * sizeof(double *) + (1 + dimension + bewohner) * sizeof(double));
    
      ausgabe->koordinaten  = (double *)(&ausgabe->wertigkeiten + 1);
      ausgabe->wertigkeiten = ausgabe->koordinaten + dimension;
    
      return ausgabe;
    }
    
    int main()
    {
      Nest * nest = LeeresNest(2, 3);
      nest->wert = 1.;
      nest->koordinaten[0] = 2.;
      nest->koordinaten[1] = 3.;
      nest->wertigkeiten[0] = 4.;
      nest->wertigkeiten[1] = 5.;
      nest->wertigkeiten[2] = 6.;
    
      cout << nest->wert;
      cout << nest->koordinaten[0] << nest->koordinaten[1];
      cout << nest->wertigkeiten[0] << nest->wertigkeiten[1] << nest->wertigkeiten[2] << endl;
      //Ausgabe: 123456; Wunderbar.
    
      return 0;
    }
    

    Overhead hält sich auch in Grenzen: Zwei Zeigerauflösungen statt einer pro Feldzugriff. Wenn das nun noch herauszugeizen wäre, wär's natürlich ideal!



  • wenn ich das bis hierhin richtig verstanden habe (da bin ich mir absolut nicht sicher), dann hättest du gerne ein struct, was folgendes kann:
    - beliebig viele elemente aufnehmen (erst zur laufzeit bekannt)
    - diese elemente haben teilweise beliebige datentypen
    - der speicherbereich soll auf dem stack sein
    - der speicherbereich soll komplett zusammenhängend sein

    da drängt sich mir die frage auf, was hast du vor?
    auf der anderen seite, warum stellst du deine frage im C++ forum, schreibst aber alles in C? Denn:
    - zusammenhängenden speicher hast du bei std::vector (wie shcon jemand gesagt)
    - die Indizierung geht per Index oder mit anderen Datenstrukturen per beliebigen Typen
    - selbst die Typsicherheit kannst du mit boost::variant (heist das ding so?!) aushebeln/ausnutzen

    aber interessanter Sprachstil den du verwendest 🙂



  • boost::any heißt das, glaub ich.

    Also ich glaube, dass das nicht geht, weil man einfach nichts dynamisch auf dem Stack anlegen kann. Wieso soll das so sein?



  • Du kannst ein großes Array auf den Stack legen und den Allocator von std::vector umschreiben, dass er dieses benutzt.
    Alternativ selbst eine Klasse schreiben, die verschieden lange Arrays mit Operator [] unterstützt und ein statisches Array hat, das als Speicher dient. Das hat natürlich den Nachteil, dass du fast immer Speicher verschwendest oder dass der Speicher nicht reicht, weil es eben kein dynamischer Speicher ist.
    Der Sinn, warum der Stack besser als der Heap ist erschließt sich mir auch nicht, der Speicher ist überall gleich schnell.



  • 50% der Leute hier scheinen nicht mal die Frage zu raffen. 🙄

    @nwp3
    Nicht unbedingt. 1. ist der Stack wohl meistens im Cache. 2. könnte man sich so eine Dereferenzierung sparen, weil alles am Stück liegt. Das kann durchaus (deutliche) Performancevorteile bringen. Das Ziel bzw. der Wunsch des TEs ist durchaus nachvollziebar.

    Bleibt die Frage, wie man es sauber implementieren soll. Denn das Ganze bringt rein strukturell einige Probleme mit sich. Da die Größen nicht zur Compilezeit bekannt sind, sind alle dieser Dinger vom selben Typ. Niemand hindert einen also daran, einen std::vector<magic_type> anzulegen. Nur wird die Berechnung der Adresse von v[5] jetzt ziemlich aufwendig. Ich muss sagen, bei näherer Betrachtung macht es einfach nur mit Compiletime-Konstanten Sinn. Wenn man dann verschiedene haben will, nimmt man halt einfach Templates:

    template <std::size_t Size1, std::size_t Size2>
    struct foo
    {
      double a;
      double b[Size1];
      double c;
      double d[Size2];
      double e;
    };
    


  • cooky451 schrieb:

    50% der Leute hier scheinen nicht mal die Frage zu raffen.

    Du gehörst auch dazu.
    Denn er will die Grössen eindeutig zur Laufzeit festgelegt haben.

    Die einzige Möglichkeit, die ich sehe ist nonstandard mit alloca.



  • Offensichtlich hast du nicht mal meinen Beitrag gelesen. 🙄



  • raffzahn schrieb:

    cooky451 schrieb:

    50% der Leute hier scheinen nicht mal die Frage zu raffen.

    Du gehörst auch dazu.

    🙄

    cooky451 schrieb:

    Ich muss sagen, bei näherer Betrachtung macht es einfach nur mit Compiletime-Konstanten Sinn.



  • Könnt ihr Mal explizit werden? Ich verstehe Compiletime-Konstanten ebenfalls als nicht dem, was TE will, zugehörig.

    Ich bleibe dabei, dass man zur Laufzeit eben nicht dynamisch auf dem Stack allokieren kann, ohne dass man mehr Speicher verwendet als meist nötig (oder wirklich das nicht-portable alloca verwendet, das ich aber nicht kenne). Wo ist in der Lösung mit CompileTime-Konstanten die Laufzeitdynamik enthalten?

    Und wenn das so sinnvoll ist, wieso gibt es dann kein C++-Sprachmittel oder keine Variante mit boost? Ich kann auch nachvollziehen, dass der Stack bessere Cachelokalität bietet, aber es wird doch wohl triftige Gründe dagegen geben es so zu realisieren.



  • Eisflamme schrieb:

    Ich kann auch nachvollziehen, dass der Stack bessere Cachelokalität bietet, aber es wird doch wohl triftige Gründe dagegen geben es so zu realisieren.

    Es geht nicht nur um den Stack, sondern auch um die "fehlende" Dereferenzierung. Das kann z.B. sowas:

    for (auto& v : vv) 
      for (auto& e : v)
    

    Wesentlich effizienter machen, wenn die e's verschiedener v's alle hintereinander liegen, und nicht kreuz und quer im Speicher verteilt sind. Und das gibt es nicht, weil verschiedene Variablen vom gleichen Typ dann unterschiedlich groß sind, und damit das funktioniert bräuchte man wieder Pointer (z.B. vector<magic_type*> oder magic_list<magic_type> o.Ä.) oder eine ziemlich aufwendige Index-Berechnung, und dann hätte man das gerade Gewonnene direkt wieder verloren. 😉



  • Neben dem zusätzlichen Argument für den Stack habe ich jetzt nicht ganz verstanden, worauf Dein Argument bezogen war. War das eine Begründung dafür, warum C++ von Haus aus nicht dynamische Stackvariablen anbietet?



  • Das waren deine trifftigen Gründe:

    aber es wird doch wohl triftige Gründe dagegen geben es so zu realisieren.



  • Ah, okay, das hätte ich jetzt auch geraten, wollte aber sichergehen. Danke 🙂



  • Oh hé, da hat sich ja ganz schön 'was entwickelt. Schauen wir uns das einmal an...

    Erstmal die kontextfreien Sachen einzeln:

    Skym0sh0 schrieb:

    wenn ich das bis hierhin richtig verstanden habe (da bin ich mir absolut nicht sicher), dann hättest du gerne ein struct, was folgendes kann:
    - beliebig viele elemente aufnehmen (erst zur laufzeit bekannt)
    - diese elemente haben teilweise beliebige datentypen
    - der speicherbereich soll auf dem stack sein
    - der speicherbereich soll komplett zusammenhängend sein

    Ja und ja. Dann "nicht ganz". Der Speicherbereich soll dort sein (können), wo die Instanz erstellt wird, so wie hier:

    typedef struct Beispiel
    {
      double werte[10];
    } Beispiel;
    
    void mehrBeispiel()
    {
      Beispiel aufDemStack; // auch Beispiel.werte liegt auf dem Stack
      Beispiel * aufDemHeap = new Beispiel(); // Beispiel.werte liegt auf dem Heap  
    }
    

    Wenn nun werte durch Nest ersetzt würde, wäre es natürlich schön, wenn sich Nest ebenso verhalten könnte.
    Nicht weil es notwendig wäre sondern der Symmetrie wegen: Ein Datentyp, der nur eingeschränkt nutzbar ist, ist von Natur aus unintuitiv.
    Zuletzt: Ja.

    Skym0sh0 schrieb:

    da drängt sich mir die frage auf, was hast du vor?

    In dem Programm, das mich auf das Thema gebracht hat, brauche ich natürlicherweise Nest *, aber es geht mir um Vollständigkeit. Mit der Lösung in dem Beitrag vor dem hier zitierten habe ich eine halbe Definition meines gewünschten Datentyps.

    Skym0sh0 schrieb:

    warum stellst du deine frage im C++ forum, schreibst aber alles in C

    Nun ja, ich schreibe ein C++-Programm mit C++-Sprachmitteln. Dass der Ausschnitt, den ich hier präsentiere, nur C enthält, liegt daran, dass die elegantest mir in den Sinn gekommenen Repräsentationen meines abstrakten Gedankenmodells keine C++-Elemente enthielten, d.h. es war ein unglücklicher Zufall.
    Es ist aber auch impliziter (und vielleicht ist das ein Fehler meinerseits) Bestandteil der Frage:
    "Gibt es C++-spezifische Sprachelemente, die das Vorgehabte eleganter darstellen?"
    Außerdem limitiert die Wahl des C++-Unterforums die möglichen Antworten, die ich ja nicht kenne (was ich implizit durch das Stellen der Frage vermittelt zu haben glaubte - der archetypische Frager fragt wohl nicht sokratisch; dann wiederum: Das weiß ich nicht, habe es nur angenommen - vielleicht fälschlicherweise?), anders als eine hypothetische Wahl des C-Unterforums nicht auf reines C - was mir zugutekommt, weil ich im weiteren Programm ohnehin C++-Elemente verwende, also getrost auch hier C++-Spezifika einbringen kann.
    Die Vorschläge std::vector und std::map sind dieser Maßnahme zu verdanken. Dass ich sie nicht benutze, hat technische Gründe, keine sprachlichen:
    std::vector unterstützt nur gleich große Elemente und wäre verschwenderisch, wenn sich ihre Größe (wie im Beispiel Nest) unterschiede.
    std::map hat dasselbe Problem und ich glaube nicht, dass Schlüssel/Wert-Paare meiner Lösung überlegen sind:

    typedef struct Nest 
    {
      double wert;
      double * koordinaten;
      double * wertigkeiten;
    } Nest;
    
    Nest * LeeresNest(const unsigned int & dimension, const unsigned int & bewohner)
    {
      Nest * ausgabe = (Nest *)malloc(2 * sizeof(double *) + (1 + dimension + bewohner) * sizeof(double));
    
      // Mit ein wenig Optimismus kann ich annehmen, dass der Compiler die Nähe erkennt
      // und die doppelte Dereferenzierung doch noch herausoptimiert
      // - SO komplex ist das hier ja nun auch nicht
      ausgabe->koordinaten  = (double *)(&ausgabe->wertigkeiten + 1);
      ausgabe->wertigkeiten = ausgabe->koordinaten + dimension;
    
      return ausgabe;
    }
    

    Skym0sh0 schrieb:

    zusammenhängenden speicher hast du bei std::vector

    Klar, aber nicht arbiträr große Stückchen. Wenn es mir nur um zusammenhängenden Speicher ginge, nutzte ich malloc und byte.

    Wenn ich aber solch ein Wunderwerk zusammenstricke, dann sollte ich auch dafür sorgen, dass es "ganz ordinär", so wie man von den grundlegenden Sprachelementen gewohnt, benutzbar ist.

    Eisflamme schrieb:

    Also ich glaube, dass das nicht geht, weil man einfach nichts dynamisch auf dem Stack anlegen kann.

    Ich fürchte, so ist es, aber es liegt weniger am "nicht können" als am "kein Sprachmittel dafür haben". Rekursive Funktionen mit dynamischer Tiefe müssen ja auch irgendwie darauf, ist kein Problem so etwas zu implementieren und der Compiler kann zur Übersetzungszeit nicht wissen, wie tief das geht, wenn es bei jedem Lauf anders sein mag.

    unsigned int tiefe;
    
    void rekursivesBeispiel()
    {
      if(tiefe)
      {
        tiefe--;
        rekursivesBeispiel();
      }
    }
    
    int main(int argumentenzahl, char * argumente[])
    {
      tiefe = atoi(argumente[1]);
      rekursivesBeispiel();
    }
    

    Da kann es also auch nicht kümmern, wieviel Platz die einzelne Funktion beansprucht. Solange überhaupt genügend Platz vorhanden ist, natürlich.

    Problem ist mehr der Umstand, dass der Funktionsprototyp statisch am Anfang des Programmspeichers abgelegt wird (abhängig von Betriebssystemeinstellungen und Hardware auch noch in schreibgeschützte Bereiche) und keine Sprachelemente zur Reflektion existieren, mit denen man nach dem Kompilieren (wie es hier erforderlich wäre) noch etwas an demselben ändern könnte. Ein JIT-Compiler wie bei C# umgeht das Problem elegant, aber es direkt zu lösen ist... schwierig.

    Hätte ich daran früher gedacht, hätte ich die Frage wohl gar nicht gestellt; hatte es schlicht vergessen.
    Andererseits: Schwierig ist definitiv nicht unlösbar und vielleicht hätte ja jemand eine schwierige Lösung für das schwierige Problem parat gehabt.

    nwp3 schrieb:

    Du kannst ein großes Array auf den Stack legen und den Allocator von std::vector umschreiben, dass er dieses benutzt.

    Aber wenn ich wüsste, wie ich genau soviel Platz auf dem Stack reservieren kann, wie ich brauche, dann brauche ich doch std::vector und seinen Allocator ohnehin nicht mehr. Dann habe ich den Platz doch!

    nwp3 schrieb:

    Das hat natürlich den Nachteil, dass du fast immer Speicher verschwendest [...]

    Jau. Und deshalb kommt das wie anti-freaks 'b' nicht in die Tüte.

    ... Alles nach diesem Punkt:
    Gute Reflektion meiner Intention von cooky451, aber leider kein Fortschritt.
    Vergessen wir die Stack-Variante bis auf Weiteres. Solange es nur um Feldlängen geht, sollte sich mit ASM etwas machen lassen oder mit compilerspezifischen Funktionen, aber beides ist selbst meiner Meinung nach ein wenig zu aufwendig (und unsicher: compiler- und plattformabhängig) als dass es erkundungswürdig erschiene.
    Es sei natürlich denn, jemand hätte sich des Problems bereits irgendwann einmal angenommen und kennte bereits die Lösung. Hè, will ich es nicht doch einmal schildern? Hé, warum nicht!

    [definitiv offtopic]
    Beim Programmstart wird zunächst der übersetzte Programmcode in den Speicher geladen. Von &main aus kann man ihn sich recht einfach anzeigen lassen.
    Es folgt der Programmeinsprungpunkt, der Aufruf von main und von dort aus der Stack als zusammenhängender Speicherbereich. Wenn man Rücksprungaddressen entern oder ähnliche Hackerkunststückchen vollbringen möchte, ist man hier richtig.
    Enthält eine Funktion (Methoden zählen dazu) nun die Deklaration einer Struct-Variable, wird man im Aufruf dieser Funktion auch sehen, wie dieselbe instantiiert wird, speziell: woher im Codesegment der Bauplan stammt.
    Nun müsste man denselben ändern. Wie genau, das hängt davon ab, wie er aussieht, ist also compilerspezifisch. Vielleicht reicht es, die Literale zu überschreiben. Das wäre der einfachste Fall. Da es aber zur Übersetzungszeit bekannte, konstante Werte waren, hat der Compiler vielleicht auch eine Art VHDL::generate-for verwendet und jedes Byte explizit definiert. Dasselbe hoffentlich nicht inline, dann reicht es einen Zeiger zu überschreiben und den modifizierten Bauplan im Heap gelagert zu haben, die Referenz darauf umzuleiten. Sorgt natürlich dafür, dass die Erstellung neuer Instanzen ein bisschen langsamer wird, ist also eventuell nicht von Nutzen.
    Mag aber auch sein, dass der Bauplan inline in der Funktion steht, dann muss man entweder mit dem Platz auskommen, der dafür verwendet wurde, oder seine eigene Umleitung schreiben und wiederum einen im Heap erstellten Bauplan anzusteuern. Das ist schwierig.
    [/definitiv offtopic]

    Zusammengefasst hat man bei zwei von vier möglichen (mag sein, dass ich an weitere existierende nicht gedacht habe) Compilerverhaltensweisen die Möglichkeit nützlich einzugreifen. Das Dumme daran:

    * Wenn der Compiler irgendwann einmal anders zu funktionieren beginnen sollte, muss man das Ganze bei Null beginnen.
    * Gnade einem Gott, wenn man darüber nachsinnt, höhere Optimierungsstufen (z.B. g++ -O[1,2,3,s]) zu benutzen!
    * Anderer Compiler - großes Bangen: Funktioniert's? Oder eben nicht.

    Von daher braucht es meiner unerfahrenen Einschätzung nach zum lohnenswerten Weiterforschen eine spracheigene Reflektionsfähigkeit, die C++ nicht hat und vermutlich in absehbarer Zeit nicht bekommen wird. Ich muss zugeben, dass mich C++11 in dieser Hinsicht ein wenig enttäuscht hat, aber andererseits ist es tatsächlich ein hochspezifisches und keineswegs notwendiges Thema - ungünstige Kombination, höchst ungünstig.

    ...

    Liest jetzt noch irgendjemand mit, oder habe ich alle erfolgreich verschreckt?
    Hohum.
    Das Problem, auf das dieses hier zurückzuführen ist, ist die Starrheit des einmal compilierten Programmes. Zum Beispiel gibt es einen fundamentalen Unterschied zwischen:

    namespace G // globale Konstanten
    {
      constexpr int DIMENSION = 4;
    }
    
    int main()
    {
      <G::DIMENSION-dimensionale Berechnung>
    }
    

    und

    namespace G // globale Konstanten
    {
      unsigned int DIMENSION;
    }
    
    int main(int argumentenzahl, char * argumente[])
    {
      G::DIMENSION = atoi(argumente[1]); // erste und einzige Festlegung von G::DIMENSION
    
      <G::DIMENSION-dimensionale Berechnung>
    }
    

    Der Art und Weise wegen, wie Templates funktionieren (und ich muss einmal nachschlagen, was genau bei Variablen-großen Feldern passiert - würde mich nicht wundern, wenn da intern eine Ersetzung durch Zeiger und Heap-Speicher geschähe) hat man im ersten Fall größere Freiheiten als im zweiten, obwohl sich im eigentlichen Programmverlauf an den "gar nicht konstanten Konstanten" nie etwas ändert. Weil es sich nur um Zahlen handelt, wären Transformationsregeln, die zur Laufzeit ab Bekanntheit der Konstanten den Programmcode anpassen, durchaus denkbar... Nur haben die Compilerbauer vermutlich Besseres zu tun, solange derlei nicht explizit in einem Standard gefordert würde.
    ... Und nicht zu vergessen, wäre es eine wahrlich widerwärtige Fummelarbeit.

    Jau, lange Rede kurzer Sinn: Wenn nicht noch jemand einen tollen Einfall aus seiner Trickkiste zieht, erkläre ich das Thema für durch und erledigt.
    Vielen Dank für alle Vorschläge und die ertragene Marterung - meine nächste Frage wird (glaube ich) einfacher zu beantworten sein. Ja, ich habe schon eine.


Anmelden zum Antworten