Fragmentiertes Datenfeld

Fragmentierte Datenfelder, also Datenfelder mit leeren Feldern, können je nach Aufgabengebiet auftreten. Wenn die Möglichkeit nicht besteht, das Feld durch verwerfen der leeren Zellen, zu verdichten, aber die leeren Felder wiederbenutzt werden soll, kann das hier beschriebene System helfen. Natürlich können leere Felder immer mit einer linearen Suche auf dem Datenfeld gefunden werden. Das lineare Verfahren hat aber seine Schwächen, spätestens bei großen Datenfeldern könnte die Suchzeit für sinnvollere Aufgaben verwendet werden.

Beispiel (Quellcode): fragmentedobjectallocator.cpp
Download (Quellcode): fragmentedobjectallocator.zip

Beschreibung

Wenn aus einem fragmentierten Datenfeld ein Feld gelöscht wird, kann dessen Index in eine Warteschlange oder einen Stapelspeicher geschrieben werden. Beim Anfordern eines neuen Feldes, wird nur der letzte Eintrag aus diesem Stapelspeicher zurückgegeben. Da beim Start noch kein Feld angefordert wurde und eine Ersterstellung des kompletten Stapels riesen Arbeit wäre, kann ein Hilfszähler benutzt werden, der das letzte ausgegebene Feld anzeigt.

Vorteil ist, der Code "weiß" sehr schnell welches Feld als nächstes frei zu benutzen ist und ist oft schneller als eine Speicheranforderung durch einen anderen Allokator (auch wenn dieser Buckets etc. hat).

Nachteile: Datenfeld verkleinern ist schwierig, da die Fragmente im Stapelspeicher geprüft werden müssen, ob diese außerhalb der neuen Maximalgröße liegen. Da Datenfelder mehr oder weniger statisch sind, ist eine Vergrößerung dieses mit Aufwand verbunden.

Somit, ist dies leider nicht, ohne Modifikation, für jede Anwendung geeignet und es muss abgewogen werden zwischen Geschwindigkeit und Speicherbenutzung. Wie überall im Umfeld der Algorithmen auf derartigen Systemen.

Durch den Beispielcode

Der Beispielcode, enthält mehrere Klassen (C++), für Tests und Beispiele:

der Konstruktor
```
CFragmentedObjectAllocator(size_t nSize);
```
```
21
```
Beim Erzeugen der Klasse wird die Größe des Datenfeldes angegeben.
Anfordern eines Feldes
```
_TYPE* Allocate();
```
```
27
```
Gibt ein freies Feld zurück oder nullptr wenn die Größe des Datenfeldes überschritten ist.
Freigeben eines Feldes
```
void Free(const _TYPE* pObject;
```
```
36
```
Legt ein Feld zurück in den Stapelspeicher freier Felder.

Codeanmerkungen

Der Beispielcode enthält eine Klasse die das fragmentierte Feld benutzt und Zeiten mit und ohne diese Veränderung ausgibt.

Der letzte Aufparameter gibt den suchenden Schlüssel an, der Rest wird als Schlüssel mit einem Pseudoindex hinzugefügt:

for(int n=1; n<argc-1; n++)
   index.Add(argv[n]);

180
181

So ergibt

./fragmentedobjectallocator dies ist ein test ein

die Ausgabe

Fragmented Object Allocator test...

   Fragmented object allocator 896ms for 100000 iterations
   'ein' found
   Normal object allocator 3924ms for 100000 iterations
   'ein' found