Standard Template Library Programmer's Guide

The HP allocator design returned entire memory pools when the entire allocator was no longer needed. To allow this, it maintains a count of containers using a particular allocator. With the SGI design, this would only happen when the last container disappears, which is typically just before program exit. In most environments, this would be highly counterproductive; free would typically have to touch many long unreferenced pages just before the operating system reclaims them anyway. It would often introduce a significant delay on program exit, and would possibly page out large portions of other applications. There is nothing to be gained by this action, since the OS normally reclaims memory on program exit, and it should do so without touching that memory .

In general, we recommend that leak detection tests be run with malloc_alloc instead of alloc. This yields more precise results with GC-based detectors ( e.g. Pure Atria's Purify), and it provides useful results with detectors that simply count allocations and deallocations.

The default allocator makes no special attempt to ensure that consecutively allocated objects are "close" to each other, i.e. share a cache line or a page. A deallocation request adds an object to the head of a free list, and allocations remove the last deallocated object of the appropriate size. Thus allocation and deallocation each require a minimum number of instructions.

This appears to perform very well for small applications which fit into cache. It also performs well for regular applications that deallocate consecutively allocated objects consecutively. For such applications, free lists tend to remain approximately in address order. But there are no doubt applications for which some effort invested in approximate sorting of free lists would be repayed in improved cache performance.

The SGI specific allocator interface is much simpler than either the HP STL one or the interface in the C++ standard. Here we outline the considerations that led to this design.

An SGI STL allocator consists of a class with 3 required member functions, all of which are static:

void * allocate(size_t n)

Allocates an object with the indicated size (in bytes). The object must be sufficiently aligned for any object of the requested size.

void deallocate(void *p, size_t n)

Deallocates the object p, which must have been allocated with the same allocator and a requested size of n.

void * reallocate(void *p, size_t old_sz, size_t new_sz)

Resize object p, previously allocated to contain old_sz bytes, so that it now contains new_sz bytes. Return a pointer to the resulting object of size new_sz. The functions either returns p, after suitably adjusting the object in-place, or it copies min(old_sz, new_sz) bytes from the old object into a newly allocated object, deallocates the old object, and returns a pointer to the new object. Note that the copy is performed bit-wise; this is usually inappropriate if the object has a user defined copy constructor or destructor. Fully generic container implementations do not normally use reallocate; however it can be a performance enhancement for certain container specializations.

A discussion of the design decisions behind this rather simple design follows:

Our allocators operate on raw, untyped memory in the same way that C's malloc does. They know nothing about the eventual type of the object. This means that the implementor of an allocator to worry about types; allocators can deal with just bytes. We provide the simple_alloc adaptor to turn a byte-based allocator into one that allocates n objects of type T. Type-oblivious allocators have the advantage that containers do not require either template template arguments or the "rebind" mechanism in the standard.

The cost is that allocators that really do need type information ( e.g. for garbage collection) become somewhat harder to implement. This can be handled in a limited way by specializing simple_alloc.

(The STL standard allocators are in fact implemented with the aid of templates. But this is done mostly so that they can be distributed easily as .h files.)

(Largely shared with SGI standard allocators. The standard allows allocators 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:

• 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 proxy reference type. Even proxy pointer types are problematic. Constructors require a real this pointer, not a proxy.

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

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

An allocator's behavior is completely determined by its type. All data members of an allocator are static.

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.

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.

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:

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