Posts Tagged ‘Lambdas’

This post is just a reminder to myself because I fell for it, again…Well, let me step back and explain the scenario.

Suppose we are using this generic approach for memoization:

template <typename R, typename... Args>
auto memoize(R(*fn)(Args...))
{
    std::map<std::tuple<Args...>, R> table;
    return [fn, table](Args... args) mutable -> R {
        auto argt = std::make_tuple(args...);
        auto memoized = table.find(argt);
        if(memoized == table.end())
        {
            auto result = fn(args...);
            table[argt] = result;
            return result;
        }
        else
        {
            return memoized->second;
        }
    };
}

Suppose also – at some point – two new requirements pop up:

  • ability to remove/update some entries of the table – because something changes somewhere else and those results become old,
  • ability to switch to other functions (the table is not needed there).

We decide to store the table and the lambda into a struct. For the sake of simplification, this is a specialized version of such a class using a toy-function simulate:

struct Memoization
{
    Memoization()
    {
        calc = [this](int i)
        {
            auto memoized = table.find(i);
            if(memoized == table.end()) {
                auto result = simulate(i); // <- somewhere
                table[i] = result;
                return result;
            } else {
                return memoized->second;
            }
        };
    }

    function<int(int)> calc;
    std::map<int, int> table;
};

Even if this design is probably silly, we can easily satisfy both the requirements (e.g. calc can be set to something else, and table is fully accessible).

This code is fine for rapid prototyping, so we don’t refactor it yet but instead we experiment a bit more. For example, we create a factory for creating different Memoization instances depending on some configuration. Each configuration merely results in a new core function to use (e.g. remember the second requirement). Since it’s prototyping, we leave the constructor as is and we instead set the function by hand:

Memoization CreateMemo(const Configuration& config)
{
   Memoization memo;
   // using config to create memo
   // e.g. memo.calc = ...
   return memo;
}

We try this code and we note that it behaves differently on two compilers: on Visual Studio 2013 we get a crash at some point while calling calc(), instead on clang it seems to work smoothly. We start debugging and we immediately spot what’s going on…Do you note that we are one step away from falling into a dangling reference problem? Actually, this accident happens on both clang and Visual Studio, but some (un)lucky condition makes this work on the former.

The culprit – in this case – is RVO, but the issue is…both capturing this into calc – that is a member variable – and copying/moving *this.

By capturing this, we have coupled calc to this->table, that won’t change anymore – say when you do move (or copy). this has not special treatment inside the callable object created by the lambda expression. It’s just a Memoization pointer and when the lambda gets moved (or copied), so does the pointer. Shallowly.

In our factory function, RVO is probably working a bit differently between clang and VS. VS is not using RVO here, clang instead uses RVO and the problem is apparently concealed. By disabling RVO on clang (e.g. -fno-elide-constructors), we get the same problem found on VS.

Did you get the point? In case of the original “memoized” version of calc (which captures this), after the move (or the copy), the returned Memoization instance has a reference to the local memo->table, not to the new one. Finally, the local temporary instance is destroyed and we get a dangling reference. This problem is subtle since the code could still “work” under certain conditions – e.g. RVO. It should be clear that copying instead of moving has the same effect.

Maintaining the original design, the problem can be quickly solved, for example by constructing the object directly:

class Memoization
{
public:
   Memoization()
   {
    // same as before
   }

   Memoization(function<int(int)> calcFn)
      : calc(calcFn)
   {
   // ...
   }
// ...
};

Memoization CreateMemo(const Configuration& config)
{
   if (config. ...)
      return {...} // won't copy nor move
   //...
}

But the main issue holds and this could lead to disaster:

Memoization m1;
auto m2 = m1; // [this] in m2.calc points to m1

Not only is it dangerous, but also wrong: you probably expect each Memoization instance has its own copy of the table – i.e. for this reason a solution – say – with shared ownership of the table doesn’t fit well.

