KnockKnock - Some Stuff
A Technique For Creating An Adaptable Array 18/11/2005
This is being placed in the public domain. It is nothing particularly revolutionary and the code I have attached in not very good (it is only there to illustrate the point).
There is a reason WHY I am putting this in the public domain (it's not because I have nothing better to do - Far from it).
One final thing: This work is based on a combination of other publicly available data and other bits that I've come up with myself; most of which from many years ago. If you want to use anything contained in this then feel free - it's in the public domain.
Some code (this compiles ok with gcc):
std.h
UseBitmap.cpp
UseBitmap.h
ManagedArray.cpp
ManagedArray.h
The two C++ classes presented here provide the following functionality:
- UseBitmap - This maintains a bitmap constructed from a series of 32 bit words. It provides facilities for searching for a free bit in the map and for allocating / de-allocating a bit. The implementation is not very good, but will do to demonstrate the principles we're talking about. This technique is trivial and well known.
- ManagedArray - This class creates an array of user-specified size. It then allows the user to allocate elements within this array; the address of the element being returned on successful allocation. This class makes use of the UseBitmap array to keep track of which elements have been allocated (but, of course it could use some other technique). The user may release a previously allocated array element by supplying its address to the 'free' function. The class will then work out where the element was allocated from and de-allocate it (adjusting the UseBitmap data accordingly). One feature of the ManagedArray class is that the array will self-expand when it becomes full (this is an option when the array is created). The array is expanded by simply creating a new array and linking it to the original one in a linked list fashion (though some other technique could be used; a simple array of ManagedArray classes for example). This is rather crude but it has the desired affect; that of providing transparent (to the user) expansion of the array. Allocations that can not be realised by the array (owing to lack of space) shall be passed on to the next linked array. If no such linked array exists (and if the appropriate option is provided at initialisation) then another array shall be created an liked to from the original array. The technique of using a bitmap to control and keep track of allocations in an array (or indeed many other kinds of structure) is trivial and well known. The same goes goes for using a linked list to dynamically expand storage requirements. Combining the two concepts is obvious and trivial.
--------------------
The techniques demonstrated by the two classes are very simple. The implementation is (admittedly) rather poor, but that doesn't matter for illustrating the concept.
Features of this construction that are worth noting:
- Because this is an array, each element of the array has a finite length. This length is fixed at initialisation, and although a length is specified when an element is allocated, this is only so that a check can be made to ensure that the user is not intending on using an amount of space larger than is provided by the single element. There is nothing novel about this idea.
- Ignoring the poor implementation, this is a very good way of dealing with large numbers of fixed size objects WITHOUT causing memory fragmentation within the underlying (OS) memory allocation mechanism (which may be the case using malloc of other heap-based allocation methods). Indeed this technique (in a more refined form, and probably not written in C++ as this example code is) could be used to provide a heap allocation mechanism with the caveat that it would not be at all suitable for allocating very large blocks of memory or memory allocation with very wide ranging size requirements.
- A separate managed array is needed for each size of element. This is obvious because an array is (usually) by definition composed of fixed sized elements. Of course, this need not be the case; with some more work, the array could probably deal with multiple sizes of array elements, though each array of a specific size would need to be stored separately to avoid fragmentation. See also below for how multiple sized array elements can be dealt with.
- An allocation will only return one element at a time. ie - if a memory allocation request is made that would require two array elements to fulfil, then the request will fail. This restriction is important. Allowing requests to span multiple elements will cause fragmentation (thus wrecking one of the main reasons for using this technique in the first place), and it would also make the system more complex (the latter obviously not being insurmountable).
Possible refinements:
- Make the code better, generally!
- The use of C++ is not at all ideal for demonstrating this. The main reason being that there are four separate memory allocations taking place; one for the ManagedArray object, one for the bitmap object, one for the ManagedArray array, and one for the bitmap array. Ideally (actually, DEFINITELY!) in a real-world environment, this would be all contained within a single memory allocation. As it stands, the C++ implementation is not optimal because of its intrinsicly poor memory allocation. Having said this, this probably wouldn't matter if there was no intention of de-allocating arrays.
- For very large arrays (with many elements) then some refinement of the bitmap would be useful; a hierarchical arrangement being (possibly) the most efficient in (time). For example, for each 32 words (assuming a 32 bit architecture), an extra word could be allocated. This extra word would have allocated one bit for each word of the block of 32 (the bit being set if the entire 32 bits of the word it is related to is fully populated (all bits set)). This makes searching the block of 32 words potentially much faster by first searching the extra word first and based on that, a direct reference to one of the words from the block can be examined to locate a free bit, and hence a free array element). The construction of a multi-layered allocation control model like this is, of course, obvious and indeed a much more sophisticated method is used by some processors to provide virtual memory management.
- The example code makes no attempt to clean up empty arrays if they are allocated and then either never used or used and then emptied again. This is an almost trivial addition that could be made to the basic array mechanism, and would probably be required for any real world implementation.
- In order to save space initially, there is no reason why the raw array (defined within the ManagedArray class) needs to be created immediately. It could be created on demand (on the first allocation request). Allocation-on-demand is a well known technique and obvious.
- An extra parameter or two to the initialisation would allow the linked arrays to be a different size from the originally created array. An example of how this could be used would be to (say) create an initial array of X elements and then any overspill could be allocated in (probably) smaller chunks. An alternative would be to make the initial array zero length and the linked arrays a fixed length (see later for why this may be useful). This is a well known technique used in database implementations (well, the ones I have written, anyway!)
- In order to obviate the need to pass in the ManagedArray object when an element is de-allocated then a reference to the allocating object could be appended to the start of each array element (the address being passed back to the user pointing to the byte just after this pointer). This is a classic technique used by malloc/free et-al so is nothing original.
- There is nothing to stop ManagedArray objects (including the bitmap data and the raw array that are contained within the object) from being allocated from a (parent) ManagedArray (rather than by using 'new' as per this example code). This could be done by overloading 'new' or by simply providing the parent ManagedArray to the sibling ManagedArray at initialisation (so that the sibling then has a reference to the parent and so knows what to do when it needs to allocate new linked arrays). One advantage of this arrangement can be seen as follows:
* Imagine a ManagedArray consisting of N number of (large) elements. By 'large' we mean (say) a kilobyte or more. We'll call this a 'parent' array.
* When a sibling array is instantiated, it could be allocated from one of these large slots on the parent array. Any linked arrays would also be allocated from within the parent array. At first, there appears to be no advantage in doing this over (say) allocating each array using malloc. The technique comes into its own though when arrays are deleted (because they are empty). Because they are allocated from a parent array, they can be de-allocated without risk of causing any kind of memory fragmentation. Another advantage is that if we need arrays of different sized elements then they could all in fact be allocated from the same parent array (the sub-arrays with the large element size obviously able to contain fewer elements, but that's not really a problem because new arrays are just created on the fly anyway). In this way, the parent array acts as a shared memory resource that can be freely allocated from and released to by multiple sub-arrays without any fragmentation occurring (no fragmentation because all parent array elements are the same size and only one is allocated on each allocation request).
The concept of objects being contained within objects of the same type is a classic (indeed fundamental) OO technique and is nothing original.
* As an aside, there is no reason why the first ManagedArray object should be allocated from the same memory area as the linked ones. ie - the first one could be allocate using (normal) malloc with only the linked arrays being allocated from a parent array. This might give the best of both worlds because it allows the initial array to be very large (for example) with more modestly sized additional array being allocated from the parent array. As previously stated, this technique is used in database implementations.
- One last option is as follows. If a user wishes to create objects of many different sizes then it would be very inconvenient to have to specifically select a ManagedArray that supports a particular element size each time a memory allocation was required. To get round this, a special kind of array can be created. This special array is not really an array at all (in that it itself does not support allocating / de-allocating elements). What it does do is contain references to multiple ManagedArray objects, each one, typically, supporting a different element size. When the user allocates an element from a special array, the special array just looks up the most appropriate 'real' array to allocate from (usually the one with the smallest usable element size), and passes the request on to that. This is totally transparent to the user, and provides (almost) arbitrary allocation sizes while only having to deal with a single array object (the special one). Freeing from such an array would be performed in the same way (or, if a ref. was made back to the allocating ManagedArray object in each array element (see above), a much faster de-allocation could be performed because the special array would not have to search for the array from which the element was originally allocated from). The idea of abstracting a mechanism like this is nothing new. Indeed, it is obvious.