Archived

This topic is now archived and is closed to further replies.

'sliding slots' memory manager implementation

This topic is 5088 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

This sliding slot algorithm seems like a really neat idea, and I''m trying to implement it in system RAM to try and get the algorithm straight. I understand the concept, but there are some implementation details that I don''t quite understand: First, Yann L says that in his system, the size of the allocated chunks changes size over time. I was originally thinking of having static lists of chunks 64K, 32K, etc in size, but if I want to implement chunks (slots) that change size, how would i go about doing it? Have a map<size_t,list<Object*>>? Another implementation detail.. should I have the Objects store list iterators? Does anyone have any concrete proof that it''s much faster or slower?

Share this post


Link to post
Share on other sites
Check out the binary buddy algorithm.
I wrote a memory manager based on this algorithm and a few others that offered some functionality that I needed and now I have the speed, small memory footprint, and less than 2% fragmentation.

Share this post


Link to post
Share on other sites
I have not understood what sliding-slots are...probably a sort of memory pool manager.
There are different solutions.
If you use lists you can implement a garbage collector list that is a list with an inner (protected) list.
When you remove an element simply move the object in the protected list and vice-versa when you need a new element move the element back in the main list (you can use list::splice to do this) or allocate a new one.
This solution is probably the most effcient and fast if you use lists.

If you need a general solution you must implement what your OS do for you...
This mean that you should allocate big chunks of memory and write your own memory header on them.
In practice you should manage split (when you alloc) and merge (when you free) on these blocks.
You should mantain a list of allocated blocks and free blocks (note that you can use your header to access these lists in O(1) ).
Note that the free block list become smaller also when you free blocks because they can be merged (you start with one big chunck).



This solution is the fastest and memory efficient I was able to think...(probably not the best in general


See also http://www.boost.org/libs/pool/doc/index.html
(I was ''inspired'' by these concepts and I''ve implemented my mempool).

Share this post


Link to post
Share on other sites
Deebo: I''m still in the ''design'' phase for my engine, so any help is appreciated. Which other algorithms did you find worked the best? I''ve looked at the binary buddy system, and one of the things I''d like to figure out is how to use it in conjunction with address manipulation (i.e. there''s supposed to be some way of telling some details of the chunk by manipulating the bits of the address)

blizzard999: Yes, sliding slots hold a list of memory chunks, and when an element is ''deleted,'' it gets moved to the back of the list (or front, depending on how you look at it.)
I think that my implementation will allocate a large chunk of RAM, and then split it into small blocks. The adaptability of this algorithm comes with its ability to change the size of the blocks to best fit the usage of the application.

Share this post


Link to post
Share on other sites
Sliding slots sound like a simple garbage collector list.
I suggest you to implement this solution because it''s simple, fast...and it''s useful for the second solution (big chunk with memory headers).

Share this post


Link to post
Share on other sites
I have a few saved documents that I used while coding mine's. If you want I can e-mail them to you and mabey the source to my memory manager if it will help. It's simply too much and too complicated to explain in one post. In the meantime check out this and this

[edited by - Deebo on January 5, 2004 9:05:14 PM]

Share this post


Link to post
Share on other sites
Thanks Deebo, that was the first site I hit when I first heard about binary buddy systems, though.. for some reason, it doesn''t appeal to me. I mean, I understand the techniques it presents, but I don''t like the site.

If you would (if I didn''t fill in the e-mail in my profile..), could you send some info to psykrathotmaildotcom? Thanks for helping.

Share this post


Link to post
Share on other sites
Hotmail won''t let me e-mail it because its over 1mb. I don''t feel like messing with it right now cuz I''m going out in a minute so in the morning I will e-mal it to you.

Share this post


Link to post
Share on other sites
>>why not upload it to a website and let ppl who want to look
>>grab a copy?
perhaps, because he has no website ?

DJSnow
---
this post is manually created and therefore legally valid without a signature

Share this post


Link to post
Share on other sites
I can host a few megabytes for you, also I'd be interested to see your work
mail me at: bilalt_j at epita dot fr
a 1 or 2 Mb file shouldn't be a problem for the mailbox

[edited by - sBibi on January 7, 2004 2:13:48 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by DJSnow
>>why not upload it to a website and let ppl who want to look
>>grab a copy?
perhaps, because he has no website ?



Plenty of places to get free webspace and most ISPs give you some space, plus ppl like myself could mirror it for download, which i'd be more than happy to do
(size pretty much no problem either)

[edited by - _the_phantom_ on January 7, 2004 2:33:39 PM]

Share this post


Link to post
Share on other sites