Advanced Allocation/Deallocation in Memory

[MattKent]

Hi there,

I'm coming to you nice people as a desperate resort with time working against me, anyway:

I have implemented an algorithm that basically generates a very large tree of nodes, where each node just contains 4 pointers to other nodes.

Now this generation of a tree occurs many times in the programs operation, and with the creation of new Node objects I gradually run out of memory. Obviously I need to deallocate them between each tree generation; so infact I decided that all the objects would be stored in an array (inter-connected via pointers to create the tree) so I could simply for-loop backwards from the last node created in the array, performing delete Node.

Unfortunately, the "last node created" in the first tree is indexed at 1251260, and they only get bigger. My memory consumption problem is now gone, but I'm finding the process of deleting (for loop + delete node +set node to null) is taking a very long time. Too long really.

I'm suprised by this, because I always thought memory allocation was more expensive than deallocation, yet it manages to allocate all the nodes in mere seconds, while taking a couple of minutes to deallocate them all. Is there some extremly quick way for me to delete the whole array of nodes much quicker? Is there something obvious I don't know that I should?

Thank you in advance,
Matt Kent

[JosAH]

Why don't you allocate entire chunks/arrays of tree nodes and marshall them to your tree code one by one? If the chunk is entirely used, allocate a new one again.

When you want to get rid of your tree you just have to deallocate the chunks used in the step above. If those chunks are quite big (say 1024 nodes or so) the freeing process won't take much time.

kind regards,

Jos

[MattKent]

A logical suggestion, and likely the best. Thank you.

[weaknessforcats]

Are you using Windows?

If so, use a private process heap and not the CRT heap. When you are done, just delete the entire heap. No need for cleanup at all.