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 > _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 > _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 > 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 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 -> 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 => The constant overhead per node. eg. for list, it is 8 bytes, 401*404b540aSrobertand for map it is 12 bytes.<br> 402*404b540aSrobertc => 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