Spread the love

Does caching calculated loop indexes make a difference?

Recently I was reviewing code to a real time financial application. Within a major for-loop construct, I came across the following subset of C# code:

for (int index = 1; index < maxLoops; index++)
{
	//Did some stuff

	_iSeries1[index] = _coeff1*MarketSeries.Close[index] + _coeff2*_iSeries1[index - 1];
	_iSeries2[index] = _coeff1*_iSeries1[index] + _coeff2*_iSeries2[index - 1];
	_iSeries3[index] = _coeff1*_iSeries2[index] + _coeff2*_iSeries3[index - 1];
	_iSeries4[index] = _coeff1*_iSeries3[index] + _coeff2*_iSeries4[index - 1];
	_iSeries5[index] = _coeff1*_iSeries4[index] + _coeff2*_iSeries5[index - 1];
	_iSeries6[index] = _coeff1*_iSeries5[index] + _coeff2*_iSeries6[index - 1];

	//Did more stuff in which objects and arrays were frequently accessed with [index - 1]
}

for (int index = 1; index < maxLoops; index++)

{

//Did some stuff

_iSeries1[index] = _coeff1*MarketSeries.Close[index] + _coeff2*_iSeries1[index - 1];

_iSeries2[index] = _coeff1*_iSeries1[index] + _coeff2*_iSeries2[index - 1];

_iSeries3[index] = _coeff1*_iSeries2[index] + _coeff2*_iSeries3[index - 1];

_iSeries4[index] = _coeff1*_iSeries3[index] + _coeff2*_iSeries4[index - 1];

_iSeries5[index] = _coeff1*_iSeries4[index] + _coeff2*_iSeries5[index - 1];

_iSeries6[index] = _coeff1*_iSeries5[index] + _coeff2*_iSeries6[index - 1];

//Did more stuff in which objects and arrays were frequently accessed with [index - 1]

}

Look how many times [index – 1] is referenced in the above code sample.

Every programmer knows that mathematical computations can require a lot of CPU time depending on the calculation. In the above example, while subtraction itself isn’t the worst performance-wise, repeating the same calculation numerous times can impact performance.

That’s where this Curious Consultant started wondering… is there a performance gain in C# if instead of calculating indexes on the fly, we do it once at the beginning of the loop, store that value, and use that value instead? What would happen if we removed the multiple subtraction operations? Eg, caching calculated loop indexes.

Let’s find out!

Constructing the Test

There is 1 method used for this test:

the first part calculates the index we’ll use to access objects and store in a local variable to provide a caching mechanism:

