I've been doing some playing around and have written some code for
mathematical operations. Among those operations is something called a
box approximation for the integral of a function
( http://en.wikipedia.org/wiki/Rectangle_Rule ).
At the behest of mhutch in #mono, I tried a few things to improve the
speed of the method. The original speed was approximately 385 ms for
10,000,000 iterations of the midpoint box approximation over the
function x^3. This included 4 multiplies, 3 adds, and 1 function call
for each run of the loop, plus a one-time cost of a divide.
The things attempted to improve speed were: inlining the function, and
removing a switch() that determined if the approximation was to be
midpoint, left, or right.
Here are the results from those tests:
Iteration 1
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, no inline, w/ branch: 469
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, inlined, w/ branch: 132
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, no inline, no branch: 235
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, inlined, no branch: 250
....(Much of the same here)....
Iteration 10
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, no inline, w/ branch: 456
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, inlined, w/ branch: 130
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, no inline, no branch: 228
Integral of x^3 over [0, 5]: 156.250062500004
Box approximation, inlined, no branch: 245
The thing that immediately struck me as odd was: how is the inlined
BoxApproximation that HAS a switch() call to check whether it's doing
left, right or midpoint faster than everything else. It's not just a
little faster, it's a lot faster. The machine running all of these tests
is running Mono trunk as of a few days ago, x86 processor with a 2.0 GHz
clock speed and 512 MB of RAM (it's a VMware server virtual machine).
Running the same thing on Mono 1.9.1 outside of VMware yields similar
results.
My question is--why is that method the fastest? Attached are compileable
versions of the Main() method and the class that holds the function
definitions.
Thanks,
Bojan Rajkovic
// Functions.cs
//
// Copyright (c) 2008 Bojan Rajkovic
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//
//
using System;
namespace MathPlay
{
public enum ApproximationType
{
Left,
Right,
Midpoint
}
static class Function
{
public static double Limit(double accuracy, long step, Func<long, double> f)
{
double lastResult, nextResult;
long n = 0;
lastResult = f(n);
if (double.IsNaN(lastResult)) lastResult = 0;
else if (double.IsInfinity(lastResult)) lastResult = 0;
long iterations = 0;
while (true) {
n += step;
nextResult = f(n);
double differential = Math.Abs(nextResult - lastResult);
if (differential <= accuracy) {
return nextResult;
} else {
lastResult = nextResult;
iterations++;
}
}
}
public static class Derivative
{
public static double Numeric(double startingApproximation, double minimumApproximation, double x, Func<double, double> f)
{
if (startingApproximation <= minimumApproximation)
return f(x);
double approximation = startingApproximation;
double value = f(x);
while (approximation > minimumApproximation) {
value = (f(x + approximation) - f(x - approximation))/(2*approximation);
approximation /= 2;
}
return value;
}
}
public static class Integral
{
public static double BoxApproximation(double start, double end, long steps, Func<double, double> f, ApproximationType type)
{
double delta = (end - start)/steps;
double approximationFactor = 0;
double result = 0;
switch (type) {
case ApproximationType.Left:
approximationFactor = 1;
break;
case ApproximationType.Midpoint:
approximationFactor = .5;
break;
case ApproximationType.Right:
approximationFactor = 0;
break;
default:
approximationFactor = 0;
break;
}
for (int i = 0; i <= steps; i++)
result += f(start + (i + approximationFactor)*delta) * delta;
return result;
}
public static double MidpointApproximation(double start, double end, long steps, Func<double, double> f)
{
double delta = (end - start)/steps;
double result = 0;
for (int i = 0; i <= steps; i++)
result += f(start + (i + 0.5)*delta) * delta;
return result;
}
public static double MidpointApproximationInline(double start, double end, long steps)
{
double delta = (end - start)/steps;
double result = 0;
double x;
for (int i = 0; i <= steps; i++) {
x = (start + (i + 0.5)*delta);
result += x*x*x*delta;
}
return result;
}
public static double BoxApproximationInline(double start, double end, long steps, ApproximationType type)
{
double delta = (end - start)/steps;
double approximationFactor = 0;
double result = 0;
double x;
switch (type) {
case ApproximationType.Left:
approximationFactor = 1;
break;
case ApproximationType.Midpoint:
approximationFactor = .5;
break;
case ApproximationType.Right:
approximationFactor = 0;
break;
default:
approximationFactor = 0;
break;
}
for (int i = 0; i <= steps; i++) {
x = (start + (i + approximationFactor)*delta);
result += x*x*x*delta;
}
return result;
}
public static double SimpsonApproximation(double start, double end, double accuracy, Func<double, double> f)
{
double h = end - start;
double s2 = 1;
double s = f(start) + f(end);
double s1, s3, x;
int iterations = 0;
do {
s3 = s2;
h /= 2;
s1 = 0;
x = start + h;
do {
s1 += 2*f(x);
x += 2*h;
} while (x < end);
s += s1;
s2 = (s + s1)*h/3;
x = Math.Abs(s3 - s2)/15;
iterations++;
} while ( x > accuracy);
return s2;
}
}
}
}
// MathPlay.cs
//
// Copyright (c) 2008 Bojan Rajkovic
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//
//
using System;
using System.Diagnostics;
using MathPlay;
public static class TestMath
{
public static void Main()
{
Func<double, double> g = x => x*x*x;
for (int i = 1; i < 11; i++) {
Console.WriteLine("Iteration {0}", i);
Stopwatch sw = new Stopwatch();
sw.Start();
Console.WriteLine("\tIntegral of x^3 over [0, 5]: {0}",
Function.Integral.BoxApproximation(0, 5, 10000000, g, ApproximationType.Midpoint));
sw.Stop();
Console.WriteLine("\tBox approximation, no inline, w/ branch: {0}", sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
Console.WriteLine("\tIntegral of x^3 over [0, 5]: {0}",
Function.Integral.BoxApproximationInline(0, 5, 10000000, ApproximationType.Midpoint));
sw.Stop();
Console.WriteLine("\tBox approximation, inlined, w/ branch: {0}", sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
Console.WriteLine("\tIntegral of x^3 over [0, 5]: {0}",
Function.Integral.MidpointApproximation(0, 5, 10000000, g));
sw.Stop();
Console.WriteLine("\tBox approximation, no inline, no branch: {0}", sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
Console.WriteLine("\tIntegral of x^3 over [0, 5]: {0}",
Function.Integral.MidpointApproximationInline(0, 5, 10000000));
sw.Stop();
Console.WriteLine("\tBox approximation, inlined, no branch: {0}", sw.ElapsedMilliseconds);
}
}
}
_______________________________________________
Mono-devel-list mailing list
Mono-devel-list@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-devel-list
