Jump to content
  • Advertisement
Sign in to follow this  
OleKaiwalker

tree or list...

This topic is 4811 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, I need some suggestions on how to store not allocated chunks in my current memory allocator. Ought I to keep them in a linked list, or perhaps a tree? No matter what way you prefer, can you please share some wisdom??

Share this post


Link to post
Share on other sites
Advertisement
List, but watch out for the per node overhead and allocation issues with managing the list. For my chunk allocator I overlay the free-chunk list and storage to avoid such issues and from my small benchmarks it performs somewhere around ~40times better than new but it's hairy buisness and do rely on some platform dependant stuff (in this case that the most restrictive alignment equals the alignment of a pointer).

Share this post


Link to post
Share on other sites
well basicly you only need to add/remove from the front so a list is low overhead and easy to get working, the only reason I can see for using a set would be memory tracking but then that should be built on top of the basic allocator.

Share this post


Link to post
Share on other sites
Same-size chunks: a list, because as has been said you can simply add/remove at the front of the list the otherwise identical chunks.


Different-size chunks: a tree, because you need to look for a specific chunk size, or what is closest to it, and also merge adjacent areas of memory when they both become free. It helps greatly if you decide adapted alignment properties ( "a block of size 2n can only start at an offset of k 2n, block sizes are rounded to the upper power of two" makes for a very easy to maintain tree, for instance).

Share this post


Link to post
Share on other sites
I second toohrVyk's answer.

Of course you could always go for both and use a threaded tree... J/K!

Share this post


Link to post
Share on other sites
Which kind of tree is the best choice in this situation.

Red / Black and AVL threes are well ordered but cause a great deal of extra work to be done every time an allocation happens.

Share this post


Link to post
Share on other sites
You still haven't told us what kind of allocator you're writing...
For general purpose allocations there's generally isn't much sense in trying to improve on the standard allocators.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!