ceph/src/boost/libs/container/bench/bench_vectors.cpp

   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:
  44    BOOST_CONTAINER_FORCEINLINE explicit MyInt(int i = 0)
  45       : int_(i)
  46    {}
  47
  48    BOOST_CONTAINER_FORCEINLINE MyInt(const MyInt &other)
  49       :  int_(other.int_)
  50    {}
  51
  52    BOOST_CONTAINER_FORCEINLINE MyInt & operator=(const MyInt &other)
  53    {
  54       int_ = other.int_;
  55       return *this;
  56    }
  57
  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 {
  68    BOOST_CONTAINER_FORCEINLINE static typename C::size_type get_capacity(const C &c)
  69    {  return c.capacity(); }
  70
  71    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 {
  78    BOOST_CONTAINER_FORCEINLINE static typename C::size_type get_capacity(const C &)
  79    {  return 0u; }
  80
  81    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 {
  89    BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
  90    {  return RangeSize;  }
  91
  92    template<class C>
  93    BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int)
  94    {  c.insert(c.end(), &a[0], &a[0]+RangeSize); }
  95
  96    const char *name() const
  97    {  return "insert_end_range"; }
  98
  99    MyInt a[RangeSize];
 100 };
 101
 102 struct insert_end_repeated
 103 {
 104    BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
 105    {  return RangeSize;  }
 106
 107    template<class C>
 108    BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
 109    {  c.insert(c.end(), RangeSize, MyInt(i)); }
 110
 111    BOOST_CONTAINER_FORCEINLINE const char *name() const
 112    {  return "insert_end_repeated"; }
 113
 114    MyInt a[RangeSize];
 115 };
 116
 117 struct push_back
 118 {
 119    BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
 120    {  return 1;  }
 121
 122    template<class C>
 123    BOOST_CONTAINER_FORCEINLINE void operator()(C &c, int i)
 124    {  c.push_back(MyInt(i)); }
 125
 126    BOOST_CONTAINER_FORCEINLINE const char *name() const
 127    {  return "push_back"; }
 128 };
 129
 130 struct insert_near_end_repeated
 131 {
 132    BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
 133    {  return RangeSize;  }
 134
 135    template<class C>
 136    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
 139    BOOST_CONTAINER_FORCEINLINE const char *name() const
 140    {  return "insert_near_end_repeated"; }
 141 };
 142
 143 struct insert_near_end_range
 144 {
 145    BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
 146    {  return RangeSize;  }
 147
 148    template<class C>
 149    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
 154    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 {
 162    BOOST_CONTAINER_FORCEINLINE std::size_t capacity_multiplier() const
 163    {  return 1;  }
 164
 165    template<class C>
 166    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
 174    BOOST_CONTAINER_FORCEINLINE const char *name() const
 175    {  return "insert_near_end"; }
 176 };
 177
 178
 179 template<class Container, class Operation>
 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>
 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
 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 }