Re: [boost] [proposal] raw move (was: [interest] underlying type library)

Subject: Re: [boost] [proposal] raw move (was: [interest] underlying type library)
From: Christopher Jefferson (chris_at_[hidden])
Date: 2011-08-23 10:26:02

On 23 Aug 2011, at 14:44, Julian Gonggrijp wrote:

> Christopher Jefferson wrote:
> 
>> Can you first of all give a good example (with source) of where using move_raw would out-perform move assignment / constructors from C++0x, particularly in any standard library function (random_shuffle has a fairly small implementation for example). I don't really see how it will help that much.
> 
> There is a very simple reason why move_raw will outperform move 
> assignment for any non-POD type:
> 
> move assignment = move_raw + fixing up the source object ,
> 
> where 'fixing up the source object' is a cheap default constructor in 
> the best case. In that case move_raw is likely to be cheap as well, 
> which means that move assignment takes about twice as much work as 
> move_raw.

Simple reasons can be misleading. Are you sure the gain is substantial enough?

Most of (for example) a std::sort is swaps, where the compiler is usually clever enough to compile out all the non-useful code. I would think the best possible case for this kind of code would be a rotation, where we move everything down one step. The following (very dodgy) code does exactly that. I think this is a fair example of a simple rotation code, which has a "heavy assignment" (I assign the variable being assigned from 0).

template<typename T>
void step(T* begin, T* end)
{
        end--;
        T cop = *begin;
        T* pos = begin;
        while(pos < end)
        {
                *pos = *(pos + 1); 
                pos++;
                *pos = *(pos + 1); 
                pos++;
                *pos = *(pos + 1); 
                pos++;
                *pos = *(pos + 1); 
                pos++;
        }
        *end = cop;
}

struct wrapped_int
{
        int i;
        wrapped_int() : i(0)
        { }

        wrapped_int(int _i) : i(_i)
        { }

        void operator=(wrapped_int& w)
        { i = w.i; w.i = 0; }
};

int main(void)
{
        TYPE* ptr = new TYPE[100000];
        for(int i = 0; i < 100000; ++i)
        {
                TYPE t(i);
                ptr[i] = t;
        }
        for(int i = 0; i < 10000; ++i)
                step(ptr, ptr + 100000);	
}

I record (here, where I believe I have the best case gain) a gain of 9%. Now, that's not to be sniffed at, but I would expect the gains for algorithms like sort, reverse, next_permutation, which mostly use swap, to be much smaller.

As well as discussing, has anyone else come up with good benchmarks (I couldn't find any in the thread you referred to).

Chris

> 
> Since the implementation of an algorithm with move_raw contains 
> exactly the same steps as when it is implemented with move assigment, 
> except that all move assignments are replaced by raw moves, the 
> implementation with raw moves will always perform strictly fewer 
> operations than the move assignment-based implementation for non-POD 
> types.
> 
> An excellent explanation is provided by Alexander Stepanov:
> http://www.stepanovpapers.com/notes.pdf (lectures 4 and 5).
> 
> For some historical background you may also want to refer to the 
> 'mother thread' of my proposal ('[interest] underlying type library'), 
> in which the efficiency benefits of move_raw have already been 
> discussed. The following post is of particular interest:
> 
> http://lists.boost.org/Archives/boost/2011/08/184933.php
> 
> The entire thread starts here (though I don't recommend reading all of 
> it):
> 
> http://lists.boost.org/Archives/boost/2011/08/184872.php
> 
> (note that the bitwise approach has been abandoned in the current 
> proposal).
> 
> HTH, Julian
> 
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost