Skip to content

Instantly share code, notes, and snippets.

@k-gregory
Last active April 24, 2017 20:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save k-gregory/3400b0dfb485f23750b6582a55e2fc54 to your computer and use it in GitHub Desktop.
Save k-gregory/3400b0dfb485f23750b6582a55e2fc54 to your computer and use it in GitHub Desktop.
C# Matrix multiplication benchmark
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace SharpoBench
{
interface Benchmark<TInit, TResult>
{
void Prepare(TInit parameters);
TResult Run();
}
class BenchmarkRunner<TInit,TResult>
{
private Stopwatch sw = new Stopwatch();
private List<Tuple<string, Benchmark<TInit,TResult>>> benchmarks = new List<Tuple<string,Benchmark<TInit, TResult>>>();
public void AddTest(string name, Benchmark<TInit, TResult> bench)
{
benchmarks.Add(new Tuple<string, Benchmark<TInit, TResult>>(name, bench));
}
public void Benchmark(TInit input)
{
foreach (var pair in benchmarks)
{
string implName = pair.Item1;
Benchmark<TInit, TResult> impl = pair.Item2;
impl.Prepare(input);
sw.Reset();
sw.Start();
var res = impl.Run();
sw.Stop();
Console.WriteLine("{0} run for {1}", implName, sw.Elapsed);
Console.WriteLine("{0}:{1}", res, implName);
}
Console.WriteLine("All tests were run!");
}
}
abstract class MatrixMultiplierBase : Benchmark<Tuple<double[,], double[,]>, double>
{
protected double[,] a, b;
protected double[,] res;
protected int m, n, p;//Matrix dismensions: MxN and NxP -- result is MxP
public void Prepare(Tuple<double[,], double[,]> parameters)
{
a = (double[,])parameters.Item1.Clone();
b = (double[,])parameters.Item2.Clone();
m = a.GetLength(0);
n = a.GetLength(1);
if (b.GetLength(0) != n) throw new InvalidOperationException();
p = b.GetLength(1);
res = new double[m, p];
}
abstract protected void DoMultiplication();//TemplateMethod
public double Run()
{
DoMultiplication();
return res[1, 1];
}
}
class NaїveMatrixMultiplier : MatrixMultiplierBase
{
override protected void DoMultiplication()
{
for(int i = 0; i < m; i++)
{
for(int j = 0; j < p; j++)
{
double s = 0;
for (int k = 0; k < n; k++)
s += a[i, k] * b[k, j];
res[i, j] = s;
}
}
}
}
class TransposedMatrixMultiplier : MatrixMultiplierBase
{
override protected void DoMultiplication()
{
//Transpose
double[,] trans = new double[p, n];
for (int i = 0; i < n; i++)
for (int j = 0; j < p; j++)
trans[j, i] = b[i, j];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < p; j++)
{
double s = 0;
for (int k = 0; k < n; k++)
s += a[i, k] * trans[j,k];
res[i, j] = s;
}
}
}
}
class ColumnExtractingMatrixMultiplier : MatrixMultiplierBase
{
override protected void DoMultiplication()
{
//Extract columns
double[][] columns = new double[p][];
for(int i = 0; i < p; i++)
{
double[] column = new double[n];
for (int j = 0; j < n; j++)
column[j] = b[j, i];
columns[i] = column;
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < p; j++)
{
double[] column = columns[j];
double s = 0;
for (int k = 0; k < n; k++)
s += a[i, k] * column[k];
res[i, j] = s;
}
}
}
}
class ColumnRowExtractingMatrixMultiplier : MatrixMultiplierBase
{
override protected void DoMultiplication()
{
//{{Extract columns
var bColumns = new double[p][];
for (int i = 0; i < p; i++)
{
double[] column = new double[n];
for (int j = 0; j < n; j++)
column[j] = b[j, i];
bColumns[i] = column;
}
//}}
double[] row = new double[n];
for (int i = 0; i < m; ++i)
{
//{{Extract row
for (int j = 0; j < n; j++)
row[j] = a[i, j];
//}}
for (int j = 0; j < p; ++j)
{
double[] column = bColumns[j];
double s = 0;
for (int k = 0; k < n; k++)
s += row[k] * column[k];
res[i, j] = s;
}
}
}
}
class Program
{
static double[,] MatGen(int n)
{
double tmp = 1.0 / n / n;
var a = new double[n, n];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
a[i, j] = tmp * (i - j) * (i + j);
return a;
}
static void Main(string[] args)
{
double[,] hardSizedMatrix = MatGen(2000);
var bench = new BenchmarkRunner<Tuple<double[,], double[,]>, double>();
bench.AddTest("Naїve", new NaїveMatrixMultiplier());
bench.AddTest("Transposed", new TransposedMatrixMultiplier());
bench.AddTest("ColumnExtracting", new ColumnExtractingMatrixMultiplier());
bench.AddTest("ColumnRowExtracting", new ColumnRowExtractingMatrixMultiplier());
Console.WriteLine("Warming up!");
for (int i = 1; i < 10; i++)
{
double[,] warmUpMatrix = MatGen(70 * i);
bench.Benchmark(new Tuple<double[,], double[,]>(warmUpMatrix, warmUpMatrix));
}
Console.WriteLine("That were warming up results, wait for reel results");
for (int i = 0; i < 3; i++) Console.WriteLine();
Console.WriteLine("Real results");
bench.Benchmark(new Tuple<double[,], double[,]>(hardSizedMatrix, hardSizedMatrix));
Console.ReadKey();
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment