Source: http://open-std.org/JTC1/SC22/WG21/docs/papers/2018/p0901r2.html
Timestamp: 2019-04-23 17:56:28+00:00

Document:
Provide access to actual malloc buffer sizes for users.
2.1 How many ::operator new's?
Throughout this document "malloc" refers to the implementation of ::operator new both as fairly standard practice for implementers, and to make clear the distinction between the interface and the implementation.
All reasonable implementations of malloc round sizes, both for alignment requirements and improved performance. It is extremely unlikely that malloc provided us exactly 37 bytes. We do not need to invoke the allocator here...except that we don’t know that for sure, and to use the 38th byte would be undefined behavior. We would like that 38th byte to be usable without a roundtrip through the allocator.
This is a good start, and does in fact work to allow vector and friends to use the true extent of returned objects. But there are three significant problems with this approach.
While many allocators have a deterministic map from requested size to allocated size, it is by no means guaranteed that all do. Presumably they can make a reasonably good guess, but if two calls to ::operator new(37) might return 64 and 128 bytes, we’d definitely rather know the right answer, not a conservative approximation.
Allocation is often a crucial limit on performance. Most allocators compute the returned size of an object as part of fulfilling that allocation...but if we make a second call to nallocx, we duplicate all that communication, and also the overhead of the function call.
Google’s malloc implementation (TCMalloc) rounds requests to one of a small (<100) number of sizeclasses: we maintain local caches of appropriately sized objects, and cannot do this for every possible size of object. Originally, these sizeclasses were just reasonably evenly spaced among the range they cover. Since then, we have used extensive telemetry on allocator use in the wild to tune these choices. In particular, as we know (approximately) how many objects of any given size are requested, we can solve a fairly simple optimization problem to minimize the total internal fragmentation for any choice of N sizeclasses.
Widespread use of nallocx breaks this. By the time TCMalloc’s telemetry sees a request that was hinted by nallocx, to the best of our knowledge the user wants exactly as many bytes as we currently provide them. If a huge number of callers wanted 40 bytes but were currently getting 48, we’d lose the ability to know that and optimize for it.
Note that we can’t take the same telemetry from nallocx calls: we have no idea how many times the resulting hint will be used (we might not allocate at all, or we might cache the result and make a million allocations guided by it.) We would also lose important information in the stack traces we collect from allocation sites.
Optimization guided by malloc telemetry has been one of our most effective tools in improving allocator performance. It is important that we fix this issue without losing the ground truth of what a caller of ::operator new wants.
These three issues explain why we don’t believe nallocx is a sufficient solution here.
This is worse than nallocx. It fixes the non-constant size problem, and avoids a feedback loop, but the performance issue is worse (this is the major issue fixed by [SizedDelete]!), and what’s worse, the above code invokes UB as soon as we touch byte new_cap+1. We could in principle change the standard, but this would be an implementation nightmare.
We should also quickly examine why the classic C API realloc is insufficient.
In principle a realloc from 37 to 38 bytes wouldn’t carry the full cost of allocation. But it’s dramatically more expensive than making no call at all. What’s more, there are a number of more complicated dynamic data structures that store variable-sized chunks of data but are never actually resized. These data structures still deserve the right to use all the memory they’re paying for.
Furthermore, realloc's original purpose was not to allow the use of more bytes the caller already had, but to (hopefully) extend an allocation in place to adjacent free space. In a classic malloc implementation this would actually be possible...but most modern allocators use variants of slab allocation. Even if the 65th byte in a 64-byte allocation isn’t in use, they cannot be combined into a single object; it’s almost certainly required to be used for the next 64-byte allocation. In the modern world, realloc serves little purpose.
We propose adding new overloads of ::operator new that directly inform the user of the size available to them. C++ makes ::operator new replaceable (15.5.4.6), allowing a program to provide its own version different from the implementation.
More importantly, this form is less efficient. In practice, underlying malloc implementations provide actual definitions of ::operator new symbols which are called like any other function. Passing a reference parameter requires us to actually return the size via memory.
Linux ABIs support returning at least two scalar values in registers (even if they’re members of a trivially copyable struct) which can be dramatically more efficient.
The [MicrosoftABI] returns large types by pointer, but this is no worse than making the reference parameter an inherent part of the API.
Effects: returns a pair (p, n) with n >= size. Behaves as if p was the return value of a call to ::operator new(n).
The intention is quite simple: we return the "actual" size of the allocation, and rely on "as if" to do the heavy lifting that lets us use more than size bytes of the resulting allocation. In particular, this means at no point do we risk undefined behavior from using more bytes than ::operator new was called with.
2.1. How many ::operator new's?
It is unfortunate that we have so many permutations of ::operator new--eight seems like far more than we should really need! But there really isn’t any significant runtime cost for having them. Use of raw calls to ::operator new is relatively rare: It’s a building block for low-level libraries, allocators ([P0401]), and so on, so the cognitive burden on C++ users is low.
The authors have considered other alternatives to the additional overloads. At the Jacksonville meeting, EWG suggested looking at parameter packs.
Parameter packs do not reduce the number of symbols introduced. Implementers still need to provide implementations each of the n overloads.
Retrofitting parameter packs leaves us with more mangled variants. Implementers need to provide both the legacy symbols as well as the parameter pack-mangled symbols.
Malloc implementations are free to properly override this with a more impactful definition, but this paper poses no significant difficulty for toolchain implementers.
TCMalloc has developed a (currently internal) implementation. While this requires mapping from an integer size class to the true number of bytes, combining this lookup with the allocation is more efficient as we avoid recomputing the sizeclass itself (given a request) or deriving it from the object’s address.
jemalloc is prototyping a smallocx function providing a C API for this functionality [smallocx].
For allocations made with sized_ptr_t-returning ::operator new, we need to relax ::operator delete's size argument (16.6.2.1 and 16.6.2.2). For allocations of T, the size quanta used by the allocator may not be a multiple of sizeof(T), leading to both the original and returned sizes being unrecoverable at the time of deletion.
The underlying heap allocation is made with ::operator new(64, std::return_size_t).
The memory allocator may return a 72 byte object: Since there is no k such that sizeof(T) * k = 72, we can’t provide that value to ::operator delete(void*, size_t). The only option would be storing 72 explicitly, which would be wasteful.
The memory allocator may instead return an 80 byte object (5 T's): We now cannot represent the original request when deallocating without additional storage.
we permit ::operator delete(p, s) where n <= s <= m.
This behavior is consistent with [jemalloc]'s sdallocx, where the deallocation size must fall between the request (n) and the actual allocated size (m) inclusive.
It’s easy to see that this approach nicely solves the problems with nallocx or the like. We pay almost nothing in speed to return an actual-size parameter; allocator telemetry knows actual request sizes exactly; and we are told exactly the size we have, without risk of UB.
For new, pointers to the object created and the end of the allocation.
For new, pointers to the initial element of the array and one past the last element of the array.
The pair of pointers provides convience for use with iterator-oriented algorithms.
We considered alternatives for returning the size.
We could return the size in units of bytes (minus the array allocation overhead).
For new, we may only end up fitting a single T into an allocator size quanta, so the extra space remains unusable. If we can fit multiple T into a single allocator size quanta, we now have an array from what was a scalar allocation site. This cannot be foreseen by the compiler as ::operator new is a replaceable function.
For new, the size in units of T can easily be derived from the returned size in bytes.
For new, this is especially useful for tail-padded arrays, but neglects default-initialized T.
For new, a common use case is expected to be the allocation of arrays of char, int, etc. The size of the overall array is irrelevant for the individual elements.
As discussed for ::operator new in §2 Proposal, a reference parameter poses difficulties for optimizers and involves returning the size via memory (depending on ABI).
For new expressions, we considered alternatively initializing the returned (sz / sizeof(T)) number of elements.
This would avoid the need to explicitly construct / destruct the elements with the additional returned space (if any).
The new-initializer is invoked for the returned number of elements, rather than the requested number of elements. This allows delete to destroy the correct number of elements (by storing sz / sizeof(T) in the array allocation overhead).
The presented proposal (leaving this space uninitialized) was chosen for consistency with new.
[AllocatorExt] considered this problem at the level of the Allocator concept. Ironically, the lack of the above API was one significant problem: how could an implementation of std::allocator provide the requested feedback in a way that would work with any underlying malloc implementation?
If this proposal is accepted, it’s likely that [AllocatorExt] should be taken up again.
Moved from passing std::return_size_t parameter by reference to by value. For many ABIs, this is more optimizable and to the authors' knowledge, no worse on any other.
Added rationale for not using parameter packs for this functionality.
Clarified in §2 Proposal the desire to leverage the existing "replacement functions" wording of the IS, particularly given the close interoperation with the existing ::operator new/::operator delete implementations.
Added a discussion of the Microsoft ABI in §2 Proposal.
Noted in §2.1 How many ::operator new's? the possibility of using a parameter pack.
Added a proposal for §3 New Expressions, as requested by EWG.
Additionally, a discussion of §2.3 Interaction with Sized Delete has been added.

References: §2
 §2
 §2
 §2
 §3
 §2