From b9efd8877a4ab62792c9df94d3075663bc46a803 Mon Sep 17 00:00:00 2001 From: paolo Date: Sun, 19 Dec 2004 11:04:48 +0000 Subject: [PATCH] 2004-12-19 Dhruv Matani * docs/html/20_util/allocator.html: Correct link. * docs/html/ext/ballocator_doc.txt: Remove. * docs/html/ext/ballocator_doc.html: Add. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@92375 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 6 + libstdc++-v3/docs/html/20_util/allocator.html | 2 +- libstdc++-v3/docs/html/ext/ballocator_doc.html | 426 +++++++++++++++++++++++++ libstdc++-v3/docs/html/ext/ballocator_doc.txt | 374 ---------------------- 4 files changed, 433 insertions(+), 375 deletions(-) create mode 100644 libstdc++-v3/docs/html/ext/ballocator_doc.html delete mode 100644 libstdc++-v3/docs/html/ext/ballocator_doc.txt diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 542a82f..d49da6c 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,9 @@ +2004-12-19 Dhruv Matani + + * docs/html/20_util/allocator.html: Correct link. + * docs/html/ext/ballocator_doc.txt: Remove. + * docs/html/ext/ballocator_doc.html: Add. + 2004-12-16 Danny Smith PR target/18997 diff --git a/libstdc++-v3/docs/html/20_util/allocator.html b/libstdc++-v3/docs/html/20_util/allocator.html index c853dd4..d847fc0 100644 --- a/libstdc++-v3/docs/html/20_util/allocator.html +++ b/libstdc++-v3/docs/html/20_util/allocator.html @@ -434,7 +434,7 @@

A high-performance allocator that uses a bit-map to keep track of the used and unused memory locations. It has its own documentation, found here. + href="../ext/ballocator_doc.html">here.

diff --git a/libstdc++-v3/docs/html/ext/ballocator_doc.html b/libstdc++-v3/docs/html/ext/ballocator_doc.html new file mode 100644 index 0000000..7b1f4d2 --- /dev/null +++ b/libstdc++-v3/docs/html/ext/ballocator_doc.html @@ -0,0 +1,426 @@ + + + + + Bitmap Allocator + + + + +

Bitmap Allocator

+
+The latest version of this document is always available +at +http://gcc.gnu.org/onlinedocs/libstdc++/ext/ballocator_doc.html.
+
+ To the libstdc++-v3 +homepage.
+
+

+As this name suggests, this allocator uses a bit-map to keep track of +the used and unused memory locations for it's book-keeping purposes.
+
+This allocator will make use of 1 single bit to keep track of whether +it has been allocated or not. A bit 1 indicates free, while 0 indicates +allocated. This has been done so that you can easily check a collection +of bits for a free block. This kind of Bitmapped strategy works best +for single object allocations, and with the STL type parameterized +allocators, we do not need to choose any size for the block which will +be represented by a single bit. This will be the size of the parameter +around which the allocator has been parameterized. Thus, close to +optimal performance will result. Hence, this should be used for node +based containers which call the allocate function with an argument of 1.
+
+The bitmapped allocator's internal pool is exponentially growing. +Meaning that internally, the blocks acquired from the Free List Store +will double every time the bitmapped allocator runs out of memory.
+
+

+The macro __GTHREADS decides whether to use Mutex Protection around +every allocation/deallocation. The state of the macro is picked up +automatically from the gthr abstration layer.
+
+

What is the Free List Store?

