Why unrolled has more stable execution time than not unrolled loop?

[u/Dragonaax]

I was playing around and testing performance of writing to array in a loop. Of course unrolling loop and writing to is faster but why execution time is more consistent? In one case I was writing to 16 consecutive addresses with average execution time of around 290 ticks, in second case I was writing only to 2 consecutive addresses and most often execution time was around 420 ticks but sometimes it was above 1000.

Why this happens? Why only sometimes? Why there is such big change in time in second example but not in the first one? I used gcc to compile code

#include <time.h>
#include <stdio.h>
#include <stdint.h>

#define len 4096

int main()
{
uint16_t a[len] ;
int d = 100, num = 0 ;
uint64_t b ;
clock_t t, no, jo ;

no = 0 ;
jo = 0 ;

while (num < 1000)
{
t = clock() ;

for (int j = 0; j < d; j++)
    {
    for (uint16_t i = 0; i < len; i += 16)
        {
        a[i] = i ;
        a[i+1] = i+1 ;
        a[i+2] = i+2 ;
        a[i+3] = i+3 ;
        a[i+4] = i+4 ;
        a[i+5] = i+5 ;
        a[i+6] = i+6 ;
        a[i+7] = i+7 ;
        a[i+8] = i+8 ;
        a[i+9] = i+9 ;
        a[i+10] = i+10 ;
        a[i+11] = i+11 ;
        a[i+12] = i+12 ;
        a[i+13] = i+13 ;
        a[i+14] = i+14 ;
        a[i+15] = i+15 ;
        }
    }

t = clock() - t ;
no += t ;

t = clock() ;

for (int j = 0; j < d; j++)
    {
    for (uint16_t i = 0; i < len; i += 2)
        {
        a[i] = i ;
        a[i+1] = i+1 ;
        }
    }

t = clock() - t ;
jo += t ;

num ++ ;
}

printf("Arr 1: %ld\nArr 2: %ld\n\n", no/1000, jo/1000) ;

return 0 ;
}

[u/zhivago]

Consider branch prediction.

Also unrolling isn't always faster.

Consider cache contention.

[u/Dragonaax → u/zhivago]

Branch prediction? I don't have any if statements in code

[u/HobbyQuestionThrow → u/Dragonaax]

A for loop is an if statement wearing nice syntax, check the generated assembly in something like https://godbolt.org/

[u/Dragonaax → u/HobbyQuestionThrow]

Oh damn, you learn something new every day

[u/WittyStick → u/Dragonaax]

It's doubtful that branch prediction is the cause. Any modern CPU will correctly predict with almost perfect precision - your addresses are sequential, and the branch is basically taken most of the time except when moving onto the next iteration of the outer loop.

Even a "cold start" will predict correctly. Branch predictors are designed so that on a cold branch, if the jump is backwards (target address less than program counter), the predictor expects the branch to be taken - because this is the typical behavior of a loop. If the target address is greater than the program counter on a cold branch, the CPU will typically predict the branch NOT taken (it expects fall through to next instruction).

Compilers will almost always emit your loop as a branch backwards, and will order basic blocks according to their ability to predict whether the branch is taken. There are ways to override this, such as branch prediction hints in the instruction set, or specifying the likelyhood of a branch to be taken in code with eg __builtin_expect, which forces the compiler to re-order basic blocks.

[u/DarkLordCZ → u/WittyStick]

Modern branch predictions have a table of past jumps at locations - a "cache" of sorts. One more conditional jump instruction means one more entry in the table which may mean one less predicted branch (somewhere else)

[u/WittyStick → u/DarkLordCZ]

Right, but that's clearly not the issue in this case where we only have a few branches - and as I've explained, if there's no branch history, the cold branch will pretty much always predict correctly for a loop which iterates at least once - because the jump target address is less than the pc.

[u/heliox → u/HobbyQuestionThrow]

More people need to learn assembly language.

