How to unroll nested for loops in c++?

Question

I want to unroll the below nested loop at compile time. I have some code and a condition after every 'for' loop as shown in the code snippet below. I found ways to unroll it without any code (and conditions) between nested 'for' loops using template metaprogramming, but that did not help for my use case. I am looking for a way for my below example. I would really appreciate your help!

for (i=0;i<2;i++)
{
  //some code
  if (some condition using i)
  { 
    for(j=0;j<12;j++)
    {
       //some code
       if (another condition using j)
       {
         for(k=0;k<10;k++)
         {
           //some code
         }
       }
     }
   }
}

score 3 · Answer 1 · answered Oct 01 '20 at 15:33

3

Compile with optimization on (e.g. -O3 -march=native), the compiler will not only unroll but transpose, vectorize or sometimes entirely eliminate loops for you.

To ensure code quality, regularly check the generated assembly of critical code, e.g. on https://gcc.godbolt.org/.

answered Oct 01 '20 at 15:33

rustyx

80,671
25
200
267

[It seem that the loop is not unrolled](https://gcc.godbolt.org/z/Ganr47), surely because the optimizer thinks the function would be too big. – Guillaume Racicot Oct 01 '20 at 16:28

lars · Answer 2 · 2020-10-01T15:46:22.880

I leave it as a challenge to you to support custom increment and start value. If your conditions are runtime, just pass N to F and implement the condition in the lambda.

This is more a template demonstration, i agree with rustyx. Let the compiler optimize it for you.

#include <iostream>

template<unsigned N>
struct IsOdd
{
    static constexpr bool value = N % 2 == 0; 
};    

template<unsigned N, typename F, template <unsigned> typename Condition>
struct RepeatIfHelper
{
    void operator()(F f)
    {
        if constexpr(Condition<N>::value)
        {
            f();
        }        
        RepeatIfHelper<N-1, F, Condition>()(f);
    }
};

template<typename F, template <unsigned> typename Condition>
struct RepeatIfHelper<0, F, Condition>
{
    void operator()(F f)
    {
        if constexpr(Condition<0>::value)
        {
            f();
        }
    }    
};

template<unsigned N, template <unsigned> typename Condition, typename F>
void RepeatIf(F f)
{
    RepeatIfHelper<N, F, Condition>()(f);
}

int main()
{
    RepeatIf<7, IsOdd>([](){ 
        RepeatIf<5, IsOdd>([](){
            RepeatIf<3, IsOdd>([](){
                std::cout << "Hi" << std::endl;
            });
        });
    });
}

this is great, thanks! Though I have a question - if I have some logic between two nested 'for' loops as I mentioned in my post "//some code", how to achieve it in your example? — coder, Oct 02 '20 at 12:48

score 0 · Answer 3 · answered Oct 01 '20 at 15:06

0

In simple cases, the compiler will do it instead of you. But one may use a compiler directive #pragma unroll. This post may be helpful - What does #pragma unroll do exactly? Does it affect the number of threads?

answered Oct 01 '20 at 15:06

spiridon_the_sun_rotator

774
10
20

score 0 · Answer 4 · answered Dec 04 '21 at 22:44

To get an idea of how you can do this, here's an example where I generate the print commands to display a 2d matrix:

#include <utility>
#include <iostream>

template <std::size_t... Xs, std::size_t... Ys>
void unroll_cartesian_impl(
    std::index_sequence<Xs...> const&, 
    std::index_sequence<Ys...> const&)
{
    auto print_row = [](std::size_t row, auto... cols) {
        (std::printf("(%lu, %lu)\n", row, cols), ...);
    };
    
    (print_row(Xs, Ys...), ...);
}

template <std::size_t X, std::size_t Y>
void unroll_cartesian()
{
    unroll_cartesian_impl(
        std::make_index_sequence<X>{},
        std::make_index_sequence<Y>{});
}

int main ()
{
    unroll_cartesian<3, 3>();
}

Output

(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2)

Demo

By changing the size or number of index sequences you control the size of each loop and the number of loops. Also by replacing the printf call with your function you change the unrolled functionality and can even abstract it to be passed as a parameter to your unroller.

How to unroll nested for loops in c++?

4 Answers4