Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christopher Jefferson (chris_at_[hidden])
Date: 2009-06-15 04:03:19

On 15 Jun 2009, at 08:55, Christian Schladetsch wrote:

> On Mon, Jun 15, 2009 at 11:37 AM, David Bergman <
> David.Bergman_at_[hidden]> wrote:
>
>> [snip]
>> Why do I carry these feeling that all samples we will see here have
>> monotonic (roped or not...) as the winner? ;-)
>
>
> I wrote a bubble-sort to compare the speed of monotonic structures  
> produced
> on the stack, versus standard structures built on the heap.
>
> The idea was to test my theoretical claim regarding list-node sizes  
> and
> spatial locality on the stack outlined a few posts ago.

I think you are over-stating the importance of the stack. I just ran  
your experiments with a heap-allocated inline_storage and got very  
similar results.
>
> The test code is here http://tinyurl.com/m77bzh.
>
> Results for VS2008, /O2
>
> size     mono     std    mono/std
> 3       0.001   0.008   0.12
> 13      0.027   0.047   0.57
> 23      0.085   0.119   0.71
> 33      0.179   0.23    0.77
> 43      0.305   0.377   0.80
> 53      0.472   0.552   0.85
> 63      0.655   0.759   0.86
> 73      0.883   1.009   0.87
> 83      1.14    1.295   0.88
> 93      1.444   1.639   0.88
>
> Results for GCC 4.3.3, -O4
>
> 3	0	0	nan%
> 13	0.01	0.02	0.5%
> 23	0.02	0.03	0.666667%
> 33	0.04	0.05	0.8%
> 43	0.05	0.08	0.625%
> 53	0.06	0.09	0.666667%
> 63	0.11	0.13	0.846154%
> 73	0.14	0.2	0.7%
> 83	0.15	0.22	0.681818%
> 93	0.22	0.27	0.814815%
>
> Times are in microseconds.
>
> It is worth noting that there is no list manipulation in this test.  
> There is
> only list creation, forward iteration, and destruction.
>
> Cheers,
> Christian
>
>
>
> *
>
> *
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost