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

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.

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:

1. A "static" allocator, which allocates memory that will never be freed during the life of the program.
2. 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.
3. 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.
4. 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;

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:

Yeah I did

ObjectA a = (Object*) chunkOfMemory;
a->init();

it doesn't work properly.

I also tried to do this with "Sprite" but that didn't work. I also tried using Texture2D to load an image into the memory chunk, but that didn't work either.

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?

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.

So I guess I can't mix them? I don't even know if I am...


chunkOfMemory = new char[1024*9000];

sprite = NULL;
sprite = (Sprite*) chunkOfMemory;
sprite->create("bush.png");
this->addChild(sprite); <=== ????

Error
Retain() reference count should be greater than zero.

wtf??

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.

Thanks, I have learned how to do it the C++ and not the C way. I didn't know this.

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.

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.