Die Verwendung von mehrdimensionalen Arrays ist oftmals ein wesentlicher Bestandteil in Programmen. Je nach Problemstellung und Größe der Arrays kann der Zugriff auf solche die Laufzeit eines Programms negativ beeinflussen.
In C# gibt es grundsätzlich neben den eindimensionalen Arrays 2 Arten von mehrdimensionalen Arrays. Diese unterscheiden sich nur in ihrer Notation:
- [,] – Multidimensionale Arrays
- [][] – Jagged-Arrays
Bei multidimensionalen Arrays werden die Dimensionen durch ein Komma getrennt, bei Jagged-Arrays durch die erneute Klammerung. Multidimensionale Arrays haben eine feste Größe. Bei einem Jagged-Array kann die Größe variieren, da es ein Array von Arrays ist. Das ist im Grunde genommen eigentlich schon alles was man darüber wissen sollte. – Wie aber steht es jetzt mit den Geschwindigkeits-Unterschieden? Gibt es vielleicht noch andere Möglichkeiten?
Ja! Die gibt es definitiv. Bei einem Disput mit einem Kommilitonen über genau dieses Thema hat dieser prompt einen Eintrag in seinem Blog dazu und dazugehörige Messergebnisse veröffentlicht:
Manolo's HPC Blog
Er verwendet dort eine weitere, eher aus der Welt der C Programmierer bekannte Technik, um mehrdimensionale Arrays zu realisieren. Es wird einfach ein eindimensionales Array verwendet, das alle Elemente linear beinhaltet.
Der Zugriff erfolgt über die Formel:
position = Y * breite + X
Als ich das Ergebnis das erste mal sah, konnte ich kaum glauben, dass dieses schneller als ein Jagged-Array ist. Aber bei einer genaueren Untersuchung erklärt sich auch warum. Darf man dem manik.net – Blog trauen:
MSIL kann eindimensionale Arrays besser optimieren wie mehrdimensionale.
Auf MSIL ebene sieht man den unterschied:
int [,] secondarr = new int[1, 2];
secondarr[0, 0] = 40;
MSIL:
IL_0029: ldc.i4.s 40
IL_002b: call instance void int32[0...,0...]::Set(int32, int32,in32)
Mit einem Jaggedarray sieht das ganze dann auf MSIL so aus:
IL_001c: ldc.i4.s 40
IL_001e: stelem.i4
stelem = „store an element“
Bei mehrdimensionalen Arrays wird der ganze „Generic Type“-Kram also betrieben was einiges an Overhead erzeugt.
Daher ist es ratsam wann immer möglich ein lineares Array anstelle von einem Mehrdimensionalen Array zu verwenden.
Ich habe mir die ganze Sache aber in eigener Regie noch einmal angesehen. Als Ergebnis habe ich es geschafft, eine noch schnellere Variante zu programmieren. Diese setzt allerdings ein \unsafe bei den Compiler-Einstellungen voraus.
Anstelle auf die einzelnen Elemente des Arrays zuzugreifen, wird direkt auf einen Pointer zugegriffen. – Eigentlich nichts besonderes, kann aber bei manch einer Berechnung den ein oder anderen Performancegewinn bringen.
Die Ergebnisse sehen dabei wie folgt aus:
Result = 249500250000000
1000times: Matrix A with [1000, 1000] (matrix array): 11637ms
Result = 249500250000000
1000times: Matrix B with [1000][1000] (jagged array): 6361ms
Result = 249500250000000
1000times: Matrix C with [1000* 1000] (linear array): 5486ms
Result = 249500250000000
1000times: Matrix D with [1000* 1000] (unsafe array): 5175ms!!!
Gegenüber dem [,] Array sind die beiden letzten Varianten ungefähr doppelt so schnell.
Also für die Zukunft merken:
Den Quellcode zum verifizieren und selber Testen gibt es hier:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace SpeedTest
{
class Program
{
static void Main(string[] args)
{
int n = 1000;
Stopwatch swatch = new Stopwatch();
double[,] A = new double[n, n];
swatch.Start();
CalcMatrix(A,n);
swatch.Stop();
Console.WriteLine("{0}times: Matrix A with [{0}, {0}] (matrix array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset();
double[][] B = new double[n][];
// init jagged arrays
for (int i = 0; i < n; i++)
{
B[i] = new double[n];
}
swatch.Start();
CalcJagged(B, n);
swatch.Stop();
Console.WriteLine("{0}times: Matrix B with [{0}][{0}] (jagged array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset();
double[] C = new double[n* n];
swatch.Start();
CalcLinear(C, n);
swatch.Stop();
Console.WriteLine("{0}times: Matrix C with [{0}* {0}] (linear array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset();
unsafe
{
double[] D = new double[n * n];
swatch.Start();
fixed(double* pD = D)
CalcUnsafe(pD,n);
swatch.Stop();
}
Console.WriteLine("{0}times: Matrix D with [{0}* {0}] (unsafe array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset();
Console.ReadKey();
}
private static void CalcJagged(double[][] B, int n)
{
double result = 0;
for (int x = 0; x < n; x++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
B[i][j] = i * j;
result += B[i][j];
}
}
}
Console.WriteLine("Result = " + result);
}
private static void CalcMatrix( double[,] A, int n)
{
double result = 0;
for (int x = 0; x < n; x++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
A[i, j] = i * j;
result += A[i, j];
}
}
}
Console.WriteLine("Result = " + result);
}
private static void CalcLinear(double[] C, int n)
{
double result = 0;
for (int x = 0; x < n; x++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
C[i * n + j] = i * j;
result += C[i * n + j];
}
}
}
Console.WriteLine("Result = " + result);
}
unsafe private static void CalcUnsafe(double* pD, int n)
{
double result = 0;
for (int x = 0; x < n; x++)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
*(pD + i * n + j) = i * j;
result += *(pD + i * n + j);
}
}
}
Console.WriteLine("Result = " + result);
}
}
}