Objekt variabler Größe mit placement new



  • Hallo,
    Achtung langer Eintrag mit haarsträubenden Speicherhacks 😃
    für einen performance-kritischen Teil meines Raytracers (kd-tree) brauche ich eine Menge relativ kleiner dynamischer Objekte (Knoten), die aber unterschiedliche Mengen an Daten "besitzen" können. Zum Beispiel kann ein Blatt des Baums auf eine variable Anzahl von anderen Objekten zeigen. Diese Referenzen sind bei meiner jetzigen Architektur vom Typ boost::intrusive_ptr<xy>, müssen also destruiert werden.
    Die Knoten sind im Moment mit std::auto_ptr verknüpft, was mir erlaubt, den Speicher für den Baum in einer einzigen Zeile root.reset() freizugeben. Schlecht daran ist jedoch, dass a) jeder noch so kleine Knoten auf dem heap erzeugt wird b) Blätter auchnoch std::vector<boost::intrusive_ptr<xy> > enthalten, was wieder Speicher auf dem Heap alloziert. Laut dem Buch "Physically Based Rendering" ist es sehr wichtig, den Speicher für die Knoten eines kd-trees nah beieinander zu halten, um Cache-Misses zu verhindern. (Die Autoren verwenden dafür miese Hacks mit union)
    Ich suche deshalb eine Möglichkeit alle Knoten in einem vorallozierten Speicherbereich abzulegen, auf std::vector zu verzichten und dabei die komfortable Möglichkeit des Kollabierens durch std::auto_ptr beizubehalten. Gegebene Voraussetzung: Der Baum wird nie teilweise zerstört und der ganze Speicherbereich kann deshalb auf einmal freigegeben werden.
    Ich habe ein bisschen Code zum Testen geschrieben, der aber sehr viele (unsichere) Pointercasts benutzt. Die Klasse dummy entspricht hier boost::intrusive_ptr<xy>, variable_length einem Blatt (innere Knoten haben feste Größe, also kein Problem). memory_range ist nicht viel mehr als das, was der Name schon sagt.

    #include <memory>
    #include <iostream>
    
    using namespace std;
    
    class memory_range
    {
      private:
      char* data;
      char* next;
      public:
      memory_range(size_t size) :data(new char[size]), next(data)
      {}
      ~memory_range()
      { delete[] data; }
      void* get(size_t size)
      {
        cout << "memory_range::get aufgerufen!" << endl;
        void* ret = next;
        next += size;
        return ret;
      }
    };
    
    class dummy
    {
      int foo;
      public:
      dummy(int bar) :foo(bar)
      { cout << "Dummy " << foo << " konstruiert." << endl; }
      ~dummy()
      { cout << "Dummy " << foo << " destruiert." << endl; }
    };
    
    class variable_length
    {
      unsigned length;
      public:
      variable_length(unsigned ilength) :length(ilength)
      {
        cout << "Konstruktion von variable_length mit Länge " << length << endl;
        dummy* dummies = (dummy*)(this + 1);
        for(unsigned i = 0; i < length; i++)
        {
          new(dummies) dummy(i);
          dummies++;
        }
      }
      ~variable_length()
      {
        cout << "Destruktion von variable_length mit Länge " << length << endl;
        dummy* dummies = (dummy*)(this + 1);
        for(unsigned i = 0; i < length; i++)
        {
          dummies->~dummy();
          dummies++;
        }
      }
    
      void* operator new(size_t size, memory_range& mr, size_t additional_size)
      {
        cout << "Fordere Speicher für variable_length an: " << size << " + " << additional_size*sizeof(dummy) << " bytes." << endl;
        return mr.get(size + additional_size * sizeof(dummy));
      }
      void operator delete(void* ptr)
      {
        cout << "Delete für variable_length aufgerufen" << endl;
        /*Speicher kann nicht an memory_range zurückgegeben werden,
    der Benutzer ist dafür verantwortlich, dass der Destruktor aller
    Objekte, für die Speicher in einer memory_range reserviert wurde,
    aufgerufen wird, bevor diese memory_range destruiert wird.*/
      }
    };
    
    int main()
    {
      memory_range mr(1024);
      //wenn variable_length anders konstruiert wird ist der Speicher zerschossen
      auto_ptr<variable_length> vl_ptr1(new(mr, 10) variable_length(10));
    }
    

    Funktioniert soweit, könnte also auf meinen kd-tree-Code übertragen werden. Nur bereiten mir die ganzen Pointer-Casts Bauchschmerzen: Was ist wenn das Alignment falsch ist oder der Compiler irgendeine Anordnung von Membern ändert? Gibt es nicht vielleicht eine schönere Mgölichkeit? Echte Arrays variabler Größe wie in C99 sind innerhalb von Klassen wohl nicht möglich. Wie kann ich verbieten, Instanzen von variable_length auf dem Stack zu erzeugen?
    Achja, std::vector habe ich rausgenommen weil ich per Allocator zwar Speicher aus dem gleichen Speicherbereich reservieren könnte, der vector aber einen speicherfressenden Pointer und womöglich noch mehr bereithält. Meine Klasse variable_length kann einfach davon ausgehen, dass alle Elemente im Speicher danach folgen.
    So, jetzt warte ich auf die Ohrfeige von den Experten... 🕶



  • Huhu? Experten?
    Vielleicht war die Warnung doch keine so gute Idee 😞



  • doch es laufen hier sicher einige leute rum die dir helfen können, nur du brauchst bei so einem komplexeren problem etwas geduld, warte mal drafu dass drakon, dravere und shade of mine das entdeckt haben und mal drüber nachgedacht haben...


Log in to reply