I wan’t to implement my own block memory allocator to speed mem. allocation up.The allocator should work exactly like malloc but instead of allocating space for one structure every time it should alloc, a whole block of,say 256 structures and use that until it’s all used up.Then it get’s another block etc.Does anybody know of any documentation on such block allocators on the web?
Hey, serious optimising. I’ve never done it, but I’d imagine you could allocate the large block when you first call you malloc replacement, then store the pointer somewhere and return it. Then, everytime your function is called, increment the pointer by the size of the structure and return the new value. If the function is called and the pointer is already at the end of the buffer, then allocate some more memory and repeat. Keep a list of pointers to all the buffers you have allocated.
You’d have to write a new free function as well I’d imagine.
The free function would be the real problem with the way you describe,because the to be freed block wouldn’t always be the last one you allocated.Nevertheless something like that could be done.But I was thinking of writing a complete memory allocator replacing malloc,using system calls to get new chunks of memory.Anyone knows of any docs,newsgrous etc. dealing with that sort of stuff.
I’m not at home so I don’t have it with me to reference at the moment but I’m 99% sure that More Effective C++ by Scott Meyers has quite a lot on this topic. It’s not available on the web though 
You’ll have to buy it. From memory he overloads operator new() and operator delete() to allocate/deallocate a pool of memory for a particular class, say x. Then, when you create an x object like this x x1 = new x(); it uses the memory from the pool. I’ll read it when I get home and update you then.
Hope that helps.
thanx ffish,I’m using C not C++ but it should help.
Baiscally what I need is a variation of malloc(which I have docs for).It should though be simpler(and more optimized) because fixed-size blocks will be allocated.malloc uses system calls to get a more space to meet a demand for say n bytes of memory if the current space has run out.Tweaking that to fetch n*blocksize bytes shouldn’t be a big problem.So the only problem seems to be how to best take advantage of the fact that allocated blocks will be of a fixed size,when managing the free list.I’ll look into it a little more.
Oh, sorry. Anyway, I was wrong (1%) - it was his first book Effective C++ that has basically what you’re talking about but in C++. However, I did find something similar in Game Programming Gems. Ch. 1.9 - Frame-Based Memory Allocation discusses a memory manager in C that allocates a block of memory at the beginning of execution for all objects to get their memory from. The difference is that each call to their memory allocator allocates a frame (duh!) that can be used for any type of object. It would be simpler to have a memory manager for just one type of object like you want to.
I’m not going to copy out the chapter here for you (too many pages and I’d be infringing their copyright 
) but they basically have some global variables that contain the value returned by malloc (_p_mem), the base pointer of the memory block (_p_base) and the current address of the next free block (_p_frame). At initialisation, they malloc memory and store it in _p_mem, align it to a byte boundary (4 or whatever you want) and store that in _p_base, then point the free block at the base _p_frame. When they call their own memory allocator, it just checks if there is any free memory left then takes an object-sized block from the memory at _p_frame and increments _p_frame. Simple! You also have to do some bookkeeping to free individual blocks and the whole memory block as well.
I’ve always meant to implement my own memory manager but never got around to it. There always seems to be other things to do! I do think there are a lot of potential savings to be made from rolling your own mallocs though. Let us know how well it works
What exactly do you plan on getting out of a new memory manager, anyway? Malloc is pretty efficient as is, and a “block memory allocator” wouldn’t do much better than malloc. You can get the same effect by allocating a single, large block of memory with malloc, and doing some simple management on it yourself (getting pointers to various structures in this memory).
Hi,
a colegue of mine have written an allocator for memory blocks with fixed size up to 512 bytes(however, simply changing some defines would allow you to allocate more large blocks.) This allocator is specialized for CAD systems, where dynamic vertex/face structures are very used. You will see, that standard allocators (like this in MS VC) work very slowly compared to this one, especially in multithreaded app. The allocator can be get from here: http://www.sirma.bg/stenly/allocator/index.html
I also have written a template memory allocator, but it is strongly oriented for subdision algorithms, and can free only the last allocated memory (which is sufficient for me). It is also template, and thus is in C++ (If you wish to know something for it, you can ask me
And at last, you can use the memory allocators which come with SGI STL. I’ve never tried them, but some friends have tell me, that they also work very fast. However, they are also in C++ )
Hope this helps
Martin
ffish:thanx again.Basically that is more or less what Benjy describes .I was considering the same but instead of depending on malloc for memory allocation I want to write my own memory allocator.The good side of this is that since I only need fixed-size blocks I can optimize it for that purpose and make it faster.The bad side is that I’ll be having two(or more if I want block allocators of different sizes)allocators.The custom and malloc.Whatever memory the custom alloc. gets from the system will be used only by him and so if at one point I need say 1000 blocks but after that I only need 100 then 900 blocks will still be used by this allocator(it’ll just be on his free list doing nothing).
Korval:
I’m developing a roam terrain engine, which is based on iterative splitting of triangles.With every split I have to allocate memory for two other triangles(the chlidren).With a couple of hundred splits per frame malloc should be too slow(cause it will ask the system for memory every time which is slow.My allocator asks it once every,say 256 blocks).
martin:
thanx I’ll have alook