Sign in to follow this  
Acetate

Pool: heap vs. stack allocation

Recommended Posts

Acetate    122
Hello, In my game (but it's a general question..), I am using a pool implementation designed by myself, that is: which may be flawed. It is composed of a vector or list of dynamically-allocated arrays of a fixed size which I call 'clusters'. The template signature is something like: Pool<OBJECT_TYPE, CLUSTER_SIZE>. The pool allocates a new cluster on the heap every time its capacity needs to be expanded. Only a few clusters should exist at a time, not zillions, it's more of a convenience trick. I wrote it like this so that I don't have to bother whether the pool is depleted and handle special cases, as it cannot happen (well, unless the system runs out of memory of course). That way, it also suits a broader range of applications. However, doesn't a heap-allocated pool defeats the goal of the concept? I am wondering whether I should use a simpler, stack-allocated pool with a fixed, large capacity (a part of it remaining unused). Or with a not-so-large capacity but with a pool depletion handling system. What do you think (regarding performance, memory fragmentation, anything...)?

Share this post


Link to post
Share on other sites
Antheus    2409
Quote:
Original post by Acetate
What do you think (regarding performance, memory fragmentation, anything...)?


It's possible to write several graduation thesis' about this topic.

Short version: heap is fine, stack can sometimes be faster.

Share this post


Link to post
Share on other sites
Sneftel    1788
Quote:
Original post by Acetate
However, doesn't a heap-allocated pool defeats the goal of the concept?

Well, that depends on what the goal of the concept is. What costs of going to the kernel for allocation are you trying to mitigate? What are you using to allocate memory from the "heap", and why did you choose that method?

Share this post


Link to post
Share on other sites
iMalc    2466
In my pool allocator I allocate on the heap and double the size of the cluster allocated each time, keeping the old clusters too of course. This works very well and all items (PODs) can be dumped very quickly.

Share this post


Link to post
Share on other sites
I've wasted some time on rather extensive benchmarks with allocators, and the gains are in my opinion not at all worth the trouble.
Getting a simple pooled allocator more than twice as fast as the standard allocator is hard, if you don't want it to crash and burn as soon as someone says "thread" in the other room.
The standard allocators may be a little slower, but they are by all means fast enough unless you do stupid things, and they're guaranteed to be safe in every environment.

Besides, some "very fast" allocators, for example the one in one of the later Game Programming Gems books, don't run any faster at all, but they add complexity. In fact, I've seen some "fast" allocators run considerably slower than GNU's default one (which is Hoard, I think... not sure), especially with several concurring threads. A lot of care is needed there to pick the right thing.

So, like Antheus said: heap is fine, and use the stack when you can. Try not to allocate and free more than 50,000 single objects every frame, and it won't be an issue.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Acetate
However, doesn't a heap-allocated pool defeats the goal of the concept?


Not at all. What takes time when you allocate from the heap is finding a chunk suitable for the allocation. When you've already set up a pool, you already know where the chunk is: i.e., where the pool says it is. Even if your pool is based on a linked list of nodes (where you put nodes back in the pool when you're done with memory instead of calling delete), you'll only have to allocate each node once. And if that creates significant overhead (I.e. you have to allocate a new node a significant fraction of the time, instead of using one already pooled), then you don't have a problem where a pool is of much help anyway.

Quote:
I am wondering whether I should use a simpler, stack-allocated pool with a fixed, large capacity (a part of it remaining unused).


It might be faster, but you have to keep in mind that with a stack-allocated pool, the client code will have to be careful of the pool's lifetime (scope). And you won't be able to resize it. (And stack space is usually rather limited compared to heap space, too, so you can't just make the array size a gazillion to be sure of not running out.) Oh, and that kind of thing is ugly anyway. :)

EDIT: For some reason I initally thought I was reading this in FB.

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