xref: /openbsd-src/gnu/gcc/libstdc++-v3/docs/html/ext/ballocator_doc.html (revision 404b540a9034ac75a6199ad1a32d1bbc7a0d4210)
1*404b540aSrobert<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
2*404b540aSrobert<html>
3*404b540aSrobert<head>
4*404b540aSrobert  <meta content="text/html; charset=ISO-8859-1"
5*404b540aSrobert http-equiv="content-type">
6*404b540aSrobert  <title>Bitmap Allocator</title>
7*404b540aSrobert  <meta content="Dhruv Matani" name="author">
8*404b540aSrobert  <meta content="Bitmap Allocator" name="description">
9*404b540aSrobert</head>
10*404b540aSrobert<body>
11*404b540aSrobert<h1 style="text-align: center;">Bitmap Allocator</h1>
12*404b540aSrobert<em><br>
13*404b540aSrobert<small><small>The latest version of this document is always available
14*404b540aSrobertat <a
15*404b540aSrobert href="http://gcc.gnu.org/onlinedocs/libstdc++/ext/ballocator_doc.html">
16*404b540aSroberthttp://gcc.gnu.org/onlinedocs/libstdc++/ext/ballocator_doc.html</a>.</small></small></em><br>
17*404b540aSrobert<br>
18*404b540aSrobert<em> To the <a href="http://gcc.gnu.org/libstdc++/">libstdc++-v3
19*404b540aSroberthomepage</a>.</em><br>
20*404b540aSrobert<br>
21*404b540aSrobert<hr style="width: 100%; height: 2px;"><br>
22*404b540aSrobertAs this name suggests, this allocator uses a bit-map to keep track of
23*404b540aSrobertthe used and unused memory locations for it's book-keeping purposes.<br>
24*404b540aSrobert<br>
25*404b540aSrobertThis allocator will make use of 1 single bit to keep track of whether
26*404b540aSrobertit has been allocated or not. A bit 1 indicates free, while 0 indicates
27*404b540aSrobertallocated. This has been done so that you can easily check a collection
28*404b540aSrobertof bits for a free block. This kind of Bitmapped strategy works best
29*404b540aSrobertfor single object allocations, and with the STL type parameterized
30*404b540aSrobertallocators, we do not need to choose any size for the block which will
31*404b540aSrobertbe represented by a single bit. This will be the size of the parameter
32*404b540aSrobertaround which the allocator has been parameterized. Thus, close to
33*404b540aSrobertoptimal performance will result. Hence, this should be used for node
34*404b540aSrobertbased containers which call the allocate function with an argument of 1.<br>
35*404b540aSrobert<br>
36*404b540aSrobertThe bitmapped allocator's internal pool is exponentially growing.
37*404b540aSrobertMeaning that internally, the blocks acquired from the Free List Store
38*404b540aSrobertwill double every time the bitmapped allocator runs out of memory.<br>
39*404b540aSrobert<br>
40*404b540aSrobert<hr style="width: 100%; height: 2px;"><br>
41*404b540aSrobertThe macro __GTHREADS decides whether to use Mutex Protection around
42*404b540aSrobertevery allocation/deallocation. The state of the macro is picked up
43*404b540aSrobertautomatically from the gthr abstraction layer.<br>
44*404b540aSrobert<br>
45*404b540aSrobert<hr style="width: 100%; height: 2px;">
46*404b540aSrobert<h3 style="text-align: center;">What is the Free List Store?</h3>
47*404b540aSrobert<br>
48*404b540aSrobertThe Free List Store (referred to as FLS for the remaining part of this
49*404b540aSrobertdocument) is the Global memory pool that is shared by all instances of
50*404b540aSrobertthe bitmapped allocator instantiated for any type. This maintains a
51*404b540aSrobertsorted order of all free memory blocks given back to it by the
52*404b540aSrobertbitmapped allocator, and is also responsible for giving memory to the
53*404b540aSrobertbitmapped allocator when it asks for more.<br>
54*404b540aSrobert<br>
55*404b540aSrobertInternally, there is a Free List threshold which indicates the Maximum
56*404b540aSrobertnumber of free lists that the FLS can hold internally (cache).
57*404b540aSrobertCurrently, this value is set at 64. So, if there are more than 64 free
58*404b540aSrobertlists coming in, then some of them will be given back to the OS using
59*404b540aSrobertoperator delete so that at any given time the Free List's size does not
60*404b540aSrobertexceed 64 entries. This is done because a Binary Search is used to
61*404b540aSrobertlocate an entry in a free list when a request for memory comes along.
62*404b540aSrobertThus, the run-time complexity of the search would go up given an
63*404b540aSrobertincreasing size, for 64 entries however, lg(64) == 6 comparisons are
64*404b540aSrobertenough to locate the correct free list if it exists.<br>
65*404b540aSrobert<br>
66*404b540aSrobertSuppose the free list size has reached it's threshold, then the largest
67*404b540aSrobertblock from among those in the list and the new block will be selected
68*404b540aSrobertand given back to the OS. This is done because it reduces external
69*404b540aSrobertfragmentation, and allows the OS to use the larger blocks later in an
70*404b540aSrobertorderly fashion, possibly merging them later. Also, on some systems,
71*404b540aSrobertlarge blocks are obtained via calls to mmap, so giving them back to
72*404b540aSrobertfree system resources becomes most important.<br>
73*404b540aSrobert<br>
74*404b540aSrobertThe function _S_should_i_give decides the policy that determines
75*404b540aSrobertwhether the current block of memory should be given to the allocator
76*404b540aSrobertfor the request that it has made. That's because we may not always have
77*404b540aSrobertexact fits for the memory size that the allocator requests. We do this
78*404b540aSrobertmainly to prevent external fragmentation at the cost of a little
79*404b540aSrobertinternal fragmentation. Now, the value of this internal fragmentation
80*404b540aSroberthas to be decided by this function. I can see 3 possibilities right
81*404b540aSrobertnow. Please add more as and when you find better strategies.<br>
82*404b540aSrobert<br>
83*404b540aSrobert<ol>
84*404b540aSrobert  <li>Equal size check. Return true only when the 2 blocks are of equal
85*404b540aSrobertsize.</li>
86*404b540aSrobert  <li>Difference Threshold: Return true only when the _block_size is
87*404b540aSrobertgreater than or equal to the _required_size, and if the _BS is &gt; _RS
88*404b540aSrobertby a difference of less than some THRESHOLD value, then return true,
89*404b540aSrobertelse return false. </li>
90*404b540aSrobert  <li>Percentage Threshold. Return true only when the _block_size is
91*404b540aSrobertgreater than or equal to the _required_size, and if the _BS is &gt; _RS
92*404b540aSrobertby a percentage of less than some THRESHOLD value, then return true,
93*404b540aSrobertelse return false.</li>
94*404b540aSrobert</ol>
95*404b540aSrobert<br>
96*404b540aSrobertCurrently, (3) is being used with a value of 36% Maximum wastage per
97*404b540aSrobertSuper Block.<br>
98*404b540aSrobert<br>
99*404b540aSrobert<hr style="width: 100%; height: 2px;"><span style="font-weight: bold;">1)
100*404b540aSrobertWhat is a super block? Why is it needed?</span><br>
101*404b540aSrobert<br>
102*404b540aSrobertA super block is the block of memory acquired from the FLS from which
103*404b540aSrobertthe bitmap allocator carves out memory for single objects and satisfies
104*404b540aSrobertthe user's requests. These super blocks come in sizes that are powers
105*404b540aSrobertof 2 and multiples of 32 (_Bits_Per_Block). Yes both at the same time!
106*404b540aSrobertThat's because the next super block acquired will be 2 times the
107*404b540aSrobertprevious one, and also all super blocks have to be multiples of the
108*404b540aSrobert_Bits_Per_Block value. <br>
109*404b540aSrobert<br>
110*404b540aSrobert<span style="font-weight: bold;">2) How does it interact with the free
111*404b540aSrobertlist store?</span><br>
112*404b540aSrobert<br>
113*404b540aSrobertThe super block is contained in the FLS, and the FLS is responsible for
114*404b540aSrobertgetting / returning Super Bocks to and from the OS using operator new
115*404b540aSrobertas defined by the C++ standard.<br>
116*404b540aSrobert<br>
117*404b540aSrobert<hr style="width: 100%; height: 2px;">
118*404b540aSrobert<h3 style="text-align: center;">How does the allocate function Work?</h3>
119*404b540aSrobert<br>
120*404b540aSrobertThe allocate function is specialized for single object allocation ONLY.
121*404b540aSrobertThus, ONLY if n == 1, will the bitmap_allocator's specialized algorithm
122*404b540aSrobertbe used. Otherwise, the request is satisfied directly by calling
123*404b540aSrobertoperator new.<br>
124*404b540aSrobert<br>
125*404b540aSrobertSuppose n == 1, then the allocator does the following:<br>
126*404b540aSrobert<br>
127*404b540aSrobert<ol>
128*404b540aSrobert  <li>Checks to see whether a free block exists somewhere in a
129*404b540aSrobertregion of memory close to the last satisfied request. If so, then that
130*404b540aSrobertblock is marked as allocated in the bit map and given to the user. If
131*404b540aSrobertnot, then (2) is executed.</li>
132*404b540aSrobert  <li>Is there a free block anywhere after the current block right up to
133*404b540aSrobertthe end of the memory that we have? If so, that block is found, and the
134*404b540aSrobertsame procedure is applied as above, and returned to the user. If not,
135*404b540aSrobertthen (3) is executed.</li>
136*404b540aSrobert  <li>Is there any block in whatever region of memory that we own free?
137*404b540aSrobertThis is done by checking <br>
138*404b540aSrobert    <div style="margin-left: 40px;">
139*404b540aSrobert    <ul>
140*404b540aSrobert      <li>The use count for each super block, and if that fails then </li>
141*404b540aSrobert      <li>The individual bit-maps for each super block. </li>
142*404b540aSrobert    </ul>
143*404b540aSrobert    </div>
144*404b540aSrobertNote: Here we are never touching any of the memory that the user will
145*404b540aSrobertbe given, and we are confining all memory accesses to a small region of
146*404b540aSrobertmemory! This helps reduce cache misses. If this succeeds then we apply
147*404b540aSrobertthe same procedure on that bit-map as (1), and return that block of
148*404b540aSrobertmemory to the user. However, if this process fails, then we resort to
149*404b540aSrobert(4).</li>
150*404b540aSrobert  <li>This process involves Refilling the internal exponentially
151*404b540aSrobertgrowing memory pool. The said effect is achieved by calling
152*404b540aSrobert_S_refill_pool which does the following: <br>
153*404b540aSrobert    <div style="margin-left: 40px;">
154*404b540aSrobert    <ul>
155*404b540aSrobert      <li>Gets more memory from the Global Free List of the Required
156*404b540aSrobertsize. </li>
157*404b540aSrobert      <li>Adjusts the size for the next call to itself. </li>
158*404b540aSrobert      <li>Writes the appropriate headers in the bit-maps.</li>
159*404b540aSrobert      <li>Sets the use count for that super-block just allocated to 0
160*404b540aSrobert(zero). </li>
161*404b540aSrobert      <li>All of the above accounts to maintaining the basic invariant
162*404b540aSrobertfor the allocator. If the invariant is maintained, we are sure that all
163*404b540aSrobertis well. Now, the same process is applied on the newly acquired free
164*404b540aSrobertblocks, which are dispatched accordingly.</li>
165*404b540aSrobert    </ul>
166*404b540aSrobert    </div>
167*404b540aSrobert  </li>
168*404b540aSrobert</ol>
169*404b540aSrobert<br>
170*404b540aSrobertThus, you can clearly see that the allocate function is nothing but a
171*404b540aSrobertcombination of the next-fit and first-fit algorithm optimized ONLY for
172*404b540aSrobertsingle object allocations.<br>
173*404b540aSrobert<br>
174*404b540aSrobert<br>
175*404b540aSrobert<hr style="width: 100%; height: 2px;">
176*404b540aSrobert<h3 style="text-align: center;">How does the deallocate function work?</h3>
177*404b540aSrobert<br>
178*404b540aSrobertThe deallocate function again is specialized for single objects ONLY.
179*404b540aSrobertFor all n belonging to &gt; 1, the operator delete is called without
180*404b540aSrobertfurther ado, and the deallocate function returns.<br>
181*404b540aSrobert<br>
182*404b540aSrobertHowever for n == 1, a series of steps are performed:<br>
183*404b540aSrobert<br>
184*404b540aSrobert<ol>
185*404b540aSrobert  <li>We first need to locate that super-block which holds the memory
186*404b540aSrobertlocation given to us by the user. For that purpose, we maintain a
187*404b540aSrobertstatic variable _S_last_dealloc_index, which holds the index into the
188*404b540aSrobertvector of block pairs which indicates the index of the last super-block
189*404b540aSrobertfrom which memory was freed. We use this strategy in the hope that the
190*404b540aSrobertuser will deallocate memory in a region close to what he/she
191*404b540aSrobertdeallocated the last time around. If the check for belongs_to succeeds,
192*404b540aSrobertthen we determine the bit-map for the given pointer, and locate the
193*404b540aSrobertindex into that bit-map, and mark that bit as free by setting it.</li>
194*404b540aSrobert  <li>If the _S_last_dealloc_index does not point to the memory block
195*404b540aSrobertthat we're looking for, then we do a linear search on the block stored
196*404b540aSrobertin the vector of Block Pairs. This vector in code is called
197*404b540aSrobert_S_mem_blocks. When the corresponding super-block is found, we apply
198*404b540aSrobertthe same procedure as we did for (1) to mark the block as free in the
199*404b540aSrobertbit-map.</li>
200*404b540aSrobert</ol>
201*404b540aSrobert<br>
202*404b540aSrobertNow, whenever a block is freed, the use count of that particular super
203*404b540aSrobertblock goes down by 1. When this use count hits 0, we remove that super
204*404b540aSrobertblock from the list of all valid super blocks stored in the vector.
205*404b540aSrobertWhile doing this, we also make sure that the basic invariant is
206*404b540aSrobertmaintained by making sure that _S_last_request and
207*404b540aSrobert_S_last_dealloc_index point to valid locations within the vector.<br>
208*404b540aSrobert<br>
209*404b540aSrobert<hr style="width: 100%; height: 2px;"><br>
210*404b540aSrobert<h3 style="text-align: center;">Data Layout for a Super Block:</h3>
211*404b540aSrobert<br>
212*404b540aSrobertEach Super Block will be of some size that is a multiple of the number
213*404b540aSrobertof Bits Per Block. Typically, this value is chosen as Bits_Per_Byte x
214*404b540aSrobertsizeof(size_t). On an x86 system, this gives the figure &nbsp;8 x
215*404b540aSrobert4 = 32. Thus, each Super Block will be of size 32 x Some_Value. This
216*404b540aSrobertSome_Value is sizeof(value_type). For now, let it be called 'K'. Thus,
217*404b540aSrobertfinally, Super Block size is 32 x K bytes.<br>
218*404b540aSrobert<br>
219*404b540aSrobertThis value of 32 has been chosen because each size_t has 32-bits
220*404b540aSrobertand Maximum use of these can be made with such a figure.<br>
221*404b540aSrobert<br>
222*404b540aSrobertConsider a block of size 64 ints. In memory, it would look like this:
223*404b540aSrobert(assume a 32-bit system where, size_t is a 32-bit entity).<br>
224*404b540aSrobert<br>
225*404b540aSrobert<table cellpadding="0" cellspacing="0" border="1"
226*404b540aSrobert style="text-align: left; width: 763px; height: 21px;">
227*404b540aSrobert  <tbody>
228*404b540aSrobert    <tr>
229*404b540aSrobert      <td style="vertical-align: top; text-align: center;">268<br>
230*404b540aSrobert      </td>
231*404b540aSrobert      <td style="vertical-align: top; text-align: center;">0<br>
232*404b540aSrobert      </td>
233*404b540aSrobert      <td style="vertical-align: top; text-align: center;">4294967295<br>
234*404b540aSrobert      </td>
235*404b540aSrobert      <td style="vertical-align: top; text-align: center;">4294967295<br>
236*404b540aSrobert      </td>
237*404b540aSrobert      <td style="vertical-align: top; text-align: center;">Data -&gt;
238*404b540aSrobertSpace for 64 ints<br>
239*404b540aSrobert      </td>
240*404b540aSrobert    </tr>
241*404b540aSrobert  </tbody>
242*404b540aSrobert</table>
243*404b540aSrobert<br>
244*404b540aSrobert<br>
245*404b540aSrobertThe first Column(268) represents the size of the Block in bytes as seen
246*404b540aSrobertby
247*404b540aSrobertthe Bitmap Allocator. Internally, a global free list is used to keep
248*404b540aSroberttrack of the free blocks used and given back by the bitmap allocator.
249*404b540aSrobertIt is this Free List Store that is responsible for writing and managing
250*404b540aSrobertthis information. Actually the number of bytes allocated in this case
251*404b540aSrobertwould be: 4 + 4 + (4x2) + (64x4) = 272 bytes, but the first 4 bytes are
252*404b540aSrobertan
253*404b540aSrobertaddition by the Free List Store, so the Bitmap Allocator sees only 268
254*404b540aSrobertbytes. These first 4 bytes about which the bitmapped allocator is not
255*404b540aSrobertaware hold the value 268.<br>
256*404b540aSrobert<br>
257*404b540aSrobert<span style="font-weight: bold;">What do the remaining values represent?</span><br>
258*404b540aSrobert<br>
259*404b540aSrobertThe 2nd 4 in the expression is the sizeof(size_t) because the
260*404b540aSrobertBitmapped Allocator maintains a used count for each Super Block, which
261*404b540aSrobertis initially set to 0 (as indicated in the diagram). This is
262*404b540aSrobertincremented every time a block is removed from this super block
263*404b540aSrobert(allocated), and decremented whenever it is given back. So, when the
264*404b540aSrobertused count falls to 0, the whole super block will be given back to the
265*404b540aSrobertFree List Store.<br>
266*404b540aSrobert<br>
267*404b540aSrobertThe value 4294967295 represents the integer corresponding to the bit
268*404b540aSrobertrepresentation of all bits set: 11111111111111111111111111111111.<br>
269*404b540aSrobert<br>
270*404b540aSrobertThe 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits
271*404b540aSrobertx 2,
272*404b540aSrobertwhich is 8-bytes, or 2 x sizeof(size_t).<br>
273*404b540aSrobert<br>
274*404b540aSrobert<hr style="width: 100%; height: 2px;"><br>
275*404b540aSrobertAnother issue would be whether to keep the all bitmaps in a separate
276*404b540aSrobertarea in memory, or to keep them near the actual blocks that will be
277*404b540aSrobertgiven out or allocated for the client. After some testing, I've decided
278*404b540aSrobertto keep these bitmaps close to the actual blocks. This will help in 2
279*404b540aSrobertways. <br>
280*404b540aSrobert<br>
281*404b540aSrobert<ol>
282*404b540aSrobert  <li>Constant time access for the bitmap themselves, since no kind of
283*404b540aSrobertlook up will be needed to find the correct bitmap list or it's
284*404b540aSrobertequivalent.</li>
285*404b540aSrobert  <li>And also this would preserve the cache as far as possible.</li>
286*404b540aSrobert</ol>
287*404b540aSrobert<br>
288*404b540aSrobertSo in effect, this kind of an allocator might prove beneficial from a
289*404b540aSrobertpurely cache point of view. But this allocator has been made to try and
290*404b540aSrobertroll out the defects of the node_allocator, wherein the nodes get
291*404b540aSrobertskewed about in memory, if they are not returned in the exact reverse
292*404b540aSrobertorder or in the same order in which they were allocated. Also, the
293*404b540aSrobertnew_allocator's book keeping overhead is too much for small objects and
294*404b540aSrobertsingle object allocations, though it preserves the locality of blocks
295*404b540aSrobertvery well when they are returned back to the allocator.<br>
296*404b540aSrobert<br>
297*404b540aSrobert<hr style="width: 100%; height: 2px;"><br>
298*404b540aSrobertExpected overhead per block would be 1 bit in memory. Also, once the
299*404b540aSrobertaddress of the free list has been found, the cost for
300*404b540aSrobertallocation/deallocation would be negligible, and is supposed to be
301*404b540aSrobertconstant time. For these very reasons, it is very important to minimize
302*404b540aSrobertthe linear time costs, which include finding a free list with a free
303*404b540aSrobertblock while allocating, and finding the corresponding free list for a
304*404b540aSrobertblock while deallocating. Therefore, I have decided that the growth of
305*404b540aSrobertthe internal pool for this allocator will be exponential as compared to
306*404b540aSrobertlinear for node_allocator. There, linear time works well, because we
307*404b540aSrobertare mainly concerned with speed of allocation/deallocation and memory
308*404b540aSrobertconsumption, whereas here, the allocation/deallocation part does have
309*404b540aSrobertsome linear/logarithmic complexity components in it. Thus, to try and
310*404b540aSrobertminimize them would be a good thing to do at the cost of a little bit
311*404b540aSrobertof memory.<br>
312*404b540aSrobert<br>
313*404b540aSrobertAnother thing to be noted is the pool size will double every time
314*404b540aSrobertthe internal pool gets exhausted, and all the free blocks have been
315*404b540aSrobertgiven away. The initial size of the pool would be sizeof(size_t) x 8
316*404b540aSrobertwhich is the number of bits in an integer, which can fit exactly
317*404b540aSrobertin a CPU register. Hence, the term given is exponential growth of the
318*404b540aSrobertinternal pool.<br>
319*404b540aSrobert<br>
320*404b540aSrobert<hr style="width: 100%; height: 2px;">After reading all this, you may
321*404b540aSrobertstill have a few questions about the internal working of this
322*404b540aSrobertallocator, like my friend had!<br>
323*404b540aSrobert<br>
324*404b540aSrobertWell here are the exact questions that he posed:<br>
325*404b540aSrobert<br>
326*404b540aSrobert<span style="font-weight: bold;">Q1) The "Data Layout" section is
327*404b540aSrobertcryptic. I have no idea of what you are trying to say. Layout of what?
328*404b540aSrobertThe free-list? Each bitmap? The Super Block?</span><br>
329*404b540aSrobert<br>
330*404b540aSrobert<div style="margin-left: 40px;"> The layout of a Super Block of a given
331*404b540aSrobertsize. In the example, a super block of size 32 x 1 is taken. The
332*404b540aSrobertgeneral formula for calculating the size of a super block is
333*404b540aSrobert32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit
334*404b540aSrobertsystems.<br>
335*404b540aSrobert</div>
336*404b540aSrobert<br>
337*404b540aSrobert<span style="font-weight: bold;">Q2) And since I just mentioned the
338*404b540aSrobertterm `each bitmap', what in the world is meant by it? What does each
339*404b540aSrobertbitmap manage? How does it relate to the super block? Is the Super
340*404b540aSrobertBlock a bitmap as well?</span><br style="font-weight: bold;">
341*404b540aSrobert<br>
342*404b540aSrobert<div style="margin-left: 40px;"> Good question! Each bitmap is part of
343*404b540aSroberta
344*404b540aSrobertSuper Block which is made up of 3 parts as I have mentioned earlier.
345*404b540aSrobertRe-iterating, 1. The use count, 2. The bit-map for that Super Block. 3.
346*404b540aSrobertThe actual memory that will be eventually given to the user. Each
347*404b540aSrobertbitmap is a multiple of 32 in size. If there are 32 x (2^3) blocks of
348*404b540aSrobertsingle objects to be given, there will be '32 x (2^3)' bits present.
349*404b540aSrobertEach
350*404b540aSrobert32 bits managing the allocated / free status for 32 blocks. Since each
351*404b540aSrobertsize_t contains 32-bits, one size_t can manage up to 32
352*404b540aSrobertblocks' status. Each bit-map is made up of a number of size_t,
353*404b540aSrobertwhose exact number for a super-block of a given size I have just
354*404b540aSrobertmentioned.<br>
355*404b540aSrobert</div>
356*404b540aSrobert<br>
357*404b540aSrobert<span style="font-weight: bold;">Q3) How do the allocate and deallocate
358*404b540aSrobertfunctions work in regard to bitmaps?</span><br>
359*404b540aSrobert<br>
360*404b540aSrobert<div style="margin-left: 40px;"> The allocate and deallocate functions
361*404b540aSrobertmanipulate the bitmaps and have nothing to do with the memory that is
362*404b540aSrobertgiven to the user. As I have earlier mentioned, a 1 in the bitmap's bit
363*404b540aSrobertfield indicates free, while a 0 indicates allocated. This lets us check
364*404b540aSrobert32 bits at a time to check whether there is at lease one free block in
365*404b540aSrobertthose 32 blocks by testing for equality with (0). Now, the allocate
366*404b540aSrobertfunction will given a memory block find the corresponding bit in the
367*404b540aSrobertbitmap, and will reset it (i.e., make it re-set (0)). And when the
368*404b540aSrobertdeallocate function is called, it will again set that bit after
369*404b540aSrobertlocating it to indicate that that particular block corresponding to
370*404b540aSrobertthis bit in the bit-map is not being used by anyone, and may be used to
371*404b540aSrobertsatisfy future requests.<br>
372*404b540aSrobert<br>
373*404b540aSroberte.g.: Consider a bit-map of 64-bits as represented below:<br>
374*404b540aSrobert1111111111111111111111111111111111111111111111111111111111111111<br>
375*404b540aSrobert<br>
376*404b540aSrobertNow, when the first request for allocation of a single object comes
377*404b540aSrobertalong, the first block in address order is returned. And since the
378*404b540aSrobertbit-maps in the reverse order to that of the address order, the last
379*404b540aSrobertbit (LSB if the bit-map is considered as a binary word of 64-bits) is
380*404b540aSrobertre-set to 0.<br>
381*404b540aSrobert<br>
382*404b540aSrobertThe bit-map now looks like this:<br>
383*404b540aSrobert1111111111111111111111111111111111111111111111111111111111111110<br>
384*404b540aSrobert</div>
385*404b540aSrobert<br>
386*404b540aSrobert<br>
387*404b540aSrobert<hr style="width: 100%; height: 2px;"><br>
388*404b540aSrobert(Tech-Stuff, Please stay out if you are not interested in the selection
389*404b540aSrobertof certain constants. This has nothing to do with the algorithm per-se,
390*404b540aSrobertonly with some vales that must be chosen correctly to ensure that the
391*404b540aSrobertallocator performs well in a real word scenario, and maintains a good
392*404b540aSrobertbalance between the memory consumption and the allocation/deallocation
393*404b540aSrobertspeed).<br>
394*404b540aSrobert<br>
395*404b540aSrobertThe formula for calculating the maximum wastage as a percentage:<br>
396*404b540aSrobert<br>
397*404b540aSrobert(32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.<br>
398*404b540aSrobert<br>
399*404b540aSrobertWhere,<br>
400*404b540aSrobertk =&gt; The constant overhead per node. eg. for list, it is 8 bytes,
401*404b540aSrobertand for map it is 12 bytes.<br>
402*404b540aSrobertc =&gt; The size of the base type on which the map/list is
403*404b540aSrobertinstantiated. Thus, suppose the type1 is int and type2 is double,
404*404b540aSrobertthey are related by the relation sizeof(double) == 2*sizeof(int). Thus,
405*404b540aSrobertall types must have this double size relation for this formula to work
406*404b540aSrobertproperly.<br>
407*404b540aSrobert<br>
408*404b540aSrobertPlugging-in: For List: k = 8 and c = 4 (int and double), we get:<br>
409*404b540aSrobert33.376%<br>
410*404b540aSrobert<br>
411*404b540aSrobertFor map/multimap: k = 12, and c = 4 (int and double), we get:<br>
412*404b540aSrobert37.524%<br>
413*404b540aSrobert<br>
414*404b540aSrobertThus, knowing these values, and based on the sizeof(value_type), we may
415*404b540aSrobertcreate a function that returns the Max_Wastage_Percentage for us to use.<br>
416*404b540aSrobert<br>
417*404b540aSrobert<hr style="width: 100%; height: 2px;"><small><small><em> See <a
418*404b540aSrobert href="file:///home/dhruv/projects/libstdc++-v3/gcc/libstdc++-v3/docs/html/17_intro/license.html">license.html</a>
419*404b540aSrobertfor copying conditions. Comments and suggestions are welcome, and may
420*404b540aSrobertbe
421*404b540aSrobertsent to <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing
422*404b540aSrobertlist</a>.</em><br>
423*404b540aSrobert</small></small><br>
424*404b540aSrobert<br>
425*404b540aSrobert</body>
426*404b540aSrobert</html>
427