At the end of the story we changed our design and we came up with another better solution. But this is not the main point of the article. Even if my example is probably goofy, this experience left a valuable lesson: capturing this into a member variable lambda is valid C++ code and may cause headache if we copy/move *this. Sometimes I think we have a duty to set some limits, for preventing traps other people could fall into. For this reason, I came to a couple of observations:

(You understand that moving instead of copying does not twist the meaning, so let me just mention copying so I do not need to write copy/move every time).

First, we usually don’t need to capture this into a member variable lambda at all. Exploring better ways is always more advisable.

Some of you could still complain that C++ is missing an opportunity by letting this behavior go undisturbed. You could expect the compiler magically sets the this pointer to the copied instance, don’t you? Honestly, I have no strong opinions on that, I’m just thinking aloud.

Second: we can judge pragmatically. Capturing this into a member variable lambda and copying *this just do not get along. Doing either is realistically better than adding some special treatment.

For this reason, I see a terse idiom: either capture this into a member variable lambda or copy *this (or neither).

This is eventually another subtle case the Rule of Zero does not cover and – in case you cannot live without capturing this – I think deleting copy and move operations in the host class is such a desirable design decision to apply (and to document?) – being understood that maybe you don’t need to capture this into a member variable lambda at all.

Advertisements

I think one of the most attractive feature of C++11 is about lambdas. They simplify and encourage the usage of STL algorithms more than before, and they (may) increase programmers productivity. Lambdas combine the benefits of function pointers and function objects: like function objects, lambdas are flexible and can maintain state, but unlike function objects, their compact syntax don’t require a class definition.

The syntax is simple:

auto aLambda = [ ] ( const string& name ) { cout << "hello " << name << endl; }
aLambda("Marco"); // prints "hello Marco"

The code above defines a lambda with no return value and receiving a const string& parameter. What about the “[ ]”? That identifier is the capture specification and tells the compiler we’re creating a lambda expression. As you know, inside the square brakets you can “capture” variables from the outside (the scope where the lambda is created). C++ provides two ways of capturing: by copy and by reference. For example:

string name = "Marco";
auto anotherLambda = [name] { cout << "hello " << name << endl; }
anotherLambda(); // prints "hello Marco"

This way the string is copied into the state of anotherLambda, so it stays alive until anotherLambda goes out of scope (note: you can omit the brackets if the lambda has no parameters). Differently:

string name = "Marco";
auto anotherLambda = [&name] () { cout << "hello " << name << endl; }
anotherLambda(); // prints "hello Marco"

The only difference is the way we capture the string name: this time we do by reference, so no copy is involved and the behavior is like passing a variable by reference. Obviously, if name is destroyed before the lambda is executed (or just before name is used): boom!

After this introduction, in this post  I’m going to discuss about an issue on capturing I encountered few days ago at work: what if I want to capture by moving an object instead of both copying and referencing? Consider this plausible scenario:

function<void()> CreateLambda()
{
   vector<HugeObject> hugeObj;
   // ...preparation of hugeObj...

   auto toReturn = [hugeObj] { ...operate on hugeObj... };
   return toReturn;
}

This fragment of code prepares a vector of HugeObject (e.g. expensive to copy) and returns a lambda which uses this vector (the vector is captured by copy because it goes out of scope when the lambda is returned). Can we do better?

Yes, of course we can!” – I heard. “We can use a shared_ptr to reference-count the vector and avoid copying it“:

function<void()> CreateLambda()
{
   shared_ptr<vector<HugeObject>> hugeObj(new vector<HugeObject>());
   // ...preparation of hugeObj...

   auto toReturn = [hugeObj] { ...operate on hugeObj via shared_ptr... };
   return toReturn;
}

I honestly don’t like the use of shared_ptr here but this should work well. The subtle (possible) aspect of this attempt is about style and clarity: why is the ownership shared? Why can’t I treat hugeObj as a temporary to move “inside” the lambda? I think that using a sharing mechanism here is like a hack to fill a gap of the language. I don’t want the lambda to share hugeObj with the outside, I’d like to “prevent” this:

function<void()> CreateLambda()
{
   shared_ptr<vector<HugeObject>> hugeObj(new vector<HugeObject>());
   // ...preparation of hugeObj...

   auto toReturn = [hugeObj] { ...operate on hugeObj via shared_ptr... };
   (*hugeObj)[0] = HugeObject(...); // can alter lambda's behavior
   return toReturn;
}

I need a sort of “capture-by-move”, so:

  1. I create the vector
  2. I “inject” it in the lambda (treating the vector like a temporary)
  3. (outside) the vector will be in a “valid but unspecified state” (what standard says about moved objects)
  4. nothing from the outside can alter the lambda’s vector

Since we are on the subject, getting rid of shared_ptr syntax (I repeat: here) should be nice!

To emulate a move capturing we can employ a wrapper that:

  • receives an rvalue reference to our to-move object
  • maintains this object
  • when copied, performs a move operation of the internal object

Here is a possible implementation:

#ifndef _MOVE_ON_COPY_
#define _MOVE_ON_COPY_

template<typename T>
struct move_on_copy
{
   move_on_copy(T&& aValue) : value(move(aValue)) {}
   move_on_copy(const move_on_copy& other) : value(move(other.value)) {}

   mutable T value;

private:

   move_on_copy& operator=(move_on_copy&& aValue) = delete; // not needed here
   move_on_copy& operator=(const move_on_copy& aValue) = delete; // not needed here

};

template<typename T>
move_on_copy<T> make_move_on_copy(T&& aValue)
{
   return move_on_copy<T>(move(aValue));
}
#endif // _MOVE_ON_COPY_

In this first version we use the wrapper this way:

vector<HugeObject> hugeObj;
// ...
auto moved = make_move_on_copy(move(hugeObj));
auto toExec = [moved] { ...operate on moved.value... };
// hugeObj here is in a "valid but unspecified state"

The move_on_copy wrapper works but it is not completed yet. To refine it, a couple of comments are needed. The first is about “usability“: the only aim of this class is to “replace” the capture-by-copy with the capture-by-move, nothing else. Now, the capture by move makes sense only when we operate on rvalues and movable objects, so is the following code conceptually correct?

// due to universal referencing, T is const T&, so no copy/move will be involved in move_on_copy's ctor
const vector<HugeObject> hugeObj;
auto moved = make_move_on_copy(hugeObj);
auto toExec = [moved] { ...operate on moved.value... };
// hugeObj here is the same as before

Not only is it useless, but also confusing. So, let’s impose our users to pass only rvalues:

template<typename T>
auto make_move_on_copy(T&& aValue)
     -> typename enable_if<is_rvalue_reference<decltype(aValue)>::value, move_on_copy<T>>::type
{
   return move_on_copy<T>(move(aValue));
}

We “enable” this function only if aValue is an rvalue reference, to do this we make use of a couple of type traits. Strangely this code does not compile on Visual Studio 2010, so, if you use it, try to settle for:

template<typename T>
move_on_copy<T> make_move_on_copy(T&& aValue)
{
   static_assert(is_rvalue_reference<decltype(aValue)>::value, "parameter should be an rvalue");
   return move_on_copy<T>(move(aValue));
}

You can also enforce the requirement about move-constructability by using other traits such as is_move_constructible, here I have not implemented it.

The second note is about compliance. Is the following code syntactically-clear?

vector<HugeObject> hugeObj;
auto moved = make_move_on_copy(move(hugeObj));
auto toExec = [moved]
  {
     moved.value[0] = HugeObject(...); // is it conform to standard lambda syntax?
  };

What aroused my suspicions was the syntax of lambda expressions: if you copy-capture an object, the only way to access its non-const members (aka: make changes) is to declare the lambda mutable. This is because a function object should produce the same result every time it is called. If we want to support this requirement then we have to make a little change:

template<typename T>
struct move_on_copy
{
   move_on_copy(T&& aValue) : value(move(aValue)) {}
   move_on_copy(const move_on_copy& other) : value(move(other.value)) {}

   T& Value()
   {
      return value;
   }