+
+The Free List Store (referred to as FLS for the remaining part of this +document) is the Global memory pool that is shared by all instances of +the bitmapped allocator instantiated for any type. This maintains a +sorted order of all free memory blocks given back to it by the +bitmapped allocator, and is also responsible for giving memory to the +bitmapped allocator when it asks for more.
+
+Internally, there is a Free List threshold which indicates the Maximum +number of free lists that the FLS can hold internally (cache). +Currently, this value is set at 64. So, if there are more than 64 free +lists coming in, then some of them will be given back to the OS using +operator delete so that at any given time the Free List's size does not +exceed 64 entries. This is done because a Binary Search is used to +locate an entry in a free list when a request for memory comes along. +Thus, the run-time complexity of the search would go up given an +increasing size, for 64 entries however, lg(64) == 6 comparisons are +enough to locate the correct free list if it exists.
+
+Suppose the free list size has reached it's threshold, then the largest +block from among those in the list and the new block will be selected +and given back to the OS. This is done because it reduces external +fragmentation, and allows the OS to use the larger blocks later in an +orderly fashion, possibly merging them later. Also, on some systems, +large blocks are obtained via calls to mmap, so giving them back to +free system resources becomes most important.
+
+The function _S_should_i_give decides the policy that determines +whether the current block of memory should be given to the allocator +for the request that it has made. That's because we may not always have +exact fits for the memory size that the allocator requests. We do this +mainly to prevent external fragmentation at the cost of a little +internal fragmentation. Now, the value of this internal fragmentation +has to be decided by this function. I can see 3 possibilities right +now. Please add more as and when you find better strategies.
+
+

Equal size check. Return true only when the 2 blocks are of equal +size.
Difference Threshold: Return true only when the _block_size is +greater than or equal to the _required_size, and if the _BS is > _RS +by a difference of less than some THRESHOLD value, then return true, +else return false.
Percentage Threshold. Return true only when the _block_size is +greater than or equal to the _required_size, and if the _BS is > _RS +by a percentage of less than some THRESHOLD value, then return true, +else return false.

+
+Currently, (3) is being used with a value of 36% Maximum wastage per +Super Block.
+
+

1) +What is a super block? Why is it needed?
+
+A super block is the block of memory acquired from the FLS from which +the bitmap allocator carves out memory for single objects and satisfies +the user's requests. These super blocks come in sizes that are powers +of 2 and multiples of 32 (_Bits_Per_Block). Yes both at the same time! +That's because the next super block acquired will be 2 times the +previous one, and also all super blocks have to be multiples of the +_Bits_Per_Block value.
+
+2) How does it interact with the free +list store?
+
+The super block is contained in the FLS, and the FLS is responsible for +getting / returning Super Bocks to and from the OS using operator new +as defined by the C++ standard.
+
+

How does the allocate function Work?

+
+The allocate function is specialized for single object allocation ONLY. +Thus, ONLY if n == 1, will the bitmap_allocator's specialized algorithm +be used. Otherwise, the request is satisfied directly by calling +operator new.
+
+Suppose n == 1, then the allocator does the following:
+
+

Checks to see whether the a free block exists somewhere in a +region of memory close to the last satisfied request. If so, then that +block is marked as allocated in the bit map and given to the user. If +not, then (2) is executed.
Is there a free block anywhere after the current block right upto +the end of the memory that we have? If so, that block is found, and the +same procedure is applied as above, and returned to the user. If not, +then (3) is executed.
Is there any block in whatever region of memory that we own free? +This is done by checking
+
+
- The use count for each super block, and if that fails then
- The individual bit-maps for each super block.
+
+Note: Here we are never touching any of the memory that the user will +be given, and we are confining all memory accesses to a small region of +memory! This helps reduce cache misses. If this succeeds then we apply +the same procedure on that bit-map as (1), and return that block of +memory to the user. However, if this process fails, then we resort to +(4).
This process involves Refilling the internal exponentially +growing memory pool. The said effect is achieved by calling +_S_refill_pool which does the following:
+
+
- Gets more memory from the Global Free List of the Required +size.
- Adjusts the size for the next call to itself.
- Writes the appropriate headers in the bit-maps.
- Sets the use count for that super-block just allocated to 0 +(zero).
- All of the above accounts to maintaining the basic invariant +for the allocator. If the invariant is maintained, we are sure that all +is well. Now, the same process is applied on the newly acquired free +blocks, which are dispatched accordingly.
+
+

