Habe mich entschlossen, ein bisschen Code zu stiften

[zeckensack]

Nachdem mir hier (http://www.forum-3dcenter.org/vbulletin/showthread.php?hreadid=24822) so schön geholfen wurde, bekommt ihr jetzt was zurück:
Einen ultraprimitiven 'Hunk' (Name inspiriert von Q3), der dynamisch 64 Byte große, perfekt alignete Speicherhappen verwalten kann.

Der Konstruktor bekommt als Parameter die maximal zu erwartende Speicherbelegung (diese wird auf die nächste 4k-Grenze aufgerundet). Dieser Speicher wird unterteilt in 4kB große 'blocks' (Bezeichnung aus dem Code), diese sind wiederum unterteilt in 'chunks' (dies sind die 64 Byte großen Häppchen). Es gibt zwei Verwaltungsstrukturen:

Hunk::block ist ein Array und speichert für jeden 'block'
1)Den Zeiger auf den vom System angeforderten Speicher
2)Die korrekt alignete Version dieses Zeigers
3)64 einzelne bits, die die Belegung der einzelnen 'chunks' speichern

Hunk::usage ist ein Bitfeld, daß für jeden 'block' genau ein Bit speichert. Ist der Block komplett voll, ist dieses Bit gesetzt, ist auch nur ein 'chunk' frei, ist das Bit leer. Auf diese Weise kann der Allokator schnell einen 'block' finden, in dem noch mindestens ein 'chunk' frei ist.

Dann gibt's noch den 'victim_cache'. Hier sind ein paar 'chunks' gespeichert, die nicht mehr verwendet werden. Sinn: der Allokator muß normalerweise einen Block mit mindestens einem freien Chunk suchen, dann einen Chunk auswählen und ein bisserl die Zeiger jonglieren. Der Victim-Cache vereinfacht diese Prozedur, was bei ständigem allocate/free potentiell deutlich schneller ist.

Einschränkung: Man kann nur Speicherhäppchen mit genau 64 Byte Größe auf den Hunk schmeißen. Das dafür sehr effizient. Sieht man auch daran, daß die 'wichtigen' Funktionen "allocate64" und "free64" heißen. Könnte man erweitern, war aber für meine Zwecke (noch) nicht notwendig.

Suppi: Die Speicherzuweisung (auf der System-Seite) erfolgt 'just in time', ie erst dann, wenn sie wirklich nötig wird. Freigegeben wird der Speicher erst dann, wenn der Hunk selbst wieder zerstört wird. Dadurch wird nur minimale Zeit in der Speicherverwaltung des Betriebssystems verbracht (was bei Windows eine ziemlich gute Idee ist ...).

Die Verwaltungsstrukturen summieren sich auf einen konstanten Overhead von 193 bit pro verwaltetem 4k-Block, respektive 6176 Byte pro verwaltetem MB, also 0,6%.
Dieser Speicher wird direkt bei der Initialisierung komplett abgegriffen.

[zeckensack]

So.
Der Header:
class
Hunk
{
public:
Hunk(const uint max_size);
~Hunk();

void* allocate64(); //will allocate a 64 byte aligned memory region
void free64(const void* location); //free it

private:
Hunk(); //no default constructor

uint max_blocks;

struct mem_block
{
void* allocation; //the pointer we get from malloc
void* aligned; //the aligned region we actually use
uint usage[2]; //one bit per 64byte chunk
};

mem_block* block;

uint* usage; //one bit per 4k block

struct victim
{
uint chunk : 6;
uint block : 26;
};

victim* victim_cache; //keep some recently freed chunks, so they can quickly be used for new allocations
uint num_victims;
uint max_victims;
};
Der Code
#include "Hunk.h"
#include <malloc.h>


#define SAFE_FREE(a) {if (a) {free(a); a=NULL;}}


Hunk::Hunk(const uint max_size)
{
max_blocks=(max_size+4095)>>12;
//allocate control structures
block=(mem_block*)calloc(max_blocks,sizeof(mem_block));
usage=(uint*)calloc((max_blocks+31)>>5,sizeof(uint));

num_victims=0;
max_victims=max_blocks>>5; //TBD, this setting sets aside two victims per 4k block
victim_cache=(victim*)calloc(max_victims,sizeof(victim));
}

