Performance of array of function vs switch

Question

After reading this topic : Performance of array of functions over if and switch statements and http://en.wikipedia.org/wiki/Branch_table , I wrote a little test to measure the performance differences between a switch/case style coding VS an array of functions. The function call (F class members) is using only cpu capacity (arithmetic stuff) on purpose: no system call, no I/O like Console output, etc.

At the end, the difference between these 2 approaches is around 30% faster for the switch method ! Ok, function pointer are a little bit slower than switch/case.

So My question is : does my test looks valid to you ? Or did I introduced any bias which leads to these incredible results ? 30% !

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

namespace ConsoleApplication1
{
    class Program
    {

// The functor used :

        delegate void functor(int i, int j);

// The enum used in switch :

        enum indexes
        {
            a = 0, b = 1, c = 2, d = 3, e = 4, f = 5,
            g = 6, h = 7, i = 8, j = 9, k = 10,
            l = 11, m = 12, n = 13, o = 14, p = 15,
            q = 16
        };

// The class with the different possible calls :

        class F
        {
            long m_j = 1;
            public void A(int i, int j) { m_j = (i + j - 2) % (j / 3 + 1); }
            public void B(int i, int j) { m_j = (i + j - 3) % (j / 3 + 1); }
            public void C(int i, int j) { m_j = (i + j - 4) % (j / 3 + 1); }
            public void D(int i, int j) { m_j = (i + j - 5) % (j / 3 + 1); }
            public void E(int i, int j) { m_j = (i + j - 6) % (j / 3 + 1); }
            public void FF(int i, int j) { m_j = (i + j - 7) % (j / 3 + 1); }
            public void G(int i, int j) { m_j = (i + j - 8) % (j / 3 + 1); }
            public void H(int i, int j) { m_j = (i + j - 9) % (j / 3 + 1); }
            public void I(int i, int j) { m_j = (i + j - 10) % (j / 3 + 1); }
            public void J(int i, int j) { m_j = (i + j - 11) % (j / 3 + 1); }
            public void K(int i, int j) { m_j = (i + j - 12) % (j / 3 + 1); }
            public void L(int i, int j) { m_j = (i + j - 13) % (j / 3 + 1); }
            public void M(int i, int j) { m_j = (i + j - 14) % (j / 3 + 1); }
            public void N(int i, int j) { m_j = (i + j - 15) % (j / 3 + 1); }
            public void O(int i, int j) { m_j = (i + j - 16) % (j / 3 + 1); }
            public void P(int i, int j) { m_j = (i + j - 17) % (j / 3 + 1); }
            public void Q(int i, int j) { m_j = (i + j - 18) % (j / 3 + 1); }
            public static int nbfunc = 17;
        }


        static void Main(string[] args)
        {

// At each round, we increase the number of calls :

            long maxi = 1000;
            for (; maxi < 10000000000; maxi *= 10)
            {
                long switch_time, array_time;
                TextWriter tw = Console.Out;
                {
                    Stopwatch sw = new Stopwatch();
                    F f = new F();

// *************** Test with switch/case ***************

                    sw.Start();
                    for (int i = 0; i < maxi; i++)
                    {
                        indexes e = (indexes)(i % F.nbfunc);
                        switch (e)
                        {
                            case indexes.a:
                                f.A(i,i/2);
                                break;
                            case indexes.b:
                                f.B(i, i / 2);
                                break;
                            case indexes.c:
                                f.C(i, i / 2);
                                break;
                            case indexes.d:
                                f.D(i, i / 2);
                                break;
                            case indexes.e:
                                f.E(i, i / 2);
                                break;
                            case indexes.f:
                                f.FF(i, i / 2);
                                break;
                            case indexes.g:
                                f.G(i, i / 2);
                                break;
                            case indexes.h:
                                f.H(i, i / 2);
                                break;
                            case indexes.i:
                                f.I(i, i / 2);
                                break;
                            case indexes.j:
                                f.J(i, i / 2);
                                break;
                            case indexes.k:
                                f.K(i, i / 2);
                                break;
                            case indexes.l:
                                f.L(i, i / 2);
                                break;
                            case indexes.m:
                                f.M(i, i / 2);
                                break;
                            case indexes.n:
                                f.N(i, i / 2);
                                break;
                            case indexes.o:
                                f.O(i, i / 2);
                                break;
                            case indexes.p:
                                f.P(i, i / 2);
                                break;
                        }
                    }
                    sw.Stop();
                    switch_time = sw.ElapsedMilliseconds;
                }
                //

// *************** Test with array of funcs ***************

                {

                    Stopwatch sw = new Stopwatch();
                    F f = new F();

                    List<functor> functors = new List<functor>()
                    {
                        f.A, f.B, f.C, f.D, f.E, f.FF, f.G, f.H, f.I, f.J, f.K, f.L, f.M, f.N, f.O, f.P, f.Q 
                    };

                    sw.Start();
                    for (int i = 0; i < maxi; i++)
                    {
                        functors[i % F.nbfunc](i, i / 2);
                    }
                    sw.Stop();
                    array_time = sw.ElapsedMilliseconds;
                }

// *************** Displaying results ***************

                Console.WriteLine("nb iterations : " + maxi.ToString());
                Console.WriteLine("  switch method total time in ms : " + (switch_time).ToString());
                Console.WriteLine("  array  method total time in ms : " + (array_time).ToString());


            }

        }

    }
}

Compiled on win7 64bits, VS2010, Xeon E5-2609 @ 2.4 Ghz Compiler flags : visual standard mode Release, with "optimize code" flag on.

Results :

nb iterations : 1000000
  switch method total time in ms : 19
  array  method total time in ms : 23
nb iterations : 10000000
  switch method total time in ms : 177
  array  method total time in ms : 237
nb iterations : 100000000
  switch method total time in ms : 1808
  array  method total time in ms : 2416
nb iterations : 1000000000
  switch method total time in ms : 18630
  array  method total time in ms : 24312

Answer 1

There is a bias in your experiment, the fact that you exercise all entries of the switch once regularly.

The switch efficiency in this experiment is dominated by the "branch prediction", i.e. do I hit the matching "case" fast or do I need to explore almost all cases ?

For this small size (16) we get on average 8 boolean tests on average to find the right "case", and we benfit from more inlining optimization possibilities, since the code structure is static; I don't think the compiler can detect that "functors" is static.

So, I would try to make functors a static constant array (plain functor[]) defined and initialized outside any function, to help the compiler have at least the option of optimizing/inlining.

Then you could try increasing the number of cases, at some point I suspect random access O(1) in the array should be faster than tests in the switch case (overall O(Nbcases)).

Finally, try plotting some random access patterns, (replaying the same seed for both runs to avoid random bias), as the switch version could be impacted but not the array version.

Answer 2

The only thing that jumps out is that you are newing your list of functors for every maxi iteration. What does your timing look like if you move that outside your loop?