+
+Thus, you can clearly see that the allocate function is nothing but a +combination of the next-fit and first-fit algorithm optimized ONLY for +single object allocations.
+
+
+

How does the deallocate function work?

+
+The deallocate function again is specialized for single objects ONLY. +For all n belonging to > 1, the operator delete is called without +further ado, and the deallocate function returns.
+
+However for n == 1, a series of steps are performed:
+
+

We first need to locate that super-block which holds the memory +location given to us by the user. For that purpose, we maintain a +static variable _S_last_dealloc_index, which holds the index into the +vector of block pairs which indicates the index of the last super-block +from which memory was freed. We use this strategy in the hope that the +user will deallocate memory in a region close to what he/she +deallocated the last time around. If the check for belongs_to succeeds, +then we determine the bit-map for the given pointer, and locate the +index into that bit-map, and mark that bit as free by setting it.
If the _S_last_dealloc_index does not point to the memory block +that we're looking for, then we do a linear search on the block stored +in the vector of Block Pairs. This vector in code is called +_S_mem_blocks. When the corresponding super-block is found, we apply +the same procedure as we did for (1) to mark the block as free in the +bit-map.

+
+Now, whenever a block is freed, the use count of that particular super +block goes down by 1. When this use count hits 0, we remove that super +block from the list of all valid super blocks stored in the vector. +While doing this, we also make sure that the basic invariant is +maintained by making sure that _S_last_request and +_S_last_dealloc_index point to valid locations within the vector.
+
+

Data Layout for a Super Block:

+
+Each Super Block will be of some size that is a multiple of the number +of Bits Per Block. Typically, this value is chosen as Bits_Per_Byte x +sizeof(size_t). On an x86 system, this gives the figure 8 x +4 = 32. Thus, each Super Block will be of size 32 x Some_Value. This +Some_Value is sizeof(value_type). For now, let it be called 'K'. Thus, +finally, Super Block size is 32 x K bytes.
+
+This value of 32 has been chosen because each size_t has 32-bits +and Maximum use of these can be made with such a figure.
+
+Consider a block of size 64 ints. In memory, it would look like this: +(assume a 32-bit system where, size_t is a 32-bit entity).
+
+ + + + + + + + + + +

268
+

0
+

4294967295
+

Data -> +Space for 64 ints
+

+
+
+The first Column(268) represents the size of the Block in bytes as seen +by +the Bitmap Allocator. Internally, a global free list is used to keep +track of the free blocks used and given back by the bitmap allocator. +It is this Free List Store that is responsible for writing and managing +this information. Actually the number of bytes allocated in this case +would be: 4 + 4 + (4x2) + (64x4) = 272 bytes, but the first 4 bytes are +an +addition by the Free List Store, so the Bitmap Allocator sees only 268 +bytes. These first 4 bytes about which the bitmapped allocator is not +aware hold the value 268.
+
+What do the remaining values represent?
+
+The 2nd 4 in the expression is the sizeof(size_t) because the +Bitmapped Allocator maintains a used count for each Super Block, which +is initially set to 0 (as indicated in the diagram). This is +incremented every time a block is removed from this super block +(allocated), and decremented whenever it is given back. So, when the +used count falls to 0, the whole super block will be given back to the +Free List Store.
+
+The value 4294967295 represents the integer corresponding to the bit +representation of all bits set: 11111111111111111111111111111111.
+
+The 3rd 4x2 is size of the bitmap itself, which is the size of 32-bits +x 2, +which is 8-bytes, or 2 x sizeof(size_t).
+
+

+Another issue would be whether to keep the all bitmaps in a separate +area in memory, or to keep them near the actual blocks that will be +given out or allocated for the client. After some testing, I've decided +to keep these bitmaps close to the actual blocks. this will help in 2 +ways.
+
+

Constant time access for the bitmap themselves, since no kind of +look up will be needed to find the correct bitmap list or it's +equivalent.
And also this would preserve the cache as far as possible.

