<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 33. Allocators</title><meta name="generator" content="DocBook XSL Stylesheets V1.75.2" /><meta name="keywords" content=" ISO C++ , library " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="extensions.html" title="Part XII. Extensions" /><link rel="prev" href="bk01pt12ch32s07.html" title="Diagnostics" /><link rel="next" href="bitmap_allocator.html" title="bitmap_allocator" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 33. Allocators</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt12ch32s07.html">Prev</a> </td><th width="60%" align="center">Part XII.
+<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 20. Allocators</title><meta name="generator" content="DocBook XSL Stylesheets V1.75.2" /><meta name="keywords" content=" ISO C++ , library " /><link rel="home" href="../spine.html" title="The GNU C++ Library Documentation" /><link rel="up" href="extensions.html" title="Part III. Extensions" /><link rel="prev" href="bk01pt03ch19s07.html" title="Diagnostics" /><link rel="next" href="bitmap_allocator.html" title="bitmap_allocator" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 20. Allocators</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt03ch19s07.html">Prev</a> </td><th width="60%" align="center">Part III.
Extensions
-</th><td width="20%" align="right"> <a accesskey="n" href="bitmap_allocator.html">Next</a></td></tr></table><hr /></div><div class="chapter" title="Chapter
33. Allocators"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.allocator"></a>Chapter 33. Allocators</h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="sect1"><a href="ext_allocators.html#manual.ext.allocator.mt">mt_allocator</a></span></dt><dd><dl><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.design_issues">Design Issues</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.impl">Implementation</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.example_single">Single Thread Example</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.example_multi">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="sect1"><a href="bitmap_allocator.html">bitmap_allocator</a></span></dt><dd><dl><dt><span class="sect2"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="sect2"><a href="bitmap_allocator.html#allocator.bitmap.impl">Implementation</a></span></dt></dl></dd></dl></div><div class="sect1" title="mt_allocator"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.ext.allocator.mt"></a>mt_allocator</h2></div></div></div><p>
-</p><div class="sect2" title="Intro"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.mt.intro"></a>Intro</h3></div></div></div><p>
+</th><td width="20%" align="right"> <a accesskey="n" href="bitmap_allocator.html">Next</a></td></tr></table><hr /></div><div class="chapter" title="Chapter
20. Allocators"><div class="titlepage"><div><div><h2 class="title"><a id="manual.ext.allocator"></a>Chapter 20. Allocators</h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="sect1"><a href="ext_allocators.html#manual.ext.allocator.mt">mt_allocator</a></span></dt><dd><dl><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.intro">Intro</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.design_issues">Design Issues</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.impl">Implementation</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.example_single">Single Thread Example</a></span></dt><dt><span class="sect2"><a href="ext_allocators.html#allocator.mt.example_multi">Multiple Thread Example</a></span></dt></dl></dd><dt><span class="sect1"><a href="bitmap_allocator.html">bitmap_allocator</a></span></dt><dd><dl><dt><span class="sect2"><a href="bitmap_allocator.html#allocator.bitmap.design">Design</a></span></dt><dt><span class="sect2"><a href="bitmap_allocator.html#allocator.bitmap.impl">Implementation</a></span></dt></dl></dd></dl></div><div class="sect1" title="mt_allocator"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="manual.ext.allocator.mt"></a>mt_allocator</h2></div></div></div><p>
+</p><div class="sect2" title="Intro"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.mt.intro"></a>Intro</h3></div></div></div><p>
The mt allocator [hereinafter referred to simply as "the allocator"]
is a fixed size (power of two) allocator that was initially
developed specifically to suit the needs of multi threaded
containing this pool that links instantiation types to common or
individual pools, and a class inheriting from the policy class that is
the actual allocator.
-</p><p>The datum describing pools characteristics is
+</p><p>The datum describing pools characteristics is
</p><pre class="programlisting">
template<bool _Thread>
class __pool
tune_type t_single(16, 5120, 32, 5120, 1, 10, false);
tune_type t;
- t = allocator_type::_M_get_options();
+ t = allocator_type::_M_get_options();
allocator_type::_M_set_options(t_opt);
- t = allocator_type::_M_get_options();
+ t = allocator_type::_M_get_options();
allocator_type a;
allocator_type::pointer p1 = a.allocate(128);
allocate() to return memory directly from a new() call, and deallocate will
only do a delete() call.
</p><p>
-- If the GLIBCXX_FORCE_NEW environment variable is not set, both ST and MT
+- If the GLIBCXX_FORCE_NEW environment variable is not set, both ST and MT
applications will:
- Calculate the number of bins needed. A bin is a specific power of two size
- of bytes. I.e., by default the allocator will deal with requests of up to
- 128 bytes (or whatever the value of _S_max_bytes is when _S_init() is
- called). This means that there will be bins of the following sizes
- (in bytes): 1, 2, 4, 8, 16, 32, 64, 128.
+ of bytes. I.e., by default the allocator will deal with requests of up to
+ 128 bytes (or whatever the value of _S_max_bytes is when _S_init() is
+ called). This means that there will be bins of the following sizes
+ (in bytes): 1, 2, 4, 8, 16, 32, 64, 128.
- - Create the _S_binmap array. All requests are rounded up to the next
- "large enough" bin. I.e., a request for 29 bytes will cause a block from
- the "32 byte bin" to be returned to the application. The purpose of
- _S_binmap is to speed up the process of finding out which bin to use.
+ - Create the _S_binmap array. All requests are rounded up to the next
+ "large enough" bin. I.e., a request for 29 bytes will cause a block from
+ the "32 byte bin" to be returned to the application. The purpose of
+ _S_binmap is to speed up the process of finding out which bin to use.
I.e., the value of _S_binmap[ 29 ] is initialized to 5 (bin 5 = 32 bytes).
</p><p>
- Create the _S_bin array. This array consists of bin_records. There will be
earlier. I.e., if _S_max_bytes = 128 there will be 8 entries.
Each bin_record is then initialized:
- bin_record->first = An array of pointers to block_records. There will be
- as many block_records pointers as there are maximum number of threads
- (in a ST application there is only 1 thread, in a MT application there
+ as many block_records pointers as there are maximum number of threads
+ (in a ST application there is only 1 thread, in a MT application there
are _S_max_threads).
This holds the pointer to the first free block for each thread in this
bin. I.e., if we would like to know where the first free block of size 32
for thread number 3 is we would look this up by: _S_bin[ 5 ].first[ 3 ]
- The above created block_record pointers members are now initialized to
+ The above created block_record pointers members are now initialized to
their initial values. I.e. _S_bin[ n ].first[ n ] = NULL;
</p><p>
- Additionally a MT application will:
- Create a list of free thread id's. The pointer to the first entry
- is stored in _S_thread_freelist_first. The reason for this approach is
- that the __gthread_self() call will not return a value that corresponds to
+ is stored in _S_thread_freelist_first. The reason for this approach is
+ that the __gthread_self() call will not return a value that corresponds to
the maximum number of threads allowed but rather a process id number or
something else. So what we do is that we create a list of thread_records.
This list is _S_max_threads long and each entry holds a size_t thread_id
which is initialized to 1, 2, 3, 4, 5 and so on up to _S_max_threads.
- Each time a thread calls allocate() or deallocate() we call
+ Each time a thread calls allocate() or deallocate() we call
_S_get_thread_id() which looks at the value of _S_thread_key which is a
thread local storage pointer. If this is NULL we know that this is a newly
created thread and we pop the first entry from this list and saves the
- pointer to this record in the _S_thread_key variable. The next time
- we will get the pointer to the thread_record back and we use the
- thread_record->thread_id as identification. I.e., the first thread that
+ pointer to this record in the _S_thread_key variable. The next time
+ we will get the pointer to the thread_record back and we use the
+ thread_record->thread_id as identification. I.e., the first thread that
calls allocate will get the first record in this list and thus be thread
number 1 and will then find the pointer to its first free 32 byte block
in _S_bin[ 5 ].first[ 1 ]
- When we create the _S_thread_key we also define a destructor
+ When we create the _S_thread_key we also define a destructor
(_S_thread_key_destr) which means that when the thread dies, this
thread_record is returned to the front of this list and the thread id
can then be reused if a new thread is created.
has made 678 requests (and no deallocations...) of 32-byte blocks this
counter will read 678.
- The above created arrays are now initialized with their initial values.
+ The above created arrays are now initialized with their initial values.
I.e. _S_bin[ n ].free[ n ] = 0;
</p><p>
- Initialize the mutex of each bin_record: The bin_record->mutex
+----------------+
</pre><p>
With this in mind we simplify things a bit for a while and say that there is
-only one thread (a ST application). In this case all operations are made to
+only one thread (a ST application). In this case all operations are made to
what is referred to as the global pool - thread id 0 (No thread may be
assigned this id since they span from 1 to _S_max_threads in a MT application).
</p><p>
When the application requests memory (calling allocate()) we first look at the
requested size and if this is > _S_max_bytes we call new() directly and return.
</p><p>
-If the requested size is within limits we start by finding out from which
+If the requested size is within limits we start by finding out from which
bin we should serve this request by looking in _S_binmap.
</p><p>
A quick look at _S_bin[ bin ].first[ 0 ] tells us if there are any blocks of
this size on the freelist (0). If this is not NULL - fine, just remove the
-block that _S_bin[ bin ].first[ 0 ] points to from the list,
+block that _S_bin[ bin ].first[ 0 ] points to from the list,
update _S_bin[ bin ].first[ 0 ] and return a pointer to that blocks data.
</p><p>
-If the freelist is empty (the pointer is NULL) we must get memory from the
+If the freelist is empty (the pointer is NULL) we must get memory from the
system and build us a freelist within this memory. All requests for new memory
-is made in chunks of _S_chunk_size. Knowing the size of a block_record and
-the bytes that this bin stores we then calculate how many blocks we can create
+is made in chunks of _S_chunk_size. Knowing the size of a block_record and
+the bytes that this bin stores we then calculate how many blocks we can create
within this chunk, build the list, remove the first block, update the pointer
-(_S_bin[ bin ].first[ 0 ]) and return a pointer to that blocks data.
+(_S_bin[ bin ].first[ 0 ]) and return a pointer to that blocks data.
</p><p>
Deallocation is equally simple; the pointer is casted back to a block_record
-pointer, lookup which bin to use based on the size, add the block to the front
-of the global freelist and update the pointer as needed
+pointer, lookup which bin to use based on the size, add the block to the front
+of the global freelist and update the pointer as needed
(_S_bin[ bin ].first[ 0 ]).
</p><p>
The decision to add deallocated blocks to the front of the freelist was made
after a set of performance measurements that showed that this is roughly 10%
faster than maintaining a set of "last pointers" as well.
</p></div><div class="sect2" title="Multiple Thread Example"><div class="titlepage"><div><div><h3 class="title"><a id="allocator.mt.example_multi"></a>Multiple Thread Example</h3></div></div></div><p>
-In the ST example we never used the thread_id variable present in each block.
-Let's start by explaining the purpose of this in a MT application.
+In the ST example we never used the thread_id variable present in each block.
+Let's start by explaining the purpose of this in a MT application.
</p><p>
The concept of "ownership" was introduced since many MT applications
allocate and deallocate memory to shared containers from different
look at the requested size and if this is >_S_max_bytes we call new()
directly and return.
</p><p>
-If the requested size is within limits we start by finding out from which
+If the requested size is within limits we start by finding out from which
bin we should serve this request by looking in _S_binmap.
</p><p>
-A call to _S_get_thread_id() returns the thread id for the calling thread
+A call to _S_get_thread_id() returns the thread id for the calling thread
(and if no value has been set in _S_thread_key, a new id is assigned and
returned).
</p><p>
a threads freelist mentioned above). The "formula" used can probably
be improved to further reduce the risk of blocks being "bounced back
and forth" between freelists.
-</p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt
12ch32s07.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="extensions.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="bitmap_allocator.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Diagnostics </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> bitmap_allocator</td></tr></table></div></body></html>
+</p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt
03ch19s07.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="extensions.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="bitmap_allocator.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Diagnostics </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> bitmap_allocator</td></tr></table></div></body></html>
OSDN Git Service
