While/For/Foreach Speed Test!

[DrabanL]

Hi!

I Was interested which of them would preform the fastest.

So i coded this:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;
namespace Speeding
{
    class Program
    {

        static void Main(string[] args)
        {
            Program p1 = new Program();
            p1.check1(97000);
            p1.check2(97000);
            p1.check3(97000);
            Console.ReadKey();
        }

        private void check1(int Size)
        {
            Stopwatch sp = new Stopwatch();
            sp.Start();
            for (int i = 0; i <= Size; i++)
            {
                for (int j = 0; j <= Size; j++)
                {

                }
            }
            sp.Stop();
            Console.WriteLine("check 1(normal for) {1} cycles: {0}", sp.Elapsed, Size);
        }

        private void check2(int Size)
        {
            Stopwatch sp = new Stopwatch();
            sp.Start();
            int[] ii = new int[Size];
            int[] jj = new int[Size];
            foreach (int i in ii)
            {
                foreach (int j in jj)
                {

                }
            }
            sp.Stop();
            Console.WriteLine("check 2(normal foreach) {1} cycles: {0}", sp.Elapsed, Size);
        }

        private void check3(int Size)
        {
            Stopwatch sp = new Stopwatch();
            sp.Start();
            int i = 0;
            int j = 0;
            while (i <= Size)
            {
                i++;
                while (j <= Size)
                {
                    j++;
                }
            }
            sp.Stop();
            Console.WriteLine("check 3(normal while) {1} cycles: {0}", sp.Elapsed, Size);
        }
    }
}

Results:


Have i done something wrong????? because i am stunned by the results actually O.O

[BigEd781]

When discussing performance....

1. Show your compiler options or it didn't happen.
2. The first time your code runs it needs to be compiled by the JIT compiler, so you need to run a large number of tests to get real numbers.
3. You have empty loops... which will obviously be optimized away be any optimizing compiler.

This is not how you test performance. Your tests are inherently flawed and any data gathered from then is useless. Also, the speed of different loop structures will never, ever be a bottleneck in your code, so measuring them this way is a complete waste of time.

[DrabanL]

I coded a program that double-loops through ~500000 (500000^500000)
Its like finding duplicates in 2 Lists, each list is 500K long.

For now, after doing some tests, using Parallel.For as the outside loop, and While as the inside loop, is the fastest.

But still, its relatively slow, as it takes +/- 50 hours to finish.

[BigEd781]

The algorithm is slow because it has O(n^2) complexity in time, not because you used a for loop instead of a foreach. Again, testing an empty loop makes no sense since it will be optimized away. If it isn't that means you're testing a debug build which likewise makes no sense.

Of course Parallel.For is faster for a job that can be broken into chunks as it runs in parallel on multiple cores. My point is that you are focusing on absolutely the wrong thing. You should be tweaking your algorithm, not testing the speed of a for v while v foreach loop. The time those takes is in the noise compared to your algorithm semantics.

[DrabanL]

The algorithm is slow because it has O(n^2) complexity in time, not because you used a for loop instead of a foreach. Again, testing an empty loop makes no sense since it will be optimized away. If it isn't that means you're testing a debug build which likewise makes no sense.

Of course Parallel.For is faster for a job that can be broken into chunks as it runs in parallel on multiple cores. My point is that you are focusing on absolutely the wrong thing. You should be tweaking your algorithm, not testing the speed of a for v while v foreach loop. The time those takes is in the noise compared to your algorithm semantics.

Still, using a While as the inside loop is faster then a for or an each (as i said they are not empty in my working code).

Another problem that i noticed is that the Parallel loop slow down with time.. I dont know why..

So actually there is not faster way to operate O(n^2) algorithm ?

EDIT: Sorry, i was mistaken, i meant that the double loop is 500,000 (500,000^2), which still is running for hours and hours..

[BigEd781]

I have still yet to see a valid test case.

1. What are your compiler options?
2. Show us your real algorithm.

O(n^2) simply means that the worst case time needed to execute the algorithm is proportional to the square of its input. Perhaps calling functions like GetEnumerator() and Enumerator.Next() slows down the foreach loop, but I'm not buying it. I would assume that any one of the operations you actually perform in the loop (like a string comparison, another function call, whatever) take orders of magnitude longer, meaning the actual loop structure time is in the noise.

This is not how you performance tune. You first optimize your algorithm. You then measure the time needed to perform each step in the algorithm and see where most of your CPU time is going, or determine if memory reads are causing a bottleneck (i.e., how well aligned is your data? Are you using the CPU cache efficiently?). You then optimize that part of code, i.e., your bottleneck. I do not believe that foreach is a bottleneck here and you have not shown us anything that would prove it is. Show us the real code.