Unrolling Loop in C/C++/Java Style

Quite often, we need to loop an array but dealing with continuous two elements at each iteration. This sounds an easy task and one can usually pay attention to the first or last element when computing the index of its successor.

The Naive way

1
2
3
4
5
6
7
8
9
10
11
12

    const int N = 5;
    int arr[N];
    for (int i = 0; i < N; i ++)
        arr[i] = i;
 
    for (int i = 0; i < N; i ++) {
        if (i == 0) {
            cout << arr[N - 1] << " " << arr[i] << endl;
        } else {
            cout << arr[i - 1] << " " << arr[i] << endl;
        }
    }

    const int N = 5;
    int arr[N];
    for (int i = 0; i < N; i ++)
        arr[i] = i;

    for (int i = 0; i < N; i ++) {
        if (i == 0) {
            cout << arr[N - 1] << " " << arr[i] << endl;
        } else {
            cout << arr[i - 1] << " " << arr[i] << endl;
        }
    }

Unloop – Version 1

The above has a conditional check inside the loop which is only true for particular index (i.e. the first element in this case). Therefore, for large array, the conditional check will slow down the performance, e.g. cache misses and branches mis-predicted.

We can easily move the check outside.

1
2
3
4

    cout << arr[N - 1] << " " << arr[0] << endl;
    for (int i = 1; i < N; i ++) {
        cout << arr[i - 1] << " " << arr[i] << endl;
    }

    cout << arr[N - 1] << " " << arr[0] << endl;
    for (int i = 1; i < N; i ++) {
        cout << arr[i - 1] << " " << arr[i] << endl;
    }

Unloop – Setting a Flag

We can also set a flag, by using an additional element in the array (extra element before or after the array). This looks elegant.

1
2
3
4
5
6
7
8
9

    const int N = 5;
    int arr[N + 1];
    for (int i = 0; i < N; i ++)
        arr[i] = i;
    arr[N] = 0;
 
    for (int i = 0; i < N; i ++) {
        cout << arr[i] << " " << arr[i + 1] << endl;
    }

    const int N = 5;
    int arr[N + 1];
    for (int i = 0; i < N; i ++)
        arr[i] = i;
    arr[N] = 0;

    for (int i = 0; i < N; i ++) {
        cout << arr[i] << " " << arr[i + 1] << endl;
    }

The C/C++/Java Style

I particularly love this style, and it shows how powerful the for loop in C/C++/Java (some other languages may work similarly e.g. C#, Javascript).

1
2
3

    for (int i = 0, j = N - 1; i < N; j = i, i ++) {
        cout << j << " " << i << endl;
    }

    for (int i = 0, j = N - 1; i < N; j = i, i ++) {
        cout << j << " " << i << endl;
    }

However, at each iteration, there is one extra operation (e.g. j = i). But I doubt it this will cause any performance bottlenecks.

–EOF (The Ultimate Computing & Technology Blog) —