MemoryPool mit Objekten unterschiedlicher Größe

[Xin]

Hi, ich habe mal wieder eins meiner merkwürdigen Sonderfall-Probleme. Ich suche einen Container, den ich ähnlich handhaben kann wie einen Vector. Nur kommen dort allerdings keine gleich großen Objekte rein.

Annahme:

Code: Alles auswählen

struct GeoObjekt {
  std::string getName() const;
};

struct Point : public GeoObject
{
  double x, y, z;
};

struct Segment : public Geo
{
  Segment( std::string const n ) : name(n) {}
  std::string name;
  Point start, end;
};

Was ich nun brauche ist quasi ein std::vector< GeoObjekt > in dem Linien und Segmente konstruiert werden können. Das Problem ist nun, dass ein Punkt 24 Byte groß ist und ein Segment 64 Bytes groß ist.

Der "Vektor" darf nicht realloziert werden. Ich muss also beliebig viele beliebig große Elemente reinwerfen dürfen, ohne dass der Speicher ausgeht. Und mit reinwerfen meine ich, dass die Elemente direkt im Vector erzeugt werden und nicht dort hinverschoben werden können. Dafür wäre vermutlich Placement-New erforderlich - ich würde mich allerdings über Alternativen freuen.

Code: Alles auswählen

myContainer c;

new( c.alloc< Segment >() ) Segment( "Hugo" );
new( c.alloc< Point >() ) Point;

Das Problem: Ich habe sehr, sehr viele kleine Objekte die einzeln im Speicher angelegt werden. Das kostet zum einen viel Zeit, zum anderen viel Speicher. Ich möchte also gerne Memory-Pools verwenden. Die Objekte sind natürlich alle unterschiedlich groß und dürfen - nachdem sie einmal erzeugt wurden - nicht mehr verschoben werden, weil Zeiger auf sie herumgereicht werden. Der Container muss sich also was anderes einfallen lassen, um zu wachsen.

Nun noch das Highlight: Der Container muss auf zwei verschiedene Weisen ansprechbar sein: Zum einen per Index (1, 2, 3, ...) und zum anderen haben manche Objekte Namen. Nicht alle. Aber manche. Und die muss ich wiederfinden, falls ich die Adresse nicht zur Hand habe.

Code: Alles auswählen

Point * p = dynamic_cast< Point * >( c[1] );
Segment * s = dynamic_cast< Segment * >( c["Hugo"] );

Hat jemand eine Idee, ob das Problem irgendwo jemand schonmal als Container bereitgestellt hat? ^^

[cloidnerux]

An sich ist mir kein Container bekannt, muss aber nichts heißen.
An sich fallen für dich ja auch die meisten Template-Container heraus, da du beim Cast zum Basisobjekt Informationen verlierst.

Wenn man dein Problem aber mal betrachtet, brauchst du einige Funktionalität nicht. Du wirst die Objekte zur Laufzeit nicht andauernd löschen und neu anlegen, daher ist eine Verwaltung nicht zu aufwendig.
Nimmt man nun bereits bekannte Konzepte zur Speicherverwaltung heran, kann man sich sicherlich was gutes Zusammenbauen.

Ich würde den Speicher in Pages unterteilen, sodass ich den Datensatz Segmentieren kann, ohne große Probleme zu bekommen. Pagegröße je nach zu erwartenden Datenmengen mal auf 4MB oder mehr festlegen.
Dann hast du eine Tabelle(mit klassischen containern oder statisch), die den absoluten Offset des Elementes mit dem Index i beinhaltet. Sinnvollerweise hat diese Tabelle n+1 Einträge, wobei der n+1 Eintrag das Ende des letzten Elementes kennzeichnet, da das nachträglich nicht so einfach zu berechnen ist. Dann noch eine Hashtable oder LuT mit Namen-Offset Paaren.

