New, Delete and other memory allocation techniques

[megatron 0]

Last night I had some form of code dream where I saw something like this:

some_allocator_object MyAllocator(SizeOfAllocationHeapInBytes);
int* SomeVar = MyAllocator.alloc<int>("SomeVar");
*SomeVar = 10;
MyAllocator.dealloc("SomeVar");

I think the idea is that you new/delete (Which is supposedly costly) only one time within your program. You give yourself a nice chunk of memory then "allocate" through that. The destructor of the some_allocator_object will free the heap.

I'm not exactly sure if this is viable? You would have to make a global allocator, or maybe even you can give different parts of your program different allocation spaces?

My problem with this is when I think about coding it I would still need some form of STL memory management through a vector ( Which in my eyes would have a type struct which holds the variable ID ("SomeVar"), it's address offset in the pool and the size of the allocation.

Does anyone know of any different memory allocation techniques? I'm intrigued.

[Avilius]

This is actually pretty popular in the game development industry. They split up memory across subsystems and give each system a specific "memory budget." These budgets can be either strict (the engine crashes when it is surpassed) or lenient (the engine maybe has a fallback).

ie: Maybe the sound system has a 256 mb memory budget, the renderer maybe has a 512 mb budget, the networking system 128 mb, etc.

The idea behind it is that when you're programming a game you should know what is going to be in your game. There aren't going to be any surprises and because of this you can cut out some unneeded flexibility for a simpler, more predictable design which can be optimized very well.

This allocator isn't going to be much faster than new/malloc and delete/free however, and probably might be slower. The allocator is still going to be fairly generic and it's going to be doing much of the same things as the standard allocation routines will be doing.

There are a plethora of allocation schemes such as object pools, stack/level allocation, etc that shouldn't be too hard to find on Google if you're interested.

[megatron 0]

Thanks for the reply.

That makes a lot of sense to me and I have looked it up. It seems common to put something like this in a game engine, but I was thinking about this for my OS project.

After further thinking why would this be slower? In my eyes if you were making an fps, each bullet you fire would be be allocated on the heap then deallocate on impact. If the weapon fires at 5 rounds per second that's 300 calls to new per minute.

Wouldn't pointer manipulation be faster than calling the OS?

As for a generic allocator I would think it would be more specialised? If you know a graphic tile is 128 bytes and there are 40 tiles on the screen the allocator could request perfect byte boundaries without any reserved space? Though I will admit I do not understand fully how C++ and linux or windows interact with each other when it comes to allocation, I imagine it to be OS specific for sure but maybe similar?

[MiiNiPaa]

each bullet you fire would be be allocated on the heap then deallocate on impact

NO! Don't do that! This is the recipe for terrible lag. Usually if you have a bunch of short-lived objects, you use object pool: you create n bullets and reuse them as needed.

Wouldn't pointer manipulation be faster than calling the OS?

Allocators still need to store information about memory they maintain, information to subsequently delete exactly requested memory, etc. Specialized allocators beats standard one because they trade something off for increased speed.

[TheHardew]

Couldn't you just use placement new? You allocate buffer and then assign pieces of it to objects. It would be faster then any user-defined classes, it's possible for os to define it even in assembly - no ctors, dtors etc.

[MiiNiPaa]

Couldn't you just use placement new? You allocate buffer and then assign pieces of it to objects.

It is not allocates memory though. It is similar to object pool: you have a pool, and you initialize objects when they are needed, leaving physical object in place (usually it is a good idea to store all data you would access sequentally as a continuous memory, so data prefetch would kick in).

And remember that you need to store which parts of buffer were given, which were deleted and keep that information somewhere.

[TheHardew]

I know it doesn't allocate memory, what I meant is the following:
megatron 0 wrote:

some_allocator_object MyAllocator(SizeOfAllocationHeapInBytes);
int* SomeVar = MyAllocator.alloc<int>("SomeVar");
*SomeVar = 10;
MyAllocator.dealloc("SomeVar");

You can do it as:

char buffer[SizeOfAllocationHeapInBytes];
int* SomeVar = new(buffer) int;
*SomeVar = 10;
delete[] buffer;

I didn't check the code, but you should get the idea.

EDIT:
Ok, you need to store informations about allocations, which means you have to use some classes, but still it should be pretty fast.

[MiiNiPaa]

Custom allocators are fast. As I said this is tradeoff. Often you are trading your ability to allocate different sized types for speed. Or excess memory for speed. Or something else.

Custom allocators is a powerful tool, but it is not a silver bullet. You should consider loss of generity and cost of implementing allocator too.