Re: [boost] Proposal: Monotonic Containers: Performance test
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(); 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; for (size_t i = 0; i < count; ++i) { int random = rand(); 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.005 std: 0.09
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
Another test, this time using a larger storage on the heap: void test_speed_heap() { typedef monotonic::map<int, monotonic::list<int> > map_with_list; monotonic::inline_storage<10000000> *storage = new monotonic::inline_storage<10000000>; map_with_list m(*storage); size_t count = 100000; 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; delete storage; // 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.011 std: 1.130
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
2009/6/10 Christian Schladetsch <christian.schladetsch@gmail.com>:
monotonic: 0.005 std: 0.09
How about intrusive? I had to up the count to 0x101010 to get a measurable value, which gave the following timings (three runs, reported in order): mono: 1.37/1.41/1.38 std: 1.51/1.51/1.51 intrusive: 1.34/1.33/1.33 Upping it to 0x1010101 gave this: mono: 35.82/35.71/35.82 std: 37.94/37.83/37.81 intrusive: 36.17/35.78/35.62 GCC 4.3.3 with -O3, 32-bit linux on Core2. Here's the intrusive code: struct mylistnode : list_base_hook<link_mode<normal_link> > { int i; }; struct mymapnode : set_base_hook<link_mode<normal_link> > { list<mylistnode> v; int k; }; bool operator<(mymapnode const &lhs, mymapnode const &rhs) { return lhs.k < rhs.k; } union node { void *_; char mapnode[sizeof(mymapnode)]; char listnode[sizeof(mylistnode)]; }; int main() { unsigned const count = 0x101010;//101; // node nodes[count]; node *nodes = new node[count]; set<mymapnode> m; boost::timer timer; for (size_t i = 0; i < count; ++i) { int random = rand(); mymapnode &mapnode = *(new(nodes[i].mapnode) mymapnode); mapnode.k = random; set<mymapnode>::iterator iter = m.find(mapnode); if (iter == m.end()) { m.insert(mapnode); } else { mapnode.~mymapnode(); mylistnode &listnode = *(new(nodes[i].listnode) mylistnode); iter->v.push_back(listnode); } } double elapsed = timer.elapsed(); cout << "intrusive: " << elapsed << endl; }
Scott McMurray-2 wrote:
2009/6/10 Christian Schladetsch <christian.schladetsch@gmail.com>:
monotonic: 0.005 std: 0.09
How about intrusive? I had to up the count to 0x101010 to get a measurable value, which gave the following timings (three runs, reported in order):
mono: 1.37/1.41/1.38 std: 1.51/1.51/1.51 intrusive: 1.34/1.33/1.33
Upping it to 0x1010101 gave this:
mono: 35.82/35.71/35.82 std: 37.94/37.83/37.81 intrusive: 36.17/35.78/35.62
GCC 4.3.3 with -O3, 32-bit linux on Core2.
Hi, As you code shows there is essential difference between the intrusive and the monotonic code. In the case of monotonic the destruction and not the deallocation is called implicitly while in the case of intrusive, it is up to the user to call the destruction of the removed element explicitly. I'm curious to know why the measures are so different concerning the std part. Best, Vicente -- View this message in context: http://www.nabble.com/Re%3A-Proposal%3A-Monotonic-Containers%3A-Performance-... Sent from the Boost - Dev mailing list archive at Nabble.com.
participants (4)
-
Christian Schladetsch -
David Bergman -
Scott McMurray -
Vicente Botet Escriba