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