for (int x = 0; x < max; x++) { int xMinus1 = x - 1; array[x] = someArray[xMinus1]; array2[x] = someArray2[xMinus1]; //etc etc }

1
2
3
4
5
6
7

for (int x = 0; x < max; x++)
{
int xMinus1 = x - 1;
array[x] = someArray[xMinus1];
array2[x] = someArray2[xMinus1];
//etc etc
}
the second part does it straight up every time. x – 1. x – 1. x – 1:

for (int x = 0; x < max; x++) { array[x] = someArray[x - 1]; array2[x] = someArray2[x - 1]; //etc etc }

1
2
3
4
5
6

for (int x = 0; x < max; x++)
{
array[x] = someArray[x - 1];
array2[x] = someArray2[x - 1];
//etc etc
}

We perform this looping while accessing common C# arrays and objects:

The code is written in Visual Studio 2017 targeting .Net Framework version 4.8 x64, compiled in “Release” mode the build option “Optimize Code” checked. The source code is available at the end of this blog so you can benchmark it on your own system.

Assumptions:

No exception handling as no exceptions should occur
to make the test worth-while, the cached index value had to be used at least half a dozen times to overcome the the cost of allocating the variable and assigning it.

The exe file was run under Windows 10 Professional 64-bit with 32GB of memory.

The test was run with each child method called the following number of times:

1,000
10,000
1,000,000
10,000,000
100,000,000

What do you think will happen?

Before starting, I predicted that the cached value would show a clear winning streak in the results. Whether it won by a little or a lot didn’t bother me so much as that it demonstrated a clear victory.

This test was run 3 times.

All times are indicated in minutes.seconds.milliseconds format. Lower numbers indicate faster run time performance.

Winners are highlighted in green; there are no points for second place.

	Number of Loops
Run #1	1,000	10,000	1,000,000	10,000,000	100,000,000
With Caching	00:00.0000025	00:00.0001509	00:00.0010144	00:00.0466154	00:05.1184002
Without Caching	00:00.0000006	00:00.0001142	00:00.0004692	00:00.0444236	00:05.1111640
Run #2	1,000	10,000	1,000,000	10,000,000	100,000,000
With Caching	00:00.0000026	00:00.0001911	00:00.0008241	00:00.0433287	00:05.0532665
Without Caching	00:00.0000004	00:00.0000780	00:00.0003955	00:00.0458396	00:05.0436073
Run #3	1,000	10,000	1,000,000	10,000,000	100,000,000
With Caching	00:00.0000024	00:00.0002148	00:00.0004917	00:00.0459788	00:05.0204457
Without Caching	00:00.0000003	00:00.0000545	00:00.0004701	00:00.0479565	00:05.0069124

In Summary:

The prediction certainly was wrong. In C#, it’s quite evident from the results that calculating the array / object index every single time won hands down.

And this is when [x – 1] is used at least 8 times in the code.

I could be wrong, but I suspect this happens because when doing the [x – 1], the CPU isn’t having to do a variable lookup, get the value, and place it where needed. Instead, it does a quick calculation, and doesn’t have the store the results anywhere, thus saving on memory lookup operations.

So in the more practical world, caching a calculated loop index isn’t the way to go unless your own benchmarks can confirm a higher win rate.

The Code:

using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Concurrent;
using System.Data;
using System.Data.Sql;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Threading;
using System.Diagnostics;

namespace TestApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime end;
            DateTime start = DateTime.Now;
            Console.WriteLine("### Overall Start Time: " + start.ToLongTimeString());
            Console.WriteLine();
            TestCachingCalculatedLoopIndex(1000);
            TestCachingCalculatedLoopIndex(10000);
            TestCachingCalculatedLoopIndex(1000000);
            TestCachingCalculatedLoopIndex(10000000);
            TestCachingCalculatedLoopIndex(100000000);
            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 how much faster it is to calculate the loop index x - 1 once versus every time on multiple arrays within a loop
        static void TestCachingCalculatedLoopIndex(int numberOfComparisons)
        {
            Console.WriteLine("######## " + System.Reflection.MethodBase.GetCurrentMethod().Name);
            Console.WriteLine("Number of comparisons: " + numberOfComparisons.ToString("#,##0"));

            Stopwatch sw = new Stopwatch();
            DateTime end = DateTime.Now;
            DateTime start = DateTime.Now;
            long totalSum = 0;
            int numberOfTimesToLoop = numberOfComparisons % 999;
            int maxNum = numberOfComparisons / 999;

            //initialize everything
            int[] i1 = new int[maxNum];
            double[] d1 = new double[maxNum];
            double[] d2 = new double[maxNum];
            string[] s1 = new string[maxNum];
            List<int> l = new List<int>();
            Dictionary<int, string> di1 = new Dictionary<int, string>();
            l = new List<int>(maxNum);
            di1 = new Dictionary<int, string>(maxNum);

            for (int x=0; x < maxNum; x++)
            {
                i1[x] = x;
                d1[x] = (x / 2);
                d2[x] = x * 0.5;
                s1[x] = x.ToString();
                l.Add(x);
                di1.Add(x, x.ToString());
            }

            Console.WriteLine("###########################################################");
            Console.WriteLine("Starting index test [x - 1] with caching at: " + DateTime.Now.ToLongTimeString());
            sw.Restart();
            for (int y = 0; y < numberOfTimesToLoop; y++)
            {
                for (int x = 0; x < maxNum; x++)
                {
                    //Cache the loop index instead of doing the "x - 1" every single time.
                    int xMinus1 = x - 1;
                    if (x > 0)
                    {
                        i1[x] = x + i1[xMinus1];
                        d1[x] = x + d1[xMinus1];
                        d2[x] = d1[x] - d2[xMinus1];
                        s1[x] = (i1[xMinus1] + d1[xMinus1]).ToString();
                        l[x] = l[xMinus1] - i1[x];
                        di1[x] = s1[xMinus1];
                        totalSum += i1[xMinus1] - i1[x];
                    }
                }
            }
            sw.Stop();
            Console.WriteLine("Finished at: " + DateTime.Now.ToLongTimeString());
            Console.WriteLine("Time to run: " + sw.Elapsed.ToString("mm\\:ss\\.fffffff"));
            Console.WriteLine("Sum is: " + totalSum.ToString("#,##0"));

            //reset everything
            Array.Clear(i1, 0, i1.Length);
            Array.Clear(d1, 0, d1.Length);
            Array.Clear(d2, 0, d2.Length);
            Array.Clear(s1, 0, s1.Length);
            l.Clear();
            di1.Clear();
            for (int x = 0; x < maxNum; x++)
            {
                i1[x] = x;
                d1[x] = (x / 2);
                d2[x] = x * 0.5;
                s1[x] = x.ToString();
                l.Add(x);
                di1.Add(x, x.ToString());
            }

            totalSum = 0;
            Thread.Sleep(500);

            Console.WriteLine("###########################################################");
            Console.WriteLine("Starting index test [x - 1] with no caching at: " + DateTime.Now.ToLongTimeString());
            sw.Restart();
            for (int y = 0; y < numberOfTimesToLoop; y++)
            {
                for (int x = 0; x < maxNum; x++)
                {
                    if (x > 0)
                    {
                        i1[x] = x + i1[x - 1];
                        d1[x] = x + d1[x - 1];
                        d2[x] = d1[x] - d2[x - 1];
                        s1[x] = (i1[x - 1] + d1[x - 1]).ToString();
                        l[x] = l[x - 1] - i1[x];
                        di1[x] = s1[x - 1];
                        totalSum += i1[x - 1] - i1[x];
                    }
                }
            }
            sw.Stop();
            Console.WriteLine("Finished at: " + DateTime.Now.ToLongTimeString());
            Console.WriteLine("Time to run: " + sw.Elapsed.ToString("mm\\:ss\\.fffffff"));
            Console.WriteLine("Sum is: " + totalSum.ToString("#,##0"));

            totalSum = 0;
            Thread.Sleep(500);

            Array.Clear(i1, 0, i1.Length);
            Array.Clear(d1, 0, d1.Length);
            Array.Clear(d2, 0, d2.Length);
            Array.Clear(s1, 0, s1.Length);
            l.Clear();
            di1.Clear();
            i1 = null;
            d1 = null;
            d2 = null;
            s1 = null;
            l = null;
            di1 = null;
            Thread.Sleep(500);
            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

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

using System;

using System.Collections.Generic;

using System.Collections;

using System.Collections.Concurrent;

using System.Data;

using System.Data.Sql;

using System.IO;

using System.Linq;

using System.Text;

using System.Text.RegularExpressions;

using System.Threading.Tasks;

using System.Threading;

using System.Diagnostics;

namespace TestApplication

{

class Program

{

static void Main(string[] args)

{

DateTime end;

DateTime start = DateTime.Now;

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

Console.WriteLine();

TestCachingCalculatedLoopIndex(1000);

TestCachingCalculatedLoopIndex(10000);

TestCachingCalculatedLoopIndex(1000000);

TestCachingCalculatedLoopIndex(10000000);

TestCachingCalculatedLoopIndex(100000000);

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 how much faster it is to calculate the loop index x - 1 once versus every time on multiple arrays within a loop

static void TestCachingCalculatedLoopIndex(int numberOfComparisons)

{

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

Console.WriteLine("Number of comparisons: " + numberOfComparisons.ToString("#,##0"));

Stopwatch sw = new Stopwatch();

DateTime end = DateTime.Now;

DateTime start = DateTime.Now;

long totalSum = 0;

int numberOfTimesToLoop = numberOfComparisons % 999;

int maxNum = numberOfComparisons / 999;

//initialize everything

int[] i1 = new int[maxNum];

double[] d1 = new double[maxNum];

double[] d2 = new double[maxNum];

string[] s1 = new string[maxNum];

List<int> l = new List<int>();

Dictionary<int, string> di1 = new Dictionary<int, string>();

l = new List<int>(maxNum);

di1 = new Dictionary<int, string>(maxNum);

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

{

i1[x] = x;

d1[x] = (x / 2);

d2[x] = x * 0.5;

s1[x] = x.ToString();

l.Add(x);

di1.Add(x, x.ToString());

}

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

Console.WriteLine("Starting index test [x - 1] with caching at: " + DateTime.Now.ToLongTimeString());

sw.Restart();

for (int y = 0; y < numberOfTimesToLoop; y++)

{

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

{

//Cache the loop index instead of doing the "x - 1" every single time.

int xMinus1 = x - 1;

if (x > 0)

{

i1[x] = x + i1[xMinus1];

d1[x] = x + d1[xMinus1];

d2[x] = d1[x] - d2[xMinus1];

s1[x] = (i1[xMinus1] + d1[xMinus1]).ToString();

l[x] = l[xMinus1] - i1[x];

di1[x] = s1[xMinus1];

totalSum += i1[xMinus1] - i1[x];

}

sw.Stop();

Console.WriteLine("Finished at: " + DateTime.Now.ToLongTimeString());

Console.WriteLine("Time to run: " + sw.Elapsed.ToString("mm\\:ss\\.fffffff"));

Console.WriteLine("Sum is: " + totalSum.ToString("#,##0"));

//reset everything

Array.Clear(i1, 0, i1.Length);

Array.Clear(d1, 0, d1.Length);

Array.Clear(d2, 0, d2.Length);

Array.Clear(s1, 0, s1.Length);

l.Clear();

di1.Clear();

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

{

i1[x] = x;

d1[x] = (x / 2);

d2[x] = x * 0.5;

s1[x] = x.ToString();

l.Add(x);

di1.Add(x, x.ToString());

}

totalSum = 0;

Thread.Sleep(500);

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

Console.WriteLine("Starting index test [x - 1] with no caching at: " + DateTime.Now.ToLongTimeString());

sw.Restart();

for (int y = 0; y < numberOfTimesToLoop; y++)

{

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

{

if (x > 0)

{

i1[x] = x + i1[x - 1];

d1[x] = x + d1[x - 1];

d2[x] = d1[x] - d2[x - 1];

s1[x] = (i1[x - 1] + d1[x - 1]).ToString();

l[x] = l[x - 1] - i1[x];

di1[x] = s1[x - 1];

totalSum += i1[x - 1] - i1[x];

}

sw.Stop();

Console.WriteLine("Finished at: " + DateTime.Now.ToLongTimeString());

Console.WriteLine("Time to run: " + sw.Elapsed.ToString("mm\\:ss\\.fffffff"));

Console.WriteLine("Sum is: " + totalSum.ToString("#,##0"));

totalSum = 0;

Thread.Sleep(500);

Array.Clear(i1, 0, i1.Length);

Array.Clear(d1, 0, d1.Length);

Array.Clear(d2, 0, d2.Length);

Array.Clear(s1, 0, s1.Length);

l.Clear();

di1.Clear();

i1 = null;

d1 = null;

d2 = null;

s1 = null;

l = null;

di1 = null;

Thread.Sleep(500);

Console.WriteLine();

}

} //class

} //namespace

Spread the love

Does caching calculated loop indexes make a difference?

Constructing the Test

What do you think will happen?

In Summary:

The Code:

David Lozinski