1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2007-2013. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10
11 #ifdef _MSC_VER
12 #pragma warning (disable : 4512)
13 #pragma warning (disable : 4541)
14 #pragma warning (disable : 4673)
15 #pragma warning (disable : 4671)
16 #pragma warning (disable : 4244)
17 #endif
18
19 #include <memory> //std::allocator
20 #include <iostream> //std::cout, std::endl
21 #include <vector> //std::vector
22 #include <cstddef> //std::size_t
23 #include <cassert> //assert
24
25 #include <boost/container/allocator.hpp>
26 #include <boost/container/adaptive_pool.hpp>
27 #include <boost/container/stable_vector.hpp>
28 #include <boost/container/vector.hpp>
29 #include <boost/timer/timer.hpp>
30
31 using boost::timer::cpu_timer;
32 using boost::timer::cpu_times;
33 using boost::timer::nanosecond_type;
34
35 namespace bc = boost::container;
36
37 typedef std::allocator<int> StdAllocator;
38 typedef bc::allocator<int, 1> AllocatorPlusV1;
39 typedef bc::allocator<int, 2> AllocatorPlusV2;
40 typedef bc::adaptive_pool
41 < int
42 , bc::ADP_nodes_per_block
43 , 0//bc::ADP_max_free_blocks
44 , 2
45 , 2> AdPool2PercentV2;
46
47 template<class Allocator> struct get_allocator_name;
48
49 template<> struct get_allocator_name<StdAllocator>
getget_allocator_name50 { static const char *get() { return "StdAllocator"; } };
51
52 template<> struct get_allocator_name<AllocatorPlusV1>
getget_allocator_name53 { static const char *get() { return "AllocatorPlusV1"; } };
54
55 template<> struct get_allocator_name<AllocatorPlusV2>
getget_allocator_name56 { static const char *get() { return "AllocatorPlusV2"; } };
57
58 template<> struct get_allocator_name<AdPool2PercentV2>
getget_allocator_name59 { static const char *get() { return "AdPool2PercentV2"; } };
60
61 class MyInt
62 {
63 int int_;
64
65 public:
MyInt(int i=0)66 MyInt(int i = 0) : int_(i){}
MyInt(const MyInt & other)67 MyInt(const MyInt &other)
68 : int_(other.int_)
69 {}
operator =(const MyInt & other)70 MyInt & operator=(const MyInt &other)
71 {
72 int_ = other.int_;
73 return *this;
74 }
75 };
76
77 template<class Allocator>
78 struct get_vector
79 {
80 typedef bc::vector
81 <MyInt, typename Allocator::template rebind<MyInt>::other> type;
vector_nameget_vector82 static const char *vector_name()
83 {
84 return "vector<MyInt>";
85 }
86 };
87
88 template<class Allocator>
89 struct get_stable_vector
90 {
91 typedef bc::stable_vector
92 <MyInt, typename Allocator::template rebind<MyInt>::other> type;
vector_nameget_stable_vector93 static const char *vector_name()
94 {
95 return "stable_vector<MyInt>";
96 }
97 };
98
99 template<template<class> class GetContainer, class Allocator>
stable_vector_test_template(unsigned int num_iterations,unsigned int num_elements,bool csv_output)100 void stable_vector_test_template(unsigned int num_iterations, unsigned int num_elements, bool csv_output)
101 {
102 typedef typename GetContainer<Allocator>::type vector_type;
103 //std::size_t top_capacity = 0;
104 nanosecond_type nseconds;
105 {
106 {
107 vector_type l;
108 cpu_timer timer;
109 timer.resume();
110
111 for(unsigned int r = 0; r != num_iterations; ++r){
112 l.insert(l.end(), num_elements, MyInt(r));
113 }
114
115 timer.stop();
116 nseconds = timer.elapsed().wall;
117
118 if(csv_output){
119 std::cout << get_allocator_name<Allocator>::get()
120 << ";"
121 << GetContainer<Allocator>::vector_name()
122 << ";"
123 << num_iterations
124 << ";"
125 << num_elements
126 << ";"
127 << float(nseconds)/(num_iterations*num_elements)
128 << ";";
129 }
130 else{
131 std::cout << "Allocator: " << get_allocator_name<Allocator>::get()
132 << '\t'
133 << GetContainer<Allocator>::vector_name()
134 << std::endl
135 << " allocation ns: "
136 << float(nseconds)/(num_iterations*num_elements);
137 }
138 // top_capacity = l.capacity();
139 //Now preprocess ranges to erase
140 std::vector<typename vector_type::iterator> ranges_to_erase;
141 ranges_to_erase.push_back(l.begin());
142 for(unsigned int r = 0; r != num_iterations; ++r){
143 typename vector_type::iterator next_pos(ranges_to_erase[r]);
144 std::size_t n = num_elements;
145 while(n--){ ++next_pos; }
146 ranges_to_erase.push_back(next_pos);
147 }
148
149 //Measure range erasure function
150 timer.stop();
151 timer.start();
152
153 for(unsigned int r = 0; r != num_iterations; ++r){
154 std::size_t init_pos = (num_iterations-1)-r;
155 l.erase(ranges_to_erase[init_pos], l.end());
156 }
157 timer.stop();
158 nseconds = timer.elapsed().wall;
159 assert(l.empty());
160 }
161 }
162
163 if(csv_output){
164 std::cout << float(nseconds)/(num_iterations*num_elements)
165 << std::endl;
166 }
167 else{
168 std::cout << '\t'
169 << " deallocation ns: "
170 << float(nseconds)/(num_iterations*num_elements)/*
171 << std::endl
172 << " max capacity: "
173 << static_cast<unsigned int>(top_capacity)
174 << std::endl
175 << " remaining cap. "
176 << static_cast<unsigned int>(top_capacity - num_iterations*num_elements)
177 << " (" << (float(top_capacity)/float(num_iterations*num_elements) - 1)*100 << " %)"*/
178 << std::endl << std::endl;
179 }
180 assert(bc::dlmalloc_all_deallocated());
181 bc::dlmalloc_trim(0);
182 }
183
print_header()184 void print_header()
185 {
186 std::cout << "Allocator" << ";" << "Iterations" << ";" << "Size" << ";"
187 << "Insertion time(ns)" << ";" << "Erasure time(ns)" << ";"
188 << std::endl;
189 }
190
stable_vector_operations()191 void stable_vector_operations()
192 {
193 {
194 bc::stable_vector<int> a(bc::stable_vector<int>::size_type(5), 4);
195 bc::stable_vector<int> b(a);
196 bc::stable_vector<int> c(a.cbegin(), a.cend());
197 b.insert(b.cend(), 0);
198 c.pop_back();
199 a.assign(b.cbegin(), b.cend());
200 a.assign(c.cbegin(), c.cend());
201 a.assign(1, 2);
202 }
203 {
204 typedef bc::stable_vector<int, std::allocator<int> > stable_vector_t;
205 stable_vector_t a(bc::stable_vector<int>::size_type(5), 4);
206 stable_vector_t b(a);
207 stable_vector_t c(a.cbegin(), a.cend());
208 b.insert(b.cend(), 0);
209 c.pop_back();
210 assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
211 a.assign(b.cbegin(), b.cend());
212 assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
213 a.assign(c.cbegin(), c.cend());
214 assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
215 a.assign(1, 2);
216 assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
217 a.reserve(100);
218 assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
219 }
220 }
221
main(int argc,const char * argv[])222 int main(int argc, const char *argv[])
223 {
224 //#define SINGLE_TEST
225 #define SIMPLE_IT
226 #ifdef SINGLE_TEST
227 #ifdef NDEBUG
228 unsigned int numit [] = { 40 };
229 #else
230 unsigned int numit [] = { 4 };
231 #endif
232 unsigned int numele [] = { 10000 };
233 #elif defined(SIMPLE_IT)
234 unsigned int numit [] = { 3 };
235 unsigned int numele [] = { 10000 };
236 #else
237 #ifdef NDEBUG
238 unsigned int numit [] = { 40, 400, 4000, 40000 };
239 #else
240 unsigned int numit [] = { 4, 40, 400, 4000 };
241 #endif
242 unsigned int numele [] = { 10000, 1000, 100, 10 };
243 #endif
244
245 //Warning: range erasure is buggy. Vector iterators are not stable, so it is not
246 //possible to cache iterators, but indexes!!!
247
248 bool csv_output = argc == 2 && (strcmp(argv[1], "--csv-output") == 0);
249
250 if(csv_output){
251 print_header();
252 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
253 stable_vector_test_template<get_stable_vector, StdAllocator>(numit[i], numele[i], csv_output);
254 }
255 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
256 stable_vector_test_template<get_vector, StdAllocator>(numit[i], numele[i], csv_output);
257 }
258 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
259 stable_vector_test_template<get_stable_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
260 }
261 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
262 stable_vector_test_template<get_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
263 }
264 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
265 stable_vector_test_template<get_stable_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
266 }
267 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
268 stable_vector_test_template<get_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
269 }
270 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
271 stable_vector_test_template<get_stable_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
272 }
273 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
274 stable_vector_test_template<get_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
275 }
276 }
277 else{
278 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
279 std::cout << "\n ----------------------------------- \n"
280 << " Iterations/Elements: " << numit[i] << "/" << numele[i]
281 << "\n ----------------------------------- \n";
282 stable_vector_test_template<get_stable_vector, StdAllocator>(numit[i], numele[i], csv_output);
283 stable_vector_test_template<get_vector, StdAllocator>(numit[i], numele[i], csv_output);
284 stable_vector_test_template<get_stable_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
285 stable_vector_test_template<get_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
286 stable_vector_test_template<get_stable_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
287 stable_vector_test_template<get_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
288 stable_vector_test_template<get_stable_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
289 stable_vector_test_template<get_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
290 }
291 }
292
293 return 0;
294 }
295