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 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
26 #pragma GCC diagnostic push
27 #pragma GCC diagnostic ignored "-Wunused-result"
28 #endif
29
30 //capacity
31 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME capacity
32 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEG namespace boost { namespace container { namespace test {
33 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}}
34 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MIN 0
35 #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_MAX 0
36 #include <boost/intrusive/detail/has_member_function_callable_with.hpp>
37
38 //#pragma GCC diagnostic ignored "-Wunused-result"
39 #if defined(BOOST_GCC) && (BOOST_GCC >= 40600)
40 #pragma GCC diagnostic pop
41 #endif
42
43 using boost::move_detail::cpu_timer;
44 using boost::move_detail::cpu_times;
45 using boost::move_detail::nanosecond_type;
46
47 namespace bc = boost::container;
48
49 class MyInt
50 {
51 int int_;
52
53 public:
MyInt(int i=0)54 BOOST_CONTAINER_FORCEINLINE explicit MyInt(int i = 0)
55 : int_(i)
56 {}
57
MyInt(const MyInt & other)58 BOOST_CONTAINER_FORCEINLINE MyInt(const MyInt &other)
59 : int_(other.int_)
60 {}
61
operator =(const MyInt & other)62 BOOST_CONTAINER_FORCEINLINE MyInt & operator=(const MyInt &other)
63 {
64 int_ = other.int_;
65 return *this;
66 }
67
~MyInt()68 BOOST_CONTAINER_FORCEINLINE ~MyInt()
69 {
70 int_ = 0;
71 }
72 };
73
74 template<class C, bool = boost::container::test::
75 has_member_function_callable_with_capacity<C>::value>
76 struct capacity_wrapper
77 {
get_capacitycapacity_wrapper78 BOOST_CONTAINER_FORCEINLINE static typename C::size_type get_capacity(const C &c)
79 { return c.capacity(); }
80
set_reservecapacity_wrapper81 BOOST_CONTAINER_FORCEINLINE static void set_reserve(C &c, typename C::size_type cp)
82 { c.reserve(cp); }
83 };
84
85 template<class C>
86 struct capacity_wrapper<C, false>
87 {
get_capacitycapacity_wrapper88 BOOST_CONTAINER_FORCEINLINE static typename C::size_type get_capacity(const C &)
89 { return 0u; }
90
set_reservecapacity_wrapper91 BOOST_CONTAINER_FORCEINLINE static void set_reserve(C &, typename C::size_type )
92 { }
93 };
94
95 const std::size_t RangeSize = 5;
96
97 struct insert_end_range
98 {
capacity_multiplierinsert_end_range99 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
100 { return RangeSize; }
101
102 template<class C>
operator ()insert_end_range103 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int)
104 { c.insert(c.end(), &a[0], &a[0]+RangeSize); }
105
nameinsert_end_range106 const char *name() const
107 { return "insert_end_range"; }
108
109 MyInt a[RangeSize];
110 };
111
112 struct insert_end_repeated
113 {
capacity_multiplierinsert_end_repeated114 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
115 { return RangeSize; }
116
117 template<class C>
operator ()insert_end_repeated118 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
119 { c.insert(c.end(), RangeSize, MyInt(i)); }
120
nameinsert_end_repeated121 BOOST_CONTAINER_FORCEINLINE const char *name() const
122 { return "insert_end_repeated"; }
123
124 MyInt a[RangeSize];
125 };
126
127 struct push_back
128 {
capacity_multiplierpush_back129 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
130 { return 1; }
131
132 template<class C>
operator ()push_back133 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
134 { c.push_back(MyInt(i)); }
135
namepush_back136 BOOST_CONTAINER_FORCEINLINE const char *name() const
137 { return "push_back"; }
138 };
139
140 struct insert_near_end_repeated
141 {
capacity_multiplierinsert_near_end_repeated142 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
143 { return RangeSize; }
144
145 template<class C>
operator ()insert_near_end_repeated146 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
147 { c.insert(c.size() >= 2*RangeSize ? c.end()-2*RangeSize : c.begin(), RangeSize, MyInt(i)); }
148
nameinsert_near_end_repeated149 BOOST_CONTAINER_FORCEINLINE const char *name() const
150 { return "insert_near_end_repeated"; }
151 };
152
153 struct insert_near_end_range
154 {
capacity_multiplierinsert_near_end_range155 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
156 { return RangeSize; }
157
158 template<class C>
operator ()insert_near_end_range159 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int)
160 {
161 c.insert(c.size() >= 2*RangeSize ? c.end()-2*RangeSize : c.begin(), &a[0], &a[0]+RangeSize);
162 }
163
nameinsert_near_end_range164 BOOST_CONTAINER_FORCEINLINE const char *name() const
165 { return "insert_near_end_range"; }
166
167 MyInt a[RangeSize];
168 };
169
170 struct insert_near_end
171 {
capacity_multiplierinsert_near_end172 BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
173 { return 1; }
174
175 template<class C>
operator ()insert_near_end176 BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
177 {
178 typedef typename C::iterator it_t;
179 it_t it (c.end());
180 it -= static_cast<typename C::size_type>(c.size() >= 2)*2;
181 c.insert(it, MyInt(i));
182 }
183
nameinsert_near_end184 BOOST_CONTAINER_FORCEINLINE const char *name() const
185 { return "insert_near_end"; }
186 };
187
188
189 template<class Container, class Operation>
vector_test_template(std::size_t num_iterations,std::size_t num_elements,const char * cont_name)190 void vector_test_template(std::size_t num_iterations, std::size_t num_elements, const char *cont_name)
191 {
192 typedef capacity_wrapper<Container> cpw_t;
193
194 Container c;
195 cpw_t::set_reserve(c, num_elements);
196
197 Operation op;
198 const typename Container::size_type multiplier = op.capacity_multiplier();
199
200 //Warm-up operation
201 for(std::size_t e = 0, max = num_elements/multiplier; e != max; ++e){
202 op(c, static_cast<int>(e));
203 }
204 c.clear();
205
206 cpu_timer timer;
207
208 const std::size_t max = num_elements/multiplier;
209 for(std::size_t r = 0; r != num_iterations; ++r){
210
211 //Unrolll the loop to avoid noise from loop code
212 int i = 0;
213 timer.resume();
214 for(std::size_t e = 0; e < max/16; ++e){
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 op(c, static_cast<int>(i++));
222 op(c, static_cast<int>(i++));
223 op(c, static_cast<int>(i++));
224 op(c, static_cast<int>(i++));
225 op(c, static_cast<int>(i++));
226 op(c, static_cast<int>(i++));
227 op(c, static_cast<int>(i++));
228 op(c, static_cast<int>(i++));
229 op(c, static_cast<int>(i++));
230 op(c, static_cast<int>(i++));
231 }
232
233 timer.stop();
234 c.clear();
235 }
236
237 timer.stop();
238
239 std::size_t capacity = cpw_t::get_capacity(c);
240
241 nanosecond_type nseconds = timer.elapsed().wall;
242
243 std::cout << cont_name << "->" << op.name() <<" ns: "
244 << float(nseconds)/(num_iterations*num_elements)
245 << '\t'
246 << "Capacity: " << capacity
247 << "\n";
248 }
249
250 template<class Operation>
test_vectors()251 void test_vectors()
252 {
253 //#define SINGLE_TEST
254 #define SIMPLE_IT
255 #ifdef SINGLE_TEST
256 #ifdef NDEBUG
257 std::size_t numit [] = { 100 };
258 #else
259 std::size_t numit [] = { 20 };
260 #endif
261 std::size_t numele [] = { 10000 };
262 #elif defined SIMPLE_IT
263 std::size_t numit [] = { 100 };
264 std::size_t numele [] = { 10000 };
265 #else
266 #ifdef NDEBUG
267 unsigned int numit [] = { 1000, 10000, 100000, 1000000 };
268 #else
269 unsigned int numit [] = { 100, 1000, 10000, 100000 };
270 #endif
271 unsigned int numele [] = { 10000, 1000, 100, 10 };
272 #endif
273
274 for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
275 vector_test_template< std::vector<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "std::vector ");
276 vector_test_template< bc::vector<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "vector ");
277 vector_test_template< bc::devector<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "devector ");
278 vector_test_template< bc::small_vector<MyInt, 0, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "small_vector ");
279 vector_test_template< std::deque<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "std::deque ");
280 vector_test_template< bc::deque<MyInt, std::allocator<MyInt> >, Operation >(numit[i], numele[i] , "deque ");
281 }
282
283 std::cout << "---------------------------------\n---------------------------------\n";
284 }
285
main()286 int main()
287 {
288 //end
289 test_vectors<push_back>();
290 test_vectors<insert_end_range>();
291 test_vectors<insert_end_repeated>();
292 //near end
293 test_vectors<insert_near_end>();
294 test_vectors<insert_near_end_range>();
295 test_vectors<insert_near_end_repeated>();
296
297 return 0;
298 }
299