A better vector trim with move semantics

[monarch_dodra]

I'm all for removing implicit move... as long as it can still be explicitly defaulted.

[nuzzle]

I went ahead and wrote an article. I link it back here when it gets posted.

I've read the article now,

http://www.codeguru.com/cpp/misc/sam...-Semantics.htm

and I have a question.

The classic swap based shrink-to-fit idiom (described in item #82 in C++ Coding Standards by Sutter & Alexandrescu) looks like this.

template <typename T>
void trim_vector(std::vector<T>& io_vector) {
   std::vector<T>(io_vector).swap(io_vector)); 
}

Now lets say the swap method becomes implemented to take advantage of move semantics allong these lines,

template <class T> swap(T& a, T& b) {
    T tmp(std::move(a));
    a = std::move(b);   
    b = std::move(tmp);
}

as suggested here,

http://www.artima.com/cppsource/rvalue.html

How does then the suggestion in your article compare?

In other words, if swap gets move semantics does your suggested new idiom offer any advantage compared with the old idiom? I don't know enougth about move semantics to be able to decide that myself.

[monarch_dodra]

I've read the article now,

http://www.codeguru.com/cpp/misc/sam...-Semantics.htm

and I have a question.

The classic swap based shrink-to-fit idiom (described in item #82 in C++ Coding Standards by Sutter & Alexandrescu) looks like this.

template <typename T>
void trim_vector(std::vector<T>& io_vector) {
   std::vector<T>(io_vector).swap(io_vector)); 
}

Now lets say the swap method becomes implemented to take advantage of move semantics allong these lines,

template <class T> swap(T& a, T& b) {
    T tmp(std::move(a));
    a = std::move(b);   
    b = std::move(tmp);
}

as suggested here,

http://www.artima.com/cppsource/rvalue.html

How does then the suggestion in your article compare?

In other words, if swap gets move semantics does your suggested new idiom offer any advantage compared with the old idiom? I don't know enougth about move semantics to be able to decide that myself.

The thing is that "the new swap with r-value semantics" is no different from "the old swap". Indeed, the old swap was specialized to basically move the vectors' internal pointers already. The only difference is that the new swap would still be efficient without the specialization.

In otherwords, the new swap changes nothing to the old idiom. So how is my new idiom different? The main difference is that the old swap made copies of the individual elements, when there was no real need. With my idiom, each of the individual elements are merely moved to their new destination, avoiding the overhead of the individual copies.

The problem with trying to solve this problem is that just plain moving the vectors doesn't solve the problem, as moving a vector merely changes the internal pointer address, but the objects themselves will always be inside an array that is over allocated.

I hope that answers your question.

[nuzzle]

I hope that answers your question.

Not quite.

I've made a small benchmark where I compare the old idiomatic approach, the new C++0x shrink_to_fit method of vector, and your new approach and there is no difference. They're equally fast.

I'm using the VS2010 compiler from Microsoft and maybe move sematics isn't implemented yet, although I believe it is.

You claim your approach is better but have you actually tested it?

[monarch_dodra]

Not quite.

I've made a small benchmark where I compare the old idiomatic approach, the new C++0x shrink_to_fit method of vector, and your new approach and there is no difference. They're equally fast.

I'm using the VS2010 compiler from Microsoft and maybe move sematics isn't implemented yet, although I believe it is.

You claim your approach is better but have you actually tested it?

I have tested it actually. Using MinGW - GCC 4.5. In release. (And I also did an assembly comparison).

During your test, where the objects inside the vector moveable? The point is that this approach is faster only if the objects are moveable. However, if the objects aren't moveable (ie vector of int), there is no extra overhead (thanks to meta).

My quick benchmarking.

I tested it with simple ints: No difference.
I tested with a simple pimple object (RAII object with pointer to int): 10x speedup.
I tested with vector of vector: speedup depending on the internal size of the stored sub-vectors
I tested with strings: Slight speed up.

I finally tested the shrink to fit method with vector of int, and inspected the resulting assembly, and it was exactly the same in both cases.

VStudio should support C++0x, but I've never found the option that actually enables it.

