C++ Sized Deallocation

ISO/IEC JTC1 SC22 WG21 N3432 = 12-0122 - 2012-09-23

Lawrence Crowl, crowl@google.com, Lawrence@Crowl.org

Problem
Solution
Implementation
Wording
    3.7.4 Dynamic storage duration [basic.stc.dynamic]
    3.7.4.2 Deallocation functions [basic.stc.dynamic.deallocation]
    5.3.5 Delete [expr.delete]
    12.5 Free store [class.free]
    17.6.3.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]

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.

• 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.

• Existing programs that redefine the global unsized version do not also define the sized version. When an implementation introduces a sized version, the replacement would be incomplete. In this case, the only viable option seems to be for the implementation to emit a diagnostic when the programmer provides an unsized replacement but does not provide a sized replacement. The workaround is to define a sized version that simply calls the unsized version.

  Note, however, that the converse case is not a problem. The programmer may define a both an unsized and a sized version even when the underlying implementation only provides a sized version. The reason is that the two versions must be functionally equivalent.

As a consequence of the second problem, we expect vendor implementations to be somewhat conservative in the introduction of the pre-defined sized versions. On the other hand, programmers may aggressively define the sized versions.

Implementation

Google has implemented much of this proposal within GCC and TCMalloc [TCM]. It has obtained significant performance improvements.

Wording

The proposed wording changes are relative to the Final Committee Draft, N3092.

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) throw(std::bad_alloc);
void* operator new[](std::size_t) throw(std::bad_alloc);
void operator delete(void*) throw();
void operator delete[](void*) throw();

Furthermore, the implementation may implicitly declare the following functions in global scope in each translation unit of a program.

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

If the implementation provides these functions, and if a translation unit provides a definition for an unsized version but not for a sized version, the program is ill-formed.

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. If there is a declaration of global operator delete with exactly two parameters, the second of which has type std::size_t (18.2), then that function is a usual (non-placement) deallocation function. Similarly, if there is a declaration of global operator delete[] with exactly two parameters, the second of which has type std::size_t, then this function is a usual deallocation function. 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.5 Delete [expr.delete]

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

.... The operand shall have a pointer to object type, or a class type having a single non-explicit conversion function (12.3.2) to a pointer to object type. The 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.

.... If it is not a null pointer value, in the first alternative (delete object), the value of the operand of delete shall be a pointer to a non-array object 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 shall be the pointer value which 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. If a delete-expression begins with a unary :: operator, the deallocation function's name is looked up in global scope. Otherwise, the lookup considers class-specific deallocations (12.5 [class.free]). If no class-specific deallocation is found, the deallocation function's name is looked up in global scope. If the lookup selects a placement deallocation function, the program is ill-formed.

Add a new paragraph as follows.

If deallocation function lookup finds both a usual deallocation function with one parameter and a usual deallocation function with two parameters, and then if the object being deleted has a complete class type, the selected deallocation function shall be the one with two parameters. Otherwise, the selected deallocation function shall be the function with one parameter.

Add a new paragraph as follows. This paragraph is identical to the existing 12.5/5.

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 is used) the size of the block as its second argument. [Footnote: If the static type of the object to be deleted is different from the dynamic type and the destructor is not virtual the size might be incorrect, but that case is already undefined, 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. the class-specific deallocation function lookup has failed and 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.

Remove paragraph 5 as follows. This paragraph moves to 5.3.5/9++.

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 is used) the size of the block as its second argument. [Footnote: If the static type of the object to be deleted 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. —end footnote]

17.6.3.6 Replacement functions [replacement.functions]

Edit paragraph 2 as follows.

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

• operator new(std::size_t)
• operator new(std::size_t, const std::nothrow_t&)
• operator new[](std::size_t)
• operator new[](std::size_t, const std::nothrow_t&)
• operator delete(void*)
• operator delete(void*, const std::nothrow_t&)
• operator delete[](void*)
• operator delete[](void*, const std::nothrow_t&)

Furthermore, a C++ program may provide the definition for any of the four dynamic memory deallocation function signatures that implementations may choose to declare in header <new>:

• operator delete(void*, std::size_t)
• operator delete(void*, std::size_t, const std::nothrow_t&)
• operator delete[](void*, std::size_t)
• operator delete[](void*, std::size_t, const std::nothrow_t&)

18.6 Dynamic memory management [support.dynamic]

At the end of the synopsis add the following.

The implementation may, but need not, provide the following additional group of functions.

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

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

At the end of the section, add a new paragraph as follows.

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

Add a new paragraph as follows.

These functions behave as their corresponding version without the std::size_t size parameter, with the additional constraints:

Requires: size shall equal that used to allocate ptr.

Required behavior: Calls to the sized and unsized versions shall be interchangable.

18.6.1.2 Array forms [new.delete.array]

At the end of the section, add a new paragraph as follows.

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

Add a new paragraph as follows.

These functions behave as their corresponding version without the std::size_t size parameter, with the additional constraints:

Requires: size shall equal that used to allocate ptr.

Required behavior: Calls to the sized and unsized versions shall be interchangable.

References

[TCM]

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