Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-11 16:39:50

Den 10-10-2017 kl. 23:26 skrev Ion Gaztañaga via Boost:
> On 10/10/2017 10:50, Thorsten Ottosen via Boost wrote:

> Interesting points. Anyone willing to do some benchmark? ;-)

Here is one example comparing boost::vector<int> with devector<int>.

32 bit, insert:

10E3    3.89232 3.4131
10E4    2.51283 2.21077
10E5    5.60785 5.48309
10E6    28.7817 26.3436
10E7    340.473 271.399

32 bit, erase

10E3    3.57414 3.87152
10E4    2.79556 2.33145
10E5    11.4395 8.43574
10E6    80.8497 68.3668
10E7    912.091 667.667

64 bit, insert:

10E3    3.11854 2.52416
10E4    2.14097 1.97018
10E5    4.72984 3.56871
10E6    27.8463 15.3933
10E7    335.868 165.534

64 bit, erase:

10E3    2.63694 3.2763
10E4    1.80957 2.77551
10E5    4.66725 9.4179
10E6    30.4746 70.3418
10E7    360.72  666.874

The 32 bit results are in line with expectations.

For 64 bit I'm puzzled as to why erase differs from the 32 bit version.

Looking at the code for devector, I can see erase is defined as follows:

   iterator erase(const_iterator position)
   {
     return erase(position, position + 1);
   }

Digging deeper, devector is using

   template <typename Iterator>
   void move_if_noexcept(Iterator first, Iterator last, Iterator dst)
   {
     while (first != last)
     {
       *dst++ = std::move_if_noexcept(*first++);
     }
   }

and

   template <typename Iterator>
   void move_if_noexcept_backward(Iterator first, Iterator last, 
Iterator   dst_last)
   {
     while (first != last)
     {
       *(--dst_last) = std::move_if_noexcept(*(--last));
     }
   }

so there is no optimization done for trivially copyable types. Checking 
boost::container's copy_move_algo.hpp, the optimization applies to 
boost::vector.

I then plugged in boost::container's code for move-forwards and 
move-backwards:

32-bit, erase:

10E3    3.39647 4.09578
10E4    2.85362 2.61519
10E5    11.4961 6.07559
10E6    80.8788 27.0292
10E7    913.022 272.85

64-bit erase:

10E3    2.47863 3.61393
10E4    1.75806 2.47981
10E5    4.77791 3.98943
10E6    30.6545 15.9707
10E7    361.743 160.078

Is this awesome or what? :-)

kind regards

Thorsten