Proposal: bitmap_allocator.
Dhruv Matani
dhruvbird@gmx.net
Tue Mar 2 04:38:00 GMT 2004
Hello,
The bitmap Allocator that I'm proposing is optimized for Single Object
Allocation (n == 1) in the call to allocate, and would be useful for
node based containers such as list, map, multimap, set, etc...
This allocator tries to reduce the L2 cache miss rate my making sure
that consecutively allocated block are always close together, and
instantiations for different types do not share the same region of
memory. However, in the larger context, the different instantiations do
share memory, but only whole blocks and only once the Use Count for that
particular block becomes 0. This has several advantages as you might hae
noticed:
1. The cache misses are reduced greatly.
2. Since the original blocks are exponentially growing, this strategy
would mean that if some container frees and allocated nodes conatnantly,
then there is a larger probability of the smaller blocks being freed and
larger blocks taking it's place. Hence, for containers around for a
longer time, the exponentially growing lists would ease out gradually
into large chunks of linear lists each having size approximately the
same.
3. There is an internal free list store that is shared by all
instantiations, so if list<int> has given up some/all of it's memory,
then list<double> may use some or all of it depending upon some size
constraints (see function Validate_Free_List and Should_I_Give).
4. Also, the free list store concept would mean that the
bitmap_allocator would try to use as far as possible memory that it has
already acquired tather than query the OS for more memory thus
increasing the speed and reducing the external fragmentation for the
underlying operator new implementation.
Files Attached:
===============
1. bitmap_allocator.h => Stand alone bitmap_allocatr that does contain
some inline assembly and platform (x86) dependant stuff. (See macro
X86_ARCH. If not defined, it uses a software emulation for the bsf
instruction).
2. mt_bit_alloc.h => A thin pthread_mutex layer on (1).
3. allocator.cc, allocator_thread.cc => Modified test-suite files to
inclide the above 2 files where appropriate.
4. map_mt_find.cc, locality_test.cc, list_search_sort.cc => 3 new
test-suite files.
The first one IMHO should be included in the test-suite, because it
depicts a real-world app. I know of. However, the locality_test.cc is
purely synthetic (AFAICS), and list_sort_search.cc again I'm not quite
sure of but it does seem that some app. would show such behaviour
(possibly!)
5. libstdc++... => The results file for tests on my system (AMD Duron
1GHz, 640MB DDRSD RAM, GNU/Linux Red-Hat 9).
Note: The test figures for __mt_alloc might seem a bit high because it
caused swap-file usage on my system for the first 2 test-cases. I'd
rather you run it on some system with more memory and check the results.
Also, make sure that you define NDEBUG in the bitmap_allocator.h file
before running the tests. I'ts not defined by default.
--
-Dhruv Matani.
http://www.geocities.com/dhruvbird/
Proud to be a Vegetarian.
http://www.vegetarianstarterkit.com/
http://www.vegkids.com/vegkids/index.html
-------------- next part --------------
A non-text attachment was scrubbed...
Name: bitmap_allocator.h
Type: text/x-c-header
Size: 28429 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040302/2c05ed1e/attachment.bin>
-------------- next part --------------
allocator.cc iterations: 327868
type: __gnu_norm::vector<int, std::allocator<int> >
allocator.cc 283r 156u 80s 0mem 3pf
allocator.cc iterations: 327868
type: __gnu_norm::vector<int, __gnu_cxx::malloc_allocator<int> >
allocator.cc 228r 155u 73s 0mem 0pf
allocator.cc iterations: 327868
type: __gnu_norm::vector<int, __gnu_cxx::__mt_alloc<int> >
allocator.cc 228r 170u 58s 582536mem 0pf
allocator.cc iterations: 52631
type: __gnu_norm::list<int, std::allocator<int> >
allocator.cc 206r 206u 0s 0mem 0pf
allocator.cc iterations: 52631
type: __gnu_norm::list<int, __gnu_cxx::malloc_allocator<int> >
allocator.cc 198r 166u 18s 0mem 0pf
allocator.cc iterations: 52631
type: __gnu_norm::list<int, __gnu_cxx::bitmap_allocator<int> >
allocator.cc 109r 95u 14s 198536mem 0pf
allocator.cc iterations: 52631
type: __gnu_norm::list<int, __gnu_cxx::mt_bitmap_allocator<int> >
allocator.cc 204r 193u 11s 198408mem 0pf
allocator.cc iterations: 52631
type: __gnu_norm::list<int, __gnu_cxx::__mt_alloc<int> >
allocator.cc 840r 315u 36s 162561368mem 794pf
allocator_thread.cc iterations: 125000
type: __gnu_norm::vector<int, std::allocator<int> >
allocator_thread.cc 374r 0u 0s 288mem 4pf
allocator_thread.cc iterations: 125000
type: __gnu_norm::vector<int, __gnu_cxx::malloc_allocator<int> >
allocator_thread.cc 376r 0u 0s 0mem 0pf
allocator_thread.cc iterations: 125000
type: __gnu_norm::vector<int, __gnu_cxx::mt_bitmap_allocator<int> >
allocator_thread.cc 378r 0u 0s 160mem 0pf
allocator_thread.cc iterations: 125000
type: __gnu_norm::vector<int, __gnu_cxx::__mt_alloc<int> >
allocator_thread.cc 371r 0u 0s 582536mem 0pf
allocator_thread.cc iterations: 13477
type: __gnu_norm::list<int, std::allocator<int> >
allocator_thread.cc 391r 0u 0s 0mem 0pf
allocator_thread.cc iterations: 13477
type: __gnu_norm::list<int, __gnu_cxx::malloc_allocator<int> >
allocator_thread.cc 460r 0u 0s 0mem 0pf
allocator_thread.cc iterations: 13477
type: __gnu_norm::list<int, __gnu_cxx::mt_bitmap_allocator<int> >
allocator_thread.cc 390r 0u 0s 198672mem 0pf
allocator_thread.cc iterations: 13477
type: __gnu_norm::list<int, __gnu_cxx::__mt_alloc<int> >
allocator_thread.cc 1083r 0u 0s 140629240mem 2pf
map_mt_find.cc iterations: 1000000
type: __gnu_norm::map<int, std::string, std::less<int>, std::allocator<int> >
map_mt_find.cc 2129r 337u 5s 2206584mem 13pf
map_mt_find.cc iterations: 1000000
type: __gnu_norm::map<int, std::string, std::less<int>, __gnu_cxx::malloc_allocator<int> >
map_mt_find.cc 2007r 393u 4s 0mem 0pf
map_mt_find.cc iterations: 1000000
type: __gnu_norm::map<int, std::string, std::less<int>, __gnu_cxx::bitmap_allocator<int> >
map_mt_find.cc 1890r 351u 4s 196984mem 1pf
map_mt_find.cc iterations: 1000000
type: __gnu_norm::map<int, std::string, std::less<int>, __gnu_cxx::mt_bitmap_allocator<int> >
map_mt_find.cc 1892r 356u 3s 196984mem 0pf
map_mt_find.cc iterations: 1000000
type: __gnu_norm::map<int, std::string, std::less<int>, __gnu_cxx::__mt_alloc<int> >
map_mt_find.cc 2170r 434u 2s 14350920mem 0pf
list_sort_search.cc iterations: 100000
type: std::allocator<int>
list_sort_search.cc 547r 546u 0s 1664768mem 15pf
list_sort_search.cc iterations: 100000
type: __gnu_cxx::malloc_allocator<int>
list_sort_search.cc 537r 535u 1s 0mem 0pf
list_sort_search.cc iterations: 100000
type: __gnu_cxx::bitmap_allocator<int>
list_sort_search.cc 317r 317u 0s 198544mem 1pf
list_sort_search.cc iterations: 100000
type: __gnu_cxx::__mt_alloc<int>
list_sort_search.cc 609r 609u 0s 2965840mem 0pf
locality_test.cc iterations: 1000000
type: std::allocator<int>
locality_test.cc 1417r 1400u 6s 2124296mem 24pf
locality_test.cc iterations: 1000000
type: __gnu_cxx::malloc_allocator<int>
locality_test.cc 1130r 1125u 5s 0mem 0pf
locality_test.cc iterations: 1000000
type: __gnu_cxx::bitmap_allocator<int>
locality_test.cc 1023r 1018u 1s 198816mem 3pf
locality_test.cc iterations: 1000000
type: __gnu_cxx::__mt_alloc<int>
locality_test.cc 1552r 1536u 7s 49215424mem 0pf
-------------- next part --------------
A non-text attachment was scrubbed...
Name: list_sort_search.cc
Type: text/x-c++
Size: 2007 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040302/2c05ed1e/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: locality_test.cc
Type: text/x-c++
Size: 2291 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040302/2c05ed1e/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: map_mt_find.cc
Type: text/x-c++
Size: 2765 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040302/2c05ed1e/attachment-0003.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: mt_bit_alloc.h
Type: text/x-c-header
Size: 2602 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20040302/2c05ed1e/attachment-0004.bin>
More information about the Libstdc++
mailing list