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


On 7/25/21 1:18 PM, Jason McKesson wrote:
>
> "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
Fornux Logo <http://www.fornux.com>