14

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?

Community
  • 1
  • 1
einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 1
    futures are for waiting for the result of some (possibly asynchronous) process. They are single-use and quite heavyweight. If you're looking for lazy evaluation in the same thread, probably not what you need. There is a library called boost.outcome being developed. It's essentially lightweight futures (not designed for cross-thread work). If you want to repeatedly call your lazy function, then a function object or lambda is probably suitable. You may also want to look at boost.hana or similar. – Richard Hodges Jan 31 '17 at 10:52

3 Answers3

14

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.

alexeykuzmin0
  • 6,344
  • 2
  • 28
  • 51
  • (1) Your cached_lambda is not thread-safe, in the sense that you might be calling the lambda twice from different threads. Also, you forgot to set `calculated` to `true` (will edit that part at least). (2) But what guarantees do I have about when the future actually gets executed? How do I know it's actually lazy? – einpoklum Jan 31 '17 at 11:02
  • 1
    @einpoklum "the task is executed on the calling thread the first time its result is requested (lazy evaluation)" - cited from http://en.cppreference.com/w/cpp/thread/launch Will update the answer after finding a confirmation in standard. – alexeykuzmin0 Jan 31 '17 at 11:10
  • 1
    @einpoklum You're right about (1), and it's an additional reason to use `std::future`. – alexeykuzmin0 Jan 31 '17 at 11:11
  • It is not just thread-unsafe, it us incorrect and has nothing to do with lazy evaluation whatsoever. Lambdas are functions that can be nested in a block scope, nothing more. You don't call `printf` or `sin` or `rand` lazy, and it makes no sense to wrap them in a call-ince adapter. – n. m. could be an AI Jan 31 '17 at 11:42
  • 2
    @n.m: `printf` and `sin` take parameters, and `rand` is called in large part for its side-effects (specifically for the fact that calling it twice typically yields different results). `std::bind(sin, 1)` might well be called lazy, and it may or may not make sense to wrap it in a call-once adaptor (or otherwise to memoize `sin` or something that uses it). The adaptor should be called `memoize_nullary` rather than `cached_lambda`, though :-) – Steve Jessop Jan 31 '17 at 13:18
  • @SteveJessop That's the point, it makes sense to talk about laziness only in context of pure evaluation, otherwise memoisation is not transparent. Call it delayed computation or something. – n. m. could be an AI Jan 31 '17 at 13:51
5

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.

Jon Chesterfield
  • 2,251
  • 1
  • 20
  • 30
  • Well, what about the [`std::launch::deferred](http://en.cppreference.com/w/cpp/thread/launch) for futures, which doesn't start the evaluation going like I had assumed in the question, but rather waits until they're needed? That's also a part, or an aspect, of the promise/future model. ... or - is it just like that in the C++ implementation rather than in the literature? – einpoklum Jan 31 '17 at 11:35
  • What about it in particular? std::launch offers async or lazy evaluation, but doesn't support async-eval-only-when-necessary via the current API. – Jon Chesterfield Jan 31 '17 at 12:56
  • In functional programming, I think I heard what you call "memoization" to be called "sharing" instead. By comparison, "memoization" is a technique to save function return values so that they won't be recomputed again, possibly turning e.g. `fib(n)=fib(n-2)+fib(n-1)` into a linear algorithm (instead of an exptime one). So "memoization" is more like dynamic programming, from what I heard. Still, you are correct in the sense that both approaches are saving the computation result in a cache that can be accessed later on. (+1) – chi Jan 31 '17 at 16:50
0

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.

John G.
  • 1