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 #include <vector>
12 #include <deque>
13 #include <boost/container/vector.hpp>
14 #include <boost/container/devector.hpp>
15 #include <boost/container/deque.hpp>
16 #include <boost/container/small_vector.hpp>
17 #include <boost/container/stable_vector.hpp>
18
19 #include <memory> //std::allocator
20 #include <iostream> //std::cout, std::endl
21 #include <cstring> //std::strcmp
22 #include <boost/move/detail/nsec_clock.hpp>
23 #include <typeinfo>
24
25 //capacity
26 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME capacity
27 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace test {
28 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
29 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
30 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
31 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
32
33 using boost::move_detail::cpu_timer;
34 using boost::move_detail::cpu_times;
35 using boost::move_detail::nanosecond_type;
36
37 namespace bc = boost::container;
38
39 class MyInt
40 {
41 int int_;
42
43 public:
MyInt(int i=0)44 BOOST_CONTAINER_FORCEINLINE explicit MyInt(int i = 0)
45 : int_(i)
46 {}
47
MyInt(const MyInt & other)48 BOOST_CONTAINER_FORCEINLINE MyInt(const MyInt &other)
49 : int_(other.int_)
50 {}
51
operator =(const MyInt & other)52 BOOST_CONTAINER_FORCEINLINE MyInt & operator=(const MyInt &other)
53 {
54 int_ = other.int_;
55 return *this;
56 }
57
~MyInt()58 BOOST_CONTAINER_FORCEINLINE ~MyInt()
59 {
60 int_ = 0;
61 }
62 };
63
64 template<class C, bool = boost::container::test::
65 has_member_function_callable_with_capacity<C>::value>
66 struct capacity_wrapper
67 {
get_capacitycapacity_wrapper68 BOOST_CONTAINER_FORCEINLINE static typename C::size_type get_capacity(const C &c)
69 { return c.capacity(); }
70
set_reservecapacity_wrapper71 BOOST_CONTAINER_FORCEINLINE static void set_reserve(C &c, typename C::size_type cp)
72 { c.reserve(cp); }
73 };
74
75 template<class C>
76 struct capacity_wrapper<C, false>
77 {
get_capacitycapacity_wrapper78 BOOST_CONTAINER_FORCEINLINE static typename C::size_type get_capacity(const C &)
79 { return 0u; }
80
set_reservecapacity_wrapper81 BOOST_CONTAINER_FORCEINLINE static void set_reserve(C &, typename C::size_type )
82 { }
83 };
84
85 const std::size_t RangeSize = 5;
86
87 struct insert_end_range
88 {
capacity_multiplierinsert_end_range89 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
90 { return RangeSize; }
91
92 template<class C>
operator ()insert_end_range93 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int)
94 { c.insert(c.end(), &a[0], &a[0]+RangeSize); }
95
nameinsert_end_range96 const char *name() const
97 { return "insert_end_range"; }
98
99 MyInt a[RangeSize];
100 };
101
102 struct insert_end_repeated
103 {
capacity_multiplierinsert_end_repeated104 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
105 { return RangeSize; }
106
107 template<class C>
operator ()insert_end_repeated108 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
109 { c.insert(c.end(), RangeSize, MyInt(i)); }
110
nameinsert_end_repeated111 BOOST_CONTAINER_FORCEINLINE const char *name() const
112 { return "insert_end_repeated"; }
113
114 MyInt a[RangeSize];
115 };
116
117 struct push_back
118 {
capacity_multiplierpush_back119 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
120 { return 1; }
121
122 template<class C>
operator ()push_back123 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
124 { c.push_back(MyInt(i)); }
125
namepush_back126 BOOST_CONTAINER_FORCEINLINE const char *name() const
127 { return "push_back"; }
128 };
129
130 struct insert_near_end_repeated
131 {
capacity_multiplierinsert_near_end_repeated132 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
133 { return RangeSize; }
134
135 template<class C>
operator ()insert_near_end_repeated136 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
137 { c.insert(c.size() >= 2*RangeSize ? c.end()-2*RangeSize : c.begin(), RangeSize, MyInt(i)); }
138
nameinsert_near_end_repeated139 BOOST_CONTAINER_FORCEINLINE const char *name() const
140 { return "insert_near_end_repeated"; }
141 };
142
143 struct insert_near_end_range
144 {
capacity_multiplierinsert_near_end_range145 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
146 { return RangeSize; }
147
148 template<class C>
operator ()insert_near_end_range149 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int)
150 {
151 c.insert(c.size() >= 2*RangeSize ? c.end()-2*RangeSize : c.begin(), &a[0], &a[0]+RangeSize);
152 }
153
nameinsert_near_end_range154 BOOST_CONTAINER_FORCEINLINE const char *name() const
155 { return "insert_near_end_range"; }
156
157 MyInt a[RangeSize];
158 };
159
160 struct insert_near_end
161 {
capacity_multiplierinsert_near_end162 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
163 { return 1; }
164
165 template<class C>
operator ()insert_near_end166 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
167 {
168 typedef typename C::iterator it_t;
169 it_t it (c.end());
170 it -= static_cast<typename C::size_type>(c.size() >= 2)*2;
171 c.insert(it, MyInt(i));
172 }
173
nameinsert_near_end174 BOOST_CONTAINER_FORCEINLINE const char *name() const
175 { return "insert_near_end"; }
176 };
177
178
179 template<class Container, class Operation>
vector_test_template(std::size_t num_iterations,std::size_t num_elements,const char * cont_name)180 void vector_test_template(std::size_t num_iterations, std::size_t num_elements, const char *cont_name)
181 {
182 typedef capacity_wrapper<Container> cpw_t;
183
184 Container c;
185 cpw_t::set_reserve(c, num_elements);
186
187 Operation op;
188 const typename Container::size_type multiplier = op.capacity_multiplier();
189
190 //Warm-up operation
191 for(std::size_t e = 0, max = num_elements/multiplier; e != max; ++e){
192 op(c, static_cast<int>(e));
193 }
194 c.clear();
195
196 cpu_timer timer;
197
198 const std::size_t max = num_elements/multiplier;
199 for(std::size_t r = 0; r != num_iterations; ++r){
200
201 //Unrolll the loop to avoid noise from loop code
202 int i = 0;
203 timer.resume();
204 for(std::size_t e = 0; e < max/16; ++e){
205 op(c, static_cast<int>(i++));
206 op(c, static_cast<int>(i++));
207 op(c, static_cast<int>(i++));
208 op(c, static_cast<int>(i++));
209 op(c, static_cast<int>(i++));
210 op(c, static_cast<int>(i++));
211 op(c, static_cast<int>(i++));
212 op(c, static_cast<int>(i++));
213 op(c, static_cast<int>(i++));
214 op(c, static_cast<int>(i++));
215 op(c, static_cast<int>(i++));
216 op(c, static_cast<int>(i++));
217 op(c, static_cast<int>(i++));
218 op(c, static_cast<int>(i++));
219 op(c, static_cast<int>(i++));
220 op(c, static_cast<int>(i++));
221 }
222
223 timer.stop();
224 c.clear();
225 }
226
227 timer.stop();
228
229 std::size_t capacity = cpw_t::get_capacity(c);
230
231 nanosecond_type nseconds = timer.elapsed().wall;
232
233 std::cout << cont_name << "->" << op.name() <<" ns: "
234 << float(nseconds)/(num_iterations*num_elements)
235 << '\t'
236 << "Capacity: " << capacity
237 << "\n";
238 }
239
240 template<class Operation>
test_vectors()241 void test_vectors()
242 {
243 //#define SINGLE_TEST
244 #define SIMPLE_IT
245 #ifdef SINGLE_TEST
246 #ifdef NDEBUG
247 std::size_t numit [] = { 100 };
248 #else
249 std::size_t numit [] = { 20 };
250 #endif
251 std::size_t numele [] = { 10000 };
252 #elif defined SIMPLE_IT
253 std::size_t numit [] = { 100 };
254 std::size_t numele [] = { 10000 };
255 #else
256 #ifdef NDEBUG
257 unsigned int numit [] = { 1000, 10000, 100000, 1000000 };
258 #else
259 unsigned int numit [] = { 100, 1000, 10000, 100000 };
260 #endif
261 unsigned int numele [] = { 10000, 1000, 100, 10 };
262 #endif
263
264 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
265 vector_test_template< std::vector<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "std::vector ");
266 vector_test_template< bc::vector<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "vector ");
267 vector_test_template< bc::devector<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "devector ");
268 vector_test_template< bc::small_vector<MyInt, 0, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "small_vector ");
269 vector_test_template< std::deque<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "std::deque ");
270 vector_test_template< bc::deque<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "deque ");
271 }
272
273 std::cout << "---------------------------------\n---------------------------------\n";
274 }
275
main()276 int main()
277 {
278 //end
279 test_vectors<push_back>();
280 test_vectors<insert_end_range>();
281 test_vectors<insert_end_repeated>();
282 //near end
283 test_vectors<insert_near_end>();
284 test_vectors<insert_near_end_range>();
285 test_vectors<insert_near_end_repeated>();
286
287 return 0;
288 }
289