Zum Eintragen würde man als aus der Indextabelle die nächste freie Speicheradresse holen, berechnen in welcher Page diese liegt, checken ob noch genug Speicher frei ist in der Page, ansonsten eine neue Page anlegen. Objekt in dem Speicher anlegen, nächsten Offset in die Tabelle anlegen, evt Namen hinterlegen, Adresse zurück geben.

Zum Abrufen wieder per Index den Offset ermitteln, mit dem Offset die Page und den Offset innerhalb der Page ermitteln, Adresse zurück geben.

Dadurch das man sich keine Gedanken macht, wie man Objekte löscht und somit freien Speicher weiternutzen kann, sollte die Zeit zum Anlegen neuer Elemente recht zügig sein. Nachteil ist aber, dass du eine Grow-Only Struktur hast, mit jedem Objekt wächst das Dingen, schreit mitunter nach Memory-leak.

[Xin]

Ein halbes Problem weniger

Ich habe bei Base new überladen. Derived "pusht" den Namen in den Pool. Das ist so aber noch etwas waghalsig, denn "this" muss nicht unbedingt der Startpunkt des Memory-Blocks sein - oder überhaupt Teil eines von mir alloziierten Memory-Blocks.

Jetzt brauche ich noch eine Idee, wie ich den Namen in die Überladung von operator new bekomme.

Code: Alles auswählen

using XSD::Type::String;
using XSD::Test;

using namespace XSD::Type;

unsigned int const multiplicator = 4;

class Base
{
public:
  char useless[10];
  
  static XSD::Type::Pool pool;

  Base() {}
  virtual ~Base();
  
  void * operator new( std::size_t size ) { return pool.alloc( size ); }
  virtual bool identify( char const * identifier ) { return false; }
};

Base::~Base() {}
XSD::Type::Pool Base::pool( 0, multiplicator );

class Derived : public Base
{
public:
  char moreuseless[5];
  char const * Identifier;
  
  Derived() {}
  Derived( char const * id ) : Identifier( id ) 
  {
    pool.push( id, this );
  }
  virtual ~Derived();
  
  virtual bool identify( char const * identifier ) override { return identifier && !strcmp( identifier, Identifier ); }
};

Derived::~Derived() {}

class Block : public Base
{
public:
  char moreuseless[1000];
};


