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