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:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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:
1234567for (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:
123456for (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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 |