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 //Enable checks in debug mode
11 #ifndef NDEBUG
12 #define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
13 #endif
14
15 #ifdef _MSC_VER
16 #pragma warning (disable : 4512)
17 #pragma warning (disable : 4127)
18 #pragma warning (disable : 4244)
19 #pragma warning (disable : 4267)
20 #endif
21
22 #include <boost/container/adaptive_pool.hpp>
23 #include <boost/container/node_allocator.hpp>
24 #include <boost/container/allocator.hpp>
25 #include <boost/container/list.hpp>
26 #include <memory> //std::allocator
27 #include <iostream> //std::cout, std::endl
28 #include <vector> //std::vector
29 #include <cstddef> //std::size_t
30 #include <cassert> //assert
31
32 #include <boost/move/detail/nsec_clock.hpp>
33
34 using boost::move_detail::cpu_timer;
35 using boost::move_detail::cpu_times;
36 using boost::move_detail::nanosecond_type;
37
38 namespace bc = boost::container;
39
40 typedef std::allocator<int> StdAllocator;
41 typedef bc::allocator<int, 2> AllocatorPlusV2;
42 typedef bc::allocator<int, 1> AllocatorPlusV1;
43 typedef bc::adaptive_pool
44 < int
45 , bc::ADP_nodes_per_block
46 , bc::ADP_max_free_blocks
47 , bc::ADP_only_alignment
48 , 1> AdPoolAlignOnlyV1;
49 typedef bc::adaptive_pool
50 < int
51 , bc::ADP_nodes_per_block
52 , bc::ADP_max_free_blocks
53 , bc::ADP_only_alignment
54 , 2> AdPoolAlignOnlyV2;
55 typedef bc::adaptive_pool
56 < int
57 , bc::ADP_nodes_per_block
58 , bc::ADP_max_free_blocks
59 , 2
60 , 1> AdPool2PercentV1;
61 typedef bc::adaptive_pool
62 < int
63 , bc::ADP_nodes_per_block
64 , bc::ADP_max_free_blocks
65 , 2
66 , 2> AdPool2PercentV2;
67 typedef bc::node_allocator
68 < int
69 , bc::NodeAlloc_nodes_per_block
70 , 1> SimpleSegregatedStorageV1;
71 typedef bc::node_allocator
72 < int
73 , bc::NodeAlloc_nodes_per_block
74 , 2> SimpleSegregatedStorageV2;
75
76 //Explicit instantiation
77 template class bc::adaptive_pool
78 < int
79 , bc::ADP_nodes_per_block
80 , bc::ADP_max_free_blocks
81 , bc::ADP_only_alignment
82 , 2>;
83
84 template class bc::node_allocator
85 < int
86 , bc::NodeAlloc_nodes_per_block
87 , 2>;
88
89 template<class Allocator> struct get_allocator_name;
90
91 template<> struct get_allocator_name<StdAllocator>
getget_allocator_name92 { static const char *get() { return "StdAllocator"; } };
93
94 template<> struct get_allocator_name<AllocatorPlusV2>
getget_allocator_name95 { static const char *get() { return "AllocatorPlusV2"; } };
96
97 template<> struct get_allocator_name<AllocatorPlusV1>
getget_allocator_name98 { static const char *get() { return "AllocatorPlusV1"; } };
99
100 template<> struct get_allocator_name<AdPoolAlignOnlyV1>
getget_allocator_name101 { static const char *get() { return "AdPoolAlignOnlyV1"; } };
102
103 template<> struct get_allocator_name<AdPoolAlignOnlyV2>
getget_allocator_name104 { static const char *get() { return "AdPoolAlignOnlyV2"; } };
105
106 template<> struct get_allocator_name<AdPool2PercentV1>
getget_allocator_name107 { static const char *get() { return "AdPool2PercentV1"; } };
108
109 template<> struct get_allocator_name<AdPool2PercentV2>
getget_allocator_name110 { static const char *get() { return "AdPool2PercentV2"; } };
111
112 template<> struct get_allocator_name<SimpleSegregatedStorageV1>
getget_allocator_name113 { static const char *get() { return "SimpleSegregatedStorageV1"; } };
114
115 template<> struct get_allocator_name<SimpleSegregatedStorageV2>
getget_allocator_name116 { static const char *get() { return "SimpleSegregatedStorageV2"; } };
117
118 class MyInt
119 {
120 std::size_t int_;
121
122 public:
MyInt(std::size_t i=0)123 explicit MyInt(std::size_t i = 0) : int_(i){}
MyInt(const MyInt & other)124 MyInt(const MyInt &other)
125 : int_(other.int_)
126 {}
operator =(const MyInt & other)127 MyInt & operator=(const MyInt &other)
128 {
129 int_ = other.int_;
130 return *this;
131 }
132 };
133
134 template<class Allocator>
list_test_template(std::size_t num_iterations,std::size_t num_elements,bool csv_output)135 void list_test_template(std::size_t num_iterations, std::size_t num_elements, bool csv_output)
136 {
137 typedef typename Allocator::template rebind<MyInt>::other IntAllocator;
138 nanosecond_type tinsert, terase;
139 bc::dlmalloc_malloc_stats_t insert_stats, erase_stats;
140 std::size_t insert_inuse, erase_inuse;
141 const size_t sizeof_node = 2*sizeof(void*)+sizeof(int);
142
143 typedef bc::list<MyInt, IntAllocator> list_t;
144 typedef typename list_t::iterator iterator_t;
145 {
146 cpu_timer timer;
147 timer.resume();
148 list_t l;
149 for(std::size_t r = 0; r != num_iterations; ++r){
150 l.insert(l.end(), num_elements, MyInt(r));
151 }
152 timer.stop();
153 tinsert = timer.elapsed().wall;
154
155 insert_inuse = bc::dlmalloc_in_use_memory();
156 insert_stats = bc::dlmalloc_malloc_stats();
157 /*
158 iterator_t it(l.begin());
159 iterator_t last(--l.end());
160 for(std::size_t n_elem = 0, n_max = l.size()/2-1; n_elem != n_max; ++n_elem)
161 {
162 l.splice(it++, l, last--);
163 }
164 */
165 //l.reverse();
166
167 //Now preprocess erase ranges
168 std::vector<iterator_t> ranges_to_erase;
169 ranges_to_erase.push_back(l.begin());
170 for(std::size_t r = 0; r != num_iterations; ++r){
171 iterator_t next_pos(ranges_to_erase[r]);
172 std::size_t n = num_elements;
173 while(n--){ ++next_pos; }
174 ranges_to_erase.push_back(next_pos);
175 }
176
177 //Measure range erasure function
178 timer.start();
179 for(std::size_t r = 0; r != num_iterations; ++r){
180 assert((r+1) < ranges_to_erase.size());
181 l.erase(ranges_to_erase[r], ranges_to_erase[r+1]);
182 }
183 timer.stop();
184 terase = timer.elapsed().wall;
185 erase_inuse = bc::dlmalloc_in_use_memory();
186 erase_stats = bc::dlmalloc_malloc_stats();
187 }
188
189
190 if(csv_output){
191 std::cout << get_allocator_name<Allocator>::get()
192 << ";"
193 << num_iterations
194 << ";"
195 << num_elements
196 << ";"
197 << float(tinsert)/(num_iterations*num_elements)
198 << ";"
199 << (unsigned int)insert_stats.system_bytes
200 << ";"
201 << float(insert_stats.system_bytes)/(num_iterations*num_elements*sizeof_node)*100.0-100.0
202 << ";"
203 << (unsigned int)insert_inuse
204 << ";"
205 << (float(insert_inuse)/(num_iterations*num_elements*sizeof_node)*100.0)-100.0
206 << ";";
207 std::cout << float(terase)/(num_iterations*num_elements)
208 << ";"
209 << (unsigned int)erase_stats.system_bytes
210 << ";"
211 << (unsigned int)erase_inuse
212 << std::endl;
213 }
214 else{
215 std::cout << std::endl
216 << "Allocator: " << get_allocator_name<Allocator>::get()
217 << std::endl
218 << " allocation/deallocation(ns): " << float(tinsert)/(num_iterations*num_elements) << '\t' << float(terase)/(num_iterations*num_elements)
219 << std::endl
220 << " Sys MB(overh.)/Inuse MB(overh.): " << (float)insert_stats.system_bytes/(1024*1024) << "(" << float(insert_stats.system_bytes)/(num_iterations*num_elements*sizeof_node)*100.0-100.0 << "%)"
221 << " / "
222 << (float)insert_inuse/(1024*1024) << "(" << (float(insert_inuse)/(num_iterations*num_elements*sizeof_node)*100.0)-100.0 << "%)"
223 << std::endl
224 << " system MB/inuse bytes after: " << (float)erase_stats.system_bytes/(1024*1024) << '\t' << bc::dlmalloc_in_use_memory()
225 << std::endl << std::endl;
226 }
227
228 //Release node_allocator cache
229 typedef boost::container::dtl::shared_node_pool
230 < (2*sizeof(void*)+sizeof(int))
231 , AdPoolAlignOnlyV2::nodes_per_block> shared_node_pool_t;
232 boost::container::dtl::singleton_default
233 <shared_node_pool_t>::instance().purge_blocks();
234
235 //Release adaptive_pool cache
236 typedef boost::container::dtl::shared_adaptive_node_pool
237 < (2*sizeof(void*)+sizeof(int))
238 , AdPool2PercentV2::nodes_per_block
239 , AdPool2PercentV2::max_free_blocks
240 , AdPool2PercentV2::overhead_percent> shared_adaptive_pool_plus_t;
241 boost::container::dtl::singleton_default
242 <shared_adaptive_pool_plus_t>::instance().deallocate_free_blocks();
243
244 //Release adaptive_pool cache
245 typedef boost::container::dtl::shared_adaptive_node_pool
246 < (2*sizeof(void*)+sizeof(int))
247 , AdPool2PercentV2::nodes_per_block
248 , AdPool2PercentV2::max_free_blocks
249 , 0u> shared_adaptive_pool_plus_align_only_t;
250 boost::container::dtl::singleton_default
251 <shared_adaptive_pool_plus_align_only_t>::instance().deallocate_free_blocks();
252 //Release dlmalloc memory
253 bc::dlmalloc_trim(0);
254 }
255
print_header()256 void print_header()
257 {
258 std::cout << "Allocator" << ";" << "Iterations" << ";" << "Size" << ";"
259 << "Insertion time(ns)" << ";"
260 << "System bytes" << ";"
261 << "System overhead(%)" << ";"
262 << "In use bytes" << ";"
263 << "In use overhead(%)" << ";"
264 << "Erasure time (ns)" << ";"
265 << "System bytes after" << ";"
266 << "In use bytes after"
267 << std::endl;
268 }
269
main(int argc,const char * argv[])270 int main(int argc, const char *argv[])
271 {
272 //#define SINGLE_TEST
273 #define SIMPLE_IT
274 #ifdef SINGLE_TEST
275 #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS
276 std::size_t numrep[] = { 1000 };
277 #elif defined(NDEBUG)
278 std::size_t numrep [] = { 15000 };
279 #else
280 std::size_t numrep [] = { 1000 };
281 #endif
282 std::size_t numele [] = { 100 };
283 #elif defined(SIMPLE_IT)
284 std::size_t numrep [] = { 3 };
285 std::size_t numele [] = { 100 };
286 #else
287 #ifdef NDEBUG
288 std::size_t numrep [] = { 300, 3000, 30000, 300000, 600000, 1500000, 3000000 };
289 #else
290 std::size_t numrep [] = { 20, 200, 2000, 20000, 40000, 100000, 200000 };
291 #endif
292 std::size_t numele [] = { 10000, 1000, 100, 10, 5, 2, 1 };
293 #endif
294
295 bool csv_output = argc == 2 && (strcmp(argv[1], "--csv-output") == 0);
296
297 if(csv_output){/*
298 print_header();
299 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
300 list_test_template<AllocatorPlusV1>(numrep[i], numele[i], csv_output);
301 }
302 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
303 list_test_template<AllocatorPlusV2>(numrep[i], numele[i], csv_output);
304 }
305 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
306 list_test_template<AdPoolAlignOnlyV1>(numrep[i], numele[i], csv_output);
307 }
308 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
309 list_test_template<AdPoolAlignOnlyV2>(numrep[i], numele[i], csv_output);
310 }
311 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
312 list_test_template<AdPool2PercentV1>(numrep[i], numele[i], csv_output);
313 }
314 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
315 list_test_template<AdPool2PercentV2>(numrep[i], numele[i], csv_output);
316 }
317 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
318 list_test_template<SimpleSegregatedStorageV1>(numrep[i], numele[i], csv_output);
319 }
320 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
321 list_test_template<SimpleSegregatedStorageV2>(numrep[i], numele[i], csv_output);
322 }*/
323 }
324 else{
325 for(std::size_t i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
326 std::cout << "\n ----------------------------------- \n"
327 << " Iterations/Elements: " << numrep[i] << "/" << numele[i]
328 << "\n ----------------------------------- \n";
329 list_test_template<AllocatorPlusV1>(numrep[i], numele[i], csv_output);
330 list_test_template<AllocatorPlusV2>(numrep[i], numele[i], csv_output);
331 list_test_template<AdPoolAlignOnlyV1>(numrep[i], numele[i], csv_output);
332 list_test_template<AdPoolAlignOnlyV2>(numrep[i], numele[i], csv_output);
333 list_test_template<AdPool2PercentV1>(numrep[i], numele[i], csv_output);
334 list_test_template<AdPool2PercentV2>(numrep[i], numele[i], csv_output);
335 list_test_template<SimpleSegregatedStorageV1>(numrep[i], numele[i], csv_output);
336 list_test_template<SimpleSegregatedStorageV2>(numrep[i], numele[i], csv_output);
337 }
338 }
339 return 0;
340 }
341