Dit artikel legt uit waarom ArenaAllocators en ArrayLists (of Writer.Allocating) in Zig niet efficiënt samenwerken. Het kernprobleem is dat een ArenaAllocator alleen geheugen daadwerkelijk vrijgeeft als het de allerlaatste allocatie was en tot de huidige node behoort.
Bij de groei van een ArrayList gebeurt het volgende:
- Er wordt nieuw, groter geheugen gealloceerd.
- De data wordt gekopieerd naar dit nieuwe blok.
- Het oude geheugen wordt vrijgegeven.
Omdat de allocatie van het nieuwe geheugen plaatsvindt voordat het oude geheugen wordt vrijgegeven, is het oude geheugen niet langer de laatste allocatie, waardoor de Arena het niet kan terugwinnen. De auteur stelt twee oplossingen voor: vooraf de capaciteit bepalen (via initCapacity) of het vermijden van andere allocaties tijdens het toevoegen van data aan de lijst.
ArenaAllocators werken niet goed samen met ArrayLists
- Het vrijgegeven geheugen moet het laatst gealloceerde geheugen zijn.
- Het vrijgegeven geheugen moet gealloceerd zijn op de huidige node van de Arena (dit is een intern detail van hoe de Arena groeit).
Kijk naar de volgende code:
var a = try arena.alloc(u8, 100);
var b = try arena.alloc(u8, 100);
arena.free(b);
arena.free(a);
We kunnen er zeker van zijn dat het geheugen voor b wordt teruggegeven aan de arena, maar we kunnen niet zeggen wat er met het geheugen van a gebeurt. Waarom? b wordt vrijgegeven omdat het de laatste allocatie was en, per definitie, uit de huidige node van de arena moet komen. Nadat b is vrijgegeven, voldoet a aan de eerste vereiste: het wordt het laatst gealloceerde geheugen. We weten echter niet of de allocatie van b ervoor heeft gezorgd dat er een nieuwe node is aangemaakt; de huidige node van de arena is mogelijk niet dezelfde node waar a vandaan kwam.
Het probleem met ArrayLists
Mocht het concept van nodes verwarrend zijn, dan kun je het oorspronkelijke bericht lezen of het simpelweg negeren, want er is een veelvoorkomende situatie waarin de eerste, eenvoudigere regel niet wordt behaald: de groei van een ArrayList (of Writer.Allocating).
Wanneer gegevens aan een ArrayList worden toegevoegd, probeert deze eerst het bestaande geheugen opnieuw in te richten (grow-in-place). Als dat mislukt, alloceert de lijst een nieuw, groter stuk geheugen, kopieert de data en geeft vervolgens de vorige allocatie vrij.
Hier is de relevante code uit array_list.zig:
const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
gpa.free(old_memory);
Zelfs als je geen andere allocaties mengt met de groei van je ArrayList, zorgt de volgorde alloceren → kopiëren → vrijgeven ervoor dat oldmemory niet de laatste allocatie is (de laatste allocatie is immers newmemory).
Mogelijke oplossingen
Er is geen directe oplossing, maar er zijn twee dingen die je kunt doen:
- Bepaal vooraf de grootte van je ArrayList: Gebruik bijvoorbeeld
initCapacity of ensureTotalCapacityPrecise.
- Vermijd het mengen van andere allocaties met je appends of writes. Als je dit kunt doen, zul je vaker in de remap-branch terechtkomen en dit probleem omzeilen.
Beide methoden zijn nuttig, ongeacht welk type Allocator je gebruikt, maar bij een ArenaAllocator is het ergste scenario dat je ongeveer 3x zoveel geheugen verbruikt.
Ik weet dat dit voor de hand ligt, maar ik had er zelf nooit over nagedacht. Ik ben waarschijnlijk niet de enige.
ArenaAllocators werken niet goed samen met ArrayLists
- Het vrijgegeven geheugen moet het laatst gealloceerde geheugen zijn.
- Het vrijgegeven geheugen moet gealloceerd zijn op de huidige node van de Arena (dit is een intern detail van hoe de Arena groeit).
Kijk naar de volgende code:
var a = try arena.alloc(u8, 100);
var b = try arena.alloc(u8, 100);
arena.free(b);
arena.free(a);
We kunnen er zeker van zijn dat het geheugen voor b wordt teruggegeven aan de arena, maar we kunnen niet zeggen wat er met het geheugen van a gebeurt. Waarom? b wordt vrijgegeven omdat het de laatste allocatie was en, per definitie, uit de huidige node van de arena moet komen. Nadat b is vrijgegeven, voldoet a aan de eerste vereiste: het wordt het laatst gealloceerde geheugen. We weten echter niet of de allocatie van b ervoor heeft gezorgd dat er een nieuwe node is aangemaakt; de huidige node van de arena is mogelijk niet dezelfde node waar a vandaan kwam.
Het probleem met ArrayLists
Mocht het concept van nodes verwarrend zijn, dan kun je het oorspronkelijke bericht lezen of het simpelweg negeren, want er is een veelvoorkomende situatie waarin de eerste, eenvoudigere regel niet wordt behaald: de groei van een ArrayList (of Writer.Allocating).
Wanneer gegevens aan een ArrayList worden toegevoegd, probeert deze eerst het bestaande geheugen opnieuw in te richten (grow-in-place). Als dat mislukt, alloceert de lijst een nieuw, groter stuk geheugen, kopieert de data en geeft vervolgens de vorige allocatie vrij.
Hier is de relevante code uit array_list.zig:
const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
gpa.free(old_memory);
Zelfs als je geen andere allocaties mengt met de groei van je ArrayList, zorgt de volgorde alloceren → kopiëren → vrijgeven ervoor dat oldmemory niet de laatste allocatie is (de laatste allocatie is immers newmemory).
Mogelijke oplossingen
Er is geen directe oplossing, maar er zijn twee dingen die je kunt doen:
- Bepaal vooraf de grootte van je ArrayList: Gebruik bijvoorbeeld
initCapacity of ensureTotalCapacityPrecise.
- Vermijd het mengen van andere allocaties met je appends of writes. Als je dit kunt doen, zul je vaker in de remap-branch terechtkomen en dit probleem omzeilen.
Beide methoden zijn nuttig, ongeacht welk type Allocator je gebruikt, maar bij een ArenaAllocator is het ergste scenario dat je ongeveer 3x zoveel geheugen verbruikt.
Ik weet dat dit voor de hand ligt, maar ik had er zelf nooit over nagedacht. Ik ben waarschijnlijk niet de enige.
Groetjes,