+
+So in effect, this kind of an allocator might prove beneficial from a +purely cache point of view. But this allocator has been made to try and +roll out the defects of the node_allocator, wherein the nodes get +skewed about in memory, if they are not returned in the exact reverse +order or in the same order in which they were allocated. Also, the +new_allocator's book keeping overhead is too much for small objects and +single object allocations, though it preserves the locality of blocks +very well when they are returned back to the allocator.
+
+

+Expected overhead per block would be 1 bit in memory. Also, once the +address of the free list has been found, the cost for +allocation/deallocation would be negligible, and is supposed to be +constant time. For these very reasons, it is very important to minimize +the linear time costs, which include finding a free list with a free +block while allocating, and finding the corresponding free list for a +block while deallocating. Therefore, I have decided that the growth of +the internal pool for this allocator will be exponential as compared to +linear for node_allocator. There, linear time works well, because we +are mainly concerned with speed of allocation/deallocation and memory +consumption, whereas here, the allocation/deallocation part does have +some linear/logarithmic complexity components in it. Thus, to try and +minimize them would be a good thing to do at the cost of a little bit +of memory.
+
+Another thing to be noted is the the pool size will double every time +the internal pool gets exhausted, and all the free blocks have been +given away. The initial size of the pool would be sizeof(size_t) x 8 +which is the number of bits in an integer, which can fit exactly +in a CPU register. Hence, the term given is exponential growth of the +internal pool.
+
+

After reading all this, you may +still have a few questions about the internal working of this +allocator, like my friend had!
+
+Well here are the exact questions that he posed:
+
+Q1) The "Data Layout" section is +cryptic. I have no idea of what you are trying to say. Layout of what? +The free-list? Each bitmap? The Super Block?
+
+

The layout of a Super Block of a given +size. In the example, a super block of size 32 x 1 is taken. The +general formula for calculating the size of a super block is +32 x sizeof(value_type) x 2^n, where n ranges from 0 to 32 for 32-bit +systems.
+

