Sign in to follow this  
SeraphLance

Linked List vs. Ring Buffer for memory pool management

Recommended Posts

So I had to write a pool allocator for something I've been working on, and my original implementation involved a large memory allocation of MAX_SIZE size, with a circular buffer of pointers (of MAX_SIZE size) each initially pointing to a sequential element in the pool.  allocation would remove an element from the beginning and return it, whereas freeing would add an element to the end.  Looking at my handy copy of Game Programming Architecture, the book mentions exactly this, but with an in-place linked list (a la malloc) as the free list.

 

Besides the memory usage difference (which is fairly minimal in my case), is there any advantage to doing it the latter way?  They're both O(1) alloc and free, and neither has any particularly advantageous cache performance as far as I can see.  I'm probably going to do it the latter way because it seems more "canonical" and because it's not terribly hard to change, but I was just wondering if there was an elephant in the room I was missing.

Share this post


Link to post
Share on other sites
Profile them both and find out.

The only thing that comes to mind is that the ring buffer is going to be FILO where as the linked list will be FIFO when it comes to de-allocated pointer reuse. This may cause memory to fragment depending on how you obtain the memory for these buffers and what else you're doing with your allocator.

But again - profile.

Share this post


Link to post
Share on other sites

Profile them both and find out.

The only thing that comes to mind is that the ring buffer is going to be FILO where as the linked list will be FIFO when it comes to de-allocated pointer reuse. This may cause memory to fragment depending on how you obtain the memory for these buffers and what else you're doing with your allocator.

But again - profile.

 

I think I probably wasn't specific enough.  This is a pool allocator for fixed-size objects.  Memory fragmentation in this case isn't meaningful.

 

I'm less worried about the sort of thing I can find out with a profiler (because, well, I can find out with a profiler), but more things in the class of "yeah, but if you take out multiple things at once, it doesn't play nice with threads", or like you said, the difference between LIFO and FIFO in this case.  However, since even that can change (since the circular buffer can be either LIFO or FIFO pretty trivially), I suppose it's a more theoretical question of whether to use a ring buffer or a linked list when either data structure does a given job.

Share this post


Link to post
Share on other sites
I see no good reason to use a ring buffer. You can implement a stack of free nodes (e.g. your inline linked list) and get better performance. You want to return recently-used blocks since that memory is more likely hot in cache.

Since it's not 100% clear from your post: definitely use a single block of memory and make your linked list inline. Otherwise you're implementing something terrible.

Pools like this are not typically thread-safe. You can with a lot of skill make it thread-safe via atomics but there are problems you have to be aware of (e.g. the ABA problem) and make sure not to fall prey to them.

If the objects are meant to be used by multiple threads (even if the allocator itself is not meant to be used by multiple threads!) then align the elements to a multiple of the cacheline size so you avoid false-sharing problems (e.g., so if two threads are working with adjacent objects, they aren't constantly invalidating each other's cache).

Share this post


Link to post
Share on other sites

I see no good reason to use a ring buffer. You can implement a stack of free nodes (e.g. your inline linked list) and get better performance. You want to return recently-used blocks since that memory is more likely hot in cache.

Since it's not 100% clear from your post: definitely use a single block of memory and make your linked list inline. Otherwise you're implementing something terrible.

Pools like this are not typically thread-safe. You can with a lot of skill make it thread-safe via atomics but there are problems you have to be aware of (e.g. the ABA problem) and make sure not to fall prey to them.

If the objects are meant to be used by multiple threads (even if the allocator itself is not meant to be used by multiple threads!) then align the elements to a multiple of the cacheline size so you avoid false-sharing problems (e.g., so if two threads are working with adjacent objects, they aren't constantly invalidating each other's cache).

 

Thanks.  I hadn't considered false-sharing problems, and I didn't even know what the ABA problem was before reading this (though I suspect it's a non-issue for my particular use case), but this is exactly what I was looking for.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this