Hello gentlemen, I'm working on a 2d game using OpenGL and need to create a memory manager to reduce context switching which will cause the game to run slowly. I have been researching various memory allocation techniques such as buddy allocation, best fit, and free list but am unsure of which technique would be most practical for this application. I would like to allocate a large chunk of memory and and create a manager of that memory that allows me to create and delete entities.
Hi! Why do you think thread context switching is a performance problem in your application and how will memory manager solve it?
Edited by Mārtiņš Možeiko
on
When malloc() and calloc() are called, the program switches between user-space code and kernel code. This is normally not a performance issue however, in my case I am using a sprite batching rendering technique where a batch of entities must be created and deleted each frame. In short, I am "allocating" and "freeing" memory every frame. The memory manager will solve this performance problem by eliminating the need to use malloc() and calloc() each frame. The memory "allocation" will all occur in user-space on a large chunk of memory allocated once at the beginning.
You could easily solve that with a allocator that behaves kinda like a stack. In the beginning you allocate a chunk and give that memory address to a "stack" struct. Every frame you just push sprites onto the stack and at the end of every frame you clear it to zero (which is just setting the stack's current address to 0, O(1) cost). That should do it I assume (which is what I did for my batched sprite renderer)? That is very similar to the "memory_arena" casey uses in handmade hero, I don't know if you watched to that part yet though.
A snippet:
struct stack {
b8 *Base; //memeory address of the "chunk" you allocated initially
size_t Used; //how much memory is currently in use, whenever you push new stuff onto the stack it will start from (Base + Used) location
};
and every frame you do:
PushStruct(stack, Sprite1);
PushStruct(stack, Sprite2);
...
After you are done, just do:
stack.Used = 0; //this "clears" the stack, so next time you push anything onto it it starts from the base address, effectively overwriting what it was storing last frame to save space.
A snippet:
struct stack {
b8 *Base; //memeory address of the "chunk" you allocated initially
size_t Used; //how much memory is currently in use, whenever you push new stuff onto the stack it will start from (Base + Used) location
};
and every frame you do:
PushStruct(stack, Sprite1);
PushStruct(stack, Sprite2);
...
After you are done, just do:
stack.Used = 0; //this "clears" the stack, so next time you push anything onto it it starts from the base address, effectively overwriting what it was storing last frame to save space.
Edited by Chen
on
AVladimirov
When malloc() and calloc() are called, the program switches between user-space code and kernel code. This is normally not a performance issue however, in my case I am using a sprite batching rendering technique where a batch of entities must be created and deleted each frame. In short, I am "allocating" and "freeing" memory every frame. The memory manager will solve this performance problem by eliminating the need to use malloc() and calloc() each frame. The memory "allocation" will all occur in user-space on a large chunk of memory allocated once at the beginning.
malloc and calloc will not do a syscall every time. They will grab a large block of memory and then pass it out piecemeal.
It's not going to be as good as a custom object pool or stack allocator because general purpose allocators have different trade-offs compared to what you need.
You really must be doing a lot of huge allocations all the time if this shows up as performance issue with profiler or debug measurements.
Anyways, as rachetfreak said - C or C++ memory allocation/free functions doesn't switch to kernel on every call. The buffer memory and give you allocations from memory pool they have.
If you want to explictly write that in your code then do what Chen96 says. I'm not sure why he calls that stack allocator, because it obviously is not stack allocator. It's a simple dynamic array. You can also implement/use resizeable array. In C++ it you would just use std::vector:
In C it's a bit of manual work to keep count of sprites:
Or if you know limit of sprites you'll have, then simply allocate it only once, and don't keep the allocated integer. Or just put them on stack/global:
Anyways, as rachetfreak said - C or C++ memory allocation/free functions doesn't switch to kernel on every call. The buffer memory and give you allocations from memory pool they have.
If you want to explictly write that in your code then do what Chen96 says. I'm not sure why he calls that stack allocator, because it obviously is not stack allocator. It's a simple dynamic array. You can also implement/use resizeable array. In C++ it you would just use std::vector:
1 2 3 4 5 6 7 8 9 10 | std::vector<Sprite> sprite; sprites.reserve(1000); // this allocates memory for initial sprites, do it outside of main loop // now these calls most of the time won't allocate new memory sprites.push_back(get_sprite(...)); // or a bit more efficiently, call sprite constructor directly: sprites.emplace_back({...}); // when done, remove sprites, this does not free memory most of the time: sprites.clear(); |
In C it's a bit of manual work to keep count of sprites:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int count = 0;
int allocated = 1000;
Sprite* sprites = calloc(allocated, sizeof(Sprite)); // initially get space for 1000 elements
// when you want to append new one, check if you need to resize array
if (count == allocated)
{
allocated *= 2
sprites = realloc(sprites, allocated * sizeof(Sprite));
}
// now just put elements inside array, and update count
sprites[count++] = ...;
// clear out array
count = 0;
|
Or if you know limit of sprites you'll have, then simply allocate it only once, and don't keep the allocated integer. Or just put them on stack/global:
1 | Sprites sprites[MAX_SPRITES]; |
Edited by Mārtiņš Možeiko
on
I edited my post to take out the word "stack allocator" to avoid confusing any more people.
I called it a "stack allocator" because to me this allocator's behavior is very much like a stack. It's not a dynamic array because it allows allocation of different type/sizes stored in a contiguous chunk of memory. And by rewriting the "Used" member the program can essentially "pop" the stack to wherever they want. User could allocate some stuff and save where the current "Used" value is, then choose to pop back to this exact location if they so wish. Sorry for my misuse of the word "stack allocator", if that confused anyone. I am curious to know what "stack allocator" actually means?
And I definitely agree with that simple array on stack/global, seems the most painless among all options.
I called it a "stack allocator" because to me this allocator's behavior is very much like a stack. It's not a dynamic array because it allows allocation of different type/sizes stored in a contiguous chunk of memory. And by rewriting the "Used" member the program can essentially "pop" the stack to wherever they want. User could allocate some stuff and save where the current "Used" value is, then choose to pop back to this exact location if they so wish. Sorry for my misuse of the word "stack allocator", if that confused anyone. I am curious to know what "stack allocator" actually means?
And I definitely agree with that simple array on stack/global, seems the most painless among all options.
Edited by Chen
on