Standard Template Library Programmer's Guide

SGI STL provides what we believe to be the most useful form of thread-safety. This explains some of the design decisions made in the SGI STL implementation.

Client must lock shared mutable containers

The SGI implementation of STL is thread-safe only in the sense that simultaneous accesses to distinct containers are safe, and simultaneous read accesses to to shared containers are safe. If multiple threads access a single container, and at least one thread may potentially write, then the user is responsible for ensuring mutual exclusion between the threads during the container accesses.

This is the only way to ensure full performance for containers that do not need concurrent access. Locking or other forms of synchronization are typically expensive and should be avoided when not necessary.

It is easy for the client or another library to provide the necessary locking by wrapping the underlying container operations with a lock acquisition and release. For example, it would be possible to provide a locked_queue container adapter that provided a container with atomic queue operations.

For most clients, it would be insufficient to simply make container operations atomic; larger grain atomic actions are needed. If a user's code needs to increment the third element in a vector of counters, it would be insuffcient to guarantee that fetching the third element and storing the third element is atomic; it is also necessary to guarantee that no other updates occur in the middle. Thus it would be useless for vector operations to acquire the lock; the user code must provide for locking in any case.

This decision is different from that made by the Java designers. There are two reasons for that. First, for security reasons Java must guarantee that even in the presence of unprotected concurrent accesses to a container, the integrity of the virtual machine cannot be violated. Such safety constraints were clearly not a driving force behind either C++ or STL. Secondly, performance was a more important design goal for STL then it was for the Java standard library.

On the other hand, this notion of thread-safety is stronger than that provided by reference-counted string implementations that try to follow the CD2 version of the draft standard. Such implementations require locking between multiple readers of a shared string.

Lock implementation

The SGI STL implementation removes all nonconstant static data from container implementations. The only potentially shared static data resides in the allocator implementations. To this end, the code to implement per- class node allocation in HP STL was transformed into inlined code for per-size node allocation in the SGI STL allocators. Currently the only explicit locking is performed inside allocators.

Many other container implementations should also benefit from this design. It will usually be possible to implement thread-safe containers in portable code that does not depend on any particular thread package or locking primitives.

Alloc.h uses three different locking primitives depending on the environment. In addition, it can be forced to perform no locking by defining _NOTHREADS. The three styles of locking are:

• Pthread mutexes. These are used if _PTHREADS is defined by the user. This may be done on SGI machines, but is not recommended in performance critical code with the currently (March 1997) released versions of the SGI Pthreads libraries.

• Win32 critical sections. These are used by default for win32 compilations with compiler options that request multi-threaded code.

• An SGI specific spin-lock implementation that is usable with both pthread and sproc threads. This could serve as a prototype implementation for other platforms. This is the default on SGI/MIPS platforms.

It would be preferable if we could always use the OS-supplied locking primitives. Unfortunately, these often do not perform well, for very short critical sections such as those used by the allocator.

Allocation intensive applications using Pthreads to obtain concurrency on multiprocessors should consider using pthread_alloc from pthread_alloc.h. It imposes the restriction that memory deallocated by a thread can only be reallocated by that thread. However, it often obtains significant performance advantages as a result.

STL Complexity Specifications

STL container, algorithm, and concept specifications include asymptotic complexity specifications. For example, iterators are required to take constant time, that is the time required by an iterator operation should be no more than a fixed constant, independent of the size of the container to which it refers.

Clearly programs will still function if a program component ignores the complexity specifications. Nonetheless, these specifications are an important part of the interface between STL components and code that uses them. If they are ignored, the performance of the resulting program will often render it useless.

As an example, consider the STL vector container. Ignoring the complexity specification, it is possible to implement vector using the same underlying data structure as list, i.e. as a doubly linked list. But for a vector of length 10,000, this would probably slow down an average computation of v[i] by something like a factor of 5,000. For a program that requires many vector accesses, such as a typical numerical computation, this is likely to change an execution time of minutes to days.

This does not preclude the use of STL algorithms in conjunction with containers or iterators that do not meet the standard complexity specifications. This is occasionally quite useful, especially if the code is either not performance critical, or other requirements on the container make the performance specifications unrealizable. But this has two potential problems. First, the algorithm may no longer be the right one, or even a reasonable one, for the problem. A different algorithm may be better tailored to actual relative costs of the container operations. Second, the algorithm is, of course, unlikely to satisfy its specified complexity constraint.

The complexity specifications in STL are, of necessity, an oversimplification. A full specification would describe exactly how the running time of an operation varies with that of the operations it invokes. The result would be rather unmanageable for the user, who would have to be keep track of large amounts of irrelevent detail. It would be overly constraining on the implementor, since overall improvements on the existing algorithms may not satisfy such detailed constraints.

Concept specifications (e.g. Forward Iterator or Container) specify complexity requirements that should be met by all instances of the concept. This is the minimum behavior required by operations (e.g. sort) parameterized with respect to the concept. Any specific instance (e.g. vector) is likely to perform better in at least some cases.

It is difficult to specify precisely when an algorithm satisfies a performance constraint. Does copying a vector on a 16-bit embedded processor take constant time? After all, the size of the vector is limited to some value less than 65,536. Thus the number of memory operations involved in the copy operation is certainly bounded by a constant. It is even conceivable that the worst case vector copy time on this processor may be less than the worst-case time for a single memory access on a machine with paged virtual memory. Nonetheless, it would be intuitively wrong to describe a vector copy or a list traversal as being a constant time operation. Even on this machine, a vector implemented as a list is unlikely to yield satisfactory performance. (Of course, so would an implementation that looped for a second for every vector access, although that would clearly run in constant time. The point here is to communicate the proper intent between implementor and user, not to guard against malicious or silly implementations.)

Fundamentally, it is difficult to define the notion of asymptotic algorithm complexity precisely for real