The allocator object

[jacob navia]

Until now, I hadn't started the problem of memory allocation. Each
container allocated with malloc each new piece of memory as needed and
freed it when deleting an element.

The first abstraction is an object with 3 function pointers:

malloc
free
realloc.

This abstract a memory allocator system. Two memory allocators are
recognized: the normal C system of memory allocation (plain malloc,
free, realloc) and the GC, with GC_malloc,GC_free, and GC_realoc.

A further abstraction is a "heap manager" object. This object will
manage memory allocations, allocating several objects at once to
minimize malloc overhead. When doing a great number of allocations, the
memory needed to manage each piece of memory increases *considerably*
memory consumption, so that for any container where the number of
objects allocateds goes beyond 10 000 this is almost a requirement.

This heap manager looks like this:
struct tagHeapObject {
AllocatorInterface *VTable;
unsigned BlockCount;
unsigned CurrentBlock;
unsigned BlockIndex;
void **Heap;
size_t ElementSize;
void *FreeList;
ContainerMemoryManager *Allocator;
size_t MemoryUsed;
};

Memory is managed in an array of arrays to allocated objects. The index
"CurrentBlock" points to the block that is currently being used. Arrays
with index smaller than "CurrentBlock" are full, arrays with index
greater than CurrentBlock aren't allocated yet.

BlockIndex points to the position within the current block that is going
to be allocated next. The "Heap" field points to the actual data.

Problems arise when initializing this stuff. When a "new" function is
called for some container, I need to

(1) Allocate memory for the header
(2) Allocate memory for the heap manager object

Which allocator should be used to allocate memory?

There is a global variable containing the default memory allocator that
is initialized by the container library either to the normal C library
or to the GC one. I could decide that this default memory allocator is
always used to create objects. This would complicate matters when
changing the allocator since some memory would be allocated with a
default allocator, and some with the custm memory allocator. This is
confusing and can lead to bugs.

I could decide that the allocator should be passed as an argument to the
creation function. If NULL is passed, it means that the default
allocator should be used. But that means another argument to all
creation functions that in 95% of the cases will be just NULL.

Another possibility is that AFTER object creation but before adding
*any* objects you change the heap object with some API like

ContainerAllocator *ChangeAllocator(container, newAllocator);

that would allocate memory for the container object using the new
allocator, copy the contents, and free the memory allocated with the
default allocator during obhect creation. This option looks quite
inefficient but allows for simple syntax for MOST cases when the
allocator used is the default one.


Maybe there are other solutions. If anyne here has any idea, do not
hesitate to answer.

jacob

 

[Keith Thompson]

A further abstraction is a "heap manager" object. This object will
manage memory allocations, allocating several objects at once to
minimize malloc overhead. When doing a great number of allocations,
the memory needed to manage each piece of memory increases
*considerably* memory consumption, so that for any container where the
number of objects allocateds goes beyond 10 000 this is almost a
requirement.

[...]

Does a "heap manager" object allocate only objects of a size that's
fixed for each specific heap manager? If so, I can see how allocating
several objects at once can reduce overhead. If not, then malloc
itself might as well use whatever technique your heap manager object
uses, and probably already does.

 

[jacob navia]

Keith Thompson a écrit :

A further abstraction is a "heap manager" object. This object will
manage memory allocations, allocating several objects at once to
minimize malloc overhead. When doing a great number of allocations,
the memory needed to manage each piece of memory increases
*considerably* memory consumption, so that for any container where the
number of objects allocateds goes beyond 10 000 this is almost a
requirement.

[...]

Does a "heap manager" object allocate only objects of a size that's
fixed for each specific heap manager?

Yes, of course. Each container has a fixed size for its objects. If you want
variable size just store the pointer

If so, I can see how allocating

 

[Ian Collins]

Until now, I hadn't started the problem of memory allocation. Each
container allocated with malloc each new piece of memory as needed and
freed it when deleting an element.

The first abstraction is an object with 3 function pointers:

malloc
free
realloc.

This abstract a memory allocator system. Two memory allocators are
recognized: the normal C system of memory allocation (plain malloc,
free, realloc) and the GC, with GC_malloc,GC_free, and GC_realoc.

A further abstraction is a "heap manager" object. This object will
manage memory allocations, allocating several objects at once to
minimize malloc overhead. When doing a great number of allocations, the
memory needed to manage each piece of memory increases *considerably*
memory consumption, so that for any container where the number of
objects allocateds goes beyond 10 000 this is almost a requirement.

I think you have discovered how messy custom allocators can be in C!

I don't know about windows, but a common technique on Unix systems is to
provide a number of specialised allocator libraries that can be linked
with the application. I've done the same on embedded systems, writing
an allocator library based on the memory use of the application.

If you want custom allocators per container, then due the the reasons
you mention, it's probably best to have a separate interface to assign
one. I think you should keep the allocator object small, just have
function pointers for malloc, calloc, realloc and free.

 

[Andrew Poelstra]

Another possibility is that AFTER object creation but before adding
*any* objects you change the heap object with some API like

ContainerAllocator *ChangeAllocator(container, newAllocator);

that would allocate memory for the container object using the new
allocator, copy the contents, and free the memory allocated with the
default allocator during obhect creation. This option looks quite
inefficient but allows for simple syntax for MOST cases when the
allocator used is the default one.

I'm not sure it would be inefficient if you setup the function to
check if any objects had been created and error out if that is the
case.

I don't think anyone would be using multiple allocators throughout
the same program, and trying to cater to such people is IMHO a bad
idea, since they are an incredible minority and you will suffer a
great complexity/inefficiency hit trying to do so.