1. Introduction
This is a library paper to describe how size feedback can be used with allocators:
-
In the case of
, the language feature proposed in [P0901R5] could be used.std :: allocator -
In the case of custom allocators, the availability of the traits interface allows standard library containers to leverage this functionality.
2. Motivation
Consider code adding elements to
:
std :: vector < int > v = { 1 , 2 , 3 }; // Expected: v.capacity() == 3 // Add an additional element, triggering a reallocation. v . push_back ( 4 );
Many allocators only allocate in fixed-sized chunks of memory, rounding up
requests. Our underlying heap allocator received a request for 12 bytes (
) while constructing
. For several implementations, this request
is turned into a 16 byte region.
2.1. Why not realloc
poses several problems problems:
-
We have unclear strategies for growing a container. Consider the two options (
anda
) outlined in the comments of the example below. Assume, as with the §2 Motivation example, that there is a 16 byte size class for our underlying allocator.b std :: vector < int > v = { 1 , 2 , 3 }; // Expected: v.capacity() == 3 // Add an additional element. Does the vector: // a) realloc(sizeof(int) * 4), adding a single element // b) realloc(sizeof(int) * 6), attempt to double, needing reallocation v . push_back ( 4 ); // Add another element. // a) realloc(sizeof(int) * 5), fails in-place, requires reallocation // b) size + 1 <= capacity, no reallocation required v . push_back ( 5 ); Option
requires every append (after the initial allocation) try toa
, requiring an interaction with the allocator each time.realloc Option
requires guesswork to probe the allocator’s true size. By doubling (the typical growth pattern forb
in libc++ and libstdc++), we skip past the existing allocation’s size boundary. While we can use a reduced growth rate, doing so requires more interactions with the allocator (calls tostd :: vector
), as well as copies (when we cannot resize in-place).realloc Both of these options add extra branching on the control flow for growing the buffer.
-
When the allocator cannot resize the buffer in-place, it allocates new memory and
's the contents. For non-trivially copyable types, this is disastrous. The language lacks support for reallocating in-place without moving. While this function could be implemented as magic library function, it could not interact with many underlyingmemcpy
implementations (libc, in the case of libc++ and libstdc++) used to buildmalloc
, nor could it interact with user-provided replacement functions.operator new In-place reallocation has been considered in [N3495] (throwing
when unable) and [P0894R1] (returningstd :: bad_alloc false
when unable). This has sometimes been referred to as an "extend" or an "expand" interface. Extending an existing allocation requires a round-trip to the allocator (and its requisite branch/call overheads) to determine whether the allocation could be expanded. As discussed previously, we need to probe for the true size of the backing object (until we find extend fails) until we give up and apply a multiplicative expansion factor.
For fixed-size allocators it makes more sense, and is much simpler for containers to adapt to, if the allocator is able to over-allocate on the initial request and inform the caller how much memory was made available.
2.2. Why not ask the allocator for the size
We could also explore APIs that answer the question: "If I ask for
bytes,
how many do I actually get?" [jemalloc] calls this
.
-
requires an extra call / size calculation. This requires we duplicate work, as the size calculation is performed as part of allocation itself.nallocx -
impairs telemetry for monitoring allocation request sizes. If anallocx
return value is cached, the user appears to be asking for exactly as many bytes asnallocx
said they would get.nallocx
See also [P0901R5]'s discussion "
: not as awesome as it looks."
3. Proposal
Wording relative to [N4800].
We propose a free function to return the allocation size simultaneously with an allocation.
Amend [allocator.requirements]:
template < typename T = void > struct sized_ptr_t { T * ptr ; size_t n ; }; template < typename T , typename Allocator = std :: allocator < T >> sized_ptr_t < T > allocate_at_least ( Allocator & a , size_t n );
- Effects: Let
be the result of
s . Memory is allocated for at least
allocate_at_least ( a , n ) objects of type
n but objects are not constructed.
T - Returns:
, where
sized_ptr_t { ptr , m } is that memory and
ptr is the number of objects for which memory has been allocated, such that
m .
m >= n - [ Note: If
, the value of
s . n == 0 is unspecified. —
s . ptr end note] Table 34 - Cpp17Allocator Requirements
a . deallocate ( p , n ) (not used) Requires: shall be a value returned by an earlier call to
p or
allocate that has not been invalidated by an intervening call to
allocate_at_least . If this memory was obtained by a call to
deallocate ,
allocate shall match the value passed to
n to obtain this memory. Otherwise,
allocate shall satisfy
n where
capacity >= n >= requested was used to obtain this memory.
[ p , capacity ] = allocate_at_least ( requested ) Throws: Nothing.
4. Design Considerations
4.1. allocate
selection
There are multiple approaches here:
-
Return a pointer-size pair, as presented.
-
Overload
and return via a reference parameter. This potentially hampers optimization depending on ABI, as the value is returned via memory rather than a register.allocate
4.2. deallocate
changes
We now require flexibility on the size we pass to
. For container
types using this allocator interface, they are faced with the choice of storing both the original size request as well as the provided size (requiring
additional auxillary storage), or being unable to reproduce one during the call
to
.
As the true size is expected to be useful for the
of a
or
instance, the returned size is available without additional storage
requirements. The original (requested) size is unavailable, so we relax the
size parameter requirements for these allocations.
4.3. Interaction with polymorphic_allocator
is implemented using virtual functions. Adding new
methods, such as the proposed allocate API would require taking an ABI break.
5. Revision History
5.1. R1 → R2
Applied LEWG feedback from [Cologne].
Poll: We want a feature like this.
SF F N A SA 2 9 2 0 0
-
As users may specialize
, this revision moves to a free functionstd :: allocator_traits
as suggested via a LEWG poll.std :: allocate_at_least
Poll: Name choice
5
allocate_with_size 4
overallocate 2
allocate_with_oversubscribe 6
allocate_oversize 14
allocate_at_least Poll: Prefer a struct rather than a requirement of structured bindings.
SF F N A SA 2 8 0 2 1