Hi to get up to speed with C I am following http://c.learncodethehardway.org/book/
offcourse a big part of C is writing these custom data structures, (list, dynamic Array, tree, hashmap, stack etc) I was wondering how one would write these while using this preallocated memory strategy?
all of these data structures (in that tutorial) obviously have malloc/calloc and free inside of them, How would you structure it differently, or would you not and try to avoid using these alltogether?
regards, Nikki
offcourse a big part of C is writing these custom data structures, (list, dynamic Array, tree, hashmap, stack etc) I was wondering how one would write these while using this preallocated memory strategy?
all of these data structures (in that tutorial) obviously have malloc/calloc and free inside of them, How would you structure it differently, or would you not and try to avoid using these alltogether?
regards, Nikki
Typically you pass in a memory arena to every function that either directly allocates memory or must call a function that allocates memory.
On the one hand, it leads to high level code "knowing" about details needed only by low level code. On the other, it makes these details explicit which is often invaluable.
On the one hand, it leads to high level code "knowing" about details needed only by low level code. On the other, it makes these details explicit which is often invaluable.
Games with custom engines tend to use a lot of special-purpose memory allocators.
Just as an example, I'm working on a little experiment which does require dynamic allocation. Using the data-oriented and semantic-compression-explore-thingy approach (i.e. finding out how the memory is actually used), I found that so far, I need at least five different allocation strategies.
The low-level allocator (I used a buddy allocator) hands out multiple-of-a-page-sized blocks of memory, which can be used by themselves (e.g. for assets) or can be managed by higher-level allocators. So far, I have:
I can already see that this won't be enough, but I'm being a good data-oriented programmer and not implementing any other allocators until I really need them.
Just as an example, I'm working on a little experiment which does require dynamic allocation. Using the data-oriented and semantic-compression-explore-thingy approach (i.e. finding out how the memory is actually used), I found that so far, I need at least five different allocation strategies.
The low-level allocator (I used a buddy allocator) hands out multiple-of-a-page-sized blocks of memory, which can be used by themselves (e.g. for assets) or can be managed by higher-level allocators. So far, I have:
- A "static" allocator, which allocates memory that will never be freed during the life of the program.
- A stack/pool-type allocator, which allocates a large block of memory, allocates pieces of it as needed, and the only "deallocation" operation is to wipe the whole thing in one go. This allocator could also support "stack popping" if it was needed, but I haven't needed it yet. This is what you use for "frame memory", for example.
- A slab/object allocator, which allocates memory for single objects of the same "type". In a data-oriented system, this doesn't happen nearly as often as you might think, but it doubles as a general-purpose allocator by maintaining object caches for various fixed sizes. This is what you typically use for data structures.
- A very temporary allocator, which is optimised for modest-sized blocks of memory which will only exist for a very short amount of time. An example is OpenGL shader source code, which is loaded, compiled, then immediately discarded.
I can already see that this won't be enough, but I'm being a good data-oriented programmer and not implementing any other allocators until I really need them.
I tried this method with cocos2d and it didn't work out. there was some initialization problems and well I don't think it works well with this engine. I might try again later. Non handmade Engines are so hard to work with when you want to do these kind of stuff.
it would be some thing like:
void* memoryChunck = new void(9000);
and if you want to make a new object you just do
Object* newObject = (Object*) memoryChunk;
and then you want to add more...
Object2 newObject2 = (Object2*) sizeof(Object)+memoryChunk;
beautiful and at the end I can just do delete memoryChunk; memoryChunk=NULL;
it would be some thing like:
void* memoryChunck = new void(9000);
and if you want to make a new object you just do
Object* newObject = (Object*) memoryChunk;
and then you want to add more...
Object2 newObject2 = (Object2*) sizeof(Object)+memoryChunk;
beautiful and at the end I can just do delete memoryChunk; memoryChunk=NULL;
Edited by popcorn
on
I can't speak for cocos2d, but do make sure that allocations are appropriately aligned. What constitutes "appropriate" depends on what it is that you're allocating, of course.
Keep in mind that cocos2d uses virtual functions. For those to work, the object's virtual function table has to be properly initialized during construction. This can only be reliably done by using "new" (or putting the object on the stack). However, you can tell the compiler to use a pre-allocated piece of memory for the object by using "placement new". This would look something like this:
You still have to take care of proper alignment. Since C++11, there's the alignof keyword that works similarly to sizeof.
By the way, generally, you wouldn't do this:
What you should do instead is write a small helper struct that keeps track of the memory for you, plus some functions for using it:
1 2 | void* memory = malloc(sizeof(Object)); Object* obj = new (memory) Object(arg1, arg2); |
You still have to take care of proper alignment. Since C++11, there's the alignof keyword that works similarly to sizeof.
By the way, generally, you wouldn't do this:
1 | Object2 newObject2 = (Object2*) sizeof(Object)+memoryChunk; |
What you should do instead is write a small helper struct that keeps track of the memory for you, plus some functions for using it:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | struct MemoryStack {
void* start;
size_t size;
size_t bytesInUse;
};
void* push(MemoryStack* stack, size_t byteCount) {
assert(stack->bytesInUse + byteCount <= stack->size);
uint8_t* memory = ((uint8_t*)stack->start) + stack->bytesInUse;
stack->bytesInUse += byteCount;
return (void*)memory;
}
// Use it like this (for POD types):
MemoryStack memoryStack = {};
memoryStack.start = malloc(MEM_SIZE);
memoryStack.size = MEM_SIZE;
Object1* newObject1 = push(&memoryStack, sizeof(Object1));
Object2* newObject2 = push(&memoryStack, sizeof(Object2));
|
Edited by Benjamin Kloster
on
Nimbal
Since C++11, there's the alignof keyword that works similarly to sizeof.
There's also aligned_alloc that allocates aligned memory.
Grr so when I do a new or alloc or malloc or whatever, it marks it as a "smart" pointer. So somehow I either have to work with it (retain?) or turn it off. There is a way to turn off in Objective C but I searched and found no way of turning it off in C++ 11. Any suggestions?
Edited by popcorn
on
What? new and malloc doesn't create any smart pointer. Just a regular C++ or C pointer which you need to deallocate yourself. Only by using std::unique_ptr or std::shared_ptr you will be creating "smart" pointers.
Edited by Mārtiņš Možeiko
on
You can write such code ONLY if Sprite is C struct, not C++ class (or more accurately - plain old data structure).
If Sprite is C++ class you must do what Nimbal said above in post #2919 - use placement new operator to "cast" memory:
This will call Sprite constructor which will call parent class constructors if there are any, initialize vtable if Sprite class has any, and call constructors of any members of Sprite class. Basically everything that regular "new" allocation does except actually allocating memory - instead it will use memory location where chunkOfMemory pointer points to.
But really, if you want to write C++ code with C++ classes, just use new/delete operators (or std::unique_ptr if you are C++11). Don't try to pretend C++ is C.
If Sprite is C++ class you must do what Nimbal said above in post #2919 - use placement new operator to "cast" memory:
1 2 3 4 5 | chunkOfMemory = new char[1024*9000];
Sprite* sprite = new (chunkOfMemory) Sprite();
sprite->create("bush.png");
this->addChild(sprite);
|
This will call Sprite constructor which will call parent class constructors if there are any, initialize vtable if Sprite class has any, and call constructors of any members of Sprite class. Basically everything that regular "new" allocation does except actually allocating memory - instead it will use memory location where chunkOfMemory pointer points to.
But really, if you want to write C++ code with C++ classes, just use new/delete operators (or std::unique_ptr if you are C++11). Don't try to pretend C++ is C.
Edited by Mārtiņš Možeiko
on
What if the constructor is private? How would it work?
sprite = (Sprite*) push(&memoryStack, sizeof(Sprite));
//sprite->init...//private
//sprite->sprite() //private
I also tried:
sprite->create();
sprite->setTexture(texture);
Not sure if it's the texture var (I get BAD_ACCESS on it) that's causing it which is
image = (Image*)push(&memoryStack, sizeof(Image));
image->initWithImageData((unsigned char*)imageData, imageSize);
//texture.initWithImage(image);
texture = (Texture2D*) push(&memoryStack, sizeof(Texture2D));
texture->initWithImage(image);
Not sure why they made these private, I read somewhere where a community of people said that it should be private in the next version of cocos2D.
I also not sure of the size of the image would be part of the size of Sprite or Texture2D.
Thanks.
sprite = (Sprite*) push(&memoryStack, sizeof(Sprite));
//sprite->init...//private
//sprite->sprite() //private
I also tried:
sprite->create();
sprite->setTexture(texture);
Not sure if it's the texture var (I get BAD_ACCESS on it) that's causing it which is
image = (Image*)push(&memoryStack, sizeof(Image));
image->initWithImageData((unsigned char*)imageData, imageSize);
//texture.initWithImage(image);
texture = (Texture2D*) push(&memoryStack, sizeof(Texture2D));
texture->initWithImage(image);
Not sure why they made these private, I read somewhere where a community of people said that it should be private in the next version of cocos2D.
I also not sure of the size of the image would be part of the size of Sprite or Texture2D.
Thanks.
Edited by popcorn
on
In case it was not clear from above posts - you are NOT ALLOWED to call any method on object (like create/setTexture/whatever) unless constructor was invoked. Either implicitly by compiler, or explicitly by placement new syntax. There is exception where you can do, but you shouldn't rely on that (class has no vtable, and no members in its or its parent classes which have constructors).
Instead of randomly trying bunch of methods, you should really be reading source to understand what they are doing and do same things but with your "push" method. I don't know what is your Sprite or Texture2D class, so I can not comment on this more.
If constructor is private then it typically means there is public static method to construct object:
In such case you will need to modify this static Create method to use your "push" and placement new syntax. There is no other good way to fix it.
There is another uglier solution - to put "#define private public" before including class declaration. Then all private methods will become public. But I don't recommend this. It is better to go and change class source code to do whatever you need it to do.
Instead of randomly trying bunch of methods, you should really be reading source to understand what they are doing and do same things but with your "push" method. I don't know what is your Sprite or Texture2D class, so I can not comment on this more.
If constructor is private then it typically means there is public static method to construct object:
1 2 3 4 5 6 7 8 9 10 | class Object { private: Object() { ... } // private constructor public: static Object* Create(..arguments..) // public method { return new Object(...); } }; |
In such case you will need to modify this static Create method to use your "push" and placement new syntax. There is no other good way to fix it.
There is another uglier solution - to put "#define private public" before including class declaration. Then all private methods will become public. But I don't recommend this. It is better to go and change class source code to do whatever you need it to do.
Edited by Mārtiņš Možeiko
on