unsigned int test_mempool( void )
{
  unsigned int expected = 0;
  unsigned int const baseSize = sizeof( Base );
  unsigned int const derivedSize = sizeof( Derived );
  unsigned int const blockSize = sizeof( Block );
  
  Base * items[100]; 
  unsigned int i = 0;
  
  Test::Chapter( "MemoryPool", "Insert and Resize" );
  
  XSD::Type::Pool & pool = Base::pool;
  
  Test::Compare( pool.Used(), 0u, "Used == 0");
  Test::Compare( pool.Allocated(), 0u, "Size == 0");
  Test::Compare( pool.Elements(), 0u, "0 Elements");
  
  items[i++] = new Base();
  expected += baseSize;
  
  Test::Compare( pool.Used(), expected, "Used == 1*expected");
  Test::Compare( pool.Allocated(), multiplicator * baseSize, "Size 1 Base Element");
  Test::Compare( pool.Elements(), 1u, "1 Elements");
  
  Test::Compare( pool[0], items[0], "Pool Index 0" );

  items[i++] = new Base();
  expected += baseSize;
  
  Test::Compare( pool.Used(), expected, "Used == 2*expected");
  Test::Compare( pool.Allocated(), multiplicator * baseSize, "Size 2 Base Elements");
  Test::Compare( pool.Elements(), 2u, "2 Elements");

  for( unsigned int j = 0; j < 9; j++ )
  {
    items[i++] = new Base();
    expected += baseSize;
  }

  Test::Compare( pool.Used(), 11 * baseSize, "Used == 11 Base");
  Test::Compare( pool.Elements(), 11u, "11 Elements");
  Test::Compare( pool.Allocated(), 12 * baseSize, "Size 11 Base Elements");

  char const * names[] = { "elf", "zwölf", "dreizehn", "vierzehn", "fünfzehn", "sechszehn", "siebzehn", "achtzehn", "neunzehn", "zwanzig", "einundzwanzig" };
  
  for( unsigned int j = 0; j < 10; j++ )
  {
    items[i++] = new Derived( names[j] );
    expected += derivedSize;
  }

  Test::Compare( pool.Used(), 11 * baseSize + 10 * derivedSize, "11+10 Elements Used Memory");
  Test::Compare( pool.Elements(), 21u, "21 Elements");
  Test::Compare( pool.Allocated(), 12 * baseSize + 12*derivedSize, "Size 12 Base Elements");

  items[i++] = new Block();
  expected += blockSize;
  
  Test::Compare( pool.Used(), 11 * baseSize + 10 * derivedSize + blockSize, "11+10+1 Elements Used Memory");
  Test::Compare( pool.Elements(), 22u, "21 Elements");
  Test::Compare( pool.Allocated(), 12 * baseSize + 12*derivedSize + 4*blockSize, "Size 12 Base Elements");

  for( unsigned int j = 0; j < 9; j++ )
  {
    items[i++] = new Base();
    expected += baseSize;
  }
  
  Test::Compare( pool.Used(), 20 * baseSize + 10 * derivedSize + blockSize, "11+10+1 Elements Used Memory");
  Test::Compare( pool.Elements(), 31u, "21 Elements");
  Test::Compare( pool.Allocated(), 12 * baseSize + 12*derivedSize + 4*blockSize, "Size 12 Base Elements");
  
  Test::Chapter( "MemoryPool", "Access" );
  
  for( unsigned int j = 0; j < pool.Elements(); j++ )
  {
    char temp[30];
    sprintf( temp, "Access Item %d\n", j );
    Test::Compare( pool[j], items[j], "Item 0" );
  }
  
  Test::Compare( pool[4711], nullptr, "Item 4711 -> nullptr" );
  
  void * temp = pool[ XSD::Type::String( "zwölf" ) ];
  
  Test::Compare( temp, items[12], "zwölf -> 12" );
  
  unsigned int index;
  pool.indexOf( temp, index );

  Test::Compare( index, 12u, "zwölf has index 12" );

  return 0;

[mfro]

Vielleicht nochmal einen Schritt zurücktreten und sich das Ganze aus der Entfernung angucken. Ohne weitere Info, warum Du das unbedingt so brauchst, ist das schwer einzuschätzen (drum mag es sein, daß ich auf dem Holzweg bin), aber irgendwie werd' ich das Gefühl nicht los, Du siehst den Wald vor Bäumen nicht.

Ein Container, der Elemente (zweier oder mehrerer) unterschiedlicher Größen enthält, muß zum Zugriff auf ein einzelnes Element immer traversiert werden (schließlich weiß man ja nicht, wo das gesuchte Element sein könnte, ohne die Größe aller vorherigen Elemente zu kennen und aufzuaddieren). Irgendwie kann ich mir nicht vorstellen, daß das - egal was man treibt - sonderlich effektiv werden kann.

Wäre es nicht viel gescheiter, statt eines einzigen Containers zwei (einen für die Liniensegmente, einen für die Punkte) in einem dritten zu kapseln und über den den Zugriff zu regeln (Element(5) ist ein Punkt und deshalb in Punkte(2) zu finden)? Selbstverständlich braucht man dazu eine weitere Indirektion, aber der Zugriff ist letztendlich sicherlich deutlich effektiver. Ebenso kann man die Speicherverwaltung auf die jeweilige Elementgröße optimieren und deine Namen kannst Du in der Kapsel auch gleich unterbringen.

[Xin]

Vielleicht nochmal einen Schritt zurücktreten und sich das Ganze aus der Entfernung angucken. Ohne weitere Info, warum Du das unbedingt so brauchst, ist das schwer einzuschätzen (drum mag es sein, daß ich auf dem Holzweg bin), aber irgendwie werd' ich das Gefühl nicht los, Du siehst den Wald vor Bäumen nicht.

Das kann man nie ausschließen.

Ein Container, der Elemente (zweier oder mehrerer) unterschiedlicher Größen enthält, muß zum Zugriff auf ein einzelnes Element immer traversiert werden (schließlich weiß man ja nicht, wo das gesuchte Element sein könnte, ohne die Größe aller vorherigen Elemente zu kennen und aufzuaddieren). Irgendwie kann ich mir nicht vorstellen, daß das - egal was man treibt - sonderlich effektiv werden kann.

Oder man schafft einen Vector, der den Index auf die Adresse des Objektes umlegt. Die Adressen sind immer gleich groß, die Traversion ist also unabhängig von der Größe der Objekte.

Wäre es nicht viel gescheiter, statt eines einzigen Containers zwei (einen für die Liniensegmente, einen für die Punkte) in einem dritten zu kapseln und über den den Zugriff zu regeln (Element(5) ist ein Punkt und deshalb in Punkte(2) zu finden)? Selbstverständlich braucht man dazu eine weitere Indirektion, aber der Zugriff ist letztendlich sicherlich deutlich effektiver. Ebenso kann man die Speicherverwaltung auf die jeweilige Elementgröße optimieren und deine Namen kannst Du in der Kapsel auch gleich unterbringen.

Ich habe nicht nur Punkte und Linien. Aktuell dürfte ich bei um die 100 unterschiedlicher Objekttypen liegen und das wird sich vermutlich noch verdoppeln.

Ich versuche Abstract-Syntax-Tree-Knoten platt zu klopfen. Das wäre zum Beispiel ein Baum wie "1+2", der aus drei Knoten besteht: + und den beiden Blättern 1 und 2. Möglichkeit 1 ist, zur Compile-Zeit solche Elemente zu erkennen und zu vernichten. Aus den drei Knoten wird einer: 3. Bei einem Baum wie "a+2" geht das aber nicht mehr, denn diesen muss ich zur Laufzeit auswerten.
Nun haben wir für einen Ausdruck wie "a+2" schon drei unterschiedliche Knotentypen: Die Addition und die zwei Blätter Lesezugriff auf "a" und den Integer-Wert 2.
Sobald das Programm etwas Nennenswertes tut, erhalten wir ASTs mit Tausenden oder Millionen Knoten. Nehmen wir an, jeder Knoten ist im Schnitt 40 Byte groß, so haben wir bei einer Million Knoten 40 Megabyte Nutzdaten und eine unglaubliche Menge an Verwaltungsdaten für den Speicher.
Es gibt zwei Strategien: Man macht alle Knoten gleich groß, also so groß, wie der größte Knoten ist und fertig. Software-technisch allerdings ein Albtraum, da das Basisobjekt alle Variablen kennen muss, die man in einer Spezialisierung benötigen würde. Machbar, aber unschön. Man kann es automatisiereren, aber das treibt die Compile-Zeit hoch. Auch unschön.
Oder man nimmt einfach Vererbung und fertig - dann sind die Knoten aber unterschiedlich groß. Dafür verbrauchen kleine Knoten aber eben auch weniger Speicher.


Nächster Schritt: Ich möchte den AST auf die Festplatte schreiben. Ich muss also alle Adressen durch Indizes austauschen. Und praktischerweise habe ich alle zu speichernden Daten in einem Memory-Pool, dem ich eine Adresse geben kann und der spuckt mir dafür einen Index raus. Aktuell muss ich in meiner Sprache "#includes" immer neu parsen. Ich möchte aber nur einen fertigen AST laden, die Indizes gegen Adressen austauschen und fertig.