Prevent unnecessary copies of C++ functor objects

Question

I have a class which accumulates information about a set of objects, and can act as either a functor or an output iterator. This allows me to do things like:

std::vector<Foo> v;
Foo const x = std::for_each(v.begin(), v.end(), Joiner<Foo>());

and

Foo const x = std::copy(v.begin(), v.end(), Joiner<Foo>());

Now, in theory, the compiler should be able to use the copy elision and return-value optimizations so that only a single Joiner object needs to be created. In practice, however, the function makes a copy on which to operate and then copies that back to the result, even in fully-optimized builds.

If I create the functor as an lvalue, the compiler creates two extra copies instead of one:

Joiner<Foo> joiner;
Foo const x = std::copy(v.begin(), v.end(), joiner);

If I awkwardly force the template type to a reference it passes in a reference, but then makes a copy of it anyway and returns a dangling reference to the (now-destroyed) temporary copy:

x = std::copy<Container::const_iterator, Joiner<Foo>&>(...));

I can make the copies cheap by using a reference to the state rather than the state itself in the functor in the style of std::inserter, leading to something like this:

Foo output;
std::copy(v.begin(), v.end(), Joiner<Foo>(output));

But this makes it impossible to use the "functional" style of immutable objects, and just generally isn't as nice.

Is there some way to encourage the compiler to elide the temporary copies, or make it pass a reference all the way through and return that same reference?

Answer 1

You have stumbled upon an often complained about behavior with <algorithm>. There are no restrictions on what they can do with the functor, so the answer to your question is no: there is no way to encourage the compiler to elide the copies. It's not (always) the compiler, it's the library implementation. They just like to pass around functors by value (think of std::sort doing a qsort, passing in the functor by value to recursive calls, etc).

You have also stumbled upon the exact solution everyone uses: have a functor keep a reference to the state, so all copies refer to the same state when this is desired.

I found this ironic:

But this makes it impossible to use the "functional" style of immutable objects, and just generally isn't as nice.

...since this whole question is predicated on you having a complicated stateful functor, where creating copies is problematic. If you were using "functional" style immutable objects this would be a non-issue - the extra copies wouldn't be a problem, would they?

Answer 2

If you have a recent compiler (At least Visual Studio 2008 SP1 or GCC 4.4 I think) you can use std::ref/std::cref

#include <string>
#include <vector>
#include <functional> // for std::cref
#include <algorithm>
#include <iostream>

template <typename T>
class SuperHeavyFunctor 
{
    std::vector<char> v500mo;
    //ban copy
    SuperHeavyFunctor(const SuperHeavyFunctor&);
    SuperHeavyFunctor& operator=(const SuperHeavyFunctor&);
public:
    SuperHeavyFunctor():v500mo(500*1024*1024){}
    void operator()(const T& t) const { std::cout << t << std::endl; }
};

int main()
{
    std::vector<std::string> v; v.push_back("Hello"); v.push_back("world");
    std::for_each(v.begin(), v.end(), std::cref(SuperHeavyFunctor<std::string>()));
    return 0;
}

Edit : Actually, the MSVC10's implementation of reference_wrapper don't seem to known how to deduce the return type of function object operator(). I had to derive SuperHeavyFunctor from std::unary_function<T, void> to make it work.

Answer 3

Just a quick note, for_each, accumulate, transform (2nd form), provide no order guarantee when traversing the provided range.

This makes sense for implementers to provide mulit-threaded/concurrent versions of these functions.

Hence it is reasonable that the algorithm be able to provide an equivalent instance (a new copy) of the functor passed in.

Be wary when making stateful functors.

Answer 4

RVO is just that -- return value optimization. Most compilers, today, have this turned-on by default. However, argument passing is not returning a value. You possibly cannot expect one optimization to fit in everywhere.

Refer to conditions for copy elision is defined clearly in 12.8, para 15, item 3.

when a temporary class object that has not been bound to a reference (12.2) would be copied to a class object with the same cv-unqualified type, the copy operation can be omitted by constructing the temporary object directly into the target of the omitted copy

[emphasis mine]

The LHS Foo is const qualified, the temporary is not. IMHO, this precludes the possibility of copy-elision.

Answer 5

For a solution that will work with pre-c++11 code, you may consider using boost::function along with boost::ref(as boost::reference_wrapper alone doesn't has an overloaded operator(), unlike std::reference_wrapper which indeed does). From this page http://www.boost.org/doc/libs/1_55_0/doc/html/function/tutorial.html#idp95780904, you can double wrap your functor inside a boost::ref then a boost::function object. I tried that solution and it worked flawlessly.

For c++11, you can just go with std::ref and it'll do the job.