Re: memory pool library (repost)
- From: Grey Alien <grey@xxxxxxxxxxxxx>
- Date: Sat, 07 Jul 2007 09:30:35 +0100
Ben Bacarisse wrote:
Grey Alien <grey@xxxxxxxxxxxxx> writes:
I am looking to write a very simple memory pool library to store only
one data type at a time - i.e. to provide a contiguous block of memory
to be alloc'd free'd by the calling program. I am
I have come up with this API so far and will welcome any feedback on
it. In particular, I will need help with implementing the linked lists
used for record keeping as to which blocks were free or not (and for
"defragging" the pool when "holes" appear in the contiguous block)
OK, you have the API but maybe you could do this differently! The
costs of mallocs and frees can be ameliorated by replacing free with a
function that puts the block onto a "free chain" for a given size.
The allocator takes an item from the free chain (if there is one) and
calls malloc otherwise:
void *my_alloc(size_t s)
{
void *p;
size_t size_idx;
if (s >= MIN_ALLOC_SIZE && s < MAX_ALLOC_SIZE &&
free_chain[size_idx = s - MIN_ALLOC_SIZE] != NULL) {
p = free_chain[size_idx];
free_chain[size_idx] = *(void **)p; /* [1] */
}
else p = malloc(s);
return p;
}
A matching my_free never calls free -- it just puts the block into the
correct chain for its size.
This works very well when most of your program's allocations are of a
few known (and ideally small) sizes.
You can pre-prime the free chains with an initial list of blocks:
for (size = MIN_ALLOC_SIZE; size < MAX_ALLOC_SIZE; size++) {
int i;
for (i = 0; i < pre_alloc_count[size - MIN_ALLOC_SIZE]; i++) {
void *p = my_alloc(size);
my_free(p, size);
}
}
Obviously you can also do one large initial allocation and just
pretend that it is made up of little bits, but that complicates the
code.
You can also avoid wasting space in the free_chain array (at the
expense of some arithmetic) if you know that the common sizes are s0,
s0 + x, s0 + 2x, s0 + 3x and so on. This may or may not be worth
while. Complicate the code only if you know there is a benefit.
[1] This is just a sketch. The yucky cast can (and should) be removed
but using a structure whose first member is a void *. If you don't
mind using C99, you can use the tidied-up "struct hack":
struct alloc_unit { void *next; unsigned char extra[]; };
MIN_ALLOC_SIZE better be >= sizeof (void *).
Ben, Thanks for the post. I am still reading the code to make sure I understand it fully. It does seem simple enough for what I want to do - but I am also very wary about mucking around with memory for two reasons:
i). I have never written a memory pool before
ii). I normally work in C++, so this is terra incognito AFAIC
Could you "flesh out" your example, a little more when you have a chance, so that there is "enough there" that can form a basis on which I build the library?.
Essentially, the C source I am using has a struct like this:
struct stag_
{
double * arr_ ;
size_t arrsz ;
size_t pos ;
};
It has functions that alloc/ free/ realloc's the arr_ variable. (double*). I have exposed functions that make extensive use of this structure, to a scripting library - to run simulations on bioinformatic data. There will be literally hundreds of 1000's of allocs/frees/realloc per single script (even before you take loops etc into account). It is a no-brainer that apart from the overhead of alloc/realloc etc - memory will be badly defragged since we are dealing with very small "chunks" (essentially - just a double). This is why I need a memory pool/allocator which starts with a pool of previously allocated doubles (although I'd prefer to make the library generic enough that any data type can be stored in it, - specified at initialization, i.e. a Simple Segregated Storage). In C++ lingo, I would make the allocator a templated factory pattern.
Back to the C world, I simply need a way of storing a large pool of a previously allocated type (specifically, in this case, a pool of doubles), and then handle requests for malloc/calloc/realloc (memmove?) and free from that pool. I hope someone can help.
.
- Follow-Ups:
- Re: memory pool library (repost)
- From: Ben Bacarisse
- Re: memory pool library (repost)
- From: Ben Bacarisse
- Re: memory pool library (repost)
- References:
- memory pool library (repost)
- From: Grey Alien
- Re: memory pool library (repost)
- From: Ben Bacarisse
- memory pool library (repost)
- Prev by Date: Re: pointer cast UB?
- Next by Date: Re: how to use PI in c99
- Previous by thread: Re: memory pool library (repost)
- Next by thread: Re: memory pool library (repost)
- Index(es):
Relevant Pages
|
