Table of contents:
In most systems the default allocator used by C++ (and C) compilers is a very general memory allocator which supports allocating and freeing blocks of memory of any size. The advantage of this is that it's memory-efficient when the sizes of the allocated blocks are very varied throughout the execution of the program.
The disadvantage of this is, however, that the bookkeeping data needed by the default allocator is relatively complicated, so managing all this memory with free-sized blocks is relatively slow.
There are many situations, especially when programming in C++ using the STL data containers, where it would be enough to have an allocator for fixed-sized memory blocks. The advantage of this is that the allocator can be made considerably faster (because the bookkeeping is much simpler).
This library presents a fixed-size block allocator which can be used
with the C++ STL data containers, specifically std::list,
std::set and std::map.
The allocator works by allocating contiguous blocks of memory where the allocated elements are stored. The size of the element is determined automatically from the objects to be allocated. Basically an allocator is created for every element size that is used. (On the other hand, if two different data containers use elements of the same size, they will share the same allocator.)
The allocator is especially suited for use with std::list,
std::set and std::map. It cannot be used with
std::vector and std::deque (but on the other hand
that doesn't matter because the memory usage and speed of those containers
is already very good).
When lots of elements are continuously allocated and deallocated, the program can become considerably faster by using this allocator.
The disadvantages of using this allocator are the following:
std::vector nor std::deque). On the other
hand, this is usually not a problem.
This allocator is most efficient when large amounts of elements are
added for example to a std::list, and if large amounts of
elements are removed from the list, if they are removed in large contiguous
groups. (If a memory block allocated by this allocator gets completely free,
it will be deallocated from the main memory as well.)
To test the speed of this allocator compared to the default allocator used by the compiler, the following test was performed on a Linux system using gcc 4.1.2 on a Pentium4 3.4GHz:
A std::list<int> was used, and the following operations
where done to it:
push_back().
erase().
push_back().
erase().
push_back().
This process was repeated in a loop 10 times.
The benchmark was run for both the default allocator and the FSB
allocator. For comparison, this test was also run using
boost::fast_pool_allocator. All conditions were otherwise
exactly identical. The results were:
The same test was repeated using std::set<int>
(obviously using insert() instead of push_back()),
and the results were:
(Note that in this case there are far fewer element creations and deletions because of all the repeated values, which is the reason why the times are closer to each other.)
Using the allocator is rather simple. Simply
#include "FSBAllocator.hh" in the source files where
the allocator is used, and then simply give the allocator to the desired
STL container as template parameter. For example, instead of writing this:
std::list<int> aList;
write this:
std::list<int, FSBAllocator<int> > aList;
That's it. No other modifications are needed.
The same for std::set would be:
std::set<int, std::less<int>, FSBAllocator<int> > aSet;
If you want to use the allocator directly, as a replacement of
new and delete, it can be done like this:
FSBAllocator<YourType> alloc;
YourType* anInstance = alloc.allocate(1);
// alloc.construct(anInstance, YourType()); // if YourType is a class
...
// alloc.destroy(anInstance); // if YourType is a class
alloc.deallocate(anInstance, 1);
Note that allocate() only allocates memory for the object
but doesn't initialize it in any way (similarly to how, for example,
std::malloc() would do). If your type is a class, you'll have
to initialize and destroy it yourself as demonstrated in the commented
lines or by using placement new directly after allocating and by
calling its destructor explicitly before deallocating.
(Also note that, as stated earlier, arrays cannot be allocated with this allocator, and thus the only valid parameter value is 1.)
By default this library is not thread-safe, and thus cannot be used as an allocator for multiple threads. (As long as only one thread uses this allocator and the memory allocated by it, it should be ok.)
If you are using the gcc compiler, however, you can make the library to
use thread-safe locking, which will make the library completely thread-safe.
Note that this uses the __sync_bool_compare_and_swap() extension
of gcc and thus will work only if your version of gcc supports it.
In order to enable this, define the precompiler constant
FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC either in your compiler
settings or before including this library, like this:
#define FSBALLOCATOR_USE_THREAD_SAFE_LOCKING_GCC #include "FSBAllocator.hh"
Note that enabling thread-safe locking will make the library somewhat slower (in my computer it slows it down by approximately 70%). It will still be much faster than the default libc allocator, though.
Other locking mechanisms might be added in the future.
(Note that due to the nature of multithreaded programming, testing the correctness of the used solution is very difficult, so I cannot guarantee its correctness, but I am pretty confident it is, due to its simplicity.)
This library is released under the MIT license.
Copyright (c) 2008 Juha Nieminen
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.