alloc.html

Standard Template Library (SOURCE + COMPLETE html man document)

to encapsulate pointer types, but does not guarantee that standard containers
are functional with allocators using nonstandard pointer types.)
Unlike the HP STL, our allocators do not attempt to allow use of
different pointer types.  They traffic only in standard void * pointers.
There were several reasons for abandoning the HP approach:
<UL>
<LI>It is not really possible to define an alternate notion of pointer
within C++ without explicit compiler support.  Doing so would also require
the definition of a corresponding "reference" type.  But there is no class
that behaves like a reference.  The "." field selection operation can
only be applied to a reference.  A template function (e.g. max)
expecting a T& will usually not work when instantiated with a
<I>proxy</i> reference type.  Even proxy pointer types are problematic.
Constructors require a real this pointer, not a proxy.

<LI>Existing STL data structures should usually not be used in
environments
which require very different notions of pointers, e.g. for disk-based
data structures.  A disk-bases set or map would require a data structure
that is much more aware of locality issues.  The implementation would
probably also have to deal with two different pointer types: real pointers to
memory allocated temporaries and references to disk based objects.
Thus even the HP STL notion of encapsulated pointer types would probably
be insufficient.

<LI>This leaves compiler supported pointers of different sizes (e.g. DOS/win16
"far" pointers).  These no longer seem to be of much interest in a general
purpose library.  Win32 no longer makes such distinctions.  Neither do any
other modern (i.e. 32- or 64-bit pointer) environments of which we are aware.
The issue will probably continue to matter for low end embedded systems,
but those typically require somewhat nonstandard programming environments
in any case.  Furthermore, the same template instantiation problems
as above will apply.
</ul>

<H3> There are no allocator objects </h3>
An allocator's behavior is completely determined by its type.  All data members
of an allocator are static.
<P>
This means that containers do not need allocator members in order to
allocate memory from the proper source.
This avoids unneeded space overhead and/or complexity in the container code.
<P>
It also avoids a
number of tricky questions about memory allocation in operations involving
multiple containers.  For example, it would otherwise be unclear whether
concatenation of ropes built with two different allocators should be
acceptable and if so, which allocator should be used for the result.
<P>
This is occasionally a significant restriction.  For example, it is not possible
to arrange for different containers to allocate memory mapped to different
files by passing different allocator instances to the container constructors.
Instead one must use one of the following alternatives:
<UL>
<LI> The container classes must be instantiated with different allocators,
one for each file.  This results in different container types.  This
forces containers that may be mapped to different files to have distinct type,
which may be a troublesome restriction, though it also results in compile-time
detection of errors that might otherwise be difficult to diagnose.

<LI>The containers can be instantiated with a single allocator, which can be
redirected to different files by calling additional member functions.
The allocator must be suitably redirected before container calls that may
allocate.
</ul>

<H3>Allocators allocate individual objects</h3>
(Shared with standard allocators.)
Some C++ programming texts have suggested that individual classes keep
a free lists of frequently allocated kinds of objects, so that most allocation
requests can be satisfied from the per-class free list.  When an allocation
request encounters an empty free list, a potentially slower allocator (e.g.
new or malloc) is called to allocate several of the required objects at once,
which are then used to replenish the free list.
<P>
The HP STL was designed along these lines.  Allocators were intended to be
used as the slower backup allocator.  Containers like list<T> were presumed
to maintain their own free list.
<P>
Based on some small experiments, this has no performance advantage over
directly calling the allocate function for individual objects.  In fact, the
generated code is essentially the same.  The default allocator we provide
is easily inlined.  Hence any calling overhead is eliminated.  If the
object size is statically known (the case in which per-class free lists
may be presumed to help), the address of the free list header can also be
determined by the compiler.
<P>
Per-class free lists do however have many disadvantages:
<UL>
<LI>
They introduce fragmentation.  Memory in the free list for class <I>A</i> cannot
be reused by another class <I>B</i>, even if only class <I>B</i> objects are
allocated for the remainder of program execution.  This is particularly
unfortunate if instead of a single class <I>A</i> there are many instances
of a template class each of which has its own free list.
<LI>
They make it much more difficult to construct thread-safe containers.
A class that maintains its own free list must ensure that allocations
from different threads on behalf of different containers cannot interfere
with each other.  This typically means that every class must be aware
of the underlying synchronization primitives.  If allocators allocate
individual objects, then only allocators themselves need to address this
issue, and most container implementations can be independent of the threading
mechanism.
<LI>
Garbage collecting allocators are difficult to accommodate.  The garbage
collector will see per-class free lists as accessible memory.  If pointers
in these free objects are not explicitly cleared, anything they reference
will also be retained by the collector, reducing the effectiveness of the
collector, sometimes seriously so.
</ul>
<H3>Deallocate requires size argument</h3>
We chose to require an explicit size argument, both for <TT>deallocate</tt>,
and to describe the original size of the object in the <TT>reallocate</tt>
call.  This means that no hidden per-object space overhead is required;
small objects use only the space explicitly requested by the client.
Thus, even in the absence of fragmentation, space usage is the same as for
per-class allocators.
<P>
This choice also removes some time overhead in the important special case
of fixed-size allocation.  In this case, the size of the object, and thus
the address of the free-list header becomes a clearly recognizable
compile-time constant.  Thus the generated code should be identical to that
needed by a per-class free-list allocator, even if the class requires
objects of only a single size.

<H3>We include realloc-style reallocation in the interface</h3>
This is probably the most questionable design decision.  It would
have probably been a bit more useful to provide a version of
<I>reallocate</i> that either changed the size of the existing object
without copying or returned NULL.  This would have made it directly
useful for objects with copy constructors.  It would also have avoided
unnecessary copying in cases in which the original object had not been
completely filled in.
<P>
Unfortunately, this would have prohibited use of <TT>realloc</tt> from
the C library.  This in turn would have added complexity to many allocator
implementations, and would have made interaction with memory-debugging
tools more difficult.  Thus we decided against this alternative.
<P>
The actual version of <TT>reallocate</tt> is still quite useful 
for container specializations to specific element types.
The STL implementation is starting to take advantage of that.

</body>
</html>