Re: Rewriting bitmap_allocator

[Dhruv Matani <dhruvbird at gmail dot com>]

Hello Jonathan,

On Thu, Jul 26, 2012 at 2:10 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
>
> There's no need to check anything else.  If bitmap_allocator is
> supposed to be a drop-in replacement for std::allocator then it needs
> to be stateless, and the default behaviour provided by
> allocator_traits is correct for that case, except that it should
> define propagate_on_container_move_assignment to true, see
> http://cplusplus.github.com/LWG/lwg-active.html#2103

I've added this - std::true_type from the link mentioned above.

>
>> (which happens to be
>> available only post 4.6.2) right?
>
> 4.7.0 onwards, but I would expect any changes to bitmap_allocator to
> only be done on trunk (4.8) anyway.

Makes sense.

I've tested this with valgrind, and it seems to be working okay. Made
some more changes to make the cost of allocation/deallocation O(1) on
the average - the trick is somewhat similar to the one used in the
argument used to show that traversing a std::map<> is O(n).

I'm happier with this implementation even though it is a tad slower
than the older one (see the link below) simply because it's much
smaller in size and is easier to explain.

Here are some numbers for the tests included in test.cpp:
https://docs.google.com/spreadsheet/ccc?key=0Ajb-gKl_fNOldC03M29FUk1Tc0RZbzBWTVkyRzJTR0E

The only thing that I am not able to figure out is why new_allocator
is causing dramatically fewer minor page faults compared to the older
bitmap_allocator in the test that uses std::list<> even though their
RSS is comparable. Any idea on that? I don't have VSZ numbers - that
may explain it.

Current list of todos:
* Add mutexes
* Handle the case when deallocate(NULL, 1) is passed in
* Some fixes that involve using size_type instead of size_t - is this required?

Do let me know if there's any other corner case that you are aware of.

Regards,
-Dhruv.


-- 
   -Dhruv Matani.
http://dhruvbird.com/

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