Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/pool/doc/concepts.html @ 33

Last change on this file since 33 was 29, checked in by landauf, 16 years ago

updated boost from 1_33_1 to 1_34_1
File size: 14.8 KB
Line 
1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
2"http://www.w3.org/TR/html4/loose.dtd">
3
4<html>
5<head>
6  <meta http-equiv="Content-Language" content="en-us">
7  <meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
8  <link href="pool.css" rel="stylesheet" type="text/css">
9
10  <title>Pool Concepts</title>
11</head>
12
13<body>
14  <img src="../../../boost.png" width="276" height="86" alt="C++ Boost">
15
16  <h1 align="center">Pool Concepts</h1>
17
18  <blockquote>
19    "Dynamic memory allocation has been a fundamental part of most computer
20    systems since roughly 1960..."<sup><a href="#ref1">1</a></sup>
21  </blockquote>
22
23  <p>Everyone uses dynamic memory allocation. If you have ever called
24  <span class="code">malloc</span> or <span class="code">new</span>, then you
25  have used dynamic memory allocation. Most programmers have a tendency to
26  treat the heap as a "magic bag": we ask it for memory, and it magically
27  creates some for us. Sometimes we run into problems because the heap is
28  <em>not</em> magic.</p>
29
30  <p>The heap is limited. Even on large systems (i.e., not embedded) with
31  huge amounts of virtual memory available, there is a limit. Everyone is
32  aware of the physical limit, but there is a more subtle, "virtual" limit,
33  that limit at which your program (or the entire system) slows down due to
34  the use of virtual memory. This virtual limit is much closer to your
35  program than the physical limit, especially if you are running on a
36  multitasking system. Therefore, when running on a large system, it is
37  considered "nice" to make your program use as few resources as necessary,
38  and release them as soon as possible. When using an embedded system,
39  programmers usually have no memory to waste.</p>
40
41  <p>The heap is complicated. It has to satisfy any type of memory request,
42  for any size, and do it <em>fast</em>. The common approaches to memory
43  management have to do with splitting the memory up into portions, and
44  keeping them ordered by size in some sort of a tree or list structure. Add
45  in other factors, such as locality and estimating lifetime, and heaps
46  quickly become very complicated. So complicated, in fact, that there is no
47  known "perfect" answer to the problem of how to do dynamic memory
48  allocation. The diagrams below illustrate how most common memory managers
49  work: for each chunk of memory, it uses part of that memory to maintain its
50  internal tree or list structure. Even when a chunk is <span class=
51  "code">malloc</span>'ed out to a program, the memory manager must "save"
52  some information in it &mdash; usually just its size. Then, when the block
53  is <span class="code">free</span>'d, the memory manager can easily tell how
54  large it is.</p>
55
56  <table cellspacing="0" border="3" rules="none" style=
57  "float: left; clear: both;" summary="">
58    <caption>
59      <em>Memory block, not allocated</em>
60    </caption>
61
62    <tr>
63      <td style="background-color: red; text-align: center;">Memory not
64      belonging to process</td>
65    </tr>
66
67    <tr>
68      <td style=
69      "padding: 1em 0em; background-color: silver; text-align: center;">
70      Memory used internally by memory allocator algorithm (usually 8-12
71      bytes)</td>
72    </tr>
73
74    <tr>
75      <td style=
76      "padding: 2em 0em; background-color: gray; text-align: center">Unused
77      memory</td>
78    </tr>
79
80    <tr>
81      <td style="background-color: red; text-align: center;">Memory not
82      belonging to process</td>
83    </tr>
84  </table>
85
86  <table cellspacing="0" border="3" rules="none" style=
87  "float: right; clear: both;" summary="">
88    <caption>
89      <em>Memory block, allocated (used by program)</em>
90    </caption>
91
92    <tr>
93      <td style="background-color: red; text-align: center;">Memory not
94      belonging to process</td>
95    </tr>
96
97    <tr>
98      <td style="background-color: silver; text-align: center;">Memory used
99      internally by memory allocator algorithm (usually 4 bytes)</td>
100    </tr>
101
102    <tr>
103      <td style=
104      "padding: 3em 0em; background-color: yellow; text-align: center">Memory
105      usable by program</td>
106    </tr>
107
108    <tr>
109      <td style="background-color: red; text-align: center;">Memory not
110      belonging to process</td>
111    </tr>
112  </table>
113
114  <p>Because of the complication of dynamic memory allocation, it is often
115  inefficient in terms of time and/or space. Most memory allocation
116  algorithms store some form of information with each memory block, either
117  the block size or some relational information, such as its position in the
118  internal tree or list structure. It is common for such "header fields" to
119  take up one machine word in a block that is being used by the program. The
120  obvious problem, then, is when small objects are dynamically allocated. For
121  example, if <span class="code">int</span>s were dynamically allocated, then
122  automatically the algorithm will reserve space for the header fields as
123  well, and we end up with a 50% waste of memory. Of course, this is a
124  worst-case scenario. However, more modern programs are making use of small
125  objects on the heap; and that is making this problem more and more
126  apparent. Wilson <em>et. al.</em> state that an average-case memory
127  overhead is about ten to twenty percent<sup><a href="#ref2">2</a></sup>.
128  This memory overhead will grow higher as more programs use more smaller
129  objects. It is this memory overhead that brings programs closer to the
130  virtual limit.</p>
131
132  <p>In larger systems, the memory overhead is not as big of a problem
133  (compared to the amount of time it would take to work around it), and thus
134  is often ignored. However, there are situations where many allocations
135  and/or deallocations of smaller objects are taking place as part of a
136  time-critical algorithm, and in these situations, the system-supplied
137  memory allocator is often too slow.</p>
138
139  <p>Simple segregated storage addresses both of these issues. Almost all
140  memory overhead is done away with, and all allocations can take place in a
141  small amount of (amortized) constant time. However, this is done at the
142  loss of generality; simple segregated storage only can allocate memory
143  chunks of a single size.</p>
144  <hr>
145
146  <h1 align="center">Simple Segregated Storage</h1>
147
148  <p>Simple Segregated Storage is the basic idea behind the Boost Pool
149  library. Simple Segregated Storage is the simplest, and probably the
150  fastest, memory allocation/deallocation algorithm. It begins by
151  <em>partitioning</em> a memory <em>block</em> into fixed-size
152  <em>chunks</em>. Where the block comes from is not important until
153  implementation time. A <em>Pool</em> is some object that uses Simple
154  Segregated Storage in this fashion. To illustrate:</p>
155
156  <table cellspacing="0" border="3" rules="none" align="center" style=
157  "clear: both;" summary="">
158    <caption>
159      <em>Memory block, split into chunks</em>
160    </caption>
161
162    <tr>
163      <td style="background-color: red; text-align: center;">Memory not
164      belonging to process</td>
165    </tr>
166
167    <tr>
168      <td style=
169      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
170      0</td>
171    </tr>
172
173    <tr>
174      <td style=
175      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
176      1</td>
177    </tr>
178
179    <tr>
180      <td style=
181      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
182      2</td>
183    </tr>
184
185    <tr>
186      <td style=
187      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
188      3</td>
189    </tr>
190
191    <tr>
192      <td style="background-color: red; text-align: center;">Memory not
193      belonging to process</td>
194    </tr>
195  </table>
196
197  <p>Each of the chunks in any given block are <strong>always</strong> the
198  same size. This is the fundamental restriction of Simple Segregated
199  Storage: you cannot ask for chunks of different sizes. For example, you
200  cannot ask a Pool of integers for a character, or a Pool of characters for
201  an integer (assuming that characters and integers are different sizes).</p>
202
203  <p>Simple Segregated Storage works by interleaving a <em>free list</em>
204  within the unused chunks. For example:</p>
205
206  <table cellspacing="0" border="3" rules="none" style=
207  "float: left; clear: both;" summary="">
208    <caption>
209      <em>Memory block, with no chunks allocated</em>
210    </caption>
211
212    <tr>
213      <td style="background-color: red; text-align: center;">Memory not
214      belonging to process</td>
215    </tr>
216
217    <tr>
218      <td style=
219      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
220      0; points to Chunk 1</td>
221    </tr>
222
223    <tr>
224      <td style=
225      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
226      1; points to Chunk 2</td>
227    </tr>
228
229    <tr>
230      <td style=
231      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
232      2; points to Chunk 3</td>
233    </tr>
234
235    <tr>
236      <td style=
237      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
238      3; end-of-list</td>
239    </tr>
240
241    <tr>
242      <td style="background-color: red; text-align: center;">Memory not
243      belonging to process</td>
244    </tr>
245  </table>
246
247  <table cellspacing="0" border="3" rules="none" style=
248  "float: right; clear: both;" summary="">
249    <caption>
250      <em>Memory block, with two chunks allocated</em>
251    </caption>
252
253    <tr>
254      <td style="background-color: red; text-align: center;">Memory not
255      belonging to process</td>
256    </tr>
257
258    <tr>
259      <td style=
260      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
261      0; points to Chunk 2</td>
262    </tr>
263
264    <tr>
265      <td style=
266      "padding: 1em 0em; background-color: silver; text-align: center;">Chunk
267      1 (in use by process)</td>
268    </tr>
269
270    <tr>
271      <td style=
272      "padding: 1em 0em; background-color: gray; text-align: center;">Chunk
273      2; end-of-list</td>
274    </tr>
275
276    <tr>
277      <td style=
278      "padding: 1em 0em; background-color: silver; text-align: center;">Chunk
279      3 (in use by process)</td>
280    </tr>
281
282    <tr>
283      <td style="background-color: red; text-align: center;">Memory not
284      belonging to process</td>
285    </tr>
286  </table>
287
288  <p>By interleaving the free list inside the chunks, each Simple Segregated
289  Storage only has the overhead of a single pointer (the pointer to the first
290  element in the list). It has <em>no</em> memory overhead for chunks that
291  are in use by the process.</p>
292
293  <p>Simple Segregated Storage is also extremely fast. In the simplest case,
294  memory allocation is merely removing the first chunk from the free list, a
295  O(1) operation. In the case where the free list is empty, another block may
296  have to be acquired and partitioned, which would result in an amortized
297  O(1) time. Memory deallocation may be as simple as adding that chunk to the
298  front of the free list, a O(1) operation. However, more complicated uses of
299  Simple Segregated Storage may require a sorted free list, which makes
300  deallocation O(N).</p>
301
302  <p>Simple Segregated Storage gives faster execution and less memory
303  overhead than a system-supplied allocator, but at the loss of generality. A
304  good place to use a Pool is in situations where many (noncontiguous) small
305  objects may be allocated on the heap, or if allocation and deallocation of
306  the same-sized objects happens repeatedly.<br clear="all"></p>
307  <hr>
308
309  <h2>References</h2>
310
311  <ol>
312    <li><a name="ref1" id="ref1">Doug Lea, <em>A Memory Allocator</em>.</a>
313    Available on the web at <a href=
314    "http://gee.cs.oswego.edu/dl/html/malloc.html">http://gee.cs.oswego.edu/dl/html/malloc.html</a></li>
315
316    <li><a name="ref2" id="ref2">Paul R. Wilson, Mark S. Johnstone, Michael
317    Neely, and David Boles, "Dynamic Storage Allocation: A Survey and
318    Critical Review" in <em>International Workshop on Memory Management</em>,
319    September 1995, pg. 28, 36.</a> Available on the web at <a href=
320    "ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps">ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps</a></li>
321  </ol>
322
323  <h2>Other Implementations</h2>
324
325  <p>Pool allocators are found in many programming languages, and in many
326  variations. The beginnings of many implementations may be found in common
327  programming literature; some of these are given below. Note that none of
328  these are complete implementations of a Pool; most of these leave some
329  aspects of a Pool as a user exercise. However, in each case, even though
330  some aspects are missing, these examples use the same underlying concept of
331  a Simple Segregated Storage described in this document.</p>
332
333  <ul>
334    <li>"The C++ Programming Language", 3rd ed., by Bjarne Stroustrup,
335    Section 19.4.2. Missing aspects:
336
337      <ol>
338        <li>Not portable</li>
339
340        <li>Cannot handle allocations of arbitrary numbers of objects (this
341        was left as an exercise)</li>
342
343        <li>Not thread-safe</li>
344
345        <li>Suffers from the static initialization problem</li>
346      </ol>
347    </li>
348
349    <li>"MicroC/OS-II: The Real-Time Kernel", by Jean J. Labrosse, Chapter 7
350    and Appendix B.04. This is an example of the Simple Segregated Storage
351    scheme at work in the internals of an actual OS. Missing aspects:
352
353      <ol>
354        <li>Not portable (though this is OK, since it's part of its own
355        OS)</li>
356
357        <li>Cannot handle allocations of arbitrary numbers of blocks (which
358        is also OK, since this feature is not needed)</li>
359
360        <li>Requires non-intuitive user code to create and destroy the
361        Pool</li>
362      </ol>
363    </li>
364
365    <li>"Efficient C++: Performance Programming Techniques", by Dov Bulka and
366    David Mayhew, Chapters 6 and 7. This is a good example of iteratively
367    developing a Pool solution; however, their premise (that the
368    system-supplied allocation mechanism is hopelessly inefficient) is flawed
369    on every system I've tested on. Run their timings on your system before
370    you accept their conclusions. Missing aspects:
371
372      <ol>
373        <li>Requires non-intuitive user code to create and destroy the
374        Pool</li>
375      </ol>
376    </li>
377
378    <li>"Advanced C++: Programming Styles and Idioms", by James O. Coplien,
379    Section 3.6. This has examples of both static and dynamic pooling.
380    Missing aspects:
381
382      <ol>
383        <li>Not thread-safe</li>
384
385        <li>The static pooling example is not portable</li>
386      </ol>
387    </li>
388  </ul>
389  <hr>
390
391  <p><a href="http://validator.w3.org/check?uri=referer"><img border="0" src=
392  "http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01 Transitional"
393  height="31" width="88"></a></p>
394
395  <p>Revised
396  <!--webbot bot="Timestamp" s-type="EDITED" s-format="%d %B, %Y" startspan -->05
397  December, 2006<!--webbot bot="Timestamp" endspan i-checksum="38516" --></p>
398
399  <p><i>Copyright &copy; 2000, 2001 Stephen Cleary (scleary AT jerviswebb DOT
400  com)</i></p>
401
402  <p><i>Distributed under the Boost Software License, Version 1.0. (See
403  accompanying file <a href="../../../LICENSE_1_0.txt">LICENSE_1_0.txt</a> or
404  copy at <a href=
405  "http://www.boost.org/LICENSE_1_0.txt">http://www.boost.org/LICENSE_1_0.txt</a>)</i></p>
406</body>
407</html>
Note: See TracBrowser for help on using the repository browser.