Re: [boost] Proposal: Monotonic Containers: Performance test

Subject: Re: [boost] Proposal: Monotonic Containers: Performance test
From: David Bergman (David.Bergman_at_[hidden])
Date: 2009-06-11 00:28:34

Of course. I reserved the space for the std::vector, just as I would  
with monotonic::vector.

We all understand the cost of pre-allocating instead of re-allocating  
on the fly. The question is, how much can we gain with  
monotonic::vector (and its related containers) compared to a reserved  
std::vector? E.g., how much would the locality of reference between  
two containers give us (in cache hit increase)?

/David

On Jun 10, 2009, at 11:27 PM, Christian Schladetsch wrote:

> You will note that I made a mistake, and used the same timer for  
> both. This
> gave an incorrect result, as the std:: timer included the time for  
> the first
> test. Even so, it was 9x faster rather than 10x faster.
>
> Another test, this time with more list insertions:
>
> void test_speed()
> {
>    typedef monotonic::map<int, monotonic::list<int> > map_with_list;
>    monotonic::inline_storage<1000000> storage;
>    map_with_list m(storage);
>    size_t count = 10000;
>    boost::timer timer;
>    for (size_t i = 0; i < count; ++i)
>    {
>        int random = rand() % 100;
>        map_with_list::iterator iter = m.find(random);
>        if (iter == m.end())
>            m.insert(make_pair(random, monotonic::list<int>(storage)));
>        else
>            iter->second.push_back(i);
>    }
>    double elapsed = timer.elapsed();
>    cout << "monotonic: " << elapsed << endl;
>
>    // do the same thing, with std::containers
>    {
>        typedef std::map<int, std::list<int> > map_with_list;
>        map_with_list m;
>        boost::timer timer;
>        for (size_t i = 0; i < count; ++i)
>        {
>            int random = rand() % 100;
>            map_with_list::iterator iter = m.find(random);
>            if (iter == m.end())
>                m[random] = std::list<int>();
>            else
>                iter->second.push_back(i);
>        }
>        double elapsed = timer.elapsed();
>        cout << "std: " << elapsed << endl;
>    }
> }
>
> monotonic: 0.001
> std: 0.017
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost