P0401R1
Providing size feedback in the Allocator interface

Published Proposal,

This version:
http://wg21.link/P0401R1
Authors:
(Google)
Audience:
LEWG, LWG
Project:
ISO/IEC JTC1/SC22/WG21 14882: Programming Language — C++

Abstract

Utilize size feedback from Allocator to reduce spurious reallocations

1. Introduction

This is a library paper to describe how size feedback can be used with allocators:

2. Motivation

Consider code adding elements to vector:

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 (3 * sizeof(int) while constructing v. For several implementations, this request is turned into a 16 byte region.

2.1. Why not realloc

realloc poses several problems problems:

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.

3. Proposal

Wording relative to [N4800].

We propose an optional extension to allocator to return the allocation size.

Table 34 - Cpp17Allocator Requirements
a.allocate(n) X::pointer Memory is allocated for n objects of type T but objects are not constructed. allocate may throw an appropriate exception. [ Note: If n == 0, the return value is unspecified. — end note ]
a.allocate_with_size(n) std::pair<X::pointer, X::size_type> Memory is allocated for at least n objects of type T but objects are not constructed and returned as the first value. The actual number of objects m, such that m>=n, that memory has been allocated for is returned in the second value. allocate may throw an appropriate exception. [ Note: If n == 0, the return value is unspecified. — end note ] {a.allocate(n), n}
a.allocate_with_size(n, y) std::pair<X::pointer, X::size_type> Memory is allocated for at least n objects of type T but objects are not constructed and returned as the first value. The actual number of objects m, such that m>=n, that memory has been allocated for is returned in the second value. allocate may throw an appropriate exception. The use of y is unspecified, but is intended as a hint to aid locality. [ Note: If n == 0, the return value is unspecified. — end note ] {a.allocate(n), n}
a.deallocate(p,n) (not used) Requires: p shall be a value returned by an earlier call to allocate or allocate_with_size that has not been invalidated by an intervening call to deallocate. If this memory was obtained by a call to allocate, n shall match the value passed to allocate to obtain this memory. Otherwise, n shall match the value returned by allocate_with_size to obtain this memory.

Throws: Nothing.

Amend [allocator.traits]:

namespace std {
  template struct allocator_traits {
    ...
    [[nodiscard]] static pointer allocate(Alloc& a, size_type n);
    [[nodiscard]] static pointer allocate(Alloc& a, size_type n, const_void_pointer hint);
    
    [[nodiscard]] static std::pair allocate_with_size(Alloc& a, size_type n);
    [[nodiscard]] static std::pair allocate_with_size(Alloc& a, size_type n, const_void_pointer hint);
    
    ...
  };
}

Amend [allocator.traits.members]:

[[nodiscard]] static pointer allocate(Alloc& a, size_type n);
[[nodiscard]] static pointer allocate(Alloc& a, size_type n, const_void_pointer hint);
[[nodiscard]] static std::pair allocate_with_size(Alloc& a, size_type n);
  • Returns: a.allocate_with_size(n) if that expression is well-formed, otherwise, {a.allocate(n), n}

[[nodiscard]] static pointer allocate(Alloc& a, size_type n, const_void_pointer hint);
  • Returns: a.allocate_with_size(n, hint) if that expression is well-formed; otherwise, a.allocate_with_size(n) if that expression is well-formed: otherwise, {a.allocate(n), n}.

4. Design Considerations

4.1. allocate selection

There are multiple approaches here:

4.2. deallocate changes

We now require flexibility on the size we pass to deallocate. 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 deallocate.

As the true size is expected to be useful for the capacity of a string or vector instance, the returned size is available without additional storage requirements. The original (requested) size is unavailable, so we relax the deallocate size parameter requirements for these allocations.

4.3. Interaction with polymorphic_allocator

std::pmr::memory_resource is implemented using virtual functions. Adding new methods, such as the proposed allocate API would require taking an ABI break.

References

Informative References

[N3495]
Ariane van der Steldt. inplace realloc. 7 December 2012. URL: https://wg21.link/n3495
[N4800]
Working Draft, Standard for Programming Language C++. 2019-01-21. URL: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/n4800.pdf
[P0894R1]
realloc for C++. 2019-01-18. URL: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0894r1.md
[P0901R3]
Size feedback in operator new. 2019-01-21. URL: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0901r3.html