Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-17 21:06:44

Hi Luke,

People are naturally skeptical of bold claims.  Up to now you have not make
> your point in a convincing manner.

I realise I have blundered in a number of areas, but I stand by my claims.

count    mono    mono_static    std        std/mono    std/mono_static
100        0.07    0.08        0.13    185.714%    162.5%
1100    1.13    1.1            1.63    144.248%    148.182%
2100    2.3        2.29        3.36    146.087%    146.725%
3100    3.78    3.53        5.13    135.714%    145.326%
4100    4.9        4.89        7.13    145.51%        145.808%
5100    6.5        6.33        9.15    140.769%    144.55%
6100    7.91    7.79        11.79    149.052%    151.348%
7100    9.58    9.38        13.53    141.232%    144.243%
8100    11.22    11.01        16.1    143.494%    146.231%
9100    12.72    13.12        17.9    140.723%    136.433%

The test-code is here http://tinyurl.com/n59qb8. I have other tests of
course, but I stick with this one because it makes a relatively modest claim
(as opposed to say test_dupe() which shows a many-times improvement).

According to a previous post, I have also added
monotonic::shared_allocator<T>. Even though you could have used just
monotonic::allocator<T> with a monotonic::shared_storage, Steven convinced
me that it is better to be explicit about it at the allocator-level. So now
you can have general containers that use thread-safe monotonic storage
without ambguity about which allocation scheme or shared_storage to use.
It's all there in the sandbox.

// single-threaded, use static_storage
std::map<int, std::list<int, monotonic::allocator<int> >, std::less<int>,
monotonic::allocator<int> > map;

// multi-threaded, use static_shared_storage
std::map<int, std::list<int, monotonic::shared_allocator<int> >,
std::less<int>, monotonic::shared_allocator<int> > shared_map;

I've also had the presumptiveness to assume that in a vector of lists, the
lists should use the same allocator as the vector. So:

typedef std::list<int, monotonic::allocator<int> > List;
typedef std::vector<List, monotonic::allocator<List> > Vector;
Vector vector;
vector.resize(42);
assert(vector[12].get_allocator().get_storage() ==
vector.get_allocator().get_storage());

This works in the general case for all containers of containers as well, and
for shared and unshared allocation.

One outstanding issue is operator[] for std::map, which cannot be fixed. It
cannot be fixed because STL implementations do not always call
allocator.construct() after allocator.allocate().

In this case, a monotonic::map is necessary to ensure that a reference
created with operator[], if it is a monotonic container, will use the same
allocator as the parent map.

>  Don't be defensive that people are skeptical, people should be skeptical.
>  Defensiveness does not engender trust, but rather distrust.

I completely understand the scepticism, and I understand that and recognise
that I have made mistakes. But I find myself in a quandary. Do I continue to
post results and develop the idea, or just drop it in the face of people,
experience people, telling me that it "just wont work". But, well, it does
work. I have the numbers that show that it works.

In retrospect, I should have sat on my hat for a few weeks longer, decided
on the necessity of default-construction myself, created an academic-quality
paper with references, tables, comparisons, and so on. I will do so now,
retro-actively and will stop bickering.

Regards,
> Luke
>

Thanks for your comments. I will limit myself to just posting important
results as they come, and I will compare with other allocation models.

Regards,
Christian.