Efficient, configurable functions with constexpr and std::optional

Introduction

I was hacking around with a personal project and bumped into a cool thing with constexpr, std::optional, and lambdas. Maybe it’s a well known interaction, but I thought I’d write a post either way!

The project in question was a library which contains an algorithm that can be parameterised by the user through options. These options are just struct instances which are pretty trivial, plain old data, and compile-time constructable.

In one specific instance, I reached the point of wanting to add a termination check to the algorithm. At a domain level, there are many different reasons that the algorithm could terminate. Clearly, we would need to parameterise our algorithm with some domain specific termination criteria, or it probably wouldn’t give us any meaningful answers! However, to keep this generic, let’s focus on two extremely common criteria for potentially long-running, iterative algorithms: exceeding either a specified wall clock time or number of iterations.

#include <cstdint>
#include <chrono>

struct TerminationCriteria
{
  std::uint32_t NumberOfIterations{1000u};
  std::chrono::duration<float> MaxWallClockTime{std::chrono::hours{1}};
  // Domain specific stuff here like tolerances, etc. ...
};

This is easy to instantiate at compile time and pass to our algorithm but here’s the thing: we could validly have one or none or both of these criteria set. For example, we have a long running algorithm but really need a coffee so choose to impose no limits on the algorithm whilst we re-caffeinate! In all seriousness, we now have a model that implies that we should initialise all of these options, even though we have just said this is not the case. So already, the code is capturing intent badly.

Maybe we could wrap them in std::optional?

#include <cstdint>
#include <chrono>
#include <optional>

struct TerminationCriteria
{
  std::optional<std::uint32_t> NumberOfIterations{1000u};
  std::optional<std::chrono::duration<float>> MaxWallClockTime{std::nullopt};
  // Domain specific stuff here like tolerances, etc. ...
};

This gives us some nicer intent capture and because std::optional itself has great constexpr support, we aren’t losing compile time semantics either! I was also able to change my defaults clearly without resorting to max values or hand-picked sentinels.

Implementation

Now, we can roll our options into a termination check and leverage the constexpr-ness of the options provided in the TerminationCriteria instance. For this, let’s introduce a magic new struct that will be passed to our termination check. This will contain the pertinent data for checking the state of the algorithm at runtime.

#include <cstdint>
#include <chrono>

struct TerminationData
{
  std::uint32_t CurrentNumberOfIterations{0u};
  std::chrono::duration<float> CurrentWallClockTime{std::chrono::seconds{0}};
};

From here, we can initialise something invocable from our TerminationCriteria. This will be our runtime check, so it will take a TerminationData instance and check for termination. I’m going to just write a function that returns a lambda for the sake of simplicity. Anything invocable that can be created and initialised in a constexpr way should be fine!

Let’s lay out the implementation of the returned lambda briefly in text. We will check each of the optional termination criteria has a value. If it does, we will perform the check associated with that criterion. If we realise we should terminate the algorithm in accordance with any of the criteria, we will return true. If we make it to the end of the termination check without this occurring, we will return false.

The implementation for this is as simple as you would expect! Note: we need to capture terminationCriteria by value or we can’t assign the return value of this factory function to an auto constexpr lambda.

constexpr auto GetTerminationFunction(TerminationCriteria const& terminationCriteria)
{
  return [terminationCriteria](TerminationData const& terminationData) -> bool
  {
    if (terminationCriteria.NumberOfIterations.has_value() &&
        terminationData.CurrentNumberOfIterations >= terminationCriteria.NumberOfIterations.value())
      return true;

    if (terminationCriteria.MaxWallClockTime.has_value() &&
        terminationData.CurrentWallClockTime >= terminationCriteria.MaxWallClockTime.value())
      return true;

    // Todo: Other domain specific checks here...

    return false;
  };
}

As an aside, we could easily add much richer information by returning an enum value containing the reasoning behind the decision whether or not to terminate.

The benefit of this approach is that for constexpr callers, the compiler can short-circuit the .has_value() check of any termination criteria with a value of std::nullopt. For runtime consumers, we won’t know if the call to a given termination criterion is required, but we will have some expressive code!

