Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-15 03:55:00

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.

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

*

*