   const T& Value() const
   {
      return value;
   }

private:
   mutable T value;
   move_on_copy& operator=(move_on_copy&& aValue) = delete; // not needed here
   move_on_copy& operator=(const move_on_copy& aValue) = delete; // not needed here
};

And:

vector<HugeObject> hugeObj;
auto moved = make_move_on_copy(move(hugeObj));
// auto toExec = [moved]  { moved.Value()[0] = HugeObject(...); }; // ERROR
auto toExec = [moved] () mutable { moved.Value()[0] = HugeObject(...); }; // OK
auto toExec = [moved]  { cout << moved.Value()[0] << endl; }; // OK

If you want to play a bit, I posted a trivial example on ideone.

Personally I’m doubtful if this is the best way to capture expensive-to-copy objects. What I mean is that working with rvalues masked by lvalues can be a little bit harder to understand and then maintaining the code can be painful. If the language supported a syntax like:

HugeObject obj;
auto lambda = [move(obj)] { ... };
// obj was moved, it is clear without need to look at its type

It would be simpler to understand that obj will be in an unspecified state after the lambda creation statement. Conversely, the move_on_copy wrapper requires the programmer looks at obj’s type (or name) to realize it was moved and some magic happened:

HugeObject obj;
auto moved_obj = make_move_on_copy(move(obj)); // this name helps but it is not enough
auto lambda = [moved_obj] { ... };
// obj was moved, but you have to read at least two lines to realize it

[Edit]

As Dan Haffey pointed out (thanks for this) “the move_on_copy wrapper introduces another problem: The resulting lambda objects have the same weakness as auto_ptr. They’re still copyable, even though the copy has move semantics. So you’re in for trouble if you subsequently pass the lambda by value”. So, as I said just before, you have to be aware some magic happens under the hood. In my specific case, the move_on_copy_wrapper works well because I don’t copy the resulting lambda object.

Another important issue is: what semantics do we expect when a function that performed a capture-by-move gets copied? If you used the capture-by-move then it’s presumable you didn’t want to pay a copy, then why copying functions? The copy should be forbidden by design, so you can employ the approach suggested by jrb, but I think the best solution would be having the support of the language. Maybe in a next standard?

Since other approaches have been proposed, I’d like to share with you my final note about this topic. I propose a sort of recipe/idiom (I think) easy to use in existent codebases. My idea is to use my move_on_copy only with a new function wrapper that I called mfunction (movable function). Differently from other posts I read, I suggest to avoid rewriting a totally new type (that may break your codebase) but instead inherit from std::function. From a OO standpoint this is not perfectly consistent because I’m going to violate (a bit) the is-a principleIn fact, my new type will be non-copyable (differently from std::function).

Anyhow, my implementation is quite simple:

template<typename T>
struct mfunction;

template<class ReturnType, typename... ParamType>
struct mfunction<ReturnType(ParamType...)> : public std::function<ReturnType(ParamType...)>
{
  typedef std::function<ReturnType(ParamType...)> FnType;

  mfunction() : FnType()
  {}

  template<typename T>
  explicit mfunction(T&& fn) : FnType(std::forward<T>(fn))
  {}

  mfunction(mfunction&& other) : FnType(move(static_cast<FnType&&>(other)))
  {}

  mfunction& operator=(mfunction&& other)
  {
    FnType::operator=(move(static_cast<FnType&&>(other)));
    return *this;
  }

  mfunction(const mfunction&) = delete;
  mfunction& operator=(const mfunction&) = delete;
};

In my opinion, inheriting from std::function avoids reinventing the wheel and allows you to use mfunction where a std::function& is needed. My code is on ideone, as usual.

[/Edit]

Make the choice you like the most don’t forgetting readability and comprehensibility. Sometimes a shared_ptr suffices, even if it’s maybe untimely.

Lambdas are cool and it’s easy to start working with. They are very useful in a plenty of contexts, from  STL algorithms to concurrency stuff. When capturing by reference is not possible and capturing by copy is not feasible, you can then consider this “capture by move” idea and remember the language always offers the chance to bypass its shortcomings.