+
+Q2) And since I just mentioned the +term `each bitmap', what in the world is meant by it? What does each +bitmap manage? How does it relate to the super block? Is the Super +Block a bitmap as well?
+
+

Good question! Each bitmap is part of +a +Super Block which is made up of 3 parts as I have mentioned earlier. +Re-iterating, 1. The use count, 2. The bit-map for that Super Block. 3. +The actual memory that will be eventually given to the user. Each +bitmap is a multiple of 32 in size. If there are 32 x (2^3) blocks of +single objects to be given, there will be '32 x (2^3)' bits present. +Each +32 bits managing the allocated / free status for 32 blocks. Since each +size_t contains 32-bits, one size_t can manage upto 32 +blocks' status. Each bit-map is made up of a number of size_t, +whose exact number for a super-block of a given size I have just +mentioned.
+

+
+Q3) How do the allocate and deallocate +functions work in regard to bitmaps?
+
+

The allocate and deallocate functions +manipulate the bitmaps and have nothing to do with the memory that is +given to the user. As I have earlier mentioned, a 1 in the bitmap's bit +field indicates free, while a 0 indicates allocated. This lets us check +32 bits at a time to check whether there is at lease one free block in +those 32 blocks by testing for equality with (0). Now, the allocate +function will given a memory block find the corresponding bit in the +bitmap, and will reset it (ie. make it re-set (0)). And when the +deallocate function is called, it will again set that bit after +locating it to indicate that that particular block corresponding to +this bit in the bit-map is not being used by anyone, and may be used to +satisfy future requests.
+
+eg: Consider a bit-map of 64-bits as represented below:
+1111111111111111111111111111111111111111111111111111111111111111
+
+Now, when the first request for allocation of a single object comes +along, the first block in address order is returned. And since the +bit-maps in the reverse order to that of the address order, the last +bit(LSB if the bit-map is considered as a binary word of 64-bits) is +re-set to 0.
+
+The bit-map now looks like this:
+1111111111111111111111111111111111111111111111111111111111111110
+

+
+
+

+(Tech-Stuff, Please stay out if you are not interested in the selection +of certain constants. This has nothing to do with the algorithm per-se, +only with some vales that must be chosen correctly to ensure that the +allocator performs well in a real word scenario, and maintains a good +balance between the memory consumption and the allocation/deallocation +speed).
+
+The formula for calculating the maximum wastage as a percentage:
+
+(32 x k + 1) / (2 x (32 x k + 1 + 32 x c)) x 100.
+
+Where,
+k => The constant overhead per node. eg. for list, it is 8 bytes, +and for map it is 12 bytes.
+c => The size of the base type on which the map/list is +instantiated. Thus, suppose the the type1 is int and type2 is double, +they are related by the relation sizeof(double) == 2*sizeof(int). Thus, +all types must have this double size relation for this formula to work +properly.
+
+Plugging-in: For List: k = 8 and c = 4 (int and double), we get:
+33.376%
+
+For map/multimap: k = 12, and c = 4 (int and double), we get:
+37.524%
+
+Thus, knowing these values, and based on the sizeof(value_type), we may +create a function that returns the Max_Wastage_Percentage for us to use.
+
+

See license.html +for copying conditions. Comments and suggestions are welcome, and may +be +sent to the libstdc++ mailing +list.
+
+
+ + diff --git a/libstdc++-v3/docs/html/ext/ballocator_doc.txt b/libstdc++-v3/docs/html/ext/ballocator_doc.txt deleted file mode 100644 index 2173b61..0000000 --- a/libstdc++-v3/docs/html/ext/ballocator_doc.txt +++ /dev/null @@ -1,374 +0,0 @@ - BITMAPPED ALLOCATOR - =================== - -2004-03-11 Dhruv Matani - ---------------------------------------------------------------------- - -As this name suggests, this allocator uses a bit-map to keep track of -the used and unused memory locations for it's book-keeping purposes. - -This allocator will make use of 1 single bit to keep track of whether -it has been allocated or not. A bit 1 indicates free, while 0 -indicates allocated. This has been done so that you can easily check a -collection of bits for a free block. This kind of Bitmapped strategy -works best for single object allocations, and with the STL type -parameterized allocators, we do not need to choose any size for the -block which will be represented by a single bit. This will be the size -of the parameter around which the allocator has been -parameterized. Thus, close to optimal performance will result. Hence, -this should be used for node based containers which call the allocate -function with an argument of 1. - -The bitmapped allocator's internal pool is exponentially -growing. Meaning that internally, the blocks acquired from the Free -List Store will double every time the bitmapped allocator runs out of -memory. - --------------------------------------------------------------------- - -The macro __GTHREADS decides whether to use Mutex Protection around -every allocation/deallocation. The state of the macro is picked up -automatically from the gthr abstration layer. - ----------------------------------------------------------------------- - -What is the Free List Store? ----------------------------- - -The Free List Store (referred to as FLS for the remaining part of this -document) is the Global memory pool that is shared by all instances of -the bitmapped allocator instantiated for any type. This maintains a -sorted order of all free memory blocks given back to it by the -bitmapped allocator, and is also responsible for giving memory to the -bitmapped allocator when it asks for more. - -Internally, there is a Free List threshold which indicates the Maximum -number of free lists that the FLS can hold internally -(cache). Currently, this value is set at 64. So, if there are more -than 64 free lists coming in, then some of them will be given back to -the OS using operator delete so that at any given time the Free List's -size does not exceed 64 entries. This is done because a Binary Search -is used to locate an entry in a free list when a request for memory -comes along. Thus, the run-time complexity of the search would go up -given an increasing size, for 64 entries however, lg(64) == 6 -comparisons are enough to locate the correct free list if it exists. - -Suppose the free list size has reached it's threshold, then the -largest block from among those in the list and the new block will be -selected and given back to the OS. This is done because it reduces -external fragmentation, and allows the OS to use the larger blocks -later in an orderly fashion, possibly merging them later. Also, on -some systems, large blocks are obtained via calls to mmap, so giving -them back to free system resources becomes most important. - -The function _S_should_i_give decides the policy that determines -whether the current block of memory should be given to the allocator -for the request that it has made. That's because we may not always -have exact fits for the memory size that the allocator requests. We do -this mainly to prevent external fragmentation at the cost of a little -internal fragmentation. Now, the value of this internal fragmentation -has to be decided by this function. I can see 3 possibilities right -now. Please add more as and when you find better strategies. - -1. Equal size check. Return true only when the 2 blocks are of equal - size. - -2. Difference Threshold: Return true only when the _block_size is - greater than or equal to the _required_size, and if the _BS is > - _RS by a difference of less than some THRESHOLD value, then return - true, else return false. - -3. Percentage Threshold. Return true only when the _block_size is - greater than or equal to the _required_size, and if the _BS is > - _RS by a percentage of less than some THRESHOLD value, then return - true, else return false. - -Currently, (3) is being used with a value of 36% Maximum wastage per -Super Block. - --------------------------------------------------------------------- - -1) What is a super block? Why is it needed? - - A super block is the block of memory acquired from the FLS from - which the bitmap allocator carves out memory for single objects and - satisfies the user's requests. These super blocks come in sizes that - are powers of 2 and multiples of 32 (_Bits_Per_Block). Yes both at - the same time! That's because the next super block acquired will be - 2 times the previous one, and also all super blocks have to be - multiples of the _Bits_Per_Block value. - -2) How does it interact with the free list store? - - The super block is contained in the FLS, and the FLS is responsible - for getting / returning Super Bocks to and from the OS using - operator new as defined by the C++ standard. - ---------------------------------------------------------------------- - -How does the allocate function Work? ------------------------------------- - -The allocate function is specialized for single object allocation -ONLY. Thus, ONLY if n == 1, will the bitmap_allocator's specialized -algorithm be used. Otherwise, the request is satisfied directly by -calling operator new. - -Suppose n == 1, then the allocator does the following: - -1. Checks to see whether the a free block exists somewhere in a region - of memory close to the last satisfied request. If so, then that - block is marked as allocated in the bit map and given to the - user. If not, then (2) is executed. - -2. Is there a free block anywhere after the current block right upto - the end of the memory that we have? If so, that block is found, and - the same procedure is applied as above, and returned to the - user. If not, then (3) is executed. - -3. Is there any block in whatever region of memory that we own free? - This is done by checking (a) The use count for each super block, - and if that fails then (b) The individual bit-maps for each super - block. Note: Here we are never touching any of the memory that the - user will be given, and we are confining all memory accesses to a - small region of memory! This helps reduce cache misses. If this - succeeds then we apply the same procedure on that bit-map as (1), - and return that block of memory to the user. However, if this - process fails, then we resort to (4). - -4. This process involves Refilling the internal exponentially growing - memory pool. The said effect is achieved by calling _S_refill_pool - which does the following: - (a). Gets more memory from the Global Free List of the - Required size. - (b). Adjusts the size for the next call to itself. - (c). Writes the appropriate headers in the bit-maps. - (d). Sets the use count for that super-block just allocated - to 0 (zero). - (e). All of the above accounts to maintaining the basic - invariant for the allocator. If the invariant is - maintained, we are sure that all is well. - Now, the same process is applied on the newly acquired free blocks, - which are dispatched accordingly. - -Thus, you can clearly see that the allocate function is nothing but a -combination of the next-fit and first-fit algorithm optimized ONLY for -single object allocations. - - -------------------------------------------------------------------------- - -How does the deallocate function work? --------------------------------------- - -The deallocate function again is specialized for single objects ONLY. -For all n belonging to > 1, the operator delete is called without -further ado, and the deallocate function returns. - -However for n == 1, a series of steps are performed: - -1. We first need to locate that super-block which holds the memory - location given to us by the user. For that purpose, we maintain a - static variable _S_last_dealloc_index, which holds the index into - the vector of block pairs which indicates the index of the last - super-block from which memory was freed. We use this strategy in - the hope that the user will deallocate memory in a region close to - what he/she deallocated the last time around. If the check for - belongs_to succeeds, then we determine the bit-map for the given - pointer, and locate the index into that bit-map, and mark that bit - as free by setting it. - -2. If the _S_last_dealloc_index does not point to the memory block - that we're looking for, then we do a linear search on the block - stored in the vector of Block Pairs. This vector in code is called - _S_mem_blocks. When the corresponding super-block is found, we - apply the same procedure as we did for (1) to mark the block as - free in the bit-map. - -Now, whenever a block is freed, the use count of that particular super -block goes down by 1. When this use count hits 0, we remove that super -block from the list of all valid super blocks stored in the -vector. While doing this, we also make sure that the basic invariant -is maintained by making sure that _S_last_request and -_S_last_dealloc_index point to valid locations within the vector. - --------------------------------------------------------------------- - - -Data Layout for a Super Block: -============================== - -Each Super Block will be of some size that is a multiple of the number -of Bits Per Block. Typically, this value is chosen as Bits_Per_Byte X -sizeof(unsigned int). On an X86 system, this gives the figure -8 X 4 = 32. Thus, each Super Block will be of size 32 X Some_Value. -This Some_Value is sizeof(value_type). For now, let it be called 'K'. -Thus, finally, Super Block size is 32 X K bytes. - -This value of 32 has been chosen because each unsigned int has 32-bits -and Maximum use of these can be made with such a figure. - -Consider a block of size 32 ints. -In memory, it would look like this: - ---------------------------------------------------------------------- -| 136 | 0 | 4294967295 | Data-> Space for 32-ints | ---------------------------------------------------------------------- - -The first Columns represents the size of the Block in bytes as seen by -the Bitmap Allocator. Internally, a global free list is used to keep -track of the free blocks used and given back by the bitmap -allocator. It is this Free List Store that is responsible for writing -and managing this information. Actually the number of bytes allocated -in this case would be: 4 + 4 + 4 + 32*4 = 140 bytes, but the first 4 -bytes are an addition by the Free List Store, so the Bitmap Allocator -sees only 136 bytes. These first 4 bytes about which the bitmapped -allocator is not aware hold the value 136. - -What do the remaining values represent? ---------------------------------------- - -The 2nd 4 in the expression is the sizeof(unsigned int) because the -Bitmapped Allocator maintains a used count for each Super Block, which -is initially set to 0 (as indicated in the diagram). This is -incremented every time a block is removed from this super block -(allocated), and decremented whenever it is given back. So, when the -used count falls to 0, the whole super block will be given back to the -Free List Store. - -The value 4294967295 represents the integer corresponding to the -bit representation of all bits set: 11111111111111111111111111111111. - -The 3rd 4 is size of the bitmap itself, which is the size of 32-bits, -which is 4-bytes, or 1 X sizeof(unsigned int). - - --------------------------------------------------------------------- - -Another issue would be whether to keep the all bitmaps in a separate -area in memory, or to keep them near the actual blocks that will be -given out or allocated for the client. After some testing, I've -decided to keep these bitmaps close to the actual blocks. this will -help in 2 ways. - -1. Constant time access for the bitmap themselves, since no kind of - look up will be needed to find the correct bitmap list or it's - equivalent. - -2. And also this would preserve the cache as far as possible. - -So in effect, this kind of an allocator might prove beneficial from a -purely cache point of view. But this allocator has been made to try -and roll out the defects of the node_allocator, wherein the nodes get -skewed about in memory, if they are not returned in the exact reverse -order or in the same order in which they were allocated. Also, the -new_allocator's book keeping overhead is too much for small objects -and single object allocations, though it preserves the locality of -blocks very well when they are returned back to the allocator. - -------------------------------------------------------------------- - -Expected overhead per block would be 1 bit in memory. Also, once -the address of the free list has been found, the cost for -allocation/deallocation would be negligible, and is supposed to be -constant time. For these very reasons, it is very important to -minimize the linear time costs, which include finding a free list -with a free block while allocating, and finding the corresponding -free list for a block while deallocating. Therefore, I have decided -that the growth of the internal pool for this allocator will be -exponential as compared to linear for node_allocator. There, linear -time works well, because we are mainly concerned with speed of -allocation/deallocation and memory consumption, whereas here, the -allocation/deallocation part does have some linear/logarithmic -complexity components in it. Thus, to try and minimize them would -be a good thing to do at the cost of a little bit of memory. - -Another thing to be noted is the the pool size will double every time -the internal pool gets exhausted, and all the free blocks have been -given away. The initial size of the pool would be sizeof(unsigned -int)*8 which is the number of bits in an integer, which can fit -exactly in a CPU register. Hence, the term given is exponential growth -of the internal pool. - ---------------------------------------------------------------------- - -After reading all this, you may still have a few questions about the -internal working of this allocator, like my friend had! - -Well here are the exact questions that he posed: - -1) The "Data Layout" section is cryptic. I have no idea of what you - are trying to say. Layout of what? The free-list? Each bitmap? The - Super Block? - - The layout of a Super Block of a given size. In the example, a super - block of size 32 X 1 is taken. The general formula for calculating - the size of a super block is 32*sizeof(value_type)*2^n, where n - ranges from 0 to 32 for 32-bit systems. - -2) And since I just mentioned the term `each bitmap', what in the - world is meant by it? What does each bitmap manage? How does it - relate to the super block? Is the Super Block a bitmap as well? - - Good question! Each bitmap is part of a Super Block which is made up - of 3 parts as I have mentioned earlier. Re-iterating, 1. The use - count, 2. The bit-map for that Super Block. 3. The actual memory - that will be eventually given to the user. Each bitmap is a multiple - of 32 in size. If there are 32*(2^3) blocks of single objects to be - given, there will be '32*(2^3)' bits present. Each 32 bits managing - the allocated / free status for 32 blocks. Since each unsigned int - contains 32-bits, one unsigned int can manage upto 32 blocks' - status. Each bit-map is made up of a number of unsigned ints, whose - exact number for a super-block of a given size I have just - mentioned. - -3) How do the allocate and deallocate functions work in regard to - bitmaps? - - The allocate and deallocate functions manipulate the bitmaps and have - nothing to do with the memory that is given to the user. As I have - earlier mentioned, a 1 in the bitmap's bit field indicates free, - while a 0 indicates allocated. This lets us check 32 bits at a time - to check whether there is at lease one free block in those 32 blocks - by testing for equality with (0). Now, the allocate function will - given a memory block find the corresponding bit in the bitmap, and - will reset it (ie. make it re-set (0)). And when the deallocate - function is called, it will again set that bit after locating it to - indicate that that particular block corresponding to this bit in the - bit-map is not being used by anyone, and may be used to satisfy - future requests. - ----------------------------------------------------------------------- - -(Tech-Stuff, Please stay out if you are not interested in the -selection of certain constants. This has nothing to do with the -algorithm per-se, only with some vales that must be chosen correctly -to ensure that the allocator performs well in a real word scenario, -and maintains a good balance between the memory consumption and the -allocation/deallocation speed). - -The formula for calculating the maximum wastage as a percentage: - -(32 X k + 1) / (2 X (32 X k + 1 + 32 X c)) X 100. - -Where, - k => The constant overhead per node. eg. for list, it is 8 - bytes, and for map it is 12 bytes. - c => The size of the base type on which the map/list is - instantiated. Thus, suppose the the type1 is int and type2 is - double, they are related by the relation sizeof(double) == - 2*sizeof(int). Thus, all types must have this double size - relation for this formula to work properly. - -Plugging-in: For List: k = 8 and c = 4 (int and double), we get: -33.376% - -For map/multimap: k = 12, and c = 4 (int and double), we get: -37.524% - -Thus, knowing these values, and based on the sizeof(value_type), we -may create a function that returns the Max_Wastage_Percentage for us -to use. - - -- 2.7.4