[C] Memory pool maken

[CurlyMo]

Ik probeer dus een memory pool te ontwikkelen maar loop een beetje vast op een tweetal aspecten.

De basis is dat ik een block geheugen alloceer van een zekere grootte. Dat is de pool die ik tot mijn beschikking heb. Voorbeeldje van een pool van 128Kb

pool #1, overhead 18, size 128
        block #0, size 110, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 3, claimed 1, from: test.c:83
        block #21, size 89, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 3, claimed 1, from: test.c:83
        block #21, size 16, claimed 1, from: test.c:85
        block #55, size 55, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 3, claimed 1, from: test.c:83
        block #21, size 16, claimed 1, from: test.c:85
        block #55, size 16, claimed 1, from: test.c:87
        block #89, size 21, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 3, claimed 1, from: test.c:83
        block #21, size 16, claimed 0, from: n/a
        block #55, size 16, claimed 1, from: test.c:87
        block #89, size 21, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 3, claimed 1, from: test.c:83
        block #21, size 89, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 110, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 110, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 110, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 30, claimed 1, from: test.c:101
        block #48, size 62, claimed 0, from: n/a

pool #1, overhead 18, size 128
        block #0, size 110, claimed 0, from: n/a

Elk block begint met een header wat hier de overhead wordt genoemd:

C:

typedef struct block_t {
    unsigned short claimed;
    unsigned int size;
    const char *file;
    int line;
} __attribute__((packed)) block_t;

Wat je hier ziet is de volgende sequentie:

C:

    mempool_init(128, 1);
    mempool_print();
    char *a = MALLOC(3);
    mempool_print();
    char *b = MALLOC(16);
    mempool_print();
    char *c = MALLOC(16);
    mempool_print();
    FREE(b);
    mempool_print();
    FREE(c);
    mempool_print();
    FREE(a);
    mempool_print();
    char *d = MALLOC(106);
    mempool_print();
    FREE(d);
    mempool_print();
    char *e = MALLOC(30);
    mempool_print();
    FREE(e);
    mempool_print();
    mempool_destroy();

Nu de nadelen waar ik niet goed van weet hoe ik het het beste kan oplossen:
- Als de pool groter is dan duurt het bij vele kleine allocaties relatief lang om een geschikt leeg blok te vinden.
- Bij het vrijgegeven van het geheugen dient vanaf het begin de pool doorzocht te worden om het juiste gealloceerde blok te vinden. In mijn huidige implementatie worden opeenvolgende lege blokken samengenomen tot weer één groot leeg blok van alle opgetelde bytes. Daarvoor is het nodig om te weten wat het voorafgaande blok was. Aangezien niet duidelijk is hoe groot het voorgaande blok is, moet ik vanaf het begin beginnen met zoeken. Ook dat duurt vrij lang.

Ik ben dus benieuwd hoe memory pool implementaties hier doorgaans mee omgaan en of er theorieën of standaarden over zijn die ik nog niet ken?

[citizen2x]

Hoort er een bepaalde patroon bij de lifecycle van wat je code malloct?

Indien wel, kan het soms erg effectief zijn om je memory pool strategie daarop af te stemmen:

code:

1 - need memory for xyz data, create_pool()

2 - alloc some xyz, call malloc(size): 
   malloc:
   at least <size> free bytes avail in current block?
   -> yes: cool, subtract <size> from block free bytes and return pointer
   -> no: too bad, alloc new block of at least <size> bytes and
      set it to current, then do 2      
   free: 
    NOP
       
3 do stuff, repeat 2..

4 - done? free_pool() //the entire pool

Heet ook 'memory arenas', hier wordt het (veel ) beter uitgelegd:
https://news.ycombinator.com/item?id=26938367


Grt

[ Voor 5% gewijzigd door citizen2x op 06-06-2021 07:10 ]

[CurlyMo]

citizen2x schreef op zondag 6 juni 2021 @ 07:07:
Hoort er een bepaalde patroon bij de lifecycle van wat je code malloct?

Indien wel, kan het soms erg effectief zijn om je memory pool strategie daarop af te stemmen:

Heet ook 'memory arenas', hier wordt het (veel ) beter uitgelegd:

Dat is ook precies wat ik probeer te realiseren en wat in de basis prima werkt. Het probleem is echter de efficiëntie. Zodra de arena groter wordt, dan is de allocatie velen malen slomer omdat het meer iteraties kost om een vrij blok te vinden.

[citizen2x]

CurlyMo schreef op zondag 6 juni 2021 @ 08:44:
[...]

Dat is ook precies wat ik probeer te realiseren en wat in de basis prima werkt. Het probleem is echter de efficiëntie. Zodra de arena groter wordt, dan is de allocatie velen malen slomer omdat het meer iteraties kost om een vrij blok te vinden.

