Monday 5 November 2012

Doing C++11 Move Semantics Right in gcc 4.7

Since upgrading to gcc 4.7 a while ago I have been making use of some of the new C++11 features available. Specifically, I have found the introduction of r-value references, which enable move semantics and perfect forwarding, to be very useful. A very good explanation of both of these topics is given by Thomas Becker (http://thbecker.net/articles/rvalue_references/section_01.html).  The purpose of this post is to instead explain a pitfall (bug?) that I stumbled into when implementing move semantics for a class in gcc 4.7,

The Problem

For a user-specified class Foo in C++11 you can specify a move constructor Foo(Foo &&) and a move assignment operator Foo & operator=(Foo &&) which enable move semantics. One of the primary purposes of move semantics is to enable the shifting of resources from an instance of an object to another. For example, when an instance is about to go out of scope move semantics allow you to specify how to efficiently "pass on" the underlying data without having to resort to deep copying. As an example, an Array class with a copy constructor and copy assignment operator has had move semantics added:

#define PRINT_OBJ_PTR std::cout << " @" \
    << static_cast<const void *>(this) << ": "

// Array
template <typename T>
class Array
{
public:
    // Constructor
    Array(int size = 0) : _size(size), _data(nullptr), _ownsData(true)
    {
        PRINT_OBJ_PTR;
        std::cout << "Array(" << size << ")" << std::endl;
        if (_size > 0)
            _data = new T[_size];
    }

    // Destructor
    ~Array()
    {
        PRINT_OBJ_PTR;
        std::cout << "~Array()" << std::endl;

        if (_ownsData && _data != nullptr)
            delete [] _data;
    }

    // Copy constructor
    Array(const Array & rhs)
    : _size(rhs._size), _data(nullptr), _ownsData(true)
    {
        PRINT_OBJ_PTR;
        std::cout << "Array(Array & rhs=" 
                  << static_cast<const void *>(&rhs) 
                  << ")" << std::endl;

        if (_size > 0)
        {
            _data = new T[_size];
            std::copy(rhs._data, rhs._data + _size, _data);
        }
    }

    // Copy assignment operator
    Array & operator=(const Array & rhs)
    {
        PRINT_OBJ_PTR;
        std::cout << "Array & operator=(Array & rhs="
                  << static_cast<const void *>(&rhs) 
                  << ")" << std::endl;

        if (_ownsData && _data != nullptr)
            delete [] _data;

        _size = rhs._size;
        _data = nullptr;
        _ownsData = true;

        if (_size > 0)
        {
            _data = new T[_size];
            std::copy(rhs._data, rhs._data + _size, _data);
        }
    }

    // Move constructor
    Array(Array && other)
    : _size(other._size), _data(other._data), _ownsData(other._ownsData)
    {
        PRINT_OBJ_PTR;
        std::cout << "Array(Array && other=" 
                  << static_cast<const void *>(&other) 
                  << ")" << std::endl;

        other._ownsData = false;
        other._data = nullptr;
        other._size = 0;
    }

    // Move asignment operator
    Array & operator=(Array && other)
    {
        PRINT_OBJ_PTR;
        std::cout << "Array & operator=(Array && other="
                  << static_cast<const void *>(&other) 
                  << ")" << std::endl;

        if (_ownsData && _data != nullptr)
            delete [] _data;
        
        _size = other._size;
        _data = other._data;
        _ownsData = other._ownsData;

        other._ownsData = false;
        other._data = nullptr;
        other._size = 0;
    }

    // Accessors
    T & operator[](int i) { return _data[i]; }
    const T & operator[](int i) const { return _data[i]; }

    int size() const { return _size; }

    void Print() const
    {
        PRINT_OBJ_PTR;
        std::cout << "_data@" << static_cast<const void *>(_data) 
                  << ": [ ";
        for (int i=0; i < _size; i++)
            std::cout << _data[i] << " ";
        std::cout << "]" << std::endl;
    }

protected:
    int _size;
    T * _data;
    bool _ownsData;
};

An example program showing the difference between the operations is shown below:

// main
int main()
{
    const int N = 10;

    // Define Array instance `a` from [0, N) 
    std::cout << "a(" << N << ")" << std::endl;
    Array<int> a(N);
    for (int i = 0; i < a.size(); ++i)
        a[i] = i;

    // Output `a`
    std::cout << "a.Print()" << std::endl;
    a.Print();

    // Initialise `b` using the move constructor
    std::cout << "\nb = std::move(a)" << std::endl;
    Array<int> b = std::move(a);

    // Output `a` and `b`
    std::cout << "a.Print()" << std::endl;
    a.Print();
    std::cout << "b.Print()" << std::endl;
    b.Print();

    // Initialise `c` using the copy constructor
    std::cout << "\nc = b" << std::endl;
    Array<int> c = b;

    // Output `c`
    std::cout << "c.Print()" << std::endl;
    c.Print();

    // Copy `c` into `a`
    std::cout << "\na = c" << std::endl;
    a = c;
    std::cout << "a.Print()" << std::endl;
    a.Print();

    // Move `b` back into `a`
    std::cout << "\na = std::move(b)" << std::endl;
    a = std::move(b);

    // Output `a` and `b`
    std::cout << "a.Print()" << std::endl;
    a.Print();
    std::cout << "b.Print()" << std::endl;
    b.Print();

    return 0;
}

Compiling with g++ and -std=c++11, the output on my 32-bit machine is:

a(10)
 @0xbfd841ec: Array(10)
a.Print()
 @0xbfd841ec: _data@0x9067008: [ 0 1 2 3 4 5 6 7 8 9 ]

b = std::move(a)
 @0xbfd841e0: Array(Array && other=0xbfd841ec)
a.Print()
 @0xbfd841ec: _data@0: [ ]
b.Print()
 @0xbfd841e0: _data@0x9067008: [ 0 1 2 3 4 5 6 7 8 9 ]

c = b
 @0xbfd841d4: Array(Array & rhs=0xbfd841e0)
c.Print()
 @0xbfd841d4: _data@0x9067038: [ 0 1 2 3 4 5 6 7 8 9 ]

a = c
 @0xbfd841ec: Array & operator=(Array & rhs=0xbfd841d4)
a.Print()
 @0xbfd841ec: _data@0x9067068: [ 0 1 2 3 4 5 6 7 8 9 ]

a = std::move(b)
 @0xbfd841ec: Array & operator=(Array && other=0xbfd841e0)
a.Print()
 @0xbfd841ec: _data@0x9067008: [ 0 1 2 3 4 5 6 7 8 9 ]
b.Print()
 @0xbfd841e0: _data@0: [ ]
 @0xbfd841d4: ~Array()
 @0xbfd841e0: ~Array()
 @0xbfd841ec: ~Array()

This all appears to be working properly as the move constructor and move assignment operators are called correctly when std::move is used to force an r-value reference. The next thing to try is using this with the std::vector container as the move semantics should now allow storage of the objects directly in the vector and all of the reshuffling can be handled efficiently with move semantics:


// main
int main()
{
    const int N = 10;

    std::vector<Array<int>> v;
    std::cout << "Start `for`" << std::endl;

    for (int i = 0; i < 3; ++i)
    {
        std::cout << "i: " << i << std::endl;
        v.push_back(Array<int>(N));
    }
    std::cout << "End `for`" << std::endl;

    return 0;
}

The output of this program is:

Start `for`
i: 0
 @0xbf96790c: Array(10)
 @0x8235038: Array(Array && other=0xbf96790c)
 @0xbf96790c: ~Array()
i: 1
 @0xbf96790c: Array(10)
 @0x8235084: Array(Array && other=0xbf96790c)
 @0x8235078: Array(Array & rhs=0x8235038)
 @0x8235038: ~Array()
 @0xbf96790c: ~Array()
i: 2
 @0xbf96790c: Array(10)
 @0x82350e0: Array(Array && other=0xbf96790c)
 @0x82350c8: Array(Array & rhs=0x8235078)
 @0x82350d4: Array(Array & rhs=0x8235084)
 @0x8235078: ~Array()
 @0x8235084: ~Array()
 @0xbf96790c: ~Array()
End `for`
 @0x82350c8: ~Array()
 @0x82350d4: ~Array()
 @0x82350e0: ~Array()

As shown, as each item is pushed onto the vector it is move-constructed into memory regardless of whether a resize was required or not. However, as the vector is resized copy constructors are being called to reconstruct the other elements into place. Why is the move constructor not being used?

The Cause

An interesting way to find the cause of this behaviour is to fire up gdb and step through to see how std::vector operates and to see what static decisions are made to determine whether a move or a copy is made. Tracing the push_back calls you land in _M_emplace_back_aux in vector.tcc:

template<typename _Tp, typename _Alloc>
    template<typename... _Args>
      void
      vector<_Tp, _Alloc>::
      _M_emplace_back_aux(_Args&&... __args)
      {
 const size_type __len =
   _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
 pointer __new_start(this->_M_allocate(__len));
 pointer __new_finish(__new_start);
 __try
   {
     _Alloc_traits::construct(this->_M_impl, __new_start + size(),
         std::forward<_Args>(__args)...);
     __new_finish = 0;

     __new_finish
       = std::__uninitialized_move_if_noexcept_a
       (this->_M_impl._M_start, this->_M_impl._M_finish,
        __new_start, _M_get_Tp_allocator());

     ++__new_finish;
   }
 ....

When the size of the vector is insufficient, the allocator is called to set __new_start. The object which was pushed onto the vector is then directly move-constructed  into memory as expected. Finally, a call to __uninitialized_move_if_noexcept_a is made which moves/copies the objects from their old location to the new section of memory. 

Looking into stl_unitialized.h, we can see that __uninitialized_move_if_noexcept_a wraps a call to __unitialized_copy_a, which wraps the __first and __last iterators in the _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR macro. Inspecting stl_iterator.h shows this is just a call to std::__make_move_if_noexcept_iterator (which is also in stl_iterator.h):

  template<typename _Iterator, typename _ReturnType
    = typename conditional<__move_if_noexcept_cond
      <typename iterator_traits<_Iterator>::value_type>::value,
                _Iterator, move_iterator<_Iterator>>::type>
    inline _ReturnType
    __make_move_if_noexcept_iterator(_Iterator __i)
    { return _ReturnType(__i); }

_ReturnType is therefore set to _Iterator if the type it iterates over is not nothrow MoveConstructible and is CopyConstructible, otherwise a special move iterator is used. Therefore, it seems we need Array to be nothrow MoveConstructible and consulting http://en.cppreference.com/w/cpp/types/is_move_constructible says that all is required is to specify the move constructors as noexcept.

The Solution

Making the move constructor and move assignment operator noexcept, however, is not enough and does not change the output. Digging further into typetraits it can be seen that Array fails __is_nt_constructible_impl under is_nothrow_constructible:


using namespace std;

// main
int main()
{
    cout << boolalpha; 

    #define P(X) cout << #X << ": " << X << endl
    P((is_nothrow_move_constructible< Array<int> >::value));
    P((is_nothrow_constructible< Array<int>, Array<int> && >::value));
    P((is_constructible< Array<int>, Array<int> && >::value));
    P((__is_nt_constructible_impl< Array<int>, Array<int> && >::value));
    #undef P

    return 0;
}

(is_nothrow_move_constructible< Array<int> >::value): false
(is_nothrow_constructible< Array<int>, Array<int> && >::value): false
(is_constructible< Array<int>, Array<int> && >::value): true
(__is_nt_constructible_impl< Array<int>, Array<int> && >::value): false

The reason for this is that noexcept(static_cast<_Tp>(std::declval<_Tp>())) includes the destructor when determining whether an exception can be thrown or not. To remedy this, it is therefore necessary to specify the destructor as noexcept as well.  In C++11 it is supposed to be the case that non-trivial destructors are noexcept(true) (http://akrzemi1.wordpress.com/2011/06/10/using-noexcept/but this is not the case here. Well, it turns out this was spotted a while ago in http://gcc.gnu.org/bugzilla/show_bug.cgi?id=51295http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50043 and discussed at http://cplusplus.github.com/LWG/lwg-active.html#2116. Whether it is changed/fixed in the latest gcc I am not sure.


No comments:

Post a Comment