Manuelle Speicherverwaltung von Records

[Namenloser]

Wenn man viele kleine Datensätze auf dem Heap allokiert, dann kann das je nach Memory Manager langsam sein und zu Heap-Fragmentierung führen. Man kann dem vorbeugen, indem man nicht jeden kleinen Block einzeln allokiert, sondern immer gleich größere Happen anfordert. Diese muss man dann selbst wieder in kleinere Blöcke aufteilen.

Man will z.B. Daten vom Typ TRecord verwalten.

Dazu allokiert nicht jeden Record einzeln, sondern gleich einen Speicherbereich, der genug Platz für beispielsweise 1000 TRecord s bietet – ich hab diesen Speicherbereich hier "Page" genannt, auch wenn es nichts mit einer Betriebssystem-Page zu tun hat. Zusätzlich zu den eigentlich Nutzdaten speichert man für jede der 1000 Elemente noch einen Zeiger auf das jeweils nächste, freie Element (beides zusammen habe ich "Block" genannt). So wird eine einfach verkettete Liste von freien Blöcken gebildet (wohl auch "freelist" genannt). Nach Initialisierung enthält diese Liste alle Blöcke der Page. Soll ein neuer TRecord allokiert werden, so entfernt man den ersten Block aus der Liste und gibt den Zeiger darauf zurück. Wenn die kein freier Block mehr verfügbar sein sollte, dann wird wieder eine neue Page mit Speicher für 1000 Records angelegt, und das Spielchen beginnt von vorn.

Das einzige, was etwas trickreich ist, ist dafür zu sorgen, dass am Ende der Speicher auch wieder freigegeben wird. Dazu speichert man in jedem nicht-freien Block noch einen Pointer auf die zugehörige Page, damit man beim Freigeben weiß, auf welcher Page dieser Block liegt. Außerdem speichert man alle Pages, die mindestens noch einen Block frei haben, in einer doppelt verketteten Liste. Immer wenn ein Block frei wird, wird die zugehörige Page in diese Liste eingefügt, und immer wenn der letzte Block belegt wird, wird die Page wieder daraus entfernt. Neue TRecord s werden immer auf der erstbesten freien Page angelegt. Wenn nach entsprechend vielen Freigaben irgendwann eine Page komplett leer ist, dann wird der von ihr belegte Speicher komplett wieder freigegeben. Somit ist sichergestellt, dass, wenn alle TRecord s freigegeben werden, auch wirklich der Speicher wieder frei ist.

Die Beispiele im Internet kümmern sich meist nicht um die Freigabe des Speichers und kommen daher ohne diese zweite Liste aus. Ich empfinde es aber als unsauber, den Speicher nicht wieder freizugeben.

Delphi-Quellcode:

type
  TRecord = record
    { ... }
  end;

type
  PRecordBlock = ^TRecordBlock;
  PRecordPage = ^TRecordPage;
  PRecordManager = ^TRecordManager;

  TRecordBlock = record
    Data: TRecord;
    case integer of
      0: (NextFree: PRecordBlock);
      1: (Page: PRecordPage);
  end;

  TRecordPage = record
    FirstFreeBlock: PRecordBlock;
    UsedBlockCount: integer;
    Next: PRecordPage;
    Prev: PRecordPage;
    Manager: PRecordManager;
    Blocks: array[0..1000 - 1] of TRecordBlock;
  end;

  TRecordManager = record
    Sentinel: TRecordPage;
  end;    

{ Record memory management internal routines }

procedure RecordPage_Init(Self: PRecordPage);
var
  i: integer;
begin
  for i := low(Self^.Blocks) to high(Self^.Blocks) - 1 do
    Self^.Blocks[i].NextFree := @(Self^.Blocks[i + 1]);
  Self^.Blocks[high(Self^.Blocks)].NextFree := nil;
  Self^.FirstFreeBlock := @(Self^.Blocks[0]);
  Self^.Next := nil;
  Self^.Prev := nil;
  Self^.UsedBlockCount := 0;
end;

procedure List_InsertItem(Item, Insert: PRecordPage);
begin
  Insert^.Next := Item^.Next;
  Insert^.Prev := Item;
  Insert^.Next^.Prev := Insert;
  Insert^.Prev^.Next := Insert;
end;

procedure List_RemoveItem(Item: PRecordPage);
begin
  Item^.Prev^.Next := Item^.Next;
  Item^.Next^.Prev := Item^.Prev;
end;

function RecordPage_NewBlock(Self: PRecordPage): PRecordBlock;
var
  Block: PRecordBlock;
  Prev, Next: PRecordPage;
begin
  Block := Self^.FirstFreeBlock;
  Self^.FirstFreeBlock := Block^.NextFree;
  inc(Self^.UsedBlockCount);

  Block.Page := Self;
  Result := Block;

  // if this page is full, remove it from the list of free pages
  if not Assigned(Self^.FirstFreeBlock) then
    List_RemoveItem(Self);
end;

procedure RecordBlock_Dispose(Self: PRecordBlock);
var
  Page: PRecordPage;
  Prev, Next: PRecordPage;
begin
  Page := Self^.Page;
  dec(Page^.UsedBlockCount);

  Self^.NextFree := Page^.FirstFreeBlock;
  Page^.FirstFreeBlock := Self;

  // if this page only became "free" by disposing this block, reinsert it
  // into the free list
  if not Assigned(Self^.NextFree) then
    List_InsertItem(@(Page^.Manager^.Sentinel), Page);

  // if this page is completely empty, remove it from linked list
  // and free memory
  if Page^.UsedBlockCount = 0 then
  begin
    List_RemoveItem(Page);
    Dispose(Page);
  end;
end;

function RecordManager_NewBlock(Self: PRecordManager): PRecordBlock;
var
  Page: PRecordPage;
begin
  if Self^.Sentinel.Next <> @(Self^.Sentinel) then
    Page := Self^.Sentinel.Next
  else
  begin
    New(Page);
    RecordPage_Init(Page);
    Page.Manager := Self;

    List_InsertItem(@(Self^.Sentinel), Page);
  end;

  Result := RecordPage_NewBlock(Page);
end;


{ Record memory management interface routines }

function NewRecord(Manager: PRecordManager): PRecord;
begin
  Result := PRecord(RecordManager_NewBlock(Manager));
end;

procedure DisposeRecord(Rec: PRecord);
begin
  RecordBlock_Dispose(PRecordBlock(Rec));
end;

procedure RecordManager_Init(Self: PRecordManager);
begin
  Self^.Sentinel.Next := @(Self^.Sentinel);
  Self^.Sentinel.Prev := @(Self^.Sentinel);
end;

Anmerkungen zum Code:
- NewRecord und DisposeRecord sind hier der eigentliche Ersatz für das normale New und Dispose . Die restlichen Routinen machen nur den internen Kram, den ich beschrieben habe.
- TRecordManager könnte man sich prinzipiell sparen und stattdessen eine einzige, globale Variable verwenden. Allerdings wäre das in Multi-Thread-Programmen ggf. problematisch.
- Unbedingt am Anfang RecordManager_Init aufrufen, um die verkettete Liste zu initalisieren.
- Namen im Code sind möglicherweise suboptimal, aber mir fällt aktuell nichts besseres ein.
- Man beachte, dass Data (TRecord ) das erste Element von TRecordBlock ist. So kann man direkt zwischen den Pointer-Typen casten, weil beide an der gleichen Adresse beginnen. Der Code nutzt das auch aus, also sollte man die Reihenfolge dort nicht verändern.