[nuzzle]

During your test, where the objects inside the vector moveable? The point is that this approach is faster only if the objects are moveable. However, if the objects aren't moveable (ie vector of int), there is no extra overhead (thanks to meta).

Could you please explain this a little bit further.

I've used this object in my benchmark,

class C {
	std::array<int,5> a;
};

If it's not moveable how do I make it moveable?

[JohnW@Wessex]

It's not moveable as the array for the data is defined in the std::array structure. The struct/class would have to have some internal pointer to the array to make moving it more efficient than copying.

[monarch_dodra]

Could you please explain this a little bit further.

I've used this object in my benchmark,

class C {
	std::array<int,5> a;
};

If it's not moveable how do I make it moveable?

Moveable objects are class (hereby known as "the_class") objects that implement the methods:

the_class::the_class(the_class&&);
the_class& the_class::operator=(the_class&&);

An std::array is not moveable because it does not implement these methods. It does not implement these methods because an std::array would not be efficiently moveable anyways (space is on the stack).

Moveable objects are typically objects that use some sort of pimpl internally: vectors, strings, unique_ptr... Shared pointer is also moveable.

This is a quick test I did with a simple pimpl object. I made a pimpl adaptor, and I used that inside the vector. You can compile activating/deactivating the USE_MOVE_OPERATORS macro switch. The output makes the result pretty clear at what is happening behind the scenes.:

#include <vector>
#include <algorithm>
#include <iostream>

#define USE_MOVE_OPERATORS

template <typename T>
void trim_vector(std::vector<T>& io_vector)
{
  if(io_vector.size() == io_vector.capacity())
    {return;}

  io_vector = //Since the temporary vector is an R-value, this will call operator(std::vector&&), ie, a move
    std::vector<T>(
      std::make_move_iterator(io_vector.begin()),
      std::make_move_iterator(io_vector.end()),
      io_vector.get_allocator()
    );
}

template <typename T>
class pimpl_object
{
public:
  //Default constructor
  pimpl_object() : _pimpl(new T)
  {
    std::cout << "default constructor: 1 allocation" << std::endl;
  }

  operator T& () {return *_pimpl;}
  operator const T& () const {return *_pimpl;}

  //Parameterized constructor
  template <typename... Args>
  pimpl_object(Args... args)
  : _pimpl(new T(args...))
  {
    std::cout << "parametrized constructor: 1 allocation" << std::endl;
  }

  //copy constructor
  pimpl_object(const pimpl_object& i_other) : _pimpl(0)
  {
    _pimpl = new T(*i_other._pimpl);
    std::cout << "copy constructor: 1 allocation" << std::endl;
  }

  //asignment operator
  pimpl_object& operator=(const pimpl_object& i_other)
  {
    T* old = _pimpl;
    _pimpl = new T(*i_other._pimpl);
    delete old;
    std::cout << "assignment operator: 1 allocation + 1 deletion" << std::endl;
    return *this;
  }

  //destructor
  ~pimpl_object()
  {
    std::cout << "destructor: ";
    if (_pimpl)
    {
      delete _pimpl;
      std::cout << "1 deletion";
    }
    else
    {
      std::cout << "No deletion";
    }
    std::cout << std::endl;
  }

#ifdef USE_MOVE_OPERATORS
  //move constructor
  pimpl_object(pimpl_object&& i_other) : _pimpl(i_other._pimpl)
  {
    i_other._pimpl = 0;
    std::cout << "move constructor: No allocation" << std::endl;
  }

  //move operator
  pimpl_object& operator=(pimpl_object&& i_other)
  {
    std::swap(_pimpl, i_other._pimpl);
    std::cout << "move operator: No allocation" << std::endl;
    return *this;
  }
#endif

private:
  T* _pimpl;
};

int main()
{
  typedef pimpl_object<int> object;
  std::vector<object> vect;
  vect.reserve(20);
  vect.resize(10);
  trim_vector(vect);
}

[superbonzo]

@monarch_dodra, just a side note on your pimpl adaptor:

first, is there any reason why you are not forwarding the arguments in the "parametrized constructor" ?:

//Parameterized constructor
template <typename... Args>
pimpl_object(Args&&... args)
	: _pimpl( new T( std::forward<Args>(args)... ) )
{
	...

second, IMHO a swap based move assignment operator is not correct in this case; quoting Abrahams

A move assignment operator “steals” the value of its argument, leaving that argument in a destructible and assignable state, and preserves any user-visible side-effects on the left-hand-side.

yes, most of the times the to be moved object will be destroyed right away, but in situations like

pimpl_object<T> a = ...;
pimpl_object<T> b = ...;

a = std::move( b );

// ...

you will loose control on when the resources owned by a will be actually released which seems unacceptable to me. So, a more correct solution should be releasing a's resources before swapping the pimpl pointers ( plus a check for self move-assignemnt, of course ).

[monarch_dodra]

@monarch_dodra, just a side note on your pimpl adaptor:

first, is there any reason why you are not forwarding the arguments in the "parametrized constructor" ?:

My code is wrong. I wrote it real quick to test a few things. I would not recommend to anyone to use my pimpl adaptor.

second, IMHO a swap based move assignment operator is not correct in this case; quoting Abrahams

yes, most of the times the to be moved object will be destroyed right away, but in situations like

pimpl_object<T> a = ...;
pimpl_object<T> b = ...;

a = std::move( b );

// ...

you will loose control on when the resources owned by a will be actually released which seems unacceptable to me. So, a more correct solution should be releasing a's resources before swapping the pimpl pointers

That is very true, and I had never considered that. I guess the vector's approach to the implementation is better:

my_class& operator=(my_class&& i_other)
{
  this->clear();
  this->swap(i_other);
}

One of the reasons I did not do this is that in my vision of a pimpl, there is a class invariant that says a pimpl cannot point to nothing.

That said, a moved object is never supposed to be touched again, except for the destructor, so as long as the destructor can handle it, it should be fine.

( plus a check for self move-assignemnt, of course ).

Actually (apparently), you aren't required to check for self-move assignment. The standard made it explicit in 17.6.3.9, after accepting defect 1204.

Additionally this clarifies that move assignment operators need not perform the traditional if (this != &rhs) test commonly found (and needed) in copy assignment operators.

1 Each of the following [US 81] statements applies to all arguments to functions defined in the C++ standard library, unless explicitly stated otherwise.
— If an argument to a function has an invalid value (such as a value outside the domain of the function or a pointer invalid for its intended use), the behavior is undefined.
— If a function argument is described as being an array, the pointer actually passed to the function shall have a value such that all address computations and accesses to objects (that would be valid if the pointer did point to the first element of such an array) are in fact valid.
— If a function argument binds to an rvalue reference parameter, the implementation may assume that this parameter is a unique reference to this argument. [ Note: If the parameter is a generic parameter of the form T&& and an lvalue of type A is bound, the argument binds to an lvalue reference (14.8.2.1) and thus is not covered by the previous sentence. —end note ] [ Note: If a program casts an lvalue to an rvalue while passing that lvalue to a library function (e.g. by calling the function with the argument move(x)), the program is effectively asking that function to treat that lvalue as a temporary. The implementation is free to optimize away aliasing checks which might be needed if the argument was an lvalue. —end note ]

The current implementation of move-assign in GCC (see above) leave the current object in an "empty" state after a move assign (this->clear), but don't create un-define behavior, in the sense that the current object is still destroyable.

[superbonzo]

One of the reasons I did not do this is that in my vision of a pimpl, there is a class invariant that says a pimpl cannot point to nothing.

That said, a moved object is never supposed to be touched again, except for the destructor, so as long as the destructor can handle it, it should be fine.

... and assignment. Actually, this implies that every movable class should support a sort of "empty" state ...

Actually (apparently), you aren't required to check for self-move assignment. The standard made it explicit in 17.6.3.9, after accepting defect 1204.

good to know, thank you !

[monarch_dodra]

Turns out, according to 23.4.1.2, that in C++0X, vectors come with a member function called "shrink_to_fit", making this whole ordeal moot.

To anyone still reading this...