Subject: [Boost-commit] svn:boost r54227 - in sandbox/monotonic/libs/monotonic/test: . results
From: christian.schladetsch_at_[hidden]
Date: 2009-06-22 16:24:29
Author: cschladetsch
Date: 2009-06-22 16:24:28 EDT (Mon, 22 Jun 2009)
New Revision: 54227
URL: http://svn.boost.org/trac/boost/changeset/54227
Log:
added test_map_erase
Added:
sandbox/monotonic/libs/monotonic/test/results/test_map_erase.txt (contents, props changed)
Text files modified:
sandbox/monotonic/libs/monotonic/test/Tests.h | 71 +++++++++---
sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp | 211 ++++++++++++++++++++++-----------------
sandbox/monotonic/libs/monotonic/test/monotonic.vcproj | 4
3 files changed, 174 insertions(+), 112 deletions(-)
Modified: sandbox/monotonic/libs/monotonic/test/Tests.h
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/Tests.h (original)
+++ sandbox/monotonic/libs/monotonic/test/Tests.h 2009-06-22 16:24:28 EDT (Mon, 22 Jun 2009)
@@ -8,6 +8,10 @@
#pragma once
+// these are guaranteed to be at least length + length*length long
+extern std::vector<int> random_numbers;
+extern std::vector<std::pair<int, int> > random_pairs;
+
struct test_vector_create
{
template <class Alloc>
@@ -21,10 +25,10 @@
struct test_vector_dupe
{
template <class Alloc>
- int test(Alloc alloc, size_t count) const
+ int test(Alloc alloc, size_t length) const
{
typedef std::vector<int, typename Rebind<Alloc, int>::type> Vector;
- Vector vector(count*rand()/RAND_MAX);
+ Vector vector(length*rand()/RAND_MAX);
Vector dupe = vector;
return dupe.size();
}
@@ -34,11 +38,11 @@
struct test_vector_sort
{
template <class Alloc>
- int test(Alloc, size_t count) const
+ int test(Alloc, size_t length) const
{
- std::vector<Ty, typename Rebind<Alloc, Ty>::type> vector(count);
- for (size_t n = 0; n < count; ++n)
- vector[n] = count - n;
+ std::vector<Ty, typename Rebind<Alloc, Ty>::type> vector(length);
+ for (size_t n = 0; n < length; ++n)
+ vector[n] = length - n;
sort(vector.begin(), vector.end());
return 0;
}
@@ -73,10 +77,10 @@
struct test_list_create
{
template <class Alloc>
- int test(Alloc alloc, size_t count) const
+ int test(Alloc alloc, size_t length) const
{
std::list<Ty, typename Rebind<Alloc, Ty>::type> list;
- fill_n(back_inserter(list), count, 42);
+ fill_n(back_inserter(list), length, 42);
return 0;
}
};
@@ -84,11 +88,11 @@
struct test_list_dupe
{
template <class Alloc>
- int test(Alloc alloc, size_t count) const
+ int test(Alloc alloc, size_t length) const
{
typedef std::list<int, typename Rebind<Alloc, int>::type> List;
List list;
- fill_n(back_inserter(list), count, 42);
+ fill_n(back_inserter(list), length, 42);
List dupe = list;
return dupe.size();
}
@@ -98,11 +102,11 @@
struct test_list_sort
{
template <class Alloc>
- int test(Alloc alloc, size_t count) const
+ int test(Alloc alloc, size_t length) const
{
std::list<Ty, typename Rebind<Alloc, Ty>::type> list;
- for (size_t n = 0; n < count; ++n)
- list.push_back(count - n);
+ for (size_t n = 0; n < length; ++n)
+ list.push_back(length - n);
list.sort();
return 0;
}
@@ -111,17 +115,17 @@
struct test_set_vector
{
template <class Alloc>
- int test(Alloc alloc, size_t count) const
+ int test(Alloc alloc, size_t length) const
{
typedef std::vector<int, typename Rebind<Alloc, int>::type> Vector;
typedef std::set<Vector, std::less<Vector>, typename Rebind<Alloc, Vector>::type> Set;
int dummy = 0;
Set set;
- for (size_t n = 0; n < count; ++n)
+ for (size_t n = 0; n < length; ++n)
{
- size_t size = count*rand()/RAND_MAX;
+ size_t size = length*rand()/RAND_MAX;
Vector vector(size);
- generate_n(vector.begin(), size, rand);
+ generate_n(back_inserter(vector), size, rand);
set.insert(vector);
dummy += set.size();
}
@@ -138,7 +142,7 @@
mod = 5;
for (size_t n = 0; n < length; ++n)
{
- int random = rand() % mod;
+ int random = random_numbers[n] % mod;
map[random].push_back(n);
}
return 0;
@@ -170,11 +174,40 @@
size_t mod = length/10;
for (size_t n = 0; n < length; ++n)
{
- int random = rand() % mod;
+ int random = random_numbers[n] % mod;
map[random].push_back(n);
}
return 0;
}
};
+//Build a std::map of size n. Loop for O(n^2) iterations.
+//In each iteration insert one random element and lookup with lower_bound one random element and remove it.
+//Precompute the random numbers and don't include the rand() calls in the time measurement of the benchmark.
+
+struct test_map_erase
+{
+ template <class Alloc>
+ int test(Alloc alloc, size_t length) const
+ {
+ typedef std::map<int
+ , int
+ , std::less<int>
+ , typename Rebind<Alloc, int>::type
+ > Map;
+ Map map;
+ std::copy(random_pairs.begin(), random_pairs.begin() + length, inserter(map, map.begin()));
+ size_t max_length = length*length;
+ for (size_t n = 0; n < max_length; ++n)
+ {
+ map.insert(random_pairs[length + n]);
+ int random_remove = random_numbers[n];
+ Map::iterator iter = map.lower_bound(random_remove);
+ if (iter != map.end())
+ map.erase(iter);
+ }
+ return 0;
+ }
+};
+
//EOF
Modified: sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp (original)
+++ sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp 2009-06-22 16:24:28 EDT (Mon, 22 Jun 2009)
@@ -128,14 +128,29 @@
return result;
}
+// these are guaranteed to be at least length + length*length long
+std::vector<int> random_numbers;
+std::vector<std::pair<int, int> > random_pairs;
+
+std::pair<int, int> random_pair()
+{
+ return make_pair(rand(), rand());
+}
+
template <class Fun>
PoolResults run_tests(size_t count, size_t max_length, size_t num_iterations, const char *title, Fun fun, Type types = Type::All)
{
boost::timer timer;
cout << title << ": reps=" << count << ", len=" << max_length << ", steps=" << num_iterations;
PoolResults results;
+ srand(42);
for (size_t length = 1; length < max_length; length += max_length/num_iterations)
{
+ size_t required = length + length*length;
+ if (random_numbers.size() < required)
+ generate_n(back_inserter(random_numbers), required - random_numbers.size(), rand);
+ if (random_pairs.size() < required)
+ generate_n(back_inserter(random_pairs), required - random_pairs.size(), random_pair);
results[length] = run_test(count, length, fun, types);
}
cout << endl << "took " << timer.elapsed() << "s" << endl;
@@ -317,110 +332,120 @@
int main()
{
- cout << "results of running test at:" << endl;
- cout << "https://svn.boost.org/svn/boost/sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp" << endl << endl;
+ try
+ {
+ cout << "results of running test at:" << endl;
+ cout << "https://svn.boost.org/svn/boost/sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp" << endl << endl;
- boost::timer timer;
- Type test_map_vector_types;
- Type test_dupe_list_types;
+ test_pools();
- bool run_small = 1;//true;
- bool run_medium = 1;//true;
- bool run_large = 1;//true;
+ boost::timer timer;
+ Type test_map_vector_types;
+ Type test_dupe_list_types;
- test_pools();
+ bool run_small = 1;//true;
+ bool run_medium = 1;//true;
+ bool run_large = 1;//true;
- // small-size (~100 elements) containers
- if (run_small)
- {
- heading("SMALL");
-#ifndef WIN32
- print(run_tests(75000, 100, 10, "list_create<int>", test_list_create<int>()));
- print(run_tests(75000, 100, 10, "list_sort<int>", test_list_sort<int>()));
- print(run_tests(2000000, 100, 10, "vector_create<int>", test_vector_create()));
- print(run_tests(200000, 100, 10, "vector_sort<int>", test_vector_sort<int>()));
- print(run_tests(1000000, 100, 10, "vector_dupe", test_vector_dupe()));
- print(run_tests(50000, 100, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
- print(run_tests(500000, 100, 10, "vector_accumulate", test_vector_accumulate()));
- print(run_tests(10000, 100, 10, "set_vector", test_set_vector()));
- print(run_tests(2000, 100, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
-#else
- print(run_tests(50000, 100, 10, "list_create<int>", test_list_create<int>()));
- print(run_tests(5000, 100, 10, "list_sort<int>", test_list_sort<int>()));
- print(run_tests(2000000, 100, 10, "vector_create<int>", test_vector_create()));
- print(run_tests(20000, 100, 10, "vector_sort<int>", test_vector_sort<int>()));
- print(run_tests(100000, 100, 10, "vector_dupe", test_vector_dupe()));
- print(run_tests(20000, 100, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
- print(run_tests(500000, 100, 10, "vector_accumulate", test_vector_accumulate()));
- print(run_tests(50, 100, 10, "set_vector", test_set_vector()));
- print(run_tests(500, 100, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
-#endif
+ //print(run_tests(1000, 100, 10, "test_map_erase<int>", test_map_erase()));
+ //return 0;
- heading("SUMMARY", '*');
- print_cumulative(cumulative);
- }
+ // small-size (~100 elements) containers
+ if (run_small)
+ {
+ heading("SMALL");
+ #ifndef WIN32
+ print(run_tests(75000, 100, 10, "list_create<int>", test_list_create<int>()));
+ print(run_tests(75000, 100, 10, "list_sort<int>", test_list_sort<int>()));
+ print(run_tests(2000000, 100, 10, "vector_create<int>", test_vector_create()));
+ print(run_tests(200000, 100, 10, "vector_sort<int>", test_vector_sort<int>()));
+ print(run_tests(1000000, 100, 10, "vector_dupe", test_vector_dupe()));
+ print(run_tests(50000, 100, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
+ print(run_tests(500000, 100, 10, "vector_accumulate", test_vector_accumulate()));
+ print(run_tests(10000, 100, 10, "set_vector", test_set_vector()));
+ print(run_tests(2000, 100, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
+ #else
+ print(run_tests(50000, 100, 10, "list_create<int>", test_list_create<int>()));
+ print(run_tests(5000, 100, 10, "list_sort<int>", test_list_sort<int>()));
+ print(run_tests(2000000, 100, 10, "vector_create<int>", test_vector_create()));
+ print(run_tests(20000, 100, 10, "vector_sort<int>", test_vector_sort<int>()));
+ print(run_tests(100000, 100, 10, "vector_dupe", test_vector_dupe()));
+ print(run_tests(20000, 100, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
+ print(run_tests(500000, 100, 10, "vector_accumulate", test_vector_accumulate()));
+ print(run_tests(50, 100, 10, "set_vector", test_set_vector()));
+ print(run_tests(500, 100, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
+ #endif
- // medium-size (~1000 elements) containers
- if (run_medium)
- {
- heading("MEDIUM");
- print(run_tests(10000, 1000, 10, "list_create<int>", test_list_create<int>()));
- print(run_tests(5000, 1000, 10, "list_sort<int>", test_list_sort<int>()));
-
-#ifndef WIN32
- print(run_tests(1000000, 100000, 10, "vector_create<int>", test_vector_create()));
- print(run_tests(300, 10000, 10, "vector_sort<int>", test_vector_sort<int>()));
- print(run_tests(1000000, 10000, 10, "vector_dupe", test_vector_dupe()));
- print(run_tests(2000, 1000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
- print(run_tests(5000000, 2000, 10, "vector_accumulate", test_vector_accumulate()));
- print(run_tests(500, 1000, 10, "set_vector", test_set_vector()));
- print(run_tests(500, 1000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
-#else
- print(run_tests(1000, 100000, 10, "vector_create<int>", test_vector_create()));
- print(run_tests(30000, 1000, 10, "vector_sort<int>", test_vector_sort<int>()));
- print(run_tests(5000, 10000, 10, "vector_dupe", test_vector_dupe()));
- print(run_tests(500, 1000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
- print(run_tests(50000, 2000, 10, "vector_accumulate", test_vector_accumulate()));
- print(run_tests(20, 500, 5, "set_vector", test_set_vector()));
- print(run_tests(50, 1000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
-#endif
- heading("SUMMARY", '*');
+ heading("SUMMARY", '*');
+ print_cumulative(cumulative);
+ }
+
+ // medium-size (~1000 elements) containers
+ if (run_medium)
+ {
+ heading("MEDIUM");
+ print(run_tests(10000, 1000, 10, "list_create<int>", test_list_create<int>()));
+ print(run_tests(5000, 1000, 10, "list_sort<int>", test_list_sort<int>()));
+
+ #ifndef WIN32
+ print(run_tests(1000000, 100000, 10, "vector_create<int>", test_vector_create()));
+ print(run_tests(300, 10000, 10, "vector_sort<int>", test_vector_sort<int>()));
+ print(run_tests(1000000, 10000, 10, "vector_dupe", test_vector_dupe()));
+ print(run_tests(2000, 1000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
+ print(run_tests(5000000, 2000, 10, "vector_accumulate", test_vector_accumulate()));
+ print(run_tests(500, 1000, 10, "set_vector", test_set_vector()));
+ print(run_tests(500, 1000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
+ #else
+ print(run_tests(1000, 100000, 10, "vector_create<int>", test_vector_create()));
+ print(run_tests(30000, 1000, 10, "vector_sort<int>", test_vector_sort<int>()));
+ print(run_tests(5000, 10000, 10, "vector_dupe", test_vector_dupe()));
+ print(run_tests(500, 1000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
+ print(run_tests(50000, 2000, 10, "vector_accumulate", test_vector_accumulate()));
+ print(run_tests(20, 500, 5, "set_vector", test_set_vector()));
+ print(run_tests(50, 1000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
+ #endif
+ heading("SUMMARY", '*');
+ print_cumulative(cumulative);
+ }
+
+ // large-size (~1000000 elements) containers
+ if (run_large)
+ {
+ heading("LARGE");
+ #ifndef WIN32
+ print(run_tests(100, 25000, 10, "list_create<int>", test_list_create<int>()));
+ print(run_tests(10, 100000, 10, "list_sort<int>", test_list_sort<int>()));
+ print(run_tests(1000000, 10000000, 10, "vector_create<int>", test_vector_create()));
+ print(run_tests(100, 500000, 10, "vector_sort<int>", test_vector_sort<int>()));
+
+ print(run_tests(1000000, 100000000, 10, "vector_dupe", test_vector_dupe()));
+ print(run_tests(100, 10000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
+ print(run_tests(1000000, 20000000, 10, "vector_accumulate", test_vector_accumulate()));
+ print(run_tests(10, 50000, 10, "set_vector", test_set_vector()));
+ print(run_tests(10, 10000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
+ #else
+ print(run_tests(10, 25000, 10, "list_create<int>", test_list_create<int>()));
+ print(run_tests(10, 100000, 10, "list_sort<int>", test_list_sort<int>()));
+ print(run_tests(1000, 1000000, 10, "vector_create<int>", test_vector_create()));
+ print(run_tests(300, 500000, 10, "vector_sort<int>", test_vector_sort<int>()));
+ print(run_tests(200, 10000000, 10, "vector_dupe", test_vector_dupe()));
+ print(run_tests(50, 10000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
+ print(run_tests(500, 10000000, 10, "vector_accumulate", test_vector_accumulate()));
+ print(run_tests(5, 2000, 5, "set_vector", test_set_vector()));
+ print(run_tests(10, 2000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
+ #endif
+ }
+
+ heading("FINAL SUMMARY", '*');
print_cumulative(cumulative);
+ cout << endl << "took " << setprecision(3) << timer.elapsed()/60. << " minutes" << endl;
}
-
- // large-size (~1000000 elements) containers
- if (run_large)
+ catch (std::exception &e)
{
- heading("LARGE");
-#ifndef WIN32
- print(run_tests(100, 25000, 10, "list_create<int>", test_list_create<int>()));
- print(run_tests(10, 100000, 10, "list_sort<int>", test_list_sort<int>()));
- print(run_tests(1000000, 10000000, 10, "vector_create<int>", test_vector_create()));
- print(run_tests(100, 500000, 10, "vector_sort<int>", test_vector_sort<int>()));
-
- print(run_tests(1000000, 100000000, 10, "vector_dupe", test_vector_dupe()));
- print(run_tests(100, 10000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
- print(run_tests(1000000, 20000000, 10, "vector_accumulate", test_vector_accumulate()));
- print(run_tests(10, 50000, 10, "set_vector", test_set_vector()));
- print(run_tests(10, 10000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
-#else
- print(run_tests(10, 25000, 10, "list_create<int>", test_list_create<int>()));
- print(run_tests(10, 100000, 10, "list_sort<int>", test_list_sort<int>()));
- print(run_tests(1000, 1000000, 10, "vector_create<int>", test_vector_create()));
- print(run_tests(300, 500000, 10, "vector_sort<int>", test_vector_sort<int>()));
- print(run_tests(200, 10000000, 10, "vector_dupe", test_vector_dupe()));
- print(run_tests(50, 10000, 10, "list_dupe", test_list_dupe(), test_dupe_list_types));
- print(run_tests(500, 10000000, 10, "vector_accumulate", test_vector_accumulate()));
- print(run_tests(5, 2000, 5, "set_vector", test_set_vector()));
- print(run_tests(10, 2000, 10, "map_vector<int>", test_map_vector<int>(), test_map_vector_types));
-#endif
+ cout << "exception: " << e.what() << endl;
+ return 1;
}
- heading("FINAL SUMMARY", '*');
- print_cumulative(cumulative);
-
- cout << endl << "took " << setprecision(3) << timer.elapsed()/60. << " minutes" << endl;
-
return 0;
}
Modified: sandbox/monotonic/libs/monotonic/test/monotonic.vcproj
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/monotonic.vcproj (original)
+++ sandbox/monotonic/libs/monotonic/test/monotonic.vcproj 2009-06-22 16:24:28 EDT (Mon, 22 Jun 2009)
@@ -395,6 +395,10 @@
RelativePath=".\results\msvc.txt"
>
</File>
+ <File
+ RelativePath=".\results\test_map_erase.txt"
+ >
+ </File>
</Filter>
<File
RelativePath=".\AllocatorTypes.h"
Added: sandbox/monotonic/libs/monotonic/test/results/test_map_erase.txt
==============================================================================
--- (empty file)
+++ sandbox/monotonic/libs/monotonic/test/results/test_map_erase.txt 2009-06-22 16:24:28 EDT (Mon, 22 Jun 2009)
@@ -0,0 +1,41 @@
+results of running test at:
+https://svn.boost.org/svn/boost/sandbox/monotonic/libs/monotonic/test/compare_memory_pool.cpp
+
+test_map_erase<int>: reps=1000, len=100, steps=10..........
+took 41.932s
+ len fast/m pool/m std/m tbb/m
+--------------------------------------------
+ 1 mono = 0s
+ 11 1.09 1.41 1.73 1.27
+ 21 1.02 1.3 1.63 1.12
+ 31 0.991 1.25 1.5 1.09
+ 41 1.02 1.19 1.42 0.983
+ 51 1 1.28 1.56 1.11
+ 61 0.98 1.27 1.51 1.09
+ 71 0.989 1.29 1.54 1.09
+ 81 0.923 1.21 1.55 1.03
+ 91 1 1.3 1.53 1.08
+
+ scheme mean std-dev min max
+ fast 1 0.0418 0.923 1.09
+ pool 1.28 0.0035 1.19 1.41
+ std 1.55 0.0805 1.42 1.73
+ tbb 1.1 0.0745 0.983 1.27
+
+
+test_map_erase<int>: reps=10, len=5000, steps=5.....
+took 454.574s
+ len fast/m pool/m std/m tbb/m
+--------------------------------------------
+ 1 mono = 0s
+1001 0.957 1.18 1.43 1.05
+2001 1.04 1.25 1.45 1.1
+3001 0.981 1.16 1.41 1.03
+4001 1.01 1.19 1.48 1.07
+
+ scheme mean std-dev min max
+ fast 0.996 0.0307 0.957 1.04
+ pool 1.2 0.00107 1.16 1.25
+ std 1.44 0.025 1.41 1.48
+ tbb 1.06 0.0228 1.03 1.1
+