Storing last valid Index in a for loop

Question

Related Question: Incrementing: x++ vs x += 1

I have code that is like this:

int lastValidIndex = -1;
for(int i = 0; i < limit; i++){
    if (condition)
        lastValidIndex++;
    else
        break;
}

And I was wondering if it would be faster to just assign lastValidIndex to i or to increment it. I'm guessing it would be faster to just assign so the computer doesn't have to add, but I'm not sure.

What I am using is C#, but the question is in a general sense like the related, linked question — BrainStorm.exe, Apr 23 '13 at 19:23
You can try to measure it, but probably it's the same code with optimizations - compiler can prove that `i == lastValidIndex` so it will likely eliminate one of these variables. — zch, Apr 23 '13 at 19:25

score 1 · Accepted Answer · answered Apr 23 '13 at 19:24

It might depend somewhat on your language. Since you didn't specify, I'll assume macro assembler (aka C).

Assuming there's not much other logic, both values will be allocated as register variables.

This means that either an increment or an assignment would be one clock cycle, or on modern processors about 1/2000000 of a second.

Depending on the size of your array, might ...ahem... save some time by using this optimization:

int lastValidIndex = -1;
while( condition ) {
    lastValidIndex++;
}

But my guess is that whatever you might save in computing the last valid index is dwarfed by your condition check, and certainly by whatever brain cycles you spend trying to figure out if you've really saved 1/2000 of a second.

You might also want to add a check to see if `lastValidIndex` is under the limit, or are you assuming that is part of `condition`? — BrainStorm.exe, Apr 23 '13 at 20:14
I'd imagine that if the index were out of bounds, it would fail "valid" condition, but YMMV (depends on the data structure and condition rules) — PaulProgrammer, Apr 23 '13 at 21:08

score 0 · Answer 2 · answered Apr 23 '13 at 19:26

0

int lastValidIndex = -1;
while(lastValidIndex < limit - 1 && condition) ++lastValidIndex;
// use lastValidIndex here ...

answered Apr 23 '13 at 19:26

wachme

2,327
20
18

score 0 · Answer 3 · answered Apr 23 '13 at 19:53

It appears in C# in the disassembly, the first uses "inc" which is one operation, while assigning it consists of two "mov" operations.

Using this code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace IncrementTest {
    class Program {
        static void Main(string[] args) {
            Stopwatch watch = new Stopwatch();
            long totalMethod1 = 0;

            for (int j = 0; j < 100; j++) {
                int lastValidIndex = -1;
                watch.Reset();
                watch.Start();
                for (int i = 0; i < 100000000; i++) {
                    lastValidIndex++;
                }
                watch.Stop();
                totalMethod1 += watch.ElapsedMilliseconds;
            }
            Console.WriteLine("Method 1 took an average of " + (double)totalMethod1 / 100 + "ms");

            long totalMethod2 = 0;
            for (int j = 0; j < 100; j++) {
                int lastValidIndex = -1;
                watch.Reset();
                watch.Start();
                for (int i = 0; i < 100000000; i++) {
                    lastValidIndex = i;
                }
                watch.Stop();
                totalMethod2 += watch.ElapsedMilliseconds;
            }
            watch.Stop();
            Console.WriteLine("Method 2 took an average of " + (double)totalMethod2 / 100 + "ms");
            Console.ReadLine();

        }
    }
}

I surprisingly get this output:

Method 1 took an average of 381.51ms
Method 2 took an average of 354.76ms

So if you are in a situation where you have to use two different varaibles, it appears to be faster to just assign, at least in C#.

Yes, I know I have `j` on the outer loops instead of the inner loops, but it took less time to use `j` than replacing all of the `i`s with `j`s — BrainStorm.exe, Apr 23 '13 at 20:10

Storing last valid Index in a for loop

3 Answers3