CODEWITHSUNDEEP
c#performancerecursioniteration
Molay
Molay

Reputation: 43

Inconsistencies in recursive vs iterative speed

I made a program to compare iterative speed vs recursive speed for a very simple operation. I noticed something weird which I can't explain. Depending on the amount of values processed, either iterative or recursive is faster. But it isn't consistent.

How comes that the iterative process is faster for the lower and higher testable amounts, but not for those in between?

I lack some deeper understanding on this and would be grateful if someone could explain this to me.

Here is the code for those that want to test it themselves.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Compare_Recursive_Iterative
{
    class Program
    {
        static void Main(string[] args)
        {
            // Amount of values processed.
            long testNumber = 200;
            // Variables to measure time taken.
            double timeIterative, timeRecursive, timeTotal;

            // Iterative process + time elapsed calculation
            DateTime start = DateTime.Now;
            long retVal = 0;
            for(long i = 1; i <= testNumber; i++)
            {
                retVal = 0;
                for (long x = 1; x <= i; x++)
                { 
                    retVal += x;
                }
                Console.WriteLine("For " + i + ": " + retVal);
            }
            TimeSpan timeDiff = DateTime.Now - start;
            timeIterative = timeDiff.TotalMilliseconds;

            // Recursive process + time elapsed calculation
            DateTime start2 = DateTime.Now;
            for (long i = 1; i <= testNumber; i++)
            {
                Console.WriteLine("For " + i + ": " + calculate(i));
            }
            timeDiff = DateTime.Now - start2;
            timeRecursive = timeDiff.TotalMilliseconds;

            // Results to console.
            Console.WriteLine("Iterative: " + timeIterative + "ms /// Recursive: " + timeRecursive + "ms");
            timeDiff = DateTime.Now - start;
            timeTotal = timeDiff.TotalMilliseconds;
            Console.WriteLine("Total time needed: " + timeTotal + "ms");
            Console.WriteLine("Iterative - Recursive: " + (timeIterative - timeRecursive) + "ms");
            Console.Read();
        }


        // Recursive method
        static long calculate(long x)
        {
            if (x <= 1)
                return x;
            else
                return x + calculate(x - 1);
        }

    }
}

Upvotes: 1

Views: 167

Answers (1)

Ronan Thibaudau
Ronan Thibaudau

Reputation: 3603

Most of the time is going to be spent in Console.WriteLine in your samples which has to do a whole lot more work than a few additions for it's work so your measures are meaningless, if you want to measure then

1) Make sure you ONLY measure what you want to measure (don't write to any outputs, you do that after the test)

2) Use a stopwatch at least, DateTime.Now won't be precise at all

3) Isolate both tests in their own functions and call each of them once each before testing to make sure you're not measuring warmup time.

4) Call both functions a substantial amount of time (maybe 1000?) and then note the min / max / average time for each

5) Make sure you're not doing anything else on your system and nothing intensive is running (disable your antivirus etc while running).

6) Also very very important, DO NOT DO YOUR TESTS IN DEBUG MODE, SWITCH TO RELEASE FIRST!!! Debug mode can slow down things massively in some case and barely at all in other cases, meaning function A could be much faster than B in debug, and the reverse in release. Also don't test with a debugger attached, just launch the exe from the folder.

As it is you're not doing step 1 and that's what's causing your issue as all of the time is spent well, outside of your own code pretty much, the other points are there so you can think of all this instead of going back & forth with Q & A here.

Made a sample to show you, probably not perfect but closer to what a benchmark should look like, also note you may want to put testiterative back in the main code if you actually want to compare having it inline (vs the recursive which must be a function)

void Main()
{
var TargetNumber = 2000;
var TestRuns = 10;
//warmup both methods
calculate(100);
TestIterative(100);

Stopwatch sw = new Stopwatch();

var RecursiveTimes = new List<long>();

for(int run = 1;run<=TestRuns;run++)
{
    sw.Restart();
    for (int i = 1; i <= TargetNumber; i++)
    {
        calculate(i);
    }
    sw.Stop();
    RecursiveTimes.Add(sw.ElapsedMilliseconds);
}

var IterativeTimes = new List<long>();

for(int run = 1;run<=TestRuns;run++)
{
    sw.Restart();
    for (int  i = 1; i <= TargetNumber; i++)
    {
        TestIterative(i);
    }
    sw.Stop();
    IterativeTimes.Add(sw.ElapsedMilliseconds);
}

Console.WriteLine("Iterative : " + IterativeTimes.Average() + " ms on average. Min and max : " + IterativeTimes.Min() + " / " + IterativeTimes.Max());
Console.WriteLine("Recursive : " + RecursiveTimes.Average() + " ms on average. Min and max : " + RecursiveTimes.Min() + " / " + RecursiveTimes.Max());  
}

static long TestIterative(long x)
{
    long retVal = 0;
    for (long y = 1; y <= x; y++)
    { 
        retVal += y;
    }
    return retVal;
}

static long calculate(long x)
{
    if (x <= 1)
        return x;
    else
        return x + calculate(x - 1);
}

Also note i separated the number you want to test (from 0 to TargetNumber) from the number of test runs as those have no reason to be linked (TestRuns) so that you could test a small set many times or a large one a few times.

As you can see all the output is moved to the end of the program since it's expensive and you don't want to measure it, even adding the times to a list is done outside of the timed areas and i'm timing per test (not within the test) as the times would be too small and we'd end up with plenty of zeroes.

Also a good benchmark is one that tests actual usable code with usable data, don't try to "micro benchmark" code that does nothing, you can't really benchmark the time it takes to do a few additions on hardware that does billion of those a second.

And a good rule of thumb, unless it makes your code massively more complex, always go for iterative, not so much for performance (but it do is better) but mostly because you have no reason to give yourself stack overflows if you can avoid it.

Upvotes: 4

Related Questions