boost/libs/container/bench/bench_alloc_stable_vector_burst_allocation.cpp

//////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2007-2013. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
//
// See http://www.boost.org/libs/container for documentation.
//
//////////////////////////////////////////////////////////////////////////////

#ifdef _MSC_VER
#pragma warning (disable : 4512)
#pragma warning (disable : 4541)
#pragma warning (disable : 4673)
#pragma warning (disable : 4671)
#pragma warning (disable : 4244)
#endif

#include <memory>    //std::allocator
#include <iostream>  //std::cout, std::endl
#include <vector>    //std::vector
#include <cstddef>   //std::size_t
#include <boost/container/allocator.hpp>
#include <boost/container/adaptive_pool.hpp>
#include <boost/container/stable_vector.hpp>
#include <boost/container/vector.hpp>
#include <boost/timer/timer.hpp>
using boost::timer::cpu_timer;
using boost::timer::cpu_times;
using boost::timer::nanosecond_type;

namespace bc = boost::container;

typedef std::allocator<int>   StdAllocator;
typedef bc::allocator<int, 1> AllocatorPlusV1;
typedef bc::allocator<int, 2> AllocatorPlusV2;
typedef bc::adaptive_pool
   < int
   , bc::ADP_nodes_per_block
   , 0//bc::ADP_max_free_blocks
   , 2
   , 2>                       AdPool2PercentV2;

template<class Allocator> struct get_allocator_name;

template<> struct get_allocator_name<StdAllocator>
{  static const char *get() {  return "StdAllocator";  } };

template<> struct get_allocator_name<AllocatorPlusV1>
{  static const char *get() {  return "AllocatorPlusV1";  } };

template<> struct get_allocator_name<AllocatorPlusV2>
{  static const char *get() {  return "AllocatorPlusV2";  } };

template<> struct get_allocator_name<AdPool2PercentV2>
{  static const char *get() {  return "AdPool2PercentV2";  } };

class MyInt
{
   int int_;

   public:
   MyInt(int i = 0) : int_(i){}
   MyInt(const MyInt &other)
      :  int_(other.int_)
   {}
   MyInt & operator=(const MyInt &other)
   {
      int_ = other.int_;
      return *this;
   }
};

template<class Allocator>
struct get_vector
{
   typedef bc::vector
      <MyInt, typename Allocator::template rebind<MyInt>::other> type;
   static const char *vector_name()
   {
      return "vector<MyInt>";
   }
};

template<class Allocator>
struct get_stable_vector
{
   typedef bc::stable_vector
      <MyInt, typename Allocator::template rebind<MyInt>::other> type;
   static const char *vector_name()
   {
      return "stable_vector<MyInt>";
   }
};

template<template<class> class GetContainer, class Allocator>
void stable_vector_test_template(unsigned int num_iterations, unsigned int num_elements, bool csv_output)
{
   typedef typename GetContainer<Allocator>::type vector_type;
   //std::size_t top_capacity = 0;
   nanosecond_type nseconds;
   {
      {
         vector_type l;
         cpu_timer timer;
         timer.resume();

         for(unsigned int r = 0; r != num_iterations; ++r){
            l.insert(l.end(), num_elements, MyInt(r));
         }

         timer.stop();
         nseconds = timer.elapsed().wall;

         if(csv_output){
            std::cout   << get_allocator_name<Allocator>::get()
                        << ";"
                        << GetContainer<Allocator>::vector_name()
                        << ";"
                        << num_iterations
                        << ";"
                        << num_elements
                        << ";"
                        << float(nseconds)/(num_iterations*num_elements)
                        << ";";
         }
         else{
            std::cout   << "Allocator: " << get_allocator_name<Allocator>::get()
                        << '\t'
                        << GetContainer<Allocator>::vector_name()
                        << std::endl
                        << "  allocation ns:   "
                        << float(nseconds)/(num_iterations*num_elements);
         }
//         top_capacity = l.capacity();
         //Now preprocess ranges to erase
         std::vector<typename vector_type::iterator> ranges_to_erase;
         ranges_to_erase.push_back(l.begin());
         for(unsigned int r = 0; r != num_iterations; ++r){
            typename vector_type::iterator next_pos(ranges_to_erase[r]);
            std::size_t n = num_elements;
            while(n--){ ++next_pos; }
            ranges_to_erase.push_back(next_pos);
         }

         //Measure range erasure function
         timer.stop();
         timer.start();

         for(unsigned int r = 0; r != num_iterations; ++r){
            std::size_t init_pos = (num_iterations-1)-r;
            l.erase(ranges_to_erase[init_pos], l.end());
         }
         timer.stop();
         nseconds = timer.elapsed().wall;
         assert(l.empty());
      }
   }

   if(csv_output){
      std::cout      << float(nseconds)/(num_iterations*num_elements)
                     << std::endl;
   }
   else{
      std::cout      << '\t'
                     << "  deallocation ns: "
                     << float(nseconds)/(num_iterations*num_elements)/*
                     << std::endl
                     << "  max capacity:    "
                     << static_cast<unsigned int>(top_capacity)
                     << std::endl
                     << "  remaining cap.   "
                     << static_cast<unsigned int>(top_capacity - num_iterations*num_elements)
                     << " (" << (float(top_capacity)/float(num_iterations*num_elements) - 1)*100 << " %)"*/
                     << std::endl << std::endl;
   }
   assert(boost_cont_all_deallocated());
   boost_cont_trim(0);
}

