This is the mail archive of the mailing list for the libstdc++ project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Rewriting bitmap_allocator


I've (slowly) been working on an implementation as described in the
pdf, and here is the first working version:

The running time & memory usage for the test (test.cpp) is lesser than
that of std::allocator, so that's promising.

The numbers aren't hugely different, but they are different none the less.

std::allocator memory: 160MiB
bitmap_allocator memory: 134MiB

std::allocator run-time: 16.7sec
bitmap_allocator run-time: 13.7sec

The actual storage occupied by the std::list<int> for (1<<23) integers is 96MiB.
There is another vector<int> which stores (1<<23) integers, which
occupies 32MiB.

The code for this allocator is much smaller, and imho more readable,
and it also gets rid of some of the mini vector badness from before.

Looking forward to comments.


On Mon, Jun 25, 2012 at 3:45 PM, Benjamin De Kosnik <> wrote:
>> With increasing memory sizes, and increasing difference between the
>> size of CPU caches and main memory, improving locality and reducing
>> the per-object allocation overhead seems to have become an important
>> idea. The current bitmap_allocator has been crashing on me (even
>> though it provides excellent cache locality).
> Maybe step one is to add a test that crashes on you when you
> use it.
>> With that in mind, I would like to propose a re-write of the
>> bitmap_allocator<> now that I have a better idea of how it can be
>> implemented. I would be happy to present a proposal for the same (with
>> details) if it is a thing of interest.
> Please. Bonus if you can figure out a way to remove __mini_vector or
> scope it such that it is clearly and implementation detail.
> -benjamin

   -Dhruv Matani.

"What's the simplest thing that could possibly work?"
-- Ward Cunningham

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]