How to explain the difference of performance in these 2 simple loops?

Question

For those who are interested in how I do the benchmark, look here , I simple replace / add a couple of methods near the build in "Loop 1K" method.

Sorry, I forgot to say my testing environment. .Net 4.5 x64 (don't pick 32bit preferred). in x86 both methods take 5x as much as time.

Loop2 takes 3x as much time as Loop. I thought that x++ / x+=y should not slow down when x gets larger (since it takes 1 or 2 cpu instructions any way)

Is it due to Locality of reference? However I thought that in Loop2 there are not many variables, they should all be close to each other...

    public long Loop(long testSize)
    {
        long ret = 0;
        for (long i = 0; i < testSize; i++)
        {
            long p = 0;
            for (int j = 0; j < 1000; j++)
            {
                p+=10;
            }
            ret+=p;
        }
        return ret;
    }

    public long Loop2(long testSize)
    {
        long ret = 0;
        for (long i = 0; i < testSize; i++)
        {
            for (int j = 0; j < 1000; j++)
            {
                ret+=10;
            }
        }
        return ret;
    }

Update: When, if ever, is loop unrolling still useful? is useful

You should show how you've set up measuring the performance. — Kirk Woll, May 05 '13 at 17:23
Might be an optimization issue. In "Loop" the optimizer can safely assume that variable p is of type int rather than long. Therefore, the increment in the inner loop can be made faster. — Axel Kemper, May 05 '13 at 17:28
I get similar results (but it only takes 2x as long when I try it). I tried it with testsize = 10000000, release build. Ran several trials in a loop, using Stopwatch for timing. — Matthew Watson, May 05 '13 at 17:28
I just verified with this method http://stackoverflow.com/a/1048708/421143 - I have similar result for both methods. — outcoldman, May 05 '13 at 17:37
@AxelKemper the test environment is x64. `int` and `long` shouldn't make any difference. — colinfang, May 05 '13 at 18:02
I'm surprised they don't get both converted to `return testSize > 0 ? 10000*testSize : 0;`. Isn't it supposed to be an optimised build? — Daniel Fischer, May 05 '13 at 18:10
I'm not sure what's going on, but locality of reference has nothing to do with it: you're not accessing any memory. — harold, May 05 '13 at 18:33

score 6 · Accepted Answer · answered May 05 '13 at 18:30

It's been said before a few times that the x86 JIT does a better job than the x64 JIT when it comes to optimization and it looks like that is what is happening in this case. Although the loops are performing essentially the same thing, the x64 assembly code that the JITer is creating are fundamentally different, and I think it accounts for the speed difference you're seeing.

The assembly code between the two methods differ in the critical inner loop, which is called 1000*N times. This is what I think is accounting for the speed difference.

Loop 1:

000007fe`97d50240 4d8bd1          mov     r10,r9 
000007fe`97d50243 4983c128        add     r9,28h 
000007fe`97d50247 4183c004        add     r8d,4  
; Loop while j < 1000d
000007fe`97d5024b 4181f8e8030000  cmp     r8d,3E8h
000007fe`97d50252 7cec            jl      000007fe`97d50240

Loop 2:


; rax = ret
; ecx = j

; Add 10 to ret 4 times
000007fe`97d50292 48050a000000    add     rax,0Ah
000007fe`97d50298 48050a000000    add     rax,0Ah
000007fe`97d5029e 48050a000000    add     rax,0Ah
000007fe`97d502a4 48050a000000    add     rax,0Ah
000007fe`97d502aa 83c104          add     ecx,4    ; increment j by 4

; Loop while j < 1000d
000007fe`97d502ad 81f9e8030000    cmp     ecx,3E8h
000007fe`97d502b3 7cdd            jl      000007fe`97d50292

You'll notice that the JIT is unrolling the inner loop, but the actual code in the loop differs greatly when it comes to the number of instructions made. Loop 1 is optimized to make a single add statement of 40, where Loop 2 makes 4 add statements of 10.

My (wild) guess is that the JITer can better optimize the variable p because it is defined in the inner scope of the first loop. Since it can detect that p is never used outside of that loop and is truly temporary, it can apply different optimizations. In the second loop, you're acting on a variable that is defined and used outside of the scope of both loops, and the optimization rules used in the x64 JIT doesn't recognize it as the same code that could have the same optimizations.

I had thought that x64 Jit are more aggressive than x86. E.g. when it comes to eliminate range check, tail recursive... x64 are definitely better — colinfang, May 05 '13 at 18:33
I feel sure that this is the right answer (or close to it). I found that if you pass in the increment used in the inner loop as a parameter to the methods, both methods then run at almost the same speed. This supports the notion that it is an optimisation in the inner loop, and presumably one that relies on the compiler knowing what the increment is at compile time. — Matthew Watson, May 05 '13 at 22:51

score 2 · Answer 2 · answered May 05 '13 at 17:41

2

I am not seeing any appreciable difference in performance. Using this LinqPad script (and including those two methods of yours):

void Main()
{
    // Warmup the vm
    Loop(10);
    Loop2(10);

    var stopwatch = Stopwatch.StartNew();
    Loop(10 * 1000 * 1000);
    stopwatch.Stop();
    stopwatch.Elapsed.Dump();

    stopwatch = Stopwatch.StartNew();
    Loop2(10 * 1000 * 1000);
    stopwatch.Stop();
    stopwatch.Elapsed.Dump();
}

Prints out (in LinqPad);

00:00:22.7749976
00:00:22.6971114

When reversing the order of the Loop / Loop2 calls, the results are similar:

00:00:22.7572688
00:00:22.6758102

This seems to indicate that the performance is the same. Perhaps you didn't warm up the VM?

answered May 05 '13 at 17:41

Kirk Woll

76,112
22
180
195

try x64 build, I forgot to mention in x86 they are similar. And LinqPad is default x86 (I tried it) – colinfang May 05 '13 at 17:58
@colinfang, I just tried it using a console application explicitly specifying x64. It performed exactly the same. Did you try my code as a console application of your own? – Kirk Woll May 05 '13 at 18:08
I did use yours. Do you wanna screen shot? – colinfang May 05 '13 at 18:13
@KirkWoll 22 seconds? Is it a release build or a debug build you're testing? Did you run it outside the debugger? I ran your code on my computer and it only took 2.5s. I doubt my computer is 8 times faster than yours, so I suspect you weren't timing a release build. – Matthew Watson May 05 '13 at 18:16
You're right, I wasn't using a release build. Now I am and am getting 6.1917275 and 6.1968686 respectively. – Kirk Woll May 05 '13 at 22:13

score 1 · Answer 3 · answered May 05 '13 at 17:33

1

Loop should be faster than Loop2, the only explanation that comes to my mind is that compiler optimizing kicks in and reduces the long p = 0; for (int j = 0; j < 1000; j++) { p++; } to somthing like long p = 1000;, checking the generated assembler code would bring clarity.

answered May 05 '13 at 17:33

Cheese

11
1

That would provide a speedup of about 1000x. – usr May 05 '13 at 17:42
I changed `p++` into `p+=10`, the issue persists. I don't think the compile is smart enough to optimize +=10... and i decompiled in C# using ILSPY, didn't find optimization. – colinfang May 05 '13 at 17:42

score 1 · Answer 4 · answered May 05 '13 at 17:48

by looking at the IL itself, loop2 should be faster (and it is faster on my computer)

loop IL

.method public hidebysig 
instance int64 Loop (
    int64 testSize
) cil managed 
{
// Method begins at RVA 0x2054
// Code size 48 (0x30)
.maxstack 2
.locals init (
    [0] int64 'ret',
    [1] int64 i,
    [2] int64 p,
    [3] int32 j
)

IL_0000: ldc.i4.0
IL_0001: conv.i8
IL_0002: stloc.0
IL_0003: ldc.i4.0
IL_0004: conv.i8
IL_0005: stloc.1
IL_0006: br.s IL_002a
// loop start (head: IL_002a)
    IL_0008: ldc.i4.0
    IL_0009: conv.i8
    IL_000a: stloc.2
    IL_000b: ldc.i4.0
    IL_000c: stloc.3
    IL_000d: br.s IL_0019
    // loop start (head: IL_0019)
        IL_000f: ldloc.2
        IL_0010: ldc.i4.s 10
        IL_0012: conv.i8
        IL_0013: add
        IL_0014: stloc.2
        IL_0015: ldloc.3
        IL_0016: ldc.i4.1
        IL_0017: add
        IL_0018: stloc.3

        IL_0019: ldloc.3
        IL_001a: ldc.i4 1000
        IL_001f: blt.s IL_000f
    // end loop

    IL_0021: ldloc.0
    IL_0022: ldloc.2
    IL_0023: add
    IL_0024: stloc.0
    IL_0025: ldloc.1
    IL_0026: ldc.i4.1
    IL_0027: conv.i8
    IL_0028: add
    IL_0029: stloc.1

    IL_002a: ldloc.1
    IL_002b: ldarg.1
    IL_002c: blt.s IL_0008
// end loop

IL_002e: ldloc.0
IL_002f: ret
} // end of method Program::Loop

loop2 IL

.method public hidebysig 
instance int64 Loop2 (
    int64 testSize
) cil managed 
{
// Method begins at RVA 0x2090
// Code size 41 (0x29)
.maxstack 2
.locals init (
    [0] int64 'ret',
    [1] int64 i,
    [2] int32 j
)

IL_0000: ldc.i4.0
IL_0001: conv.i8
IL_0002: stloc.0
IL_0003: ldc.i4.0
IL_0004: conv.i8
IL_0005: stloc.1
IL_0006: br.s IL_0023
// loop start (head: IL_0023)
    IL_0008: ldc.i4.0
    IL_0009: stloc.2
    IL_000a: br.s IL_0016
    // loop start (head: IL_0016)
        IL_000c: ldloc.0
        IL_000d: ldc.i4.s 10
        IL_000f: conv.i8
        IL_0010: add
        IL_0011: stloc.0
        IL_0012: ldloc.2
        IL_0013: ldc.i4.1
        IL_0014: add
        IL_0015: stloc.2

        IL_0016: ldloc.2
        IL_0017: ldc.i4 1000
        IL_001c: blt.s IL_000c
    // end loop

    IL_001e: ldloc.1
    IL_001f: ldc.i4.1
    IL_0020: conv.i8
    IL_0021: add
    IL_0022: stloc.1

    IL_0023: ldloc.1
    IL_0024: ldarg.1
    IL_0025: blt.s IL_0008
// end loop

IL_0027: ldloc.0
IL_0028: ret
} // end of method Program::Loop2

IL analysis alone is not the entire story. Lots of different IL can be jitted into the same efficient result. — Kirk Woll, May 05 '13 at 17:50
It comes as a (negative) surprise that the optimizer is not capable to speed things up more. — Axel Kemper, May 05 '13 at 18:16
@AxelKemper Most optimisations are made by the JIT compiler, rather than by the C# compiler. — Matthew Watson, May 05 '13 at 18:18

score 1 · Answer 5 · answered May 05 '13 at 18:12

I can confirm this result on my system.

The results of my test are:

x64 Build

00:00:01.1490139 Loop
00:00:02.5043206 Loop2

x32 Build

00:00:04.1832937 Loop
00:00:04.2801726 Loop2

This is a RELEASE build run outside of the debugger.

using System;
using System.Diagnostics;

namespace Demo
{
    internal class Program
    {
        private static void Main()
        {
            new Program().test();
        }

        private void test()
        {
            Stopwatch sw = new Stopwatch();

            int count = 10000000;

            for (int i = 0; i < 5; ++i)
            {
                sw.Restart();
                Loop(count);
                Console.WriteLine(sw.Elapsed + " Loop");
                sw.Restart();
                Loop2(count);
                Console.WriteLine(sw.Elapsed + " Loop2");
                Console.WriteLine();
            }
        }


        public long Loop(long testSize)
        {
            long ret = 0;
            for (long i = 0; i < testSize; i++)
            {
                long p = 0;
                for (int j = 0; j < 1000; j++)
                {
                    p++;
                }
                ret += p;
            }
            return ret;
        }

        public long Loop2(long testSize)
        {
            long ret = 0;
            for (long i = 0; i < testSize; i++)
            {
                for (int j = 0; j < 1000; j++)
                {
                    ret++;
                }
            }
            return ret;
        }
    }
}

score 0 · Answer 6 · answered May 05 '13 at 17:44

I have run my own test and I don't see any significant difference. Try it:

using System;
using System.Diagnostics;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            while (true)
            {
                sw.Start();
                Loop(5000000);
                sw.Stop();
                Console.WriteLine("Loop: {0}ms", sw.ElapsedMilliseconds);
                sw.Reset();

                sw.Start();
                Loop2(5000000);
                sw.Stop();
                Console.WriteLine("Loop2: {0}ms", sw.ElapsedMilliseconds);
                sw.Reset();

                Console.ReadLine();
            }
        }

        static long Loop(long testSize)
        {
            long ret = 0;
            for (long i = 0; i < testSize; i++)
            {
                long p = 0;
                for (int j = 0; j < 1000; j++)
                {
                    p++;
                }
                ret += p;
            }
            return ret;
        }

        static long Loop2(long testSize)
        {
            long ret = 0;
            for (long i = 0; i < testSize; i++)
            {
                for (int j = 0; j < 1000; j++)
                {
                    ret++;
                }
            }
            return ret;
        }
    }

}

So, my answer: reason is in your overcomplicated measurment system.

try x64 build, I forgot to mention in x86 they are similar. – colinfang May 05 '13 at 17:58 — colinfang, May 05 '13 at 17:58

score 0 · Answer 7 · answered May 05 '13 at 22:45

The outer loop is the same in both cases but that is what blocks the compiler to optimize the code in the second case.

The problem is that the variable ret is not declared close enough to the inner loop so it is not in the outer loop's body. The ret variable is outside the outer loop which means that it is out of scope for the compiler optimizer which can't optimize the code through 2 loops.

However the variable p is declared right before the inner loop that's why it is well optimized.

How to explain the difference of performance in these 2 simple loops?

7 Answers7