Re: [boost] Proposal: Monotonic Containers

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

Due to popular demand, I introduce monotonic::chained_storage.
http://tinyurl.com/llahjq

        /// storage that spans the stack/heap boundary.
        ///
        /// allocation requests first use inline storage of N bytes.
        /// once that is exhausted, later requests are serviced from the
heap.
        ///
        /// all allocations remain valid at all times.
        template <size_t N, size_t MinLinkSize = N*1000, class Al =
std::allocator<char> >
        struct chained_storage;

I re-ran test_map_list() using

  monotonic::chained_storage<1000> storage;

rather than

  monotonic::storage<1000000> storage;

The rest of the code remained unchanged.

MSVC /O2, chained_storage<1000>
100     0.175   0.358   0.488827%
1100    2.068   4.415   0.468403%
2100    4.145   8.59    0.482538%
3100    6.604   13.08   0.504893%
4100    8.821   17.246  0.511481%
5100    11.145  22.099  0.504321%
6100    13.708  26.431  0.518633%
7100    16.97   31.065  0.546274%
8100    19.394  36.177  0.536086%
9100    21.698  40.566  0.534881%

GCC 4.33 -O4

100	0.09	0.13	0.692308%
1100	1.19	1.74	0.683908%
2100	2.45	3.69	0.663957%
3100	3.94	5.39	0.730983%
4100	5.25	7.4	0.709459%
5100	6.73	9.96	0.675703%
6100	8.64	11.68	0.739726%
7100	10.3	13.92	0.739943%
8100	11.63	16.29	0.713935%
9100	13.44	19.07	0.704772%

Point being, chained_storage<N> is the same as storage<N>. But
chained_storage<N> will only fail an allocation request after the heap is
exhausted.

chained_storage can be used as a buffer for either sequence-based or
node-based containers.

This buffer will start on the stack if you like, or via an inline buffer on
the heap. Later requests that cannot be serviced by this inline buffer will
then fall back to heap allocation, which is cached on reset().

You can use chained_storage<N> and storage<N> interchangeably.

Indeed, there is little need for storage<N> now, unless you really want to
set a fixed high-water mark on memory usage.

I havel renamed storage<N> to fixed_storage<N>, and chained_storage<N> to
storage<> with a default inline-storage size of 8k.

Regards,
Christian.