Performance testing functions for wrapping an index

Question

After asking this question, I decided to write a test and determine the fastest way to wrap an index (where my maxSize is always a power of 2).

There are 3 functions that I'm comparing:

// plain wrap
public static int WrapIndex(int index, int endIndex, int maxSize)
{
    return (endIndex + index) > maxSize ? (endIndex + index) - maxSize : endIndex + index;
}

// wrap using mod
public static int WrapIndexMod(int index, int endIndex, int maxSize)
{
    return (endIndex + index) % maxSize;
}

// wrap my masking out the top bits
public static int WrapIndexMask(int index, int endIndex, int maxSize)
{
    return (endIndex + index) & (maxSize - 1);
}

Here is my test:

public static void WrapTest(int numRuns = 10000)
{
    int index = 256;
    int endIndex = 0;
    int maxSize = 4096;

    long wrapPlain = 0;
    long wrapMod = 0;
    long wrapMask = 0;

    Stopwatch sw = new Stopwatch();

    for (int i = 0; i < numRuns; i++)
    {

        // plain
        sw.Start();
        for (int j = 0; j < numRuns; j++)
        {
            WrapIndex(index, endIndex, maxSize);
        }
        sw.Stop();
        wrapPlain += sw.ElapsedTicks;
        sw.Reset();

        // mod
        sw.Start();
        for (int j = 0; j < numRuns; j++)
        {
            WrapIndexMod(index, endIndex, maxSize);
        }
        sw.Stop();
        wrapMod += sw.ElapsedTicks;
        sw.Reset();

        // mask
        sw.Start();
        for (int j = 0; j < numRuns; j++)
        {
            WrapIndexMask(index, endIndex, maxSize);
        }
        sw.Stop();
        wrapMask += sw.ElapsedTicks;
        sw.Reset();

        // change indexes
        endIndex++;
        endIndex = endIndex % maxSize;

        index++;
        index = index % maxSize;
    }
    Console.WriteLine(String.Format("Plain: {0} Mod: {1} Mask: {2}", wrapPlain / numRuns, wrapMod / numRuns, wrapMask / numRuns));
}

I ran the test and I'm consistently getting the following results (in ticks):

Plain: 25 Mod: 16 Mask: 16 (maxSize = 512)
Plain: 25 Mod: 17 Mask: 17 (maxSize = 1024)
Plain: 25 Mod: 17 Mask: 17 (maxSize = 4096)

I was expecting that the mask will be faster than all of them, but it seems to be as fast as using the modulo operator. I've also tried increasing the numRuns, but the results are consistent.

Is my test valid? Is there a better way to test the performance?

I think this link may be useful for future visitors: Benchmarking small code samples in C# — Artemix
– Artemix, Commented May 22, 2013 at 8:17

Saeed · Accepted Answer · 2011-02-05 11:50:32Z

Your results do seem odd, so I tried to rewrite your test and see if I can get different results. I suspected that you might be starting and stopping the stopwatch too frequently, which can skew your results due to the loss of precision every time you start and stop. In my code, I only start and stop the stopwatch once per type of calculation.

Using the code below, I get results more in line with what you would expect, namely that masking is the fastest, followed by plain subtraction, followed by modulo division.

Here is a typical output from one of my test runs:

Plain: 59.7033
Mod: 64.6872
Mask: 58.1923

In various runs, Plain and Mask tend to vary with respect to each other, and sometimes show very similar numbers. Mod always tends to be slower.

And here is the code:

static void Main(string[] args)
{
    TestPerf(WrapIndex, "Plain");
    TestPerf(WrapIndexMod, "Mod");
    TestPerf(WrapIndexMask, "Mask");
}

public static void TestPerf(Func<int, int, int, int> getIndex, string label, int numRuns = 10000)
{
    int maxSize = 4096;

    Stopwatch sw = new Stopwatch();
    sw.Start();

    for (int i = 0; i < numRuns; i++)
    {
        for (int index = 0; index < maxSize; index++)
        {
            getIndex(index, 1234, maxSize);
        }
    }

    sw.Stop();
    Console.WriteLine(string.Format("{0}: {1}", label, ((double)sw.ElapsedTicks) / numRuns));
}

EDIT: Also notice that I cast ElapsedTicks to double before dividing to avoid rounding. You should be careful to avoid rounding in your calculations because that just adds noise to your final result.

EDIT 2:
I played around with the code snippet in your pastie link and I was originally getting the same results as you, but I think I've finally gotten to the bottom of it.

What's happening is that without that Func wrapper, the jitter is able to do some serious optimizing. I know it's the jitter and not the C# compiler, because all of the code is intact in the ildasm output. In fact, for 2 out of your 3 methods (mod and mask), it's able to deduce that the methods aren't accomplishing anything at all (because they're doing a simple calculation, and the return value is just discarded), so it doesn't even bother calling them.

To validate that statement, simply comment out the line in WrapIndex() and return a plain 0, which is sure to get optimized out. Run your program again and you'll see that all three methods now report the same times. There's no way that doing a mod or a mask has the same cost as returning a constant 0, so that tells you that the code just isn't being executed.

This is another issue you have to be aware of when doing perf tests. If your test is too simple, the optimizer will just discard all of your code.

In my test, the Func wrapper was preventing the jitter from optimizing as much, because it doesn't know which code is going to be executed, so it can't inline and then discard the code, which is why you get more reasonable numbers.

So I think the results from my code, using the Func delegate, give a more accurate reflection of the relative costs of your three index methods.

Are you running it in release mode? I'm seeing almost no difference even if I only reset the stopwatch once and I cast the elapsed ticks to doubles: Plain: 0.011272 Mod: 0.001699 Mask: 0.001698 — Kiril
– Kiril, Commented Feb 5, 2011 at 8:11
Note that the version you've suggested also captures the incrementation of the indexes (which should always be the same, but it may have some impact). The above results were with a version nearly identical to yours although I avoid the use of the Func delegate, here is a pastie for it: pastie.org/1530568 — Kiril
– Kiril, Commented Feb 5, 2011 at 8:29
Any time you're doing perf tests, you have to build it in release mode, and then run it outside of Visual Studio. Even in release mode, VS does extra things to aid in debugging. Try running from the command line and see what happens. — Saeed
– Saeed, Commented Feb 5, 2011 at 8:33
@Saeed, I was running it in release mode through the exe this whole time... in command prompt I get similar results: Plain: 0.0114577 Mod: 0.0017611 Mask: 0.001707 — Kiril
– Kiril, Commented Feb 5, 2011 at 8:35
@Lirik, I updated my answer. Updating the index in the loop shouldn't matter since we're doing it the same for all operation types, but it does add a lot of noise to do two % operations in a perf test that's testing the effects of %. I updated the test to just do a simple iteration over start indices, and always use a fixed end index. This still gives the same kind of results, though plain and mask tend to be closer to each other now, while mod is relatively more expensive. — Saeed
– Saeed, Commented Feb 5, 2011 at 8:43

Stack Exchange Network

Performance testing functions for wrapping an index

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Performance testing functions for wrapping an index

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions