C++ Sized Deallocation

ISO/IEC JTC1 SC22 WG21 N3778 - 2013-09-27

Lawrence Crowl, Lawrence@Crowl.org

Problem
Solution
    Size Unavailable
    Backwards Compatiblity
Implementation
Wording
    3.7.4 Dynamic storage duration [basic.stc.dynamic]
    3.7.4.2 Deallocation functions [basic.stc.dynamic.deallocation]
    5.3.4 New [expr.new]
    5.3.5 Delete [expr.delete]
    12.5 Free store [class.free]
    17.6.4.6 Replacement functions [replacement.functions]
    18.6 Dynamic memory management [support.dynamic]
    18.6.1.1 Single-object forms [new.delete.single]
    18.6.1.2 Array forms [new.delete.array]
    20.8.9.1 allocator members [allocator.members]
    C.?.? Clause 3: Basic concepts [diff.cpp11.basic]
Revision History
References

Problem

With C++11, programmers may define a static member function operator delete that takes a size parameter indicating the size of the object to be deleted. The equivalent global operator delete is not available. This omission has unfortunate performance consequences.

Modern memory allocators often allocate in size categories, and, for space efficiency reasons, do not store the size of the object near the object. Deallocation then requires searching for the size category store that contains the object. This search can be expensive, particularly as the search data structures are often not in memory caches.

Solution

Permit implementations and programmers to define sized versions of the global operator delete. The compiler shall call the sized version in preference to the unsized version when the sized version is available.

There are two potential problems with this solution.

Size Unavailable

When deleting an incomplete type, there is no size available. In this case, the unsized version must be used. This observation implies that calls to one version must be effectively equivalent to calls to the other version. Excepting the specific deallocation function called, we believe that any programs that would change behavior already have undefined behavior within the standard.

Backwards Compatiblity

Existing programs use only the unsized version. Linking them with a new system allocation library that provides the sized version is safe because the unsized version is equivalent. Interposing a new user allocation library on old code is safe for the same reason.

New programs using the sized version linking against an old system allocation library would fail to link. This can be fixed with the addition of a small shim, in which a sized version simply forwards to the unsized version. Likewise with new binaries linked against a new application allocation library.

The primary problem occurs when the system allocation library is new, but an interposed user allocation library is old. In new programs, calls to the unsized version would go to the user library, but calls to the sized version would go to the system library. However, as currently defined, default the sized version calls the unsized version. Programmers that desire the improved performance must take positive action. The intent is that in some future standard, this default will change. In that case, there would be a mismatch in allocators.

The remaining issue is diagnosing the case of a future change in default. Since interposition is often done at the binary level, there appears to be no diagnostic solution other than changing the signature of all allocation functions. The pain of the ABI change would be larger than the pain of adding shims at the appropriate places.

Implementation

Google has implemented much of this proposal within GCC (at the library level) and TCMalloc [TCM]. It has obtained significant performance improvements.

Wording

The proposed wording changes are relative to N3691.

There are no direct inconsistencies with N3396 Dynamic memory allocation for over-aligned data. However, the final paper adopted must address the issue of sized deallocation of over-aligned types.

Editorial, resolutions to core issue 255 might affect the proposed text.

3.7.4 Dynamic storage duration [basic.stc.dynamic]

Edit within paragraph 2 as follows.

.... The following allocation and deallocation functions (18.6) are implicitly declared in global scope in each translation unit of a program. 


void* operator new(std::size_t);
void* operator new[](std::size_t);
void operator delete(void*) noexcept;
void operator delete[](void*) noexcept;
void operator delete(void*, std::size_t) noexcept;
void operator delete[](void*, std::size_t) noexcept;

These implicit declarations introduce only the function names operator new, operator new[], operator delete, operator delete[]. ....

3.7.4.2 Deallocation functions [basic.stc.dynamic.deallocation]

Edit paragraph 2 as follows.

Each deallocation function shall return void and its first parameter shall be void*. A deallocation function can have more than one parameter. The global operator delete with exactly one parameter is a usual (non-placement) deallocation function. The global operator delete with exactly two parameters, the second of which has type std::size_t, is a usual deallocation function. Similarly, the global operator delete[] with exactly one parameter is a usual deallocation function. The global operator delete[] with exactly two parameters, the second of which has type std::size_t, is a usual deallocation function. [Footnote: This deallocation function precludes use of an allocation function void operator new(std::size_t, std::size_t) as a placement allocation function (C.?.? [diff.cpp11.basic]). —end footnote] If a class T has a member deallocation function named operator delete with exactly one parameter, then that function is a usual (non-placement) deallocation function. If class T does not declare such an operator delete but does declare a member deallocation function named operator delete with exactly two parameters, the second of which has type std::size_t (18.2), then this function is a usual deallocation function. Similarly, if a class T has a member deallocation function named operator delete[] with exactly one parameter, then that function is a usual (non-placement) deallocation function. If class T does not declare such an operator delete[] but does declare a member deallocation function named operator delete[] with exactly two parameters, the second of which has type std::size_t, then this function is a usual deallocation function. A deallocation function can be an instance of a function template. Neither the first parameter nor the return type shall depend on a template parameter. [Note: that is, a deallocation function template shall have a first parameter of type void* and a return type of void (as specified above). —end note] A deallocation function template shall have two or more function parameters. A template instance is never a usual deallocation function, regardless of its signature.

5.3.4 New [expr.new]

Paragraph 13 is unchanged. This paragraph is relevant because one possible global placement new function may become unavailable.

The new-placement syntax is used to supply additional arguments to an allocation function. If used, overload resolution is performed on a function call created by assembling an argument list consisting of the amount of space requested (the first argument) and the expressions in the new-placement part of the new-expression (the second and succeeding arguments). The first of these arguments has type std::size_t and the remaining arguments have the corresponding types of the expressions in the new-placement.

Paragraph 14 is unchanged.

[Example:

Here, x and y are non-negative unspecified values representing array allocation overhead; the result of the new-expression will be offset by this amount from the value returned by operator new[]. This overhead may be applied in all array new-expressions, including those referencing the library function operator new[](std::size_t, void*) and other placement allocation functions. The amount of overhead may vary from one invocation of new to another. —end example]

Edit paragraph 22 as follows. This paragraph is relevant because the example now applies at global scope as well as at class scope.

A declaration of a placement deallocation function matches the declaration of a placement allocation function if it has the same number of parameters and, after parameter transformations (8.3.5), all parameter types except the first are identical. Any non-placement deallocation function matches a non-placement allocation function. If the lookup finds a single matching deallocation function, that function will be called; otherwise, no deallocation function will be called. If the lookup finds the two-parameter form of a usual deallocation function (3.7.4.2) and that function, considered as a placement deallocation function, would have been selected as a match for the allocation function, the program is ill-formed. For a non-placement allocation function, the normal deallocation function lookup is used to find the matching deallocation function (5.3.5) [Example: 

struct S {
  // Placement allocation function:
  static void* operator new(std::size_t, std::size_t);
  // Usual (non-placement) deallocation function:
  static void operator delete(void*, std::size_t);
};

S* p = new (0) S; // ill-formed: non-placement deallocation function matches
                  // placement allocation function

—end example]

5.3.5 Delete [expr.delete]

Paragraph 1 remains unchanged, though note the restrictions on the delete operand.

.... The operand shall be of pointer to object type of of class type. If of class type, the operand is contextually implicitly converted (Clause 4) to a pointer to object type. The delete-expression's result has type void. [Footnote: This implies that an object cannot be deleted using a pointer of type void* because void is not an object type. —end footnote]

Paragraph 2 remains unchanged, though note the restriction on inheritance with respect to the delete operand.

.... In the first alternative (delete object), the value of the operand of delete may be a null pointer value, a pointer to a non-array object created by a previous new-expression, or a pointer to a subobject (1.8) representing a base class of such an object (Clause 10). If not, the behavior is undefined. In the second alternative (delete array), the value of the operand of delete may be a null pointer value or a pointer value that resulted from a previous array new-expression. [Footnote: For non-zero-length arrays, this is the same as a pointer to the first element of the array created by that new-expression. Zero-length arrays do not have a first element. —end footnote] If not, the behavior is undefined. [Note: this means that the syntax of the delete-expression must match the type of the object allocated by new, not the syntax of the new-expression. —end note] ....

Paragraph 3 remains unchanged, though note the further restriction on inheritance.

In the first alternative (delete object), if the static type of the object to be deleted is different from its dynamic type, the static type shall be a base class of the dynamic type of the object to be deleted and the static type shall have a virtual destructor or the behavior is undefined. In the second alternative (delete array) if the dynamic type of the object to be deleted differs from its static type, the behavior is undefined.

Paragraph 5 remains unchanged.

If the object being deleted has incomplete class type at the point of deletion and the complete class has a non-trivial destructor or a deallocation function, the behavior is undefined.

Edit paragraph 9 as follows.

When the keyword delete in a delete-expression is preceded by the unary :: operator, the global deallocation function is used to deallocate the storage. the deallocation function's name is looked up in global scope. Otherwise, the lookup considers class-specific deallocation functions (12.5 [class.free]). If no class-specific deallocation function is found, the deallocation function's name is looked up in global scope.

Add a new paragraph as follows.

If the type is complete and if deallocation function lookup finds both a usual deallocation function with only a pointer parameter and a usual deallocation function with both a pointer parameter and a size parameter, then the selected deallocation function shall be the one with two parameters. Otherwise, the selected deallocation function shall be the function with one parameter.

Move paragraph 5 of 12.5 to here and edit it as follows. Note the commas inserted into the footnote.

When a delete-expression is executed, the selected deallocation function shall be called with the address of the block of storage to be reclaimed as its first argument, and (if the two parameter style deallocation function is used), the size of the block as its second argument. [Footnote: If the static type of the object to be deleted is complete and is different from the dynamic type, and the destructor is not virtual, the size might be incorrect, but that case is already undefined; see 5.3.5, as stated above. —end footnote]

12.5 Free store [class.free]

Edit paragraph 4 as follows.

Class-specific deallocation function lookup is a part of general deallocation function lookup (5.3.5 [expr.delete]) and occurs as follows. If a delete-expression begins with a unary :: operator, the deallocation function's name is looked up in global scope. Otherwise, if If the delete-expression is used to deallocate a class object whose static type has a virtual destructor, the deallocation function is the one selected at the point of definition of the dynamic type's virtual destructor (12.4). [Footnote: A similar provision is not needed for the array version of operator delete because 5.3.5 requires that in this situation, the static type of the object to be deleted be the same as its dynamic type. —end footnote] Otherwise, if the delete-expression is used to deallocate an object of class T or array thereof, the static and dynamic types of the object shall be identical and the deallocation function's name is looked up in the scope of T. If this lookup fails to find the name, the name is looked up in the global scope. general deallocation function lookup (5.3.5 [expr.delete]) continues. If the result of the lookup is ambiguous or inaccessible, or if the lookup selects a placement deallocation function, the program is ill-formed.

Move paragraph 5 to 5.3.5/9++.

17.6.4.6 Replacement functions [replacement.functions]

Edit paragraph 2 as follows.

A C++ program may provide the definition for any of eight twelve dynamic memory allocation function signatures declared in header <new> (3.7.4, Clause 18 18.4 [support.dynamic]):

18.6 Dynamic memory management [support.dynamic]

Edit within the synopsis add the following. 


....
void operator delete(void* ptr) noexcept;
void operator delete(void* ptr, const std::nothrow_t&) noexcept;
void operator delete(void* ptr, std::size_t size) noexcept;
void operator delete(void* ptr, std::size_t size,
                     const std::nothrow_t&) noexcept;
....
void operator delete[](void* ptr) noexcept;
void operator delete[](void* ptr, const std::nothrow_t&) noexcept;
void operator delete[](void* ptr, std::size_t size) noexcept;
void operator delete[](void* ptr, std::size_t size,
                       const std::nothrow_t&) noexcept;

18.6.1.1 Single-object forms [new.delete.single]

Edit the synopsis before paragraph 10 as follows.

void operator delete(void* ptr) noexcept;
void operator delete(void* ptr, std::size_t size) noexcept;

Edit paragraph 11 as follows.

Replaceable: a C++ program may define a function with this function signature void operator delete(void* ptr) noexcept that displaces the default version defined by the C++ standard. If this function (without size parameter) is defined, the program should also define void operator delete(void* ptr, std::size_t size) noexcept. If this function with size parameter is defined, the program shall also define the version without the size parameter. [Note: The default behavior below may change in the future, which will require replacing both deallocation functions when replacing the allocation function. —end note]

After paragraph 13, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument shall equal the size argument passed to the allocation function that returned ptr.

After paragraph 13, insert a new paragraph as follows.

Required behavior: Calls to operator delete(void* ptr, std::size_t size) may be changed to calls to operator delete(void* ptr) without affecting memory allocation. [Note: A conforming implementation is for operator delete(void* ptr, std::size_t size) to simply call operator delete(ptr). —end note]

Add a new paragraph before paragraph 14 as follows.

Default behavior: the function operator delete(void* ptr, std::size_t size) calls operator delete(ptr). [Note: See the note in the above Replaceable paragraph. —end note]

Paragraph 14 is unchanged. It applies to both functions.

If ptr is null, does nothing. Otherwise, reclaims the storage allocated by the earlier call to operator new.

Edit the synopsis before paragraph 16 as follows.

void operator delete(void* ptr, const std::nothrow_t&) noexcept;
void operator delete(void* ptr, std::size_t size, const std::nothrow_t&) noexcept;

Edit paragraph 17 as follows.

Replaceable: a C++ program may define a function with this function signature void operator delete(void* ptr, const std::nothrow_t&) noexcept that displaces the default version defined by the C++ standard. If this function (without size parameter) is defined, the program should also define void operator delete(void* ptr, std::size_t size, const std::nothrow_t&) noexcept. If this function with size parameter is defined, the program shall also define the version without the size parameter. [Note: The default behavior below may change in the future, which will require replacing both deallocation functions when replacing the allocation function. —end note]

After paragraph 18, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 18, insert a new paragraph as follows.

Required behavior: Calls to operator delete(void* ptr, std::size_t size, const std::nothrow_t&) may be changed to calls to operator delete(void* ptr, const std::nothrow_t&) without affecting memory allocation. [Note: A conforming implementation is for operator delete(void* ptr, std::size_t size, const std::nothrow_t&) to simply call operator delete(void* ptr, const std::nothrow_t&). —end note]

Edit paragraph 19 as follows.

Default behavior: operator delete(void* ptr, std::size_t size, const std::nothrow_t&) calls operator delete(ptr, std::nothrow), and operator delete(void* ptr, const std::nothrow_t&) calls operator delete(ptr).

18.6.1.2 Array forms [new.delete.array]

Edit the synopsis before paragraph 9 as follows.

void operator delete[](void* ptr) noexcept;
void operator delete[](void* ptr, std::size_t size) noexcept;

Edit paragraph 10 as follows.

Replaceable: a C++ program may define a function with this function signature void operator delete[](void* ptr) noexcept that displaces the default version defined by the C++ standard. If this function (without size parameter) is defined, the program should also define void operator delete[](void* ptr, std::size_t size) noexcept. If this function with size parameter is defined, the program shall also define the version without the size parameter. [Note: The default behavior below may change in the future, which will require replacing both deallocation functions when replacing the allocation function. —end note]

After paragraph 11, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 11, insert a new paragraph as follows.

Required behavior: Calls to operator delete[](void* ptr, std::size_t size) may be changed to calls to operator delete[](void* ptr) without affecting memory allocation. [Note: A conforming implementation is for operator delete[](void* ptr, std::size_t size) to simply call operator delete[](void* ptr). —end note]

Edit paragraph 13 as follows.

Default behavior: operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) calls operator delete[](ptr, std::nothrow), and operator delete[](void* ptr, const std::nothrow_t&) calls operator delete(ptr).

Edit the synopsis before paragraph 14 as follows.

void operator delete[](void* ptr, const std::nothrow_t&) noexcept;
void operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) noexcept;

Edit paragraph 15 as follows.

Replaceable: a C++ program may define a function with this function signature void operator delete[](void* ptr, const std::nothrow_t&) noexcept that displaces the default version defined by the C++ standard. If this function (without size parameter) is defined, the program should also define void operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) noexcept. If this function with size parameter is defined, the program shall also define the version without the size parameter. [Note: The default behavior below may change in the future, which will require replacing both deallocation functions when replacing the allocation function. —end note]

After paragraph 16, insert a new paragraph as follows.

Requires: If present, the std::size_t size argument must equal the size argument passed to the allocation function that returned ptr.

After paragraph 16, insert a new paragraph as follows.

Required behavior: Calls to operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) may be changed to calls to operator delete[](void* ptr, const std::nothrow_t&) without affecting memory allocation. [Note: A conforming implementation is for operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) to simply call operator delete[](void* ptr, const std::nothrow_t&). —end note]

Edit paragraph 17 as follows.

Default behavior: operator delete[](void* ptr, std::size_t size, const std::nothrow_t&) calls operator delete[](ptr, std::nothrow), and operator delete[](void* ptr, const std::nothrow_t&) calls operator delete[](ptr).

20.8.9.1 allocator members [allocator.members]

Edit paragraph 10 as follows.

Remark: Uses ::operator delete(void*, std::size_t) (18.6.1), but it is unspecified when this function is called.

C.?.? Clause 3: Basic concepts [diff.cpp11.basic]

Add a new paragraph as follows.

Change: New usual (non-placement) deallocator
Rationale: Required for new features.
Effect on original feature: In C++ 2011, one could declare a global placement allocation function and deallocation function as follows. 

void operator new(std::size_t, std::size_t);
void operator delete(void*, std::size_t) noexcept;

Now, however, the declaration of operator delete might match a predefined usual (non-placement) operator delete (3.7.4 [basic.stc.dynamic]). If so, the program is ill-formed, as it was for class member allocation functions and deallocation functions (5.3.4 [new.expr]).

Revision History

This paper revises N3663 - 2013-04-30 as follows.

N3663 revised N3536 as follows.

N3536 revised N3432 - 2012-09-23 as follows.

References

[TCM]
TCMalloc : Thread-Caching Malloc, http://goog-perftools.sourceforge.net/doc/tcmalloc.html.