SmallAlloc : a memory manager, better than HeapAlloc in many cases

[u]

I designed it for allocating thousands of small objects (1..8192bytes), but with apropriate tweaks (it's easy to tweak), it can handle millions of objects too. With minimum possible overhead on alloc/free.  :toothy
I'm thinking of using it as memmanager for objects in ATC 

Has a debug proc to see how many pages (and objects in them) are allocated, detecting memory leaks is a snap.
Also, you can free all allocated data in one call - just in case there are leaks, and just in case Windows doesn't handle them.

Compiled as a .lib with an .inc for the exported procs, also included an example app.

[hutch--]

Ultrano,

This looks like good stuff.  :U

[James Ladd]

Ultrano,
I have downloaded the zip and will look at it when time permits.
Are you able to describe the algo you use and how you do things
like compacting free blocks?
rgs, striker

[u]

Sorry, I've been very busy with my job lately.
Actually, in artificial benchmarks, SmallAlloc is not faster than HeapAlloc - it's equally fast for up to 10000 objects allocated immediately in sequence, and then becomes a bit slower. But this benchmark did not resemble anything used in reallife, so it might actually be fast.
But the best thing about SmAlloc is that per object it takes _only_one_ additional bit, not like HeapAlloc 4 to 12 additional bytes. Thus, allocating many small objects will actually take much less memory.

SmallAlloc works like this: for each different size of object we allocate, there's at least 1 64kB page. This page holds a header, a bitfield and the data left out of these 64kB is reserved for the objects. Since the sizes of objects can be different, bitfields take different amount of space. Example: 507 16-byte objects will fit in one page, 64 bytes are reserved for bitfield, 2 bytes are padding to make the first object dword-aligned. I probably should make the alignment 8-byte, right ? Or 16-byte?

When an object is allocated, we search for suitable page that holds objects of this size. And it should have at least one empty cell. If we don't find such a page, we create a new one. We go through the bitfield to find at which offset we have an empty cell, and then we take it - and we register it in the bitfield.
Freeing is easier - we run through the pages to find to which page this address belongs. Then, we calculate which cell it's actually in, and we check if the address specified is correct. Then, we unregister that cell in the bitfield.

Also, SmallAlloc is extra flexible on object size - you can make it allocate 1MB, and it'll use HeapAlloc internally to do this. And when you free this 1MB object with SmFree, SmallAlloc will notice that address doesn't belong to any of its pages, and will free it with HeapFree.

There's a bit modified, thread-safe version here: www.ultrano.com/ilix