Hunk::~Hunk()
{
//free victim cache
SAFE_FREE(victim_cache);
//free controlled memory
for (uint b=0;b<max_blocks;++b)
{
SAFE_FREE(block[b].allocation);
}
//free control structures
SAFE_FREE(block);
SAFE_FREE(usage);
}

void*
Hunk::allocate64()
{
uint vacant_block;
uint chunk;
//try to get an entry from the victim cache, so we don't have to search
if (num_victims)
{
--num_victims;
vacant_block=victim_cache[num_victims].block;
chunk=victim_cache[num_victims].chunk;

block[vacant_block].usage[chunk>>5]|=1<<(chunk&31); //mark chunk as used

if ((block[vacant_block].usage[0]==~0)&&
(block[vacant_block].usage[1]==~0))
//this block is completely full
usage[vacant_block>>5]|=1<<(vacant_block&31); //mark block as full

return((void*)(uint(block[vacant_block].aligned)+(chunk<<6)));
}
else
{
vacant_block=0;
//look for a block with at least one vacancy
while(1)
{
if (vacant_block==max_blocks) return(NULL); //we're completely full
if (usage[vacant_block>>5]&(1<<(vacant_block&31)))
{
++vacant_block; //skip over completely full blocks
}
else
break; //we found one
}

//check memory allocation for that block
if (block[vacant_block].allocation==NULL)
{
block[vacant_block].allocation=calloc(64,64);
//check alignment
if (uint(block[vacant_block].allocation)&63)
{
//reallocate a little bigger and align
block[vacant_block].allocation=realloc(block[vacant_block].allocation,4096+63);
block[vacant_block].aligned=(void*)((uint(block[vacant_block].allocation)+63)&~63);
}
else
block[vacant_block].aligned=block[vacant_block].allocation;
}

//find the unused 64 byte chunk (there _must_ be one)
for (uint chunk=0;chunk<64;++chunk) //64 chunks per block
{
if (block[vacant_block].usage[chunk>>5]&(1<<(chunk&31))) continue; //skip over used chunks
//we found it
block[vacant_block].usage[chunk>>5]|=1<<(chunk&31); //mark chunk as used

if ((block[vacant_block].usage[0]==~0)&&
(block[vacant_block].usage[1]==~0))
//this block is completely full
usage[vacant_block>>5]|=1<<(vacant_block&31); //mark block as full

return((void*)(uint(block[vacant_block].aligned)+(chunk<<6)));
}
}
return(NULL);
}

void
Hunk::free64(const void* location)
{
//find owning block
uint b=0;
uint chunk;
while (1)
{
if (b==max_blocks) return; //not ours

chunk=(uint(location)-uint(block[b].aligned))>>6;
if (chunk<64) break; //chunk lies in block #b
++b;
}

//mark chunk as unused
block[b].usage[chunk>>5]&=~(1<<(chunk&31));

//block now has at least one vacancy, mark accordingly
usage[b>>5]&=~(1<<b&31);

//try to add freed chunk to victim cache
if (num_victims<max_victims)
{
victim_cache[num_victims].block=b;
victim_cache[num_victims].chunk=chunk;
++num_victims;
}
}
Kommentare zum bombastischen Stil, Lobpreisungen und Flames erwünscht :)

[zeckensack]

Errr, ich vergaß:

typedef unsigned int uint;

Kann man sich ja fast denken :)

[Nasenbaer]

Wozu braucht man sowas ???

Mfg Nasenbaer

[zeckensack]

Originally posted by Nasenbaer
Wozu braucht man sowas ???

Mfg Nasenbaer Für ... ähh ... Speicherverwaltung?
Das ist quasi die andere Hälfte der Lösung für das Problem aus dem anderen Thread.

Die Variante da oben eignet sich wesentlich besser als Standard malloc/free, wenn man sehr oft kleinere Speicherbereiche reserviert und wieder freigibt :)