ISO/IEC JTC1 SC22 WG21 N3899 - 2014-01-20
Lawrence Crowl, Lawrence@Crowl.org
Introduction
Local Non-Static Arrays
Enabling Abstraction
Generalizing Storage Class
Nested Lifetime
Nested Allocation
Stack allocation is generally faster than heap allocation.
C and C++ have exploited this speed
by allocating statically-sized local variables on the execution stack.
With the exception of the rather limited alloca facility,
all non-statically-sized objects could only be allocated on the heap.
That is, programmers had the choice between fast-but-limited and general-but-slow.
This paper explores some of the issues when refining allocation choices.
C99 introduced variable-length arrays (VLAs). These arrays may appear only as automatic-duration objects. They are typically implemented as a static-sized handle with a pointer to variable-sized data area. The handle is allocated within the main activation record and the data is separately allocated from the stack. C has variable-length arrays
N3639 Runtime-sized arrays with automatic storage duration (revision 5) defines the C++ equivalent to VLAs. These are called arrays of runtime bound (ARBs). They have the same restrictions and implementations as VLAs.
N3810 Alternatives for Array Extensions
proposes a bs_array (bikeshed name),
which is the std::array equivalent to ARB.
It too has the same restrictions and implementations as VLAs.
The above facilities may only appear as direct local variables, and thus may not be used to implement new data abstractions. I consider this a critical flaw because good abstraction is the great strength of C++.
N3875 Run-time bounded array data members (RBADMs) presents two proposals for extending ARBs to data member variables, thus satisfying the essential requirement for abstraction. The proposals still restrict RBADM and their containing classes to automatic storage duration. That is, an RBADM will prohibit use of all containing classes in static-duration, thread-duration, or dynamic-duration objects.
The essential idea of the proposals is to expose the dynamic size of the array bounds computation to the compiler so that it can allocate the arrays' data areas. This approach requires inlining of the constructors, or at least the part of them concerned with allocation. Furthermore, the inlining is not just nominal, it must also be effective. That is, the constructors must not create a separate activation record.
In essence, the implementation strategy is to promote all allocations (through inlining) to the function (and its activation record) of the complete object.
All of the above facilities require using the complete object only as an automatic variable. Use in static-duration, thread-duration and static-duration variables is prohibited. One of C++'s great strengths is being able to use an abstraction anywhere it is needed. This strength is particularly important in generic contexts.
N3662 C++ Dynamic Arrays
addresses this problem.
A dynarray is a general container,
suitable for use in an arbitrary location.
Because allocation is possible anywhere,
stack allocation is not guaranteed,
and allocation falls back to the heap (or an allocator) when necessary.
With compiler support,
stack allocation should be implementable in all situations
where more restricted facilities are permitted.
However,
some environments may restrict the size of objects allocated on the stack,
thus forcing allocation of larger objects on the heap.
Other environments may be very latency sensitive,
thus prohibiting any implicit heap allocations.
Thus, the allocation behavior of dynarray
needs to be a property of the implementation.
The primary objection to dynarray
is the problem of reallocation
as described by Richard Smith and Chandler Carruth.
Consider the following example.
int f(dynarray<int>& r) {
.... r.~dynarray<int>();
.... new(r) dynarray<int>(2);
....
}
....
{
dynarray<int> a(1);
f(a);
}
The lifetime of a is split in two,
one from declaration of a to the explicit destruction and
one from the placement new to the destruction of a.
The core of the problem comes from the activation record for f,
and any local objects,
incompletely overlapping the split lifetimes.
That is, with reallocation,
the lifetimes of automatic-duration objects are no longer strictly nested.
Reallocation was not an implementation problem in the past because storage was either statically sized and could be simply reused, or obtained from the heap and could be managed out-of-order.
The problem outlined here is fundamental to any named class,
including bs_array
and any class built using RBADM.
Indeed the RBADM requires inline constructors and destructors because otherwise the allocation would be inside the lifetime of the activation record of a non-inline function and the destructor would be outside. That is, the lifetimes are not strictly nested.
The C++ language needs a mechanism to identify and enforce nested lifetimes. We cannot simply prohibit reallocation because N2544 Unrestricted Unions depends on reallocation to change active fields.
Nested lifeimes permit nested allocation and deallocation.
In addition to stack allocation,
nested lifetimes also enable merging heap allocations.
N3664 Clarifying Memory Alocation
already permits this merging through compiler analysis.
Indeed, the present definition of RBADMs and dynarray
rely on compiler analysis through inlining to allocate on the stack.
Direct support for nested allocation would
take stack allocation and heap merging beyond the reach of compiler analysis.
The nature of that direct support is unclear right now. However, the support would probably require three-phase construction. The first phase would calculate sizes by traversing the construction hierarchy of a complete object, the second phase would allocate the total size as one object, and the third phase would traverse the hierarchy to partitioning the storage and initializing it. At present, constructors are not structured so as to easily enable that separation.