Lazy evaluation in C++14/17 - just lambdas or also futures etc.?

Question

I just read:

Lazy Evaluation in C++

and noticed it's kind of old and most of the answers regard pre-2011 C++. These days we have syntactic lambdas, which can even deduce the return type, so lazy evaluation seems to boil down to just passing them around: Instead of

auto x = foo();

you execute

auto unevaluted_x = []() { return foo(); };

and then evaluate when/where you need to:

auto x = unevaluted_x();

Seems like there's nothing more to it. However, one of the answers there suggests using futures with asynchronous launching. Can someone lay out why/if futures are significant for lazy-evaluation work, in C++ or more abstractly? It seems as though futures may very well be evaluated eagerly, but simply, say, on another thread, and perhaps with less priority than whatever created them; and anyway, it should be implementation-dependent, right?

Also, are there other modern C++ constructs which are useful to keep in mind in the context of lazy evaluation?

Answer 1

In a multithreaded application where simultaneous requests are made for data that takes a lot of effort to prepare, thread-safe memoization can be used so that users not only avoid redoing work that's already been performed but avoid starting their own version of work that's already in progress.

Using a future or futures to deliver the data is the easy part: C++ already has that implemented. The tricks are (a) find a way to ensure that multiple threads asking for the same data create objects that will be treated as equivalent (or identical) keys in a map... this would be up to the user... and (b) using a concurrent map with that key and with a future as data. At most one simultaneously executed insert, emplace or try_emplace attempted with the same key would be able to insert a key-value pair and all of them would return an iterator to the same key-value pair (which could have been in the map already for some time). Using an std::unordered_map with a mutex would work, but it doesn't scale very well. Java already has concurrent maps with excellent performance in these situations: C++ needs the same, preferably in the Standard Library, as soon as possible.

Answer 2

When you write

auto unevaluted_x = []() { return foo(); };
...
auto x = unevaluted_x();

Each time you want to get the value (when you call unevaluated_x) it's calculated, wasting computational resources. So, to get rid of this excessive work, it's a good idea to keep track whether or not the lambda has already been called (maybe in other thread, or in a very different place in the codebase). To do so, we need some wrapper around lambda:

template<typename Callable, typename Return>
class memoized_nullary {
public:
    memoized_nullary(Callable f) : function(f) {}
    Return operator() () {
        if (calculated) {
            return result;
        }
        calculated = true;
        return result = function();
    }
private:
    bool calculated = false;
    Return result;
    Callable function;
};

Please note that this code is just an example and is not thread safe.

But instead of reinventing the wheel, you could just use std::shared_future:

auto x = std::async(std::launch::deferred, []() { return foo(); }).share();

This requires less code to write and supports some other features (like, check whether the value has already been calculated, thread safety, etc).

There's the following text in the standard [futures.async, (3.2)]:

If launch::deferred is set in policy, stores DECAY_COPY(std::forward<F>(f)) and DECAY_COPY(std::forward<Args>(args))... in the shared state. These copies of f and args constitute a deferred function. Invocation of the deferred function evaluates INVOKE(std::move(g), std::move(xyz)) where g is the stored value of DECAY_COPY(std::forward<F>(f)) and xyz is the stored copy of DECAY_COPY(std::forward<Args>(args)).... Any return value is stored as the result in the shared state. Any exception propagated from the execution of the deferred function is stored as the exceptional result in the shared state. The shared state is not made ready until the function has completed. The first call to a non-timed waiting function (30.6.4) on an asynchronous return object referring to this shared state shall invoke the deferred function in the thread that called the waiting function. Once evaluation of INVOKE(std::move(g),std::move(xyz)) begins, the function is no longer considered deferred. [ Note: If this policy is specified together with other policies, such as when using a policy value of launch::async | launch::deferred, implementations should defer invocation or the selection of the policy when no more concurrency can be effectively exploited. —end note ]

So, you have a guarantee the calculation will not be called before it's needed.

Answer 3

There are a few things going on here.

Applicative order evaluation means evaluating arguments before passing them into a function. Normal order evaluation mean passing the arguments into a function before evaluating them.

Normal order evaluation has the benefit that some arguments are never evaluated and the drawback that some arguments get evaluated over and over again.

Lazy evaluation usually means normal order + memoization. Postpone evaluation in the hope that you don't have to evaluate at all, but if you do need to, remember the result so you only have to do it once. The important part is evaluating a term never or once, memoization is the easiest mechanism to provide this.

The promise/future model is different again. The idea here is to start an evaluation going, probably in another thread, as soon as you have enough information available. You then leave looking at the result for as long as possible to improve the chances that it's already available.

---

The promise/future model has some interesting synergy with lazy evaluation. The strategy goes:

1. Postpone evaluation until the result will definitely be needed
2. Start the evaluation going in another thread
3. Do some other stuff
4. The background thread completes and stores the result somewhere
5. The initial thread retrieves the result

Memoization can be neatly introduced when the result is produced by the background thread.

Despite the synergy between the two, they're not the same concept.