Spread the love

C# .Net: Use the Modulus Operator or Alternative?

This investigates the performance of the modulus operator % in C# .Net and benchmarks against other techniques to determine if you should in C# .Net: use the Modulus Operator or alternative.

The Background:

Of the C# additive and multiplicative operators: +, -, *, /, and %, the % operator is the most expensive to use. Times can be seen from the website DotNetPerls http://www.dotnetperls.com/modulo and the MSDN article on writing faster managed code http://msdn.microsoft.com/en-us/library/ms973852.aspx (complete with a table).

Given developers frequently write code using modulus %, such as in a for-loop where x % 2 to highlight every other row from the results of a database query, I put on the curious consultant hat and wondered if there was a better, faster way.

The Set Up:

I wrote a C# Console application which uses the following techniques – all mathematically equivalent to the modulus operator:

Technique

Code Snippet

Modulus %

for (int x = 0; x < max; x++)
{
        if (x % threshold == 0)
               total += x;
}

for (int x = 0; x < max; x++)

{

if (x % threshold == 0)

total += x;

}

System.Math.DivRem

for (int x = 0; x < max; x++)
{
        System.Math.DivRem((long)x, (long)threshold, out value);
        if (value == 0)
               total += x;
}

for (int x = 0; x < max; x++)

{

System.Math.DivRem((long)x, (long)threshold, out value);

if (value == 0)

total += x;

}

Add Alternative

for (int x = 0; x < max; x++)
{
        if (y > (threshold - 1))
        {
               y = 0; //reset
               total += x;
        }
        y += 1;
}

for (int x = 0; x < max; x++)

{

if (y > (threshold - 1))

{

y = 0; //reset

total += x;

}

y += 1;

}

((x/y) * y) == x

for (int x = 0; x < max; x++)
{
        if (((x / threshold) * threshold) == x)
               total += x;
}

for (int x = 0; x < max; x++)

{

if (((x / threshold) * threshold) == x)

total += x;

}

While loop countdown

y = 0;
for (int x = 0; x < max; x++)
{
        y = x;
        while (y >= threshold)
               y -= threshold;
        if (y == 0)
               total += x;
}

y = 0;

for (int x = 0; x < max; x++)

{

y = x;

while (y >= threshold)

y -= threshold;

if (y == 0)

total += x;

}

To test the different techniques I call the method 9 times:

The first 3 times setting the modulus value to 123 over a loop of 2,147,483,647 iterations, 2,147,483 iterations, and 214,748 iterations.
The next 3 times setting the modulus value to 10 over the same loop iterations.
The last 3 times setting the modulus to the more common value of 2 over the same number of loop iterations.

The code is written in Visual Studio 2012 targeting .Net Framework version 4.5 x64. The source code is available at the end of this blog so you can benchmark it on your own system if you wish.

This trial was run three times, but all the results were practically the same, so only one table will be listed.

The Runs:

Before starting, my hypothesis was that I expected add alternative method to be fast enough to notice a difference.

Let’s see what happened on my machine. All times are indicated in minutes:seconds.milliseconds format.

Fastest runs are highlighted in green; second fastest in yellow.

Lower numbers indicate faster performance.

Modulus By:	% 123			% 10			% 2
	Loop iterations:			Loop iterations:			Loop iterations:
	2,147,483,647	2,147,483	214,748	2,147,483,647	2,147,483	214,748	2,147,483,647	2,147,483	214,748
T1: modulus	10.3855940	00.0090005	00.0010001	10.7486148	00.0090005	00.0010001	11.0446317	00.0090005	00.0010001
T2: Math.DivRem	41.3433647	00.0410024	00.0040002	41.3743665	00.0410023	00.0040002	42.0134030	00.0420024	00.0050002
T3: add alternative	01.6080920	00.0010000	00.00	02.5181440	00.0020002	00.0010001	02.1611237	00.0020001	00.00
T4: ((x/y) * y) == x	10.4305966	00.0100006	00.0010000	10.5566038	00.0090005	00:00:00	10.9176244	00.0100006	00.0010000
T5: while loop	– too long –	05.6933257	00.0620036	– too long –	– too long –	00.7140408	– too long –	– too long –	03.5632038

The Winner Is Obvious:

Check out the run times! The add alternative kicked butt running significantly faster than anything else.

From what I read, I thought the modulus % operator would have been significantly slower over the course of 2 million or 200,000 iterations. Given the results, there’s probably nil difference over 20 iterations.

I am surprised at how well T4 performed.

In Summary:

