📄 alloc.html
字号:
<HTML><HEAD><TITLE>SGI STL Allocator Design</title></head><BODY TEXT="#000000" LINK="#006600" ALINK="#003300" VLINK="#7C7F87" BGCOLOR="#FFFFFF"><A HREF="/"><IMG SRC="/images/common/sgilogo_small.gif" ALT="SGI Logo" WIDTH="80" HEIGHT="72" BORDER="0"></A><P><!--end header--><H1> SGI STL Allocator Design</h1>This document consists of 2 sections.The first discusses some of the decisions made in the implementationof default allocators in the SGI STL. These decisionsinfluence both the performance of the default allocator, as wellas its behavior with leak detectors.<P>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 STLand cannot be used in code that must be portable to other STLimplementations. Thus its use is now discouraged. The discussionis nonetheless preserved both for historical reasons, and because it exposessome of the issues surrounding the standard interface.<H2>The SGI Default Allocator</h2>The default allocator <TT>alloc</tt> maintains its own free lists for smallobjects. It uses an underlying system-provided allocator both to satisfylarger requests, and to obtain larger chunks of memory which can be subdividedinto small objects. Two of the detailed design decisions have proven tobe controversial, and are explained here.<H3><TT>Alloc</tt> obtains memory from <TT>malloc</tt></h3><TT>Malloc</tt> is used as the underlying system-provided allocator.This is a minor design decision. <TT>::operator new</tt> could also have beenused. <TT>Malloc</tt> has the advantage that it allows for predictable andsimple failure detection. <TT>::operator new</tt> would have made this morecomplicated given the portability and thread-safety constraints, and thepossibility of user provided new handlers.<H3><TT>Alloc</tt> does not <TT>free</tt> all memory</h3>Memory allocated for blocks of small objects is not returned to<TT>malloc</tt>. It can only be reused by subsequent<TT>alloc::allocate</tt> requests of (approximately) the same size.Thus programs that use <TT>alloc</tt> may appear to leak memory when monitoredby some simple leak detectors. <I>This is intentional</i>.Such "leaks" do not accumulate over time. Such "leaks" are not reported bygarbage-collector-like leak detectors.<P>The primary design criterion for <TT>alloc</tt> was to make it no slowerthan the HP STL per-class allocators, but potentially thread-safe, andsignificantly less prone to fragmentation. Like the HP allocators, itdoes not maintain the necessary data structures to <TT>free</tt> entirechunks 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 notbe appropriate for all programs. On many systems <TT>malloc_alloc</tt>may be more space efficient, and can be used when that is crucial.<P>The HP allocator design returned entire memory pools when the entireallocator was no longer needed. To allow this, it maintains a count ofcontainers using a particular allocator. With the SGI design, this wouldonly happen when the last container disappears, which is typically just beforeprogram exit. In most environments, this would be highly counterproductive;<TT>free</tt> would typically have to touch many long unreferenced pagesjust before the operating system reclaims them anyway. It would oftenintroduce a significant delay on program exit, and would possibly page outlarge portions of other applications. There is nothing to be gained by thisaction, since the OS normally reclaims memory on program exit, and itshould do so <I>without touching that memory</i>.<P>In general, we recommend that leak detection tests be run with<TT>malloc_alloc</tt> instead of <TT>alloc</tt>. This yields moreprecise results with GC-based detectors (<I>e.g.</i> Pure Atria's Purify),and it provides useful results with detectors that simply count allocationsand deallocations.<H3>No Attempt to sort free lists</h3>The default allocator makes no special attempt to ensure thatconsecutively allocated objects are "close" to each other, i.e. sharea cache line or a page. A deallocation request adds an object tothe head of a free list, and allocations remove the last deallocated objectof the appropriate size. Thus allocation and deallocation each requirea minimum number of instructions.<P>This appears to perform very well for small applications which fit into cache.It also performs well for regular applications that deallocate consecutivelyallocated objects consecutively. For such applications, free lists tend toremain approximately in address order. But there are no doubt applicationsfor which some effort invested in approximate sorting of free lists would berepayed in improved cache performance.<H2>The Original SGI STL allocator interface</h2>The SGI specific allocator interface is much simpler than eitherthe HP STL one or the interface in the C++ standard.Here we outline the considerations that led to this design.<P>An SGI STL allocator consists of a class with 3 required member functions,all of which are <TT>static</tt>:<DL><DT><B><TT>void * allocate(size_t n)</tt></b><DD>Allocates an object with the indicated size (in bytes). The objectmust be sufficiently aligned for any object of the requested size.<DT><B><TT>void deallocate(void *p, size_t n)</tt></b><DD>Deallocates the object p, which must have been allocated with the sameallocator and a requested size of <TT>n</tt>.<DT><B><TT>void * reallocate(void *p, size_t old_sz, size_t new_sz)</tt></b><DD> Resize object p, previously allocated to contain old_sz bytes, so that itnow contains new_sz bytes. Return a pointer to the resulting object of sizenew_sz. The functions either returns p, after suitably adjusting theobject in-place, or it copies min(old_sz, new_sz) bytes from the old objectinto a newly allocated object, deallocates the old object, and returns apointer to the new object. Note that the copy is performed bit-wise;this is usually inappropriate if the object has a user defined copyconstructor or destructor. Fully generic container implementations donot normally use reallocate; however it can be a performance enhancementfor certain container specializations.</dl>A discussion of the design decisions behind this rather simple designfollows:<H3> Allocators are not templates </h3>Our allocators operate on raw, untyped memory in the sameway that C's <TT>malloc</tt> does.They know nothing about the eventual type of the object.This means that theimplementor of an allocator to worry about types;allocators can deal with just bytes.We provide the <TT>simple_alloc</tt>adaptor to turn a byte-based allocator into one that allocates nobjects of type T. Type-oblivious allocators have the advantagethat containers do not require either template template arguments orthe "rebind" mechanism in the standard.<P>The cost is thatallocators that really do need type information (<I>e.g.</i>for garbage collection) become somewhat harder to implement.This can be handled in a limited way by specializing<TT>simple_alloc</tt>.<P>(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.)<H3> Allocators do not encapsulate pointer types </h3>(Largely shared with SGI standard allocators. The standard allows allocators⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -