Re: [boost] Proposal: Monotonic Containers

Subject: Re: [boost] Proposal: Monotonic Containers
From: Christian Schladetsch (christian.schladetsch_at_[hidden])
Date: 2009-06-12 02:40:24

Hi Ross,

I am in the process of updating the sandbox, but in the meantime:

#include <boost/timer.hpp>
#include <boost/monotonic/vector.h>
#include <iostream>

namespace
{
    template<typename C>
    struct Foo
    {
        long ord;
        C c;
    };

    const int LOOP_COUNT = 100000000;
    const int ELEM_COUNT = 1000;

    template<typename C>
    void test_loop_monotonic()
    {
        boost::monotonic::inline_storage<100000> storage;
        boost::monotonic::vector<Foo<C> > vec(storage);
        Foo<C> orig = { 'A', 65 };
        vec.assign(ELEM_COUNT, orig);
        boost::timer timer;
        for (int i = 0; i < LOOP_COUNT; ++i)
            ++vec[1 + i % (ELEM_COUNT - 2)].ord;
        double elapsed = timer.elapsed();
        std::cout << "Incrementing ord = " << 1000000000*elapsed/LOOP_COUNT
<< " ps per iteration" << std::endl;
    }

    template <class C>
    void test_loop_std()
    {
        Foo<C> orig = { 'A', 65 };
        std::vector<Foo<C> > vec;
        vec.assign(ELEM_COUNT, orig);
        boost::timer timer;
        for (int i = 0; i < LOOP_COUNT; ++i)
            ++vec[1 + i % (ELEM_COUNT - 2)].ord;
        double elapsed = timer.elapsed();
        std::cout << "STD: Incrementing ord = " <<
1000000000*elapsed/LOOP_COUNT << " ps per iteration" << std::endl;
    }

} // namespace

void test_alignment()
{
    test_loop_monotonic<char>();
    test_loop_monotonic<long>();

    test_loop_std<char>();
    test_loop_std<short>();
}

//EOF

Incrementing ord = 2.88 ps per iteration
Incrementing ord = 2.87 ps per iteration
STD: Incrementing ord = 3.11 ps per iteration
STD: Incrementing ord = 3.12 ps per iteration

Regards,
Christian.

On Fri, Jun 12, 2009 at 6:28 PM, Ross Levine <ross.levine_at_[hidden]> wrote:

> Can you post the full source for the test?
>
> Ross
>
> On Fri, Jun 12, 2009 at 2:10 AM, Christian Schladetsch <
> christian.schladetsch_at_[hidden]> wrote:
>
> > Hi David,
> >
> > Thanks for helping to bring the problem of alignment to my (admittedly
> > somewhat dim at times) attention.
> >
> > I have changed inline_storage.h:
> >
> >            /// allocate storage. ignore hint.
> >            void *allocate(size_t num_bytes, void const * = 0)
> >            {
> >                // ensure we return a pointer on an aligned boundary
> >                size_t extra = num_bytes & 15; // todo: policy-based on
> the
> > alignment is overkill?
> >                size_t required = num_bytes + extra;
> >                char *ptr = &buffer[cursor];
> >                cursor += required;
> >                return ptr + extra;
> >            }
> >
> > Then I re-ran your test. I also added another test, which does exactly
> the
> > same thing, but using std::vector, rather than monotonic::vector:
> >
> > Incrementing ord = 2.89 ps per iteration
> > Incrementing ord = 2.86 ps per iteration
> > STD: Incrementing ord = 3.1 ps per iteration
> > STD: Incrementing ord = 3.1 ps per iteration
> >
> > My other tests dont change much:
> > monotonic: 0.001
> > std: 0.016
> > monotonic: 0.01
> > std: 0.95
> >
> > I am using VS2008, full optimisation.
> >
> > Note that your test case is ~8% faster when implemented using
> > monotonic::vector over using std::vector. This is because the monotonic
> > vector is using the stack for storage, where the loop controls and other
> > fields are also.
> >
> > I will upload the change to boost/monotonic/inline_storage.h within
> hours,
> > with this and more tests.
> >
> > Regards and Thanks,
> > Christian.
> >
> > On Fri, Jun 12, 2009 at 4:58 PM, David Bergman <
> > David.Bergman_at_[hidden]> wrote:
> >
> > >
> > > On Jun 11, 2009, at 8:26 PM, Christian Schladetsch wrote:
> > >
> > >  Hi Luke,
> > >>
> > >> Please compare performance of your container to std containers with a
> > good
> > >>
> > >>> memory pooling allocator and include system settings with your
> > benchmarks
> > >>> so
> > >>> that we know what you are measuring.  Your benchmarks mean nothing to
> > me
> > >>> because I don't know what allocator you are comparing to, but suspect
> > you
> > >>> are comparing to the system allocator, which is clearly a straw man
> > >>> argument.
> > >>>
> > >>
> > >>
> > >> I am directly comparing monotonic::allocator to std::allocator, so
> there
> > >> is
> > >> no straw-man.
> > >>
> > >> I agree that eventually I'll have to compare against as many other
> > >> possible
> > >> arrangements as possible, stopping when any of them fails to provide a
> > >> performance benefit for the proposed system.
> > >>
> > >> The benchmarks I posted, while hardly exhaustive, do indeed show a
> > >> performance increase of 10-100x over the standard schemes. At least
> this
> > >> was
> > >> a proof-of-concept over and above my hand-waving.
> > >>
> > >> I showed this for both stack- and heap-based storage, for the same
> > >> algorithm
> > >> implemented using the same containers, which no other changes or
> custom
> > >> data-structures.
> > >>
> > >
> > > NOTE: I do get that preserving space - on stack or heap - is better
> than
> > > incremental allocations (or reallocations.), and your "monotonic"
> > allocator
> > > could definitely be a good one if one is willing to bet on a fairly
> small
> > > maximum size.
> > >
> > > But. if we skip this reserve+monotonic vs unreserved+standard
> comparison:
> > >
> > > What we have then is for your allocator simply creates crashing code
> for
> > a
> > > lot of structures or classes on certain platforms, whereas it yields
> > worse
> > > performance (for my simple examples of misaligned structures, I got
> > between
> > > 10% and 20% slower) for the lenient (in this aspect...) Intel processor
> > > family.
> > >
> > > /David
> > >
> > >  I agree that more testing should be done, and I'll do so with a better
> > >> system analysis. I'll post more results and an updated library with
> full
> > >> constructor forwarding and alignment. It may well be that a more
> > extensive
> > >> performance analysis shows that my proposed allocator is a wash.
> > >>
> > >> Regards,
> > >>
> > >>> Luke
> > >>>
> > >>
> > >>
> > >> Cheers,
> > >> Christian.
> > >> _______________________________________________
> > >> Unsubscribe & other changes:
> > >> http://lists.boost.org/mailman/listinfo.cgi/boost
> > >>
> > >
> > > _______________________________________________
> > > Unsubscribe & other changes:
> > > http://lists.boost.org/mailman/listinfo.cgi/boost
> > >
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> >
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>