LEWG, SG14: P0040R2
2016-05-29
Brent Friedman
fourthgeek@gmail.com

Extending memory management tools

And so it is that we, as men, do not exist until we do; and then it is that we play with our world of existent things, and order and disorder them, and so it shall be that non-existence shall take us back from existence and that nameless spirituality shall return to Void, like a tired child home from a very wild circus.

I. Motivation

It is common for both the standard library and user libraries to manage memory without the use of standard-compliant allocators. They may use internal buffers (like optional) or use an allocator model that does not manage object lifetime [bde] [sgi] [eastl] [bitsquid]. Such alternative allocator models are common in efficiency-critical applications.

Any container-like entity will need to solve the problems of how to create, move, copy, and destroy the objects which it maintains. Optimized, exception-correct implementations of these algorithms aren't necessarily obvious however. For example, destroy can be optimized into a no-op for trivially destructible types and uninitialized_value_construct can be optimized to memset for integral types. Having a standardized implementation of these features will help the performance and correctness of libraries.

II. Summary

The function templates destroy_at, destroy and destroy_n call the destructor for specified elements.
The function templates uninitialized_move and uninitialized_move_n perform move construction of elements over a range of memory, similar to uninitialized_copy.
The function templates uninitialized_value_construct and uninitialized_value_construct_n perform value-initialization of objects over a range of memory.
The function templates uninitialized_default_construct and uninitialized_default_construct_n perform default-initialization of objects over a range of memory.

Destruction order notwithstanding, these algorithms are isomorphic to existing features. The following table summarizes the relevant existing and proposed algorithms.

Our wording for destroy depends on a fix for LWG 2598.

This proposal directly contradicts N0639 which removed earlier versions of these algorithms in 1995. That proposal removed destroy(begin,end) and destroy(pointer) which are identical to the destroy algorithms proposed here. That paper advocated removing these algorithms on the following grounds:

While they may be useful in implementing STL and collections similar to it, they are not really necessary for the purposes of the Standard Library, in that they do not aid communication between modules, implement semantics that cannnot reproduced by users, or provide substantial functionality. Furthermore, they are mostly subsumed by STL allocator members, which are what STL-conforming collections are expected to use.

III. Discussion

Organization

Each following section begins with a table. These tables represent an informal survey of existing practice, made mostly by searching github and the Visual Studio standard library implementation. They are by no means complete or scientific.
Many standard library implementations already contain our algorithms, except in that they take an additional allocator parameter and forward memory management operations into that allocator object. This paper does not propose adding such algorithms. However, for completeness, those algorithms are included in the survey as "+ allocator"

In addition to these surveys, Creative Assembly has noted that they also have internal implementations of these algorithms.

destroy

A design decision must be made regarding the order of destruction in destroy. Should bidirectional iterators destroy objects in reverse order? We argue no, for the following reasons:

• Order of construction and destruction is a property of the container, not a property of the iterator category. Not all containers with bidirectional iterators necessarily imply reverse-order destruction.
• It would be a very strange API which requires users to provide reverse iterators in order to destroy in forward order
• Reverse-order destruction can be provided by explicitly providing a reverse iterator (or, if truly desired, a destroy_reverse algorithm). Explicitness is the key here.
• The semantics of an algorithm should not change based on the iterator category. This could lead to suprises during code maintenance.
• Leaving the order as implementation-defined will likely damage its usefulness

It is conceivable that always destroying in forward order would be seen as suprising behavior to some. However, this is at least a consistent behavior which can be accounted for once understood. If we choose to change the behavior based on iterator category, we create a situation which is difficult for users to control.

A good implementation of destroy should not accept cases where expression *first resolves to an rvalue. For example, dereferencing an iterator could return int or int&& instead of int&. Returning an int is forbidden by our use of ForwardIterator but without Concepts we are as yet unable to enforce this, so an alternative error checking mechanism is needed. With appropriate reslolution of LWG 2598, the expression addressof(*first) will produce an error if *first returns an rvalue.

The specification of destroy_at may seem odd and restrictive in how it requires a non-null pointer rather than a reference or arbitrary iterator type. This design is chosen for the following reasons:

• It matches existing practice in various libraries (see table)
• It is conceptually compatible with allocator::destroy which operates on the allocator's pointer type
• By requiring a pointer, the API makes it difficult to call on a temporary object. If the algorithm operated on a reference or iterator, we would need to do extra work to exclude const T&&s
• The restrictive API makes it somewhat less likely to be called incorrectly. If the API accepted a reference, users might pass in a pointer and the pointer would be destroyed rather than the value to which it points.

All implementations of the standard library which were surveyed have some equivalent of the logic for destroy implemented in the exception handling block of the existing uninitialized_* algorithms.

The author wanted destroy to use InputIterator instead of ForwardIterator. As destroy is a single-pass algorithm, many of the features of ForwardIterator provide more guarantees than are strictly needed. Conversations on std-proposals and in private with Stepanov indicate broad disapproval for using InputIterator in this algorithm, so it has been restricted to the more conservative ForwardIterator. Objections revolved around questions regarding exception handling on iterator operations and a lack of compelling use cases.

uninitialized_move

Some concern is raised about exception handling with respect to uninitialized_move. If a move-constructor throws, the source object may have been irreparably damaged. As there is no solution to this problem, we implement the natural and expected semantics of destroying all fully constructed objects in the destination buffer and propagating the exception. This matches the behavior of uninitialized_copy as closely as possible.
An additional algorithm, uninitialized_move_if_noexcept, could be considered as a resolution to this concern. Such an algorithm was found already implemented in libstdc++ using a move_if_noexcept iterator. Given that there is currently no range-based move_if_noexcept algorithm, such a solution is not considered here. It seems clear that such a feature is readily possible, however.

LWG 2242 reports a defect in copy_n and uninitialized_copy_n. We make no attempt to resolve the existing issue in uninitialized_copy_n, and replicate its flaws in uninitialized_move_n.
During implementation research, it was found that libstdc++ implements a variation of uninitialized_move by combining move_iterator with uninitialized_copy. Although this implementation would provide us with a clever and simple wording, it makes resolution of LWG 2242 more difficult in the future, and so is not used.

uninitialized_value_construct; uninitialized_default_construct

The names uninitialized_value_construct and uninitialized_default_construct were the originally proposed names, and were approved by ballot at Kona. Since that time, this author has grown to prefer the names default_initialize and value_initialize as they more clearly reflect the terminology used in the standard. The words "construct" and "initialize" already imply operating on uninitialized memory so the repetition seems redundant. In respect for Kona's decision, however, the names have been left as per their vote.

The table demonstrates that many libraries use the word "default" to refer to value-initialization. This is likely a historical artifact from a time before the distinction between default-initialization and value-initialization. It may also be caused simply by the fact that allocators provide no mechanism for containers to request one form of initialization over another. We seek to support multiple forms of initialization, so the distinction is important to make clearly.

The solution of using uninitialized_fill to fill a range with a default-initialized or value-initialized object is suboptimal, making this algorithm useful. Using fill presents the following issues:

• Requires unnecessary copy-construction which is not possible for move-only types
• May incur additional overhead

No algorithms equivalent to uninitialized_default_construct were found in our (very incomplete) search. The author believes that the Standard Library would be remiss to support only one form.

IV. Proposed Text

This document is written as a set of changes against n4582.

The existing structure of [specialized.algorithms] made amendments difficult, especially with respect to exception behavior. As such, the proposed wording applies a conservative refactoring in order to make the section more flexible. This wording is copied almost verbatim from 25.1 [algorithms.general]

A minor inconsistency was noted in that uninitialized_copy and uninitialized_copy_n are in the same section, but uninitialized_fill and uninitialized_fill_n are in separate sections. The fill algorithms are combined into one section as part of this wording.

Amend the <memory> header synposis in 20.9.2 [memory.syn]

The header <memory> defines several types and function templates that describe properties of pointers and pointer-like types, manage memory for containers and other template types, destroy objects, and construct multiple objects in uninitialized memory buffers (20.9.3–20.9.12).

// 20.9.12, specialized algorithms:
...
template <class ExecutionPolicy, class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ExecutionPolicy&& exec, // see 25.2.5
ForwardIterator first, Size n, const T& x);


template <class T>
 void destroy_at(T* location); 
 
template <class ExecutionPolicy, class ForwardIterator>
 void destroy(ExecutionPolicy&& exec, //see 25.2.5
 ForwardIterator begin, ForwardIterator end);
 template <class ForwardIterator>
 void destroy(ForwardIterator begin, ForwardIterator end);

template <class ForwardIterator, class Size>
 ForwardIterator destroy_n(ForwardIterator begin, Size n);
template <class ExecutionPolicy&& exec, //see 25.2.5
class ForwardIterator, class Size>
 ForwardIterator destroy_n(ForwardIterator begin, Size n);
 
template <class ExecutionPolicy, class InputIterator, class ForwardIterator>
 ForwardIterator uninitialized_move(ExecutionPolicy&& exec,//see 25.2.5
 InputIterator first, InputIterator last, ForwardIterator result);
 template <class InputIterator, class ForwardIterator>
 ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);
 
template <class ExecutionPolicy, class InputIterator, class Size, class ForwardIterator>
 ForwardIterator uninitialized_move_n(ExecutionPolicy&& exec, //see 25.2.5
 InputIterator first, Size n, ForwardIterator result);
template <class InputIterator, class Size, class ForwardIterator>
 ForwardIterator uninitialized_move_n(InputIterator first, Size n, ForwardIterator result);

template <class ExecutionPolity, class ForwardIterator>
 void uninitialized_value_construct(ExecutionPolicy&& exec, //see 25.2.5
 ForwardIterator first, ForwardIterator last);
template <class ForwardIterator>
 void uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
 
template <class ExecutionPolicy, class ForwardIterator, class Size>
 ForwardIterator uninitialized_value_construct_n(ExecutionPolicy&& exec, //see 25.2.5
 ForwardIterator first, Size n);
template <class ForwardIterator, class Size>
 ForwardIterator uninitialized_value_construct_n(ForwardIterator first, Size n);

 template <class ExecutionPolicy, class ForwardIterator>
 void uninitialized_default_construct(ExecutionPolity&& exec, //see 25.2.5
 ForwardIterator first, ForwardIterator last); 
 template <class ForwardIterator>
 void uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
 
 template <class ExecutionPolicy, class ForwardIterator, class Size>
 ForwardIterator uninitialized_default_construct_n(ExecutionPolicy&& exec, //see 25.2.5
 ForwardIterator first, Size n);
 template <class ForwardIterator, class Size>
 ForwardIterator uninitialized_default_construct_n(ForwardIterator first, Size n);
 
...

Amend [specialized.algorithms] in 20.9.12:

20.9.12 Specialized algorithms [specialized.algorithms]

In the algorithm uninitialized_copy, the template parameter InputIterator is required to satisfy the requirements of an input iterator (24.2.3). In all of the following algorithms, the template parameter ForwardIterator is required to satisfy the requirements of a forward iterator (24.2.5), and is required to have the property that no exceptions are thrown from increment, assignment, comparison, or indirection through valid iterators.
Throughout this Clause, the names of template parameters are used to express type requirements.

• If an algorithm's template parameter is named InputIterator, the template argument shall satisfy the requirements of an input iterator (24.2.3).
• If an algorithm's template parameter is named ForwardIterator, the template argument shall satisfy the requirements of a forward iterator (24.2.5), and is required to have the property that no exceptions are thrown from increment, assignment, comparison, or indirection through valid iterators.

In the descriptions of the algorithms operator + and - observe the same rules as §25.1.12.

20.9.12.1 addressof [specialized.addressof]

template <class T> T* addressof(T& r) noexcept;
    Returns: The actual address of the object or function referenced by r, even in the presence of an overloaded operator&.

20.9.12.2 uninitialized_copy [uninitialized.copy]

template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

    Effects:

        for (; first != last; ++result, (void) ++first)
            ::new (static_cast<void*>(addressof(*result)))
             typename iterator_traits<ForwardIterator>::value_type(*first);

    Returns: result
    Remarks: If an exception is thrown there are no effects.

template <class InputIterator, class Size, class ForwardIterator>
ForwardIterator uninitialized_copy_n(InputIterator first, Size n, ForwardIterator result);

    Effects:

        for ( ; n > 0; ++result, (void) ++first, --n) {
            ::new (static_cast<void*>(addressof(*result)))
            typename iterator_traits<ForwardIterator>::value_type(*first);
        }

    Returns: result
    Remarks: If an exception is thrown there are no effects.

20.9.12.3 uninitialized_fill [uninitialized.fill]

template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

    Effects:

        for (; first != last; ++first)
            ::new (static_cast<void*>(addressof(*first))) typename iterator_traits<ForwardIterator>::value_type(x);

    Remarks: If an exception is thrown there are no effects.

template <class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x);

    Effects:

        for (; n--; ++first)
            ::new (static_cast<void*>(addressof(*first))) typename iterator_traits<ForwardIterator>::value_type(x);

    Returns: first
    Remarks: If an exception is thrown there are no effects.

template <class ForwardIterator>
void destroy(ForwardIterator first, ForwardIterator last);   
    Effects: 
            for(;first!=last;++first)
                destroy_at(addressof(*first));
     

template <class ForwardIterator, class Size>
ForwardIterator destroy_n(ForwardIterator first, Size n);
    Effects: 
            for ( ; n > 0; (void)++first, --n)
                  destroy_at(addressof(*first));
    
    Returns: first
			
template <class T>
void destroy_at(T* location);    
    Effects: 
            location->~T();
    

template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_move(InputIterator first, InputIterator last, ForwardIterator result);

    Effects:

        for (; first != last; ++result, (void) ++first)
            ::new (static_cast<void*>(addressof(*result)))
             typename iterator_traits::value_type(move(*first));

    Returns: result
    Remarks: If an exception is thrown, there are no effects on objects in the range [result,result+(last-first)).
		
template <class InputIterator, class Size, class ForwardIterator>
ForwardIterator uninitialized_move_n(InputIterator first, Size n, ForwardIterator result);    

    Effects:

        for ( ; n > 0; ++result, (void) ++first, --n) {
            ::new (static_cast<void*>(addressof(*result)))
            typename iterator_traits<ForwardIterator>::value_type(move(*first));
        }

    Returns: result
    Remarks: If an exception is thrown, there are no effects on objects in the range [result,result+n).

template<class ForwardIterator>
void uninitialized_value_construct(ForwardIterator first, ForwardIterator last);
    
    Effects: 
	for (; first != last; ++first)
          ::new (static_cast<void*>(addressof(*first)))
            typename iterator_traits<ForwardIterator>::value_type();
    
    Remarks: If an exception is thrown there are no effects.

template<class ForwardIterator, class Size>
ForwardIterator uninitialized_value_construct_n(ForwardIterator first, Size n);
    
    Effects: 
	for (; n>0; (void)++first, --n)
          ::new (static_cast<void*>(addressof(*first)))
            typename iterator_traits<ForwardIterator>::value_type();
    
    Returns: first
    Remarks: If an exception is thrown there are no effects.

template<class ForwardIterator>
void uninitialized_default_construct(ForwardIterator first, ForwardIterator last);
    
    Effects: 
	for (; first != last; ++first)
          ::new (static_cast<void*>(addressof(*first)))
            typename iterator_traits<ForwardIterator>::value_type;
    
    Remarks: If an exception is thrown there are no effects.

template<class ForwardIterator, class Size>
ForwardIterator uninitialized_default_construct_n(ForwardIterator first, Size n);
    
    Effects: 
	for (; n>0; (void)++first, --n)
          ::new (static_cast<void*>(addressof(*first)))
            typename iterator_traits<ForwardIterator>::value_type;
    
    Returns: first
    Remarks: If an exception is thrown there are no effects.

V. Revision history

R2

• Added destroy_n, uninitialized_value_construct_n, uninitialized_default_construct_n for symmetry with existing algorithms.
• Tweaks to iterator categories and return values for better correctness
• Added destroy_at, which makes destroy both simpler and safer.
• Refactored [specialized.algorithm] for simpler wording
• Refactored discussions and surveys
• Rejected alternative wording for uninitialized_move
• Added references to LWG 2422 and 2598
• Added recommendation that we change the name of uninitialized_*_construct algorithms
• Made wording normative against n4582
• Reference and discussion of N0639
• Added cross-reference to 25.1.12
• Improved formatting
• Added amendments to memory.syn
• Added revision history

R1

• Added surveys of existing code
• Added discussion about order of destruction in destroy
• Added alternative wording for uninitialized_move
• Exempted destroy and uninitialized_move from no-effects policy

R0

• Initial revision

VI. Credits

Special thanks is given to Billy Baker and Patrice Roy for feedback and championship. Thanks to Michael Wong for helping to organize this effort. Thanks to Howard Hinnant for feedback regarding uninitialized_move. Thanks to Alexander Stepanov for consultations regarding destroy.