Should the allocator parameter to STL container templates be a template parameter?

[Walt Karas]

Specifcally, should it be:  template <typename, size_t> class allocator

The size_t parameter is the fixed size of each allocation.  I've never tried to implement STL containers, but my speculation is that this would enable a variety of allocator implementations with different trade-offs appropriate for different situations.  One could have faster allocation, and less dynamic allocation overhead space, at the expense of not returning as much memory for general allocation upon deallocation (in some cases).

[Thiago Macieira]

On terça-feira, 28 de março de 2017 07:05:29 PDT 'Walt Karas' via ISO C++

Standard - Future Proposals wrote:
> Specifcally, should it be: template <typename, size_t> class allocator
>
> The size_t parameter is the fixed size of each allocation.

What is the fixed size of each allocation for the containers? std::vector (for
example) does not have a fixed size allocation..

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
Software Architect - Intel Open Source Technology Center

[Walt Karas]

OK, that's a good point.  So it seems a better strategy that the allocator remain a class parameter, but be required to have the public members:

template <size_t> pointer fixed_size_alloc();

template <size_t> void fixed_size_dealloc(pointer p);

(Except that, for reasons I don't understand, allocate/deallocate currently use T* rather then pointer for the raw memory pointers.)

One could write short definitions of these that simply call allocate and deallocate if no optimization for certain constant sizes was useful.

vector and deque would get no benefit from this.  But list, the associative containers, and the unordered associative containers (if using chained collision buckets) I think could benefit from dedicated allocators for particular allocation sizes.

[Thiago Macieira]

On terça-feira, 28 de março de 2017 10:09:24 PDT 'Walt Karas' via ISO C++

That sounds like a good plan.

[Nicol Bolas]

I think this is all rather wrongheaded. I think what we really need is the ability to have the allocator more effectively know about what the container is allocating.

There are several patterns of allocations:

* Array of T: The container allocates arrays of the element type `T`. `vector` uses these.
* Array of U: The container allocates arrays of some type `U`, which may or may not be related to the element type `T`. `deque` and the various unordered container uses these. `deque` implementations generally use two separate `U` types: the array of pointers to block and the block type itself.
* Individual node related to T: The container allocates some node type which explicitly depends on `T`. `list`, `forward_list`, and the associative containers use these.

Allocators should be able to specifically support particular patterns, and containers need to be able to communicate the explicit patterns they support. Preferably at a static level.

So you should be able to create an allocator that only supports "node related to T" allocations, and the allocator/user can ask exactly what this type's size/alignment will be for the container. The container will be bound not to request any allocations of different sizes/alignments.

[Walt Karas]

I think also it might be good if the container could somehow pass a "move(pointer_to_empty_spot, pointer_to_live_obj)" callback type thingy to the fixed sized allocator.  This would be helpful if the fixed sized allocator was allocating small things in contiguous blocks from the more general dynamic memory allocator.  It could then perhaps move in-use small things into available spots in a different block, so it could release blocks back to the general memory pool more efficiently. But then the rules about invalidation of iterators and pointer/references into the container would get much more complicated.

[Bo Persson]

On 2017-03-28 19:09, 'Walt Karas' via ISO C++ Standard - Future

Proposals wrote:
>
>
> On Tuesday, March 28, 2017 at 12:26:13 PM UTC-4, Thiago Macieira wrote:
>
> On terça-feira, 28 de março de 2017 07:05:29 PDT 'Walt Karas' via
> ISO C++
> Standard - Future Proposals wrote:
> > Specifcally, should it be: template <typename, size_t> class
> allocator
> >
> > The size_t parameter is the fixed size of each allocation.
>
> What is the fixed size of each allocation for the containers?
> std::vector (for
> example) does not have a fixed size allocation..
>
> --
>
>

> Thiago Macieira - thiago (AT) macieira.info <http://macieira.info> -
> thiago (AT) kde.org <http://kde.org>

> Software Architect - Intel Open Source Technology Center
>
>
> OK, that's a good point. So it seems a better strategy that the
> allocator remain a class parameter, but be required to have the public
> members:
>
> template <size_t> pointer fixed_size_alloc();
> template <size_t> void fixed_size_dealloc(pointer p);
>
> (Except that, for reasons I don't understand, allocate/deallocate
> currently use T* rather then pointer for the raw memory pointers.)
>
> One could write short definitions of these that simply call allocate and
> deallocate if no optimization for certain constant sizes was useful.
>

Can't we just have a node_allocator<T> and use that with std::list? Then
we can have that allocator assume that it will **always** be called with
allocate(1), and optimize for that.


Bo Persson