While loop is more efficient than for loop. What could be the reason?

Question

I was doing a LeetCode challenge (here) for fun and was surprised that the while loop was more efficient than the for loop. I would have expected the compiler to generate identical code (also as per these question and answers), but the run times are different.

The while loop was around 3 ms, whilst the for loop took around 6ms. I repeated a couple of times and it seemd to be often like that.

I don't have the test cases unfortunately, and I don't have any information about compiler used, the architecture or optimizations set. I think it is not important because the programs are almost identical and use the same compiler, architecture and options surely.

Any ideas or experiences in that matter ?

For loop:

vector<int> twoSum(vector<int>& numbers, int target) {
    int upper = numbers.size() - 1;
    int lower = 0;
    int sum;

    for (;lower<upper;) {
        sum = numbers[lower] + numbers[upper];
        if (sum == target) {
            return vector<int> { lower+1, upper+1 };
        } else if (sum > target) {
            upper--;
        } else {
            lower++;
        }
    }
}

While loop:

vector<int> twoSum(vector<int>& numbers, int target) {
    int upper = numbers.size() - 1;
    int lower = 0;
    int sum;

    while (lower<upper) {
        sum = numbers[lower] + numbers[upper];
        if (sum == target) {
            return vector<int> { lower+1, upper+1 };
        } else if (sum > target) {
            upper--;
        } else {
            lower++;
        }
    }
}

Strange; can't think of a reason for it to do that unless the code generation is really poor and optimisations are turned off — Lightness Races in Orbit, May 04 '17 at 16:04
How many times did you run the loops? Were optimizations on? Micro-benchmarking can be very tricky. — NathanOliver, May 04 '17 at 16:05
GCC generates [nearly identical assembly for both](https://godbolt.org/g/J7sh0n). Only difference I can see is that some instructions are in different order. — eerorika, May 04 '17 at 16:08
*because the programs are almost identical and use the same compiler, architecture and options surely* -- Unless you run the site, you don't know what the options are, so no assumptions can be made. — PaulMcKenzie, May 04 '17 at 16:27
@user2079303 - it is a minimal, complete and verifiable example. Just copy and paste the code into the corresponding text area on the linked page. — Ely, May 04 '17 at 16:52
@user2079303 the assembly codes for the two loops are identical, see my answer. — Jonas, May 04 '17 at 17:48
@user2079303 I tend to believe you. Yes, how come the difference in run time ? The while loop constantly performs better than the for loop. — Ely, May 05 '17 at 09:39

Jonas · Answer 1 · 2017-05-04T17:51:14.280

3

You did not run enough or long enough tests, benchmarks in milliseconds is hard to verify.

A better way is to compare the generated assembly: for-loop and while-loop. The snippets are compiled with maximum optimization (-O3), using g++ 6.3. From this it is clear that there is no performance difference at all, since the assembly for the two is exactly the same.

edited May 04 '17 at 17:51

answered May 04 '17 at 17:45

Jonas

6,915
8
35
53

score 0 · Answer 2 · answered May 04 '17 at 16:24

0

All loops follow the same template:

{
// Initialize
LOOP: 
if(!(/* Condition */) ) {
    goto END
}

// Loop body

// Loop increment/decrement
goto LOOP
}
END:

Your test must have differed by the available processing power on your CPU.

answered May 04 '17 at 16:24

Sterling Beason

622
6
12

I would avoid the negation in the condition, it seems unnecessary. – Jonas May 04 '17 at 19:22
If the negation wasn't there, then your c++ coded condition would be opposite of what it is supposed to be. This is under-the-hood of c++ – Sterling Beason May 04 '17 at 19:33
That's not what I meant. I would change the if statement to just check condition and then let the if body contain the loop body, increment step, and go-to loop. – Jonas May 04 '17 at 19:38
Oh, I see what you are saying. I don't make the rules – Sterling Beason May 04 '17 at 19:47

While loop is more efficient than for loop. What could be the reason?

2 Answers2