To start off with, please see my update which is now very generic (except the untested vectors):

https://github.com/philippeb8/cache_alloc/blob/main/README.md

"fixed size number of contiguous elements" is not "exactly" like "each
new array block being larger than the previous". It's quite the
opposite in fact. A stack is not a queue; it only grows and shrinks in
one direction. As such, if each new block is bigger than the previous
block, you'll have that many fewer allocations to make.

For example, let's say a stack needs eventually 1000 elements. You
could have a "page" size of 100, and have 10 "pages". Or, you could
have an initial size of 10, and just double it each allocation. So you
start off with a block of 10 elements, then a block of 20, then 40,
etc. How many allocations do you need to cover 1000 elements? Just six
allocations (and you can even go up to 1270 without needing a new
allocation).

Six is less than 10. Exponential is better than linear.

Sorry I read that part quickly and you're right but my goal is to make these linear allocations negligible to the overall operation but you're probably right on this. Let me check it out and see if there's a big difference.

Also, what you've said doesn't really make sense, because the
*container* needs to know this is happening. The pointers between
blocks *cannot* be internal to the allocator; the container needs to
know that they are there and make use of them. When you pop the last
element of a block off of the container, the *container* is the one
that needs to chase down the pointer to the next/previous block. That
requires that the container knows that those pointers exist and how to
access them. Therefore, they *cannot* be internal to the allocator.

Again, this is why you should have started with the container, not the
allocator. You would have quickly seen that the container would be
unable to use any other allocator type. In which case your container
and allocator are really just the same class.

Yeah again I rewrote everything now and the allocator is very generic.

The lion's share of the performance benefits will come from having
such a container type, not from playing around with its allocator.

Also I know a stack knows it's a stack but the way things are abstracted currently, the same generic allocator is used for all container types. So if we specialize the allocator for FIFO / LIFO operations then everything will be maximized optimally.

The only thing the allocator could help with in such a stack is to
hold on to a list of *deallocated* blocks instead of returning them to
the heap immediately. That's maybe nice if you're pushing and popping
a *lot* of elements into and outof the stack.

But such an allocator doesn't even need to know about "blocks". It
just needs to know to hold onto previous allocations instead of
returning them to the heap. It therefore only needs to know about the
allocations themselves.

And even in this event, your implementation is needlessly bulky, with
an external `std::list` instead of storing pointers to the next free
allocation in the freed blocks themselves. If freeing memory requires
heap *allocation*, you're doing your memory allocation wrong.

There is no heap allocation on deletions.

Maybe you could spend some time workshopping ideas on your own before
bringing them up here for review by others. It'd be nice if we had
more fully-formed, well-researched ideas.

You're really supposed to run the executable once, benchmark it with BOOST_BENCHMARK, and adjust the buffers on the need basis. You then create a release version.

--

Phil Bouchard
Founder & CTO
C.: (819) 328-4743