If you want to check an example of this in action, try this code snippet in Godbolt. You should see that the compiler can nicely propagate the constant std::optional instance (even when the function is not constantly evaluated!).

Here’s the linked example in text:

#include <optional>
#include <iostream>

constexpr bool IsIterationsExceeded(std::optional<int> maxIterations, int currentIterations) {
  if (maxIterations.has_value())
    return currentIterations >= maxIterations.value();
  return false;
}

int main() {
  std::optional constexpr maxIterations = 100;
  int iterations = 0;
  std::cin >> iterations;

  std::cout << std::boolalpha << IsIterationsExceeded(maxIterations, iterations);

  return 0;
}

Conclusion

I hadn’t though of using the constexpr-ness of std::optional to generate better functions in a “one or many of these conditions” situation, so this was an interesting exercise! I’m not sure how useful this will turn out to be in practice. In some domains, algorithm specific parameters are fixed for releases so this pattern might find some use in those limited cases.

The termination check example given herein is probably not the best candidate for caring about micro-optimising the performance of the function. Hopefully it illustrates the broader point about applying this pattern though!

This approach does certainly have some notable flaws however.

The most notable, is that the configuration struct must be compile-time constructable. This might be a problem if you need dynamic collections or more complicated data structures. Furthermore, users are likely to want to sweep domain-specific configuration options for experimentation. To this end, they may be read from a file or other external source at runtime, which would preclude this approach entirely.

Perhaps a smaller, but still worthy consideration is that we incur a size penalty by wrapping things in std::optional. From cppreference:

If an optional contains a value, the value is guaranteed to be allocated as part of the optional object footprint, i.e. no dynamic memory allocation ever takes place.

Lastly, your code might be less obvious to future readers. I suppose this is a bit subjective in general, but adding has_value() calls everywhere inside a returned lambda is hardly a textbook code example.

Full Code Example

#include <optional>
#include <iostream>
#include <vector>
#include <cstdint>
#include <chrono>

using namespace std::chrono_literals;

struct TerminationCriteria
{
  std::optional<std::uint32_t> NumberOfIterations{1000u};
  std::optional<std::chrono::duration<float>> MaxWallClockTime{std::nullopt};
  // Domain specific stuff here like tolerances, etc. ...
};

struct TerminationData
{
  std::uint32_t CurrentNumberOfIterations{0u};
  std::chrono::duration<float> CurrentWallClockTime{std::chrono::seconds{0}};
};

constexpr auto GetTerminationFunction(TerminationCriteria const& terminationCriteria)
{
  return [terminationCriteria](TerminationData const& terminationData) -> bool
  {
    if (terminationCriteria.NumberOfIterations.has_value() &&
        terminationData.CurrentNumberOfIterations >= terminationCriteria.NumberOfIterations.value())
      return true;

    if (terminationCriteria.MaxWallClockTime.has_value() &&
        terminationData.CurrentWallClockTime >= terminationCriteria.MaxWallClockTime.value())
      return true;

    // Other domain specific checks here...

    return false;
  };
}

int main() {
    std::cout << std::boolalpha;

    TerminationData terminationData { 2, 2s };

    // No checks.
    TerminationCriteria constexpr noChecksCriteria{std::nullopt, std::nullopt};
    auto constexpr noChecksLambda = GetTerminationFunction(noChecksCriteria);
    std::cout << noChecksLambda(terminationData) << "\n";

    // Just iterations.
    TerminationCriteria constexpr iterationCheckCriteria{1, std::nullopt};
    auto constexpr iterationCheckLambda = GetTerminationFunction(iterationCheckCriteria);
    std::cout << iterationCheckLambda(terminationData) << "\n";

    // Just time.
    TerminationCriteria constexpr timeCheckCriteria{std::nullopt, 1s};
    auto constexpr timeCheckLambda = GetTerminationFunction(timeCheckCriteria);
    std::cout << timeCheckLambda(terminationData) << "\n";

    // Both checks. 
    TerminationCriteria constexpr bothChecksCriteria{1, 1s};
    auto constexpr bothChecksLambda = GetTerminationFunction(bothChecksCriteria);
    std::cout << bothChecksLambda(terminationData) << "\n";

    return 0;
}