On my system, unless someone spots a flaw in my test code, the add-alternative to the modulus operator will shave several seconds off the clock depending on how many numbers you’re doing a modulus against.

But seriously… unless you have a mission critical micro-optimization need, stick with the modulus operator for easy to read code rather than trying to save roughly 00.0070000 milliseconds execution time.

Obviously you should test on your system before micro-optimizing this functionality for your .Net application.

The Code:

using System;

namespace TestApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime end;
            DateTime start = DateTime.Now;

            Console.WriteLine("### Overall Start Time: " + start.ToLongTimeString());
            Console.WriteLine();

            TestModulusVsIncrement(Int32.MaxValue, 123);
            TestModulusVsIncrement(Int32.MaxValue / 1000, 123);
            TestModulusVsIncrement(Int32.MaxValue / 10000, 123);

            TestModulusVsIncrement(Int32.MaxValue, 10);
            TestModulusVsIncrement(Int32.MaxValue / 1000, 10);
            TestModulusVsIncrement(Int32.MaxValue / 10000, 10);

            TestModulusVsIncrement(Int32.MaxValue, 2);
            TestModulusVsIncrement(Int32.MaxValue / 1000, 2);
            TestModulusVsIncrement(Int32.MaxValue / 10000, 2);

            end = DateTime.Now;

            Console.WriteLine();
            Console.WriteLine("### Overall End Time: " + end.ToLongTimeString());
            Console.WriteLine("### Overall Run Time: " + (end - start));

            Console.WriteLine();
            Console.WriteLine("Hit Enter to Exit");
            Console.ReadLine();

        }

        //#########################################################################################

        //Tests which is faster -- modulus or alternate.
        static void TestModulusOrAlternative(int max, int threshold)
        {
            Console.WriteLine("################################################################");
            Console.WriteLine("######## " + System.Reflection.MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("Iterations: " + max.ToString("#,##0") + " Modulus threshold: " + threshold.ToString("#,##0"));
            Console.WriteLine();
            long total = 0;
            long value = 0;
            int y = 0;
            string xAsString;
            DateTime end;
            DateTime start = DateTime.Now;
            Console.WriteLine("Starting T1: modulus % at: " + start);
            for (int x = 0; x < max; x++)
            {
                if (x % threshold == 0)
                    total += x;
            }
            end = DateTime.Now;
            Console.WriteLine("Finished at: " + end);
            Console.WriteLine("Total: " + total.ToString("#,##0"));
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine();

            total = 0;
            value = 0;
            start = DateTime.Now;
            Console.WriteLine("Starting T2: System.Math.DivRem " + start.ToLongTimeString());
            for (int x = 0; x < max; x++)
            {
                System.Math.DivRem((long)x, (long)threshold, out value);
                if (value == 0)
                    total += x; 
            } 
            end = DateTime.Now;
            Console.WriteLine("Finished at: " + end);
            Console.WriteLine("Total: " + total.ToString("#,##0"));
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine();

            total = 0;
            y = 0;
            start = DateTime.Now;
            Console.WriteLine("Starting T3: add alternative: " + start);
            for (int x = 0; x < max; x++)
            {
                if (y > (threshold - 1))
                {
                    y = 0;
                    total += x;
                }
                y += 1;
            }
            end = DateTime.Now;
            Console.WriteLine("Finished at: " + end);
            Console.WriteLine("Total: " + total.ToString("#,##0"));
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine();

            total = 0;
            start = DateTime.Now;
            Console.WriteLine("Starting T4: ((x/y) * y) == x: " + start);
            for (int x = 0; x < max; x++)
            {
                if (((x / threshold) * threshold) == x)
                    total += x; 
            }
            end = DateTime.Now;
            Console.WriteLine("Finished at: " + end);
            Console.WriteLine("Total: " + total.ToString("#,##0"));
            Console.WriteLine("Time: " + (end - start));
            Console.WriteLine();

            if (max <= Int32.MaxValue / 1000)
            { //if it's greater than Int32.MaxValue / 1000 it takes way toooooooooooooooo looooooong
                y = 0;
                total = 0;
                start = DateTime.Now;
                Console.WriteLine("Starting T5: while-loop countdown: " + start);
                for (int x = 0; x < max; x++)
                {
                    y = x;
                    while (y >= threshold)
                        y -= threshold;
                    if (y == 0)
                        total += x;
                }
                end = DateTime.Now;
                Console.WriteLine("Finished at: " + end);
                Console.WriteLine("Total: " + total.ToString("#,##0"));
                Console.WriteLine("Time: " + (end - start));
                Console.WriteLine();
            }

        }

    } //class

} //namespace

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