void print_header()
{
   std::cout   << "Allocator" << ";" << "Iterations" << ";" << "Size" << ";"
               << "Insertion time(ns)" << ";" << "Erasure time(ns)" << ";"
               << std::endl;
}

void stable_vector_operations()
{
   {
      bc::stable_vector<int> a(bc::stable_vector<int>::size_type(5), 4);
      bc::stable_vector<int> b(a);
      bc::stable_vector<int> c(a.cbegin(), a.cend());
      b.insert(b.cend(), 0);
      c.pop_back();
      a.assign(b.cbegin(), b.cend());
      a.assign(c.cbegin(), c.cend());
      a.assign(1, 2);
   }
   {
      typedef bc::stable_vector<int, std::allocator<int> > stable_vector_t;
      stable_vector_t a(bc::stable_vector<int>::size_type(5), 4);
      stable_vector_t b(a);
      stable_vector_t c(a.cbegin(), a.cend());
      b.insert(b.cend(), 0);
      c.pop_back();
      assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
      a.assign(b.cbegin(), b.cend());
      assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
      a.assign(c.cbegin(), c.cend());
      assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
      a.assign(1, 2);
      assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
      a.reserve(100);
      assert(static_cast<std::size_t>(a.end() - a.begin()) == a.size());
   }
}

int main(int argc, const char *argv[])
{
   #define SINGLE_TEST
   #ifndef SINGLE_TEST
      #ifdef NDEBUG
      unsigned int numit [] = { 400, 4000, 40000, 400000 };
      #else
      unsigned int numit [] = { 4,   40,   400,   4000 };
      #endif
      unsigned int numele [] = { 10000, 1000, 100,   10     };
   #else
      #ifdef NDEBUG
      unsigned int numit [] = { 400 };
      #else
      unsigned int numit [] = { 4 };
      #endif
      unsigned int numele [] = { 10000 };
   #endif

   //Warning: range erasure is buggy. Vector iterators are not stable, so it is not
   //possible to cache iterators, but indexes!!!

   bool csv_output = argc == 2 && (strcmp(argv[1], "--csv-output") == 0);

   if(csv_output){
      print_header();
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_stable_vector, StdAllocator>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_vector, StdAllocator>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_stable_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_stable_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_stable_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
      }
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         stable_vector_test_template<get_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
      }
   }
   else{
      for(unsigned int i = 0; i < sizeof(numele)/sizeof(numele[0]); ++i){
         std::cout   << "\n    -----------------------------------    \n"
                     <<   "  Iterations/Elements:         " << numit[i] << "/" << numele[i]
                     << "\n    -----------------------------------    \n";
         stable_vector_test_template<get_stable_vector, StdAllocator>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_vector, StdAllocator>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_stable_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_vector, AllocatorPlusV1>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_stable_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_vector, AllocatorPlusV2>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_stable_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
         stable_vector_test_template<get_vector, AdPool2PercentV2>(numit[i], numele[i], csv_output);
      }
   }

   return 0;
}