Troubles creating a virtual heap system...
Author
Hello all,
So I was trying to figure out a way to do the following.
When a new entity needs to be spawned
A. It needs to be made part of a global,world list where all the in-game entities live. ( generic , typeless )
B. Be part of a localized,system where all like typed entities think and coordinate amongst themselves. (specific types )
My solution was to come up with a virtual heap system for B that is subordinate to the global schema of A.
Ok, my problem is implementing B. Right now, I have calls to VH_Malloc and VH_Free. VH_Malloc returns void* and keeps track of an internal pointer that points to the next entity to allocate. The biggest problem is with VH_Free. Right now, it decrements that pointer and resorts the remaining space so that there are no gaps ( left when an entity is destroyed ). I am not sure, however, that this is how dynamic allocation works. My main question is, with 'delete' and 'free' what goes on *besides* reclaiming the memory so that it can be allocated out again? Does it always return blocks of memory in sequence, or sometimes out of sequence?
ahayweh
I am open to any alternative solutions as well if anyone has had to deal with something similar...
Quote:Does it always return blocks of memory in sequence, or sometimes out of sequence?
I'm not quite sure what you mean. If you're talking about allocation of memory, I don't know for sure, but I assume that it would return the first block of memory that is large enough. I mean, if you have 4 slots, A,B,C,D and you have 3 objects allocated A,B,C and then delete B and try to allocate some more memory of the same size, it will probably return the pointer to slot B. It makes sense to try and reduce the fragmenting of the memory heap.
But I think you may be doing this the wrong way. Are you working in C++?
Does the global world list consist only of objects, regardless of type? If so, you might want to look into using shared pointers for a common base class instead of messing with void pointers. This way you can change the actual memory location of the objects to avoid significant fragmentation while not having to go and change the reference for every single reference to that object. You just change the shared pointer, and all the objects that need the moved object are always accessing it through the shared pointer.
Also keep track of the fragmentation of the memory pool because you'll want to allocate the first free block of the right size, not the next block in sequence at the end of the memory pool. You'll generally get bad fragmentation working like that, because you'll end up deleting a bunch of objects at the front and then you'll re-allocate space when you get to the end of the pool without using all the free space at the start.
Before anything else, make sure you don't mix memory allocation (which works on uninitialized buffers) and your 'A' and 'B' objects (which should work on initialized objects).
That being said, from the outside, the task of a memory manager is the following:
On the inside, memory managers divide into two categories: fixed-size and variable-size. A fixed-size allocator is faster, but can only ever allocate one size of buffer. Smaller sizes can be accomodated by wasting memory, and a variable-size allocated will have to be used for bigger requests. Fixed-size is faster, though, since you don't have any fragmentation issues (you just fill in the holes left by deallocations with objects of the same size). Conversely, variable-size allocation will run into fragmentation problems because, as holes appear and are filled with smaller allocations, spaces too small to be filled will appear in the heap and will remain there.
This is because of a fundamental requirement on C++ memory allocators: they may not compact the storage (or otherwise do anything which may invalidate the pointers of data). This is because you cannot, in C++, move an object (at least, one that isn't compatible in C) in memory without using its constructor (i.e. memcpy isn't reliable and will only do the right thing once in a while). So, the free store (operator new) and the heap (malloc) are just frozen into place with currently active unfreed allocations, and there's nothing you can do to fill the holes short of allocating new stuff in them.
That being said, from the outside, the task of a memory manager is the following:
- The allocation function (malloc, ::operator new) returns a new block of memory of a given size and alignment. In the case of most sane allocators, this block of memory has unspecified contents, and its position in memory is also unspecified.
- An initialization operator (new) also calls the constructor and sets up any bookkeeping data on the allocated buffer.
- A deinitialization operator (delete) calls the destructor based on either the static (non-virtual) or dynamic (virtual) type of the object.
- A deallocation function eliminates the memory (it is assumed that the memory is reclaimed to reduce memory usage by the program) so that it is not usable anymore. There is no guarantee that the data inside the buffer remains the same once it's gone, that the same buffer will resurface on the next allocation, or that there is any resemblance or relationship between previously freed buffers and newly allocated ones.
On the inside, memory managers divide into two categories: fixed-size and variable-size. A fixed-size allocator is faster, but can only ever allocate one size of buffer. Smaller sizes can be accomodated by wasting memory, and a variable-size allocated will have to be used for bigger requests. Fixed-size is faster, though, since you don't have any fragmentation issues (you just fill in the holes left by deallocations with objects of the same size). Conversely, variable-size allocation will run into fragmentation problems because, as holes appear and are filled with smaller allocations, spaces too small to be filled will appear in the heap and will remain there.
This is because of a fundamental requirement on C++ memory allocators: they may not compact the storage (or otherwise do anything which may invalidate the pointers of data). This is because you cannot, in C++, move an object (at least, one that isn't compatible in C) in memory without using its constructor (i.e. memcpy isn't reliable and will only do the right thing once in a while). So, the free store (operator new) and the heap (malloc) are just frozen into place with currently active unfreed allocations, and there's nothing you can do to fill the holes short of allocating new stuff in them.
Author
I have worked up a stripped down version to better illustrate :
This would allow for calls like
You can see how this is mimicking dynamic allocation, but internally, it's only an array ( whose size may or may not be dynamic ).
[Edited by - ahayweh on September 17, 2007 4:52:25 AM]
#ifndef __MINI_VHEAP_H__#define __MINI_VHEAP_H__#define MINI_HEAP_ADDRESS_SPACE 5#define TYPE_A 0#define TYPE_B 1 struct TypeA_t{ int heapPointer,globalPointer; int state;};struct TypeB_t{ int heapPointer,globalPointer; int state;};struct MiniHeap_t{ TypeA_t array_1[ MINI_HEAP_ADDRESS_SPACE ]; int array_1_pointer; TypeB_t array_2[ MINI_HEAP_ADDRESS_SPACE ]; int array_2_pointer;};void InitMiniHeap( MiniHeap_t* );void* Malloc( MiniHeap_t* , int );void Free( MiniHeap_t* , int , int );#endif#include <memory.h>#include <stdio.h>#include "mini_vheap.h"void InitMiniHeap( MiniHeap_t* heap ){ memset( (void*)heap , 0 , sizeof(*heap) );}void* Malloc( MiniHeap_t* pHeap , int type ){ void* pointer = NULL; int index=0; switch( type ) { default: case TYPE_A: { index = pHeap->array_1_pointer; // bounds checking. Send last slot if all space is 'allocated' index = ( index>=MINI_HEAP_ADDRESS_SPACE) ? MINI_HEAP_ADDRESS_SPACE : index; pointer = (void*)&pHeap->array_1[ index ]; // move to next space pHeap->array_1_pointer++; break; } case TYPE_B: { index = pHeap->array_2_pointer; index = ( index>=MINI_HEAP_ADDRESS_SPACE) ? MINI_HEAP_ADDRESS_SPACE : index; pointer = (void*)&pHeap->array_2[ index ]; pHeap->array_2_pointer++; break; } } return pointer;}void Free( MiniHeap_t* pHeap , int type , int pointer ){ switch( type ) { default: case TYPE_A: { // this version just 'destroys' the value at the specified index. The real one, after doing so, resorts the space so that there are no gaps ( allowing for easy iterative processing ) pHeap->array_1[ pointer ].state = 0; break; } case TYPE_B: { pHeap->array_2[ pointer ].state = 0; } }}This would allow for calls like
TypeA_t* pTA = (TypeA_t*)Malloc( &heap , TYPE_A );TypeB_t* pTB = (TypeB_t*)Malloc( &heap , TYPE_B );You can see how this is mimicking dynamic allocation, but internally, it's only an array ( whose size may or may not be dynamic ).
[Edited by - ahayweh on September 17, 2007 4:52:25 AM]
Quote:TypeA_t array_1[ MINI_HEAP_ADDRESS_SPACE ];
Standard C (at least C89) requires that you prefix structure names (such as TypeA_t) with struct. Your code wouldn't compile on a C compiler (such as gcc) so I suggest you correct these little details.
As for your problem, I fail to see how memory allocation (the thing which creates pointers to memory buffers) has anything to do with both 'A' and 'B' (the things which manipulate the pointers which are handled to them by their users). If you're trying to solve a problem that malloc doesn't solve, then you should clearly state that problem (as it stands, I don't see any reason in your posts explaining why you have to use your own heap instead of just calling malloc to allocate memory).
In short:
- Allocate a memory buffer with malloc, initialize the buffer.
- Store a pointer to the buffer in the global world list A.
- Store a pointer to the buffer in the localized system B.
- When you're done, call free on the object.
This saves you the pain of having your own allocation system.
Author
Thanks for the help so far, but I looks like I may have to scrap this is favor of a simpler design. This system is being designed with the intent of having a 'cleaner' interface. It was working before, but the code didn't look very nice... My goal was not to create a memory manager, but a "virutal" system... I may mess around with it a bit longer...
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement