Pool: heap vs. stack allocation

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.

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?

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.

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.

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.