using System;

namespace TestApplication

{

class Program

{

static void Main(string[] args)

{

DateTime end;

DateTime start = DateTime.Now;

Console.WriteLine("### Overall Start Time: " + start.ToLongTimeString());

Console.WriteLine();

TestModulusVsIncrement(Int32.MaxValue, 123);

TestModulusVsIncrement(Int32.MaxValue / 1000, 123);

TestModulusVsIncrement(Int32.MaxValue / 10000, 123);

TestModulusVsIncrement(Int32.MaxValue, 10);

TestModulusVsIncrement(Int32.MaxValue / 1000, 10);

TestModulusVsIncrement(Int32.MaxValue / 10000, 10);

TestModulusVsIncrement(Int32.MaxValue, 2);

TestModulusVsIncrement(Int32.MaxValue / 1000, 2);

TestModulusVsIncrement(Int32.MaxValue / 10000, 2);

end = DateTime.Now;

Console.WriteLine();

Console.WriteLine("### Overall End Time: " + end.ToLongTimeString());

Console.WriteLine("### Overall Run Time: " + (end - start));

Console.WriteLine();

Console.WriteLine("Hit Enter to Exit");

Console.ReadLine();

}

//#########################################################################################

//Tests which is faster -- modulus or alternate.

static void TestModulusOrAlternative(int max, int threshold)

{

Console.WriteLine("################################################################");

Console.WriteLine("######## " + System.Reflection.MethodBase.GetCurrentMethod().Name);

Console.WriteLine("Iterations: " + max.ToString("#,##0") + " Modulus threshold: " + threshold.ToString("#,##0"));

Console.WriteLine();

long total = 0;

long value = 0;

int y = 0;

string xAsString;

DateTime end;

DateTime start = DateTime.Now;

Console.WriteLine("Starting T1: modulus % at: " + start);

for (int x = 0; x < max; x++)

{

if (x % threshold == 0)

total += x;

}

end = DateTime.Now;

Console.WriteLine("Finished at: " + end);

Console.WriteLine("Total: " + total.ToString("#,##0"));

Console.WriteLine("Time: " + (end - start));

Console.WriteLine();

total = 0;

value = 0;

start = DateTime.Now;

Console.WriteLine("Starting T2: System.Math.DivRem " + start.ToLongTimeString());

for (int x = 0; x < max; x++)

{

System.Math.DivRem((long)x, (long)threshold, out value);

if (value == 0)

total += x;

}

end = DateTime.Now;

Console.WriteLine("Finished at: " + end);

Console.WriteLine("Total: " + total.ToString("#,##0"));

Console.WriteLine("Time: " + (end - start));

Console.WriteLine();

total = 0;

y = 0;

start = DateTime.Now;

Console.WriteLine("Starting T3: add alternative: " + start);

for (int x = 0; x < max; x++)

{

if (y > (threshold - 1))

{

y = 0;

total += x;

}

y += 1;

}

end = DateTime.Now;

Console.WriteLine("Finished at: " + end);

Console.WriteLine("Total: " + total.ToString("#,##0"));

Console.WriteLine("Time: " + (end - start));

Console.WriteLine();

total = 0;

start = DateTime.Now;

Console.WriteLine("Starting T4: ((x/y) * y) == x: " + start);

for (int x = 0; x < max; x++)

{

if (((x / threshold) * threshold) == x)

total += x;

}

end = DateTime.Now;

Console.WriteLine("Finished at: " + end);

Console.WriteLine("Total: " + total.ToString("#,##0"));

Console.WriteLine("Time: " + (end - start));

Console.WriteLine();

if (max <= Int32.MaxValue / 1000)

{ //if it's greater than Int32.MaxValue / 1000 it takes way toooooooooooooooo looooooong

y = 0;

total = 0;

start = DateTime.Now;

Console.WriteLine("Starting T5: while-loop countdown: " + start);

for (int x = 0; x < max; x++)

{

y = x;

while (y >= threshold)

y -= threshold;

if (y == 0)

total += x;

}

end = DateTime.Now;

Console.WriteLine("Finished at: " + end);

Console.WriteLine("Total: " + total.ToString("#,##0"));

Console.WriteLine("Time: " + (end - start));

Console.WriteLine();

}

} //class

} //namespace

Spread the love

C# .Net: Use the Modulus Operator or Alternative?

The Background:

The Set Up:

The Runs:

The Winner Is Obvious:

In Summary:

The Code:

David Lozinski