Speeding up C++ code with template lambdas

15 March 2025 · 5 min

Let us consider a simple C++ function which divides all values in a range of integers:

void divide(std::span<int> i, int d) {
    for (auto& value : i) {
        value /= d;
    }
}

A division between two integers is one of the most expensive operations you can do over integers: it is much slower than a multiplication which is, in turn, more expensive than an addition. If the divisor d is known at compile-time, this function can be much faster. E.g., if d is 2, the compiler might optimize away the division and use a shift and a few cheap instructions instead. The same is true with all compile-time constant: the compiler can often do better knowing the constant. (See Lemire et al., Integer Division by Constants: Optimal Bounds, 2021)

If the ‘divide’ function is inline and the divisor is known at compile time, then an optimizing compiler will do fine. But we cannot expect all our functions to get inline in practice.

In C++, a template function is defined using the template keyword followed by a parameter (usually a type parameter) enclosed in angle brackets < >. The template parameter acts as a placeholder that gets replaced with actual data type when the function is called.

In C++, you can turn the division parameter into a template parameter:

template <int d>
void divide(std::span<int> i) {
    for (auto& value : i) {
        value /= d;
    }
}

The template function is not itself a function, but rather a recipe to generate functions: we provide the integer d and a function is created. This allows the compiler to work with a compile-time constant, producing faster code.

If you expect the divisor to be between 2 and 6, you can call the template function from a general-purpose function like so:

void divide_fast(std::span<int> i, int d) {
    if(d == 2) {
        return divide<2>(i);
    }
    if(d == 3) {
        return divide<3>(i);
    }
    if(d == 4) {
        return divide<4>(i);
    }
    if(d == 5) {
        return divide<5>(i);
    }
    if(d == 6) {
        return divide<6>(i);
    }

    for (auto& value : i) {
        value /= d;
    }
}

You could do it with a switch/case if you prefer but it does not simplify the code significantly. The compiler can produce efficient code with a series of if clauses (e.g., a jump table).

Unfortunately we have to expose a template function, which creates noise in our code base. We would prefer to keep all the logic inside one function. We can do so with lambda functions.

In C++, a lambda function (or lambda expression) is an anonymous, inline function that you can define on-the-fly, typically for short-term use. Starting with C++20, you have template lambda expressions.
We can almost do it like so:
void divide_fast(std::span<int> i, int d) {
    auto f = [&i]<int divisor>() {
      for (auto& value : i) {
        value /= divisor;
      }
    };
    if(d == 2) {
        return f<2>();
    }
    if(d == 3) {
        return f<3>();
    }
    if(d == 4) {
        return f<4>();
    }
    if(d == 5) {
        return f<5>();
    }
    if(d == 6) {
        return f<6>();
    }

    for (auto& value : i) {
        value /= d;
    }
}
Unfortunately, it does not quite work. Given template lambda expressions, you cannot directly pass template parameters. In C++, lambdas are syntactic sugar for objects of an unnamed class (a closure type). This class has an overloaded function call operator, operator(), which is what gets invoked when you “call” the lambda like a function. For a generic lambda, the operator() is a template, and its signature depends on the template parameters provided. Thus you need to specialize the template with an ugly expression (‘operator()<params>’):
void divide_fast(std::span<int> i, int d) {
    auto f = [&i]<int divisor>() {
      for (auto& value : i) {
        value /= divisor;
      }
    };
    if(d == 2) {
        return f.operator()<2>();
    }
    if(d == 3) {
        return f.operator()<3>();
    }
    if(d == 4) {
        return f.operator()<4>();
    }
    if(d == 5) {
        return f.operator()<5>();
    }
    if(d == 6) {
        return f.operator()<6>();
    }

    for (auto& value : i) {
        value /= d;
    }
}

In practice, it might still be a good choice. It keeps all the messy optimization hidden inside your function.

In the specific case of this function, I can probably get the same compiled output without templates as remarked by Martin Leitner-Ankerl:

void divide_fast_simple(std::span<int> i, int d) {
    auto f = [&i](int divisor) {
    for (auto& value : i) {
        value /= divisor;
    }
    };
    if(d == 2) {
        return f(2);
    }
    if(d == 3) {
        return f(3);
    }
    if(d == 4) {
        return f(4);
    }
    if(d == 5) {
        return f(5);
    }
    if(d == 6) {
        return f(6);
    }

    for (auto& value : i) {
        value /= d;
    }
}

And if it works in your particular case, you should avoid templates.

At the other end of the spectrum, Paul Dreik suggests doing it with template metaprogramming and fold expression like so:

void divide_fast(std::span<int> i, int d) {
  auto implementation =
      [&i]<int... ints>(std::integer_sequence<int, 0, ints...>, 
                                                  int d) {
    auto specialized =
        [&i]<int static_divisor>(
              std::integral_constant<int, static_divisor>,
                                 int dynamic_divisor) {
          if (static_divisor == dynamic_divisor) {
            for (auto &value : i) {
              value /= static_divisor;
            }
            return true;
          }
          return false;
        };
    const bool handled =
        (specialized(std::integral_constant<int, ints>{}, d) || ...);

    if (!handled) {
      // resort to dynamic calculation
      for (auto &value : i) {
        value /= d;
      }
    }
  };
  implementation(std::make_integer_sequence<int, 5>(), d);
}

It is likely overkill in this example, but template metaprogramming becomes handy with more challenging problems.

Daniel Lemire, "Speeding up C++ code with template lambdas," in Daniel Lemire's blog, March 15, 2025, https://lemire.me/blog/2025/03/15/speeding-up-c-code-with-template-lambdas/.
[BibTeX]

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

24 thoughts on “Speeding up C++ code with template lambdas”

  2. What are you talking about? Division only takes one instruction, making this in templates is waste of time and only puts more work on the compiler. If you tested this on Debug mode then lol

    Reply

    1. I didn’t take as the intention is to actually make a division. I thought it was showing the process, then you can adapt the division part to your actual case

      Reply

    2. This is a microoptimization but the thing is that. A. Division is a very expensive instruction which burns a lot of CPU cycles. B. If the divider is known on compile time, the compiler can replace the division with a much less expensive operation such as a a shift or a fixed.point multiplication + shift.

      I had to do something like this once in a company for transforming big chunks of data very fast in real time. I did not use this exact method though.

      Reply

    5. Not all instructions are created equal. Historically, division has been the among the slowest operations, and this holds true today. I don’t have the numbers to hand, but DIVQ was something like 100 cycles on Haswell? You can check Agner Fog for more up to date processors.

      A shift, by contrast, is far, far faster.

      Reply

      1. In the example of integer division, do constructs like constexpr/consteval not work in place of template lambdas? I haven’t benchmarked myself, but this seems like a place where the roles overlap.

        Reply

        1. Please see this paragraph in the article:

          “If the ‘divide’ function is inline and the divisor is known at compile time, then an optimizing compiler will do fine. But we cannot expect all our functions to get inline in practice.”

          Reply

  3. Sorry but this post is not helpful at all. As mentioned in the previous comment, division is one instruction. All this is doing is massively obslfuscating a simple task. Compile in release mode for benchmarks.

    Reply

    1. Each instruction has a latency in cycles. X86 multiplication IMUL is 3 cycles, while division IDIV is up to 90 cycles – i.e. 30 times slower.

      Reply

  4. I don’t think you need a template at all. Just use a lambda, the compiler should be smart enough to see you pass in a constant and optimize accordingly.

    Reply

  5. This isn’t unrolling a loop. In fact, I think this code would operate slower with the comparisons before execution of the single-operation division. You say your research is focused on what now?

    Reply

  8. If you can compute 1/d as a scale multiply, just compute that at the beginning of the whole thing and do that each time.

    Reply

  9. Hi Daniel,
    Boost has mp11 library that in my opinion makes this much nicer than “manual” code:

    https://godbolt.org/z/xMdcqKj96

    I did not check the asm in detail, so it is possible it does not optimize well, but from what I see code is generated per special case.

    Reply

  10. Seems like a good programming language would allow the compiler to make such optimizations without our help. Posts like this remind me of the box C++ has us in. I like C++ and mostly only program in it but perhaps it is time to take it in a different direction.

    Reply

  11. Just quickly, some who have replied to this thread do not seem to understand the use case. Imagine a copy routine (memcpy) that wishes to use different instructions based on the alignment of the pointer (common case)…

    I think the approach bellow is more readable/maintainable. You would expect any decent optimiser to be able to “see through” the “value_or” function.
    =========
    // use std::optional and value or to chain together exceptional values
    #include
    #include

    template
    std::optional inline DivideImp(int v, int divisor) {
    if (divisor == Divisor) {
    std::cout << "Special:" << Divisor << "=";
    return v / Divisor;
    }
    return {};
    }

    int inline DivideFull(int v, int divisor) {
    std::cout << "Generic:" << "=";
    return v / divisor;
    }

    inline int Divide(int v, int divisor)
    {
    // List of
    return
    DivideImp(v, divisor).value_or(
    DivideImp(v, divisor).value_or(
    DivideImp(v, divisor).value_or(
    DivideImp(v, divisor).value_or(
    DivideFull(v, divisor)
    ))));
    }

    int main() {
    for (int i = 1; i < 10;++i)
    std::cout << Divide(100, i) << "\n";
    return 0;
    }

    Reply

Leave a Reply

Your email address will not be published.

You can also subscribe by email to this blog (non-commercial, no ads, weekly email).

How to post code (C, C++, Java, Python, etc.):

Wrap your code in backticks, like this:

`int main() {
    return 0;
}`