Omdat in het geval van de arena allocator FREE een NO-OP is, je werkt altijd met slechts *een* blok wat free space bevat, de 'current block'. De andere blokken zijn, per definitie, al 'vol' (dus wel wat "memory waste", maar in het algemeen betere performance)

[ Voor 6% gewijzigd door citizen2x op 06-06-2021 08:57 ]

[CurlyMo]

citizen2x schreef op zondag 6 juni 2021 @ 08:52:
[...]


Omdat in het geval van de arena allocator FREE een NO-OP is, je werkt altijd met slechts *een* blok wat free space bevat, de 'current block'. De andere blokken zijn, per definitie, al 'vol' (dus wel wat "memory waste", maar in het algemeen betere performance)

Dat begrijp ik. Het verschil met mijn eigen implementatie is dat ik niet een arena per doel alloceer, maar een groter geheugengebied reserveer voor allerhande allocaties van verschillende doelen.

[citizen2x]

wat soms ook helpt is om "bitmaps" te maken van je block, waar bijvb:

code:

1bit = 16bytes
where
0 = free
1 = taken

malloc kan een bitmap tabel gebriuken om de search sneller te maken. Een wellicht nog sneller op X86's met trucjes zoals BSF & POPCNT.

Wat voor free betreft, kan een LRU/MRU cache *soms* helpen met performance.

.

[CurlyMo]

citizen2x schreef op zondag 6 juni 2021 @ 09:34:
wat soms ook helpt is om "bitmaps" te maken van je block, waar bijvb:

Is dat hoe dit bij bijv. filesystems die met fixed blocksizes werken wordt gedaan zoals ZFS?

[ Voor 15% gewijzigd door CurlyMo op 06-06-2021 09:51 ]

[citizen2x]

CurlyMo schreef op zondag 6 juni 2021 @ 09:50:
[...]

Is dat hoe dit bij bijv. filesystems die met fixed blocksizes werken wordt gedaan zoals ZFS?

ja, interessant, ik ben niet zo bekend met ZFS, maar mogelijk wel.

Voor wat malloc & bitmaps betreft, ik heb wat slides van de Uni.Illinois gevonden:

https://courses.engr.illinois.edu/cs241/sp2011/lectures/21-MemoryAlloc.pdf

happy coding.

[farlane]

Geen directe oplossing of antwoord op je vraag maar:

https://github.com/foonathan/memory
https://github.com/emeryberger/Hoard

Ik vermoed overigens dat je packed meer kwaad doet dan goed, performance wise. Ik zou wat dat betreft die ouderwetse manier van denken ("ik weet het beter dan de compiler(bouwers)" een beetje proberen lost te te laten.

[CurlyMo]

farlane schreef op zondag 6 juni 2021 @ 20:17:
Ik vermoed overigens dat je packed meer kwaad doet dan goed, performance wise. Ik zou wat dat betreft die ouderwetse manier van denken ("ik weet het beter dan de compiler(bouwers)" een beetje proberen lost te te laten.

Packed is ook zo weer uitgezet

Verder is het gebruik van standaard libraries prima, behalve dat je er niks van leert. Er is een reden dat ik in C blijf programmeren, omdat ik daar het meeste lol uit haal. Een memory pool heb ik niet eerder geschreven en het goed doen is gewoon een leuke uitdaging. Vandaar dat ik vraag naar best practices en theorieën.

[bwerg]

CurlyMo schreef op zaterdag 5 juni 2021 @ 23:22:
Aangezien niet duidelijk is hoe groot het voorgaande blok is, moet ik vanaf het begin beginnen met zoeken. Ook dat duurt vrij lang.

Gek idee: zet dat ook in de header?

Kost natuurlijk wel allemaal overhead, dus misschien wil je dat niet. Je hebt natuurlijk altijd een afweging tussen ruimte-efficiëntie en tijds-efficiëntie.

[CurlyMo]

bwerg schreef op maandag 7 juni 2021 @ 14:07:
[...]

Gek idee: zet dat ook in de header?

Kost natuurlijk wel allemaal overhead, dus misschien wil je dat niet. Je hebt natuurlijk altijd een afweging tussen ruimte-efficiëntie en tijds-efficiëntie.

Nieuwe oplossing is de grootte in de laatste bytes van het blok te zetten.

[farlane]

CurlyMo schreef op zondag 6 juni 2021 @ 22:19:
[...]

Packed is ook zo weer uitgezet

Verder is het gebruik van standaard libraries prima, behalve dat je er niks van leert. Er is een reden dat ik in C blijf programmeren, omdat ik daar het meeste lol uit haal. Een memory pool heb ik niet eerder geschreven en het goed doen is gewoon een leuke uitdaging. Vandaar dat ik vraag naar best practices en theorieën.

Oh ja, daar was ik vanuit gegaan, de links waren om inspiratie uit op te doen.