Memory allocators

["Bjarke Hammersholt Roune" <asmild@post6.tele.dk>]

I've finished those memory allocators I talked about. I'm not sending the
source yet, as though I'm pretty sure there are no bugs, memory allocators
are a little tricky to debug. I should get it done today, though.

The first allocator, ppMemAlloc, is the most advanced. It is a variation of
a memory allocator printed in the magazine C/C++ Users Journal. The way it
works is by allocating memory in blocks, each block containing a number of
units. A unit is what is returned at allocation. So, if a block contains 20
units, you get 20 allocations, but only 1 call to new.

ppMemAlloc keeps track of units by means of a linked list. The memory this
list uses is the memory of the free units. This means that ppMemAlloc cannot
allocate units of a size less than 4. ppMemAlloc also keeps track of its
blocks by means of a linked list. Each block has a 4 byte head (might be
larger in some builds to ensure correct memory alignment) that points to the
next block.

Allocation and deallocation is very fast. Deallocation is only a matter of
adding the deallocated unit to the list of free units, which takes exactly 2
pointer assignments. Allocation is only a matter of taking and removing a
unit from the list of free units, which also take exactly 2 pointer
assignments. Allocation migth also cause the ppMemAlloc to allocate more
memory for itself, which takes some small fixed (in relation to the
blocksize)number of operations.

Now, the problem comes in when trying to find out if all the units in a
block is free, so that block can be deallocated. The only way to do that is
to go thorugh the list of free units and see if all the positions in that
block is present in that list, and if they are, then deallocate it. This is
bad because it gets slower and slower the larger the list of free units is.
Nothing to do about it, though. ppMemAlloc has been designed in suchs a way
as to make it possible to only check 1 block at a time, so this can be done
as an idle-time job.

Having extra capacity lying around in the allocator isn't that bad, though,
as it makes it possible to do more allocations before having to call new
again.

Both unit size and blocksize can be set at construction and reinitialisation
(all blocks are deleted), but at no other point.

---

The other allocator I've coded, ppStatMemAlloc, is a little different. It
supports allocation of any size of unit. Allocation still only takes exactly
2 pointer assignments. The way this is accomplished is by allocating one big
block of code at construction. How big this block of code is can only be set
at construction and reinitilisation. ppStatMemAlloc cannot allocate any more
memory than is in this block of memory, and it cannot deallocate units
one-by-one. It can, though, deallocate all units at once, by simply deleting
the allocated block of code.

---

Both ppMemAlloc and ppStatMemAlloc has a wrapper. ppMemAlloc's wrapper is
called ppObjAlloc, and its template parameter is a class. ppMemAlloc can
only allocate objects of this class. ppStatMemAlloc's wrapper is called
ppStatObjAlloc, and we have the same template situation here.

The wrappers cannot only allocate memory that is of the correct size, but
they also have a method for allocating memory, and then also constructing
that memory, using the default constructor. If a exception is thrown from
the constructor, its catched and the memory is deallocated. The exception is
not re-thrown. I don't know if its correct behavior for it to be re-thrown.

ppObjAlloc can also deconstruct and deallocate objects. ppStatObjAlloc
cannot, as it cannot deallocate objects on a one-by-one basis. Objects
allocated by ppStatObjAlloc will therefore have to be deconstructed by the
code using the allocator.

the wrappers are mostly convenience classes, and their methods are all
inline, except for the method that both allocates and constructs (called
ConstructAllocate() ).

---

Now, for the most interesting part: how fast is it?

First, I take ppMemAlloc.

I've made two allocation benchmarks for this. In the first benchmark, what
happends is that an object of class ppMemAlloc is asked to allocate 10.000
entries one-by-one, and then deallocate them one-by-one (the deallocation
benchmark is presented later in this e-mail). New and delete is set on the
same task. This is then repeated 10.000 times. Then the time new took to do
the 10.000*10.000 allocations is divided by the time it took
ppMemAlloc::Allocate() to the 10.000*10.000 allocations. That's the first
allocation benchmark.

In the second allocation benchmark, everything is the same, except that the
object of type ppMemAlloc is reset before each allocation of the 10.000
entries. When the object is reset, it deleted all its blocks. This means
that it does not save the capacity it built in the previous allocation of
10.000 entries for now, so it has to reallocate enough blocks to hold 10.000
entries.

In allocation benchmark 1, ppMemAlloc is 550% to 650% faster than new.

In allocation benchmark 2, ppMemAlloc is 270% to 300% faster than new.

The above benchmark was done with a unit size of 4, and a blocksize of 16.
I've made the same benchmark with the same unit size of 4, but this time
with a blocksize of 128.

In allocation benchmark 1, ppMemAlloc is 550% to 650% faster than new.

In allocation benchmark 2, ppMemAlloc is 300% to 320% faster than new.

And now for deallocation. Here, tablesize and resetting doesn't matter, so
there's only 1 benchmark.

In the deallocation benchmark, ppMemAlloc is 330% to 390% faster than new.

--

Now to the allocation benchmark for ppStatMemAlloc:

In the allocation benchmark, ppStatMemAlloc is 800% to 980% faster than new.

Deallocation by ppStatMemAlloc and deallocation by delete is not really
sometihng you can compare, so I couldn't make a benchmark on that.

These benchmarks aren't very accurate, and I've done a little rounding down
and up, but they give a good image of the effeciency of these allocators. As
I said, I'll try to get certain that they are, as I suspect they are
already, bug-free, or I'll make them so.