6 Lazy evaluation

This chapter introduces lazy evaluation in C++ as a practical way to defer work until results are actually needed and to remember those results once computed. Because C++ lacks built-in laziness, the approach is to model it with templates, lambdas, and thread-safe primitives so expensive computations aren’t performed prematurely or repeatedly. The core idea marries on-demand calculation with memoization, and it works best when computations are pure, ensuring delayed evaluation doesn’t change outcomes due to intervening side effects.

The text develops a reusable lazy_val wrapper that stores a computation, exposes a value-like interface, and caches the first result, first with a mutex and then more efficiently with std::call_once. It then shows laziness as an optimization technique: a lazy variant of quicksort that partitions eagerly but only fully sorts the partitions that will be shown (e.g., top-k), improving work to roughly O(n + k log k); user-interface views that fetch and cache data and images on demand rather than loading everything up front; and pruning recursion by caching results of pure functions. Classic examples include memoizing Fibonacci (first with a vector cache, then with a two-value rolling cache) and framing dynamic programming as systematic memoization for problems like the Levenshtein distance, where a matrix stores intermediate results to avoid exponential recomputation.

To generalize, the chapter introduces memoization utilities: one that wraps ordinary functions in a cache keyed by argument tuples, and a more sophisticated helper that supports recursive functions by injecting a memoized “self” into recursive calls. Finally, it applies laziness to expression construction with expression templates, building a deferred string-concatenation tree that computes total size once and performs a single allocation and copy, eliminating chains of temporaries. The discussion closes with cautions: storing references in deferred expressions can violate expectations if lifetimes or values change, reinforcing that lazy techniques depend on purity, careful cache design, and thread-safe initialization to be both correct and efficient.

When sorting just a part of the collection, you can optimize the quicksort algorithm not to recursively call itself for the partitions that don’t need to be sorted.

You don’t need to get the data that’s not shown to the user. You can fetch the required information when it’s needed.

With fib implemented recursively, you calculate the same value more than once. The recursion tree that calculates fib(5) contains three identical subtrees calculating fib(2) and two identical subtrees calculating fib(3). The multiplication of work grows exponentially with n.

With fib implemented lazily, you can avoid evaluating the same trees over and over. If one branch calculates fib(2), other branches will use the previously calculated value. Now, the number of nodes this tree has grows linearly with n.

Each invocation of lev(m, n) calculates the minimum distance for all paths whose last operation is addition, for all paths whose last operation is removal, and for all paths whose last operation is replacing a character.

When you concatenate strings eagerly, you may need to allocate new memory if the previous buffer isn’t large enough to store the concatenated string.

Instead of generating a string, operator+ generates an object that remembers which strings should be concatenated. When you need to create the resulting string, you’ll know the exact size of the buffer you need to generate.

• Executing code lazily and caching results can significantly improve the speed of your programs.
• It’s not often easy (and sometimes not even possible) to construct lazy variants of algorithms you use in your programs, but if you manage to do it, you can make your programs much more responsive.
• A big class of algorithms has exponential complexity that can be optimized to be linear or quadratic just by caching intermediary results.
• Levenshtein distance has many applications (in sound processing, DNA analysis, and spell checking, for instance) but can also find its place in regular programs. When you need to notify the UI of changes in a data model, it’s useful to be able to minimize the number of operations the UI needs to perform.
• Although you should write the caching mechanisms for each problem separately, it’s sometimes useful to have functions such as make_memoized to benchmark the speed gain you could achieve by caching function results.
• Expression templates are a powerful mechanism for delaying computation. They’re often used in libraries that operate on matrices, and other places where you need to optimize expressions before handing them to the compiler.

FAQ