This is the mail archive of the
mailing list for the libstdc++ project.
Re: Rewriting bitmap_allocator
- From: Dhruv Matani <dhruvbird at gmail dot com>
- To: Benjamin De Kosnik <bkoz at redhat dot com>
- Cc: "libstdc++" <libstdc++ at gcc dot gnu dot org>
- Date: Tue, 24 Jul 2012 23:48:58 -0700
- Subject: Re: Rewriting bitmap_allocator
- References: <CAOG+gn2uvg-tfhj8rbo9dP1TY_iOTKXN7fyYdLj_YiR=2HWzDg@mail.gmail.com> <20120625154511.2da206f7@adair>
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
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 <email@example.com> 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.
"What's the simplest thing that could possibly work?"
-- Ward Cunningham