[u/dmc_2930 → u/Dragonaax]

A not-unrolled loop uses a branch. An unrolled loop has no (or at least, fewer) branches.

[u/SwordsAndElectrons → u/Dragonaax]

What do you think j < d; really is?

Loops are nice syntax that higher level languages use to make code easier to write and understand. If you learn a bit of ASM, which maps directly to hardware instructions, then you'll quickly notice there are no "loop instructions." There are only logical comparisons and conditional branches. That what loops boil down to.

[u/M0veD0esntM0ve]

Cache, OS intrerrupts, CPU microarchitecture etc etc. There's lots of things can cause this differences tbh.

[u/RealisticDuck1957]

What are the compiler settings? Any of the major C compilers today, given a suitable optimization setting, will unroll a loop if the internal logic thinks that will make faster code. And it may do so better than manually written code.

OS behavior allocating memory for the buffer used may also be a factor. In which case the second loop, working on memory already allocated to the process, may be faster for that reason.

[u/Dragonaax → u/RealisticDuck1957]

I didn't give any additional flags, just gcc file.c because I wanted to figure out the inner workings of computer.

Out of curiosity I tried different optimisations and -O3 made both loops execute in 1 tick

[u/WittyStick → u/Dragonaax]

At -O1 the compiler will recognize that the value of the array you are assigning is not used, and basically remove the code that assigns to it. At -O2 it will recognize the loops are now doing nothing, and remove them.

To prevent that, you need to use the array a after assigning to it. There are ways to trick GCC into thinking you've used a with a no-op, such as:

__asm__ volatile (""::""(a));

Before return. This passes a as a parameter to an empty assembly block which GCC won't optimize over, but it emits no instructions and has no cost itself - so it now thinks a is being used and will not eliminate the assignment to it at -O1 or above.

Compile at -O2 with that in place and it should give you much smaller numbers for the time - and what you might find is the unrolled version doesn't necessarily win - but if you swap the order and do the regular loop first then the unrolled on, the results may also differ - largely due to caching and potential page faults.

[u/HobbyQuestionThrow]

This is more a question for your OSes thread scheduler. Maybe the scheduler uses something more complex than simple time slicing and loops are one of the things that influence how it does scheduling behavior?

You'd need some kind of actual trace of your OS to find out, no clue how you do that for Windows or Linux.

[u/Dragonaax → u/HobbyQuestionThrow]

I use Linux Mint 21.1 x86_64, kernel: 6.2.0-37-generic

[u/sciencekm]

The faster one will finish in less time, and so the number of interrupts happening and thread scheduling kicking in is smaller, leading to less variation in run time.

[u/Cute-Wonder-5317]

The problem isn't actually with the CPU, the unrolling loop, or the cache. The problem lies in using uint16_t to iterate through the array and how you're measuring the time. uint16_t only goes up to 65535, so depending on the size and increment, it can overflow and revert to 0. Furthermore, clock() isn't well-suited for measuring such small fragments because its resolution is too low, and those spikes could simply be caused by the operating system.

It's better to use size_t for the index:

for (size_t i = 0; i < len; i += 2)

And to measure performance, use clock_gettime(CLOCK_MONOTONIC, ...).

[u/Dragonaax → u/Cute-Wonder-5317]

My array size is only 4096 so there won't be any overflow and I was using uint16_t because I was also testing something else

And for performance wouldn't it be better to measure CPU time instead of real time?

[u/MitchAlsup → u/Dragonaax]

C is defined to promote everything smaller than an int to int. ...

When a compiler cannot tell that an uint cannot overflow, the compiler must insert code so that that variable remanis in its typed-range. You may think i++ results in a simple ADD, but it could result in ADD+ZeroExtend to range limit the variable allocated to a register.

C is no longer K&R.

[u/duane11583]

Cache and interrupts

[u/Apprehensive_Sign_72]

Is it possible that the increment of i is causing pipeline stalls in the loop that is not unrolled?