Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk