providing an iterator assignment operation which does not copy the cache part of the iterator unless it has been initialized.
The character buffer in the iterator is needed since there is not another place to cache characters returned for the evaluation of a function node. (This is less of an issue with a garbage collector, since it turns out to be reasonably efficient to maintain such caches in the function object itself. Without a garbage collector, this requires locking around cache accesses, which is usually unacceptable.)
Mutable iterators differ primarily in that they also contain a pointer to the rope itself (i.e. a pointer to the tree node pointer), so that they can be used to perform updates, and in that the rope root pointer is included in the reference count. In this case the rope root pointer is redundant, except that it us used to detect changes in the rope, so that the cached information in the iterator can be invalidated. The rope has changed iff the rope itself no longer points to the same node as the rope root pointer in the iterator. The fact that the iterator is included in the reference count ensures that the root node cannot be dropped and reused. It also prevents the rope from being destructively updated while the iterator must remain valid.
SGI STL Allocator Design
This document consists of 2 sections. The first discusses some of the decisions made in the implementation of default allocators in the SGI STL. These decisions influence both the performance of the default allocator, as well as its behavior with leak detectors.
The second section describes the original design of SGI STL allocators. The current SGI STL also supports the allocator interface in the C++ standard. The interface described here is specific to the SGI STL and cannot be used in code that must be portable to other STL implementations. Thus its use is now discouraged. The discussion is nonetheless preserved both for historical reasons, and because it exposes some of the issues surrounding the standard interface.
The default allocator alloc maintains its own free lists for small objects. It uses an underlying system- provided allocator both to satisfy larger requests, and to obtain larger chunks of memory which can be subdivided into small objects. Two of the detailed design decisions have proven to be controversial, and are explained here.
Malloc is used as the underlying system-provided allocator. This is a minor design decision. ::operator new could also have been used. Malloc has the advantage that it allows for predictable and simple failure detection. ::operator new would have made this more complicated given the portability and thread-safety constraints, and the possibility of user provided new handlers.
Memory allocated for blocks of small objects is not returned to malloc. It can only be reused by subsequent alloc::allocate requests of (approximately) the same size. Thus programs that use alloc may appear to leak memory when monitored by some simple leak detectors.
The primary design criterion for alloc was to make it no slower than the HP STL per-class allocators, but potentially thread-safe, and significantly less prone to fragmentation. Like the HP allocators, it does not maintain the necessary data structures to free entire chunks of small objects when none of the contained small objects are in use. This is an intentional choice of execution time over space use. It may not be appropriate for all programs. On many systems malloc_alloc may be more space efficient, and can be used when that is crucial.
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
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 (
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 (
(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.)
