I am writing code that should apply a different algorithm to a large data set, depending on the setting. The data set is large, and real timings have shown that we need to optimize this if possible.
The selected algorithm should be executed in many subsets of data from a large array. So I decided to try several different approaches:
- Assign a delegate
Func<>to reference the desired algorithm. Call this delegate from the main loop. - Scroll through the data and call the corresponding algorithm from the main loop.
- Call a separate method that implements the main loop for each algorithm.
In my tests, each approach invoked the same basic method calculate(). (Of course, the actual code calls a different method for each algorithm, but here I am testing the fastest way to call the algorithm, not the algorithm itself.)
Each of the tests calls the required algorithm in the ITERStimes loop .
This test code DataReductionAlgorithmis just an enumeration that defines various algorithms. It really was not used, except for modeling what will happen in real code.
Here is my test implementation for approach (1). It is very simple: assign the Func<> aalgorithm that is being called, then call it from the loop:
private static void test1(int[] data, DataReductionAlgorithm algorithm)
{
Func<int[], int, int, int> a;
switch (algorithm)
{
case DataReductionAlgorithm.Max:
a = calculate;
break;
case DataReductionAlgorithm.Mean:
a = calculate;
break;
default:
a = calculate;
break;
}
for (int i = 0; i < ITERS; ++i)
a(data, 0, data.Length);
}
(2). if . , :
private static void test2(int[] data, DataReductionAlgorithm algorithm)
{
switch (algorithm)
{
case DataReductionAlgorithm.Max:
for (int i = 0; i < ITERS; ++i)
calculate(data, 0, data.Length);
break;
case DataReductionAlgorithm.Mean:
for (int i = 0; i < ITERS; ++i)
calculate(data, 0, data.Length);
break;
default:
for (int i = 0; i < ITERS; ++i)
calculate(data, 0, data.Length);
break;
}
}
(3). if . , (2), if ITERS , :
private static void test3(int[] data, DataReductionAlgorithm algorithm)
{
for (int i = 0; i < ITERS; ++i)
{
switch (algorithm)
{
case DataReductionAlgorithm.Max:
calculate(data, 0, data.Length);
break;
case DataReductionAlgorithm.Mean:
calculate(data, 0, data.Length);
break;
default:
calculate(data, 0, data.Length);
break;
}
}
}
- , , , test2(), , , .
, , test2():
private static void test4(int[] data, DataReductionAlgorithm algorithm)
{
switch (algorithm)
{
case DataReductionAlgorithm.Max:
iterate(ITERS, data);
break;
case DataReductionAlgorithm.Mean:
iterate(ITERS, data);
break;
default:
iterate(ITERS, data);
break;
}
}
private static void iterate(int n, int[] data)
{
for (int i = 0; i < n; ++i)
calculate(data, 0, data.Length);
}
, - :
using System;
using System.Diagnostics;
using System.Linq;
namespace Demo
{
public enum DataReductionAlgorithm
{
Single,
Max,
Mean
}
internal class Program
{
private const int ITERS = 100000;
private void run()
{
int[] data = Enumerable.Range(0, 10000).ToArray();
Stopwatch sw = new Stopwatch();
for (int trial = 0; trial < 4; ++trial)
{
sw.Restart();
test1(data, DataReductionAlgorithm.Mean);
Console.WriteLine("test1: " + sw.Elapsed);
sw.Restart();
test2(data, DataReductionAlgorithm.Mean);
Console.WriteLine("test2: " + sw.Elapsed);
sw.Restart();
test3(data, DataReductionAlgorithm.Mean);
Console.WriteLine("test3: " + sw.Elapsed);
sw.Restart();
test4(data, DataReductionAlgorithm.Mean);
Console.WriteLine("test4: " + sw.Elapsed);
Console.WriteLine();
}
}
private static void test1(int[] data, DataReductionAlgorithm algorithm)
{
Func<int[], int, int, int> a;
switch (algorithm)
{
case DataReductionAlgorithm.Max:
a = calculate;
break;
case DataReductionAlgorithm.Mean:
a = calculate;
break;
default:
a = calculate;
break;
}
for (int i = 0; i < ITERS; ++i)
a(data, 0, data.Length);
}
private static void test2(int[] data, DataReductionAlgorithm algorithm)
{
switch (algorithm)
{
case DataReductionAlgorithm.Max:
for (int i = 0; i < ITERS; ++i)
calculate(data, 0, data.Length);
break;
case DataReductionAlgorithm.Mean:
for (int i = 0; i < ITERS; ++i)
calculate(data, 0, data.Length);
break;
default:
for (int i = 0; i < ITERS; ++i)
calculate(data, 0, data.Length);
break;
}
}
private static void test3(int[] data, DataReductionAlgorithm algorithm)
{
for (int i = 0; i < ITERS; ++i)
{
switch (algorithm)
{
case DataReductionAlgorithm.Max:
calculate(data, 0, data.Length);
break;
case DataReductionAlgorithm.Mean:
calculate(data, 0, data.Length);
break;
default:
calculate(data, 0, data.Length);
break;
}
}
}
private static void test4(int[] data, DataReductionAlgorithm algorithm)
{
switch (algorithm)
{
case DataReductionAlgorithm.Max:
iterate(ITERS, data);
break;
case DataReductionAlgorithm.Mean:
iterate(ITERS, data);
break;
default:
iterate(ITERS, data);
break;
}
}
private static void iterate(int n, int[] data)
{
for (int i = 0; i < n; ++i)
calculate(data, 0, data.Length);
}
private static int calculate(int[] data, int i1, int i2)
{
int result = 0;
for (int i = i1; i < i2; ++i)
result += data[i];
return result;
}
private static void Main()
{
new Program().run();
}
}
}
-, , RELEASE BUILD . - - .
.Net 4.51 Windows 8.1 Intel. ( , .Net 4.5 .Net 4.)
, x64/AnyCPU x86.
: , test1() test3() , test2() , test4() , test2().
x86:
test1: 00:00:00.5892166
test2: 00:00:00.5848795
test3: 00:00:00.5866006
test4: 00:00:00.5867143
, , , test1() , , (, , ).
x64:
test1: 00:00:00.8769743
test2: 00:00:00.8750667
test3: 00:00:00.5839475
test4: 00:00:00.5853400
Whoah!
test1() test2()? . test2() , test3()?
test4() , test2()?
x86 x64?
- ? - -, 10 , 15 .
.
, JIT, @usr, :
using System;
using System.Diagnostics;
namespace Demo
{
internal class Program
{
private const int ITERS = 10000;
private void run()
{
Stopwatch sw = new Stopwatch();
int[] data = new int[10000];
for (int trial = 0; trial < 4; ++trial)
{
sw.Restart();
test1(data, 0);
var elapsed1 = sw.Elapsed;
sw.Restart();
test2(data, 0);
var elapsed2 = sw.Elapsed;
Console.WriteLine("Ratio = " + elapsed1.TotalMilliseconds / elapsed2.TotalMilliseconds);
}
Console.ReadLine();
}
private static void test1(int[] data, int x)
{
switch (x)
{
case 0:
{
for (int i = 0; i < ITERS; ++i)
dummy(data);
break;
}
}
}
private static void test2(int[] data, int x)
{
switch (x)
{
case 0:
{
loop(data);
break;
}
}
}
private static int dummy(int[] data)
{
int max = 0;
for (int i = 0; i < data.Length; ++i)
if (data[i] > max)
max = data[i];
return max;
}
private static void loop(int[] data)
{
for (int i = 0; i < ITERS; ++i)
dummy(data);
}
private static void Main()
{
new Program().run();
}
}
}
// Also try with "int i = 1" in the loop below..
i = 0, x64 build:
Ratio = 1.52235829774506
Ratio = 1.50636405328076
Ratio = 1.52291602053827
Ratio = 1.52803278744701
i = 1, :
Ratio = 1.16920209593233
Ratio = 0.990370350435142
Ratio = 0.991150637472754
Ratio = 0.999941245001628
!:)