Comparing the speed of array assumptions.

Windows Live™

ProfileManolo's HPC BlogBlogLists

Tools

Help

< Previous Next >

August 08

Comparing the speed of array assumptions.

Dealing with arrays is not as trivial as the commodity .NET developer thinks. The assumption of all elements from a array is a practical computation in HPC applications. So a Microsoft Student Partner told me that in C# the best way to allocate and sum the array is the jagged way. But why? He could not give me an answer. I searched the Internet and found an article on the MSDN about FxCop (A tool to analyze managed assemblies). The tool shows some kind of warnings if you are a stupid programmer. So one warning is: “Prefer jagged arrays over multidimensional”. Okay, Microsoft choice seems to be “jagged arrays”.

I remember my first HPC lecture at the University where the lecturer told me that jagged arrays are potentially slow. An option to speed up the array operations is to use linear arrays. Comparing the speed of the different arrays would be helpful to argument in this discussion.

First let me introduce the sample benchmark code. First the preferred array will be initialized with the value 0.01 for each element. Next a sum of the whole array is computed p-times. In pseudo code:

init n = 1E+04, A = 0.01, p = 100
FOR o = 1,…,p DO
   FOR i = 1,…,n DO
      FOR j = 1,…,n DO
            s += A[i,j]     |     s += A[i][j]      |      s += A[i*n+j]
      OD
   OD
OD

The next table presents the results for multi, jagged and linear array. I unrolled the loop 8-times to get higher speedup. Each time represents one computation.

Type	Time in ms. without unroll	Time in ms. unroll
multi	1412	1026
jagged	419	344
linear	360	321

I benchmarked the versions on my INTEL Core2 E8400 with 4 GB 1,3 GHz DDR3 RAM. And now the code for this little ad-hoc benchmark of the array assumptions.

const int n = (int)1E+04;
const int p = 100;
double s = 0;
double[,] multi = new double[n, n];
Stopwatch watch = new Stopwatch();

for (int k = 0; k < n; k++)
  for (int h = 0; h < n; h++)
    multi[k, h] = 0.01;
            
watch.Start();
for (int o = 0; o < p; o++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      s += multi[i, j];

watch.Stop();
Console.WriteLine("multi sum time " + watch.ElapsedMilliseconds / p + " ms.");
watch.Reset();

multi = null;
double[][] jagged = new double[n][];

for (int k = 0; k < n; k++)
{
  jagged[k] = new double[n];
  for (int h = 0; h < n; h++)
    jagged[k][h] = 0.01;
}

s = 0;
watch.Start();
for (int o = 0; o < p; o++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      s += jagged[i][j];

watch.Stop();
Console.WriteLine("jagged sum time " + watch.ElapsedMilliseconds / p + " ms.");
watch.Reset();

jagged = null;
double[] linear = new double[n * n];

for (int k = 0; k < n; k++)
  for (int h = 0; h < n; h++)
    linear[k * n + h] = 0.01;

s = 0;
watch.Start();
for (int o = 0; o < p; o++)
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      s += linear[i * n + j];

watch.Stop();
Console.WriteLine("linear sum time " + watch.ElapsedMilliseconds / p + " ms.");
watch.Reset();

And the code for unrolling the loops.

const int n = (int)1E+04;
const int p = 10;
double s = 0;
double[,] multi = new double[n, n];
Stopwatch watch = new Stopwatch();

for (int k = 0; k < n; k++)
    for (int h = 0; h < n; h++)
        multi[k, h] = 0.01;

watch.Start();
for (int o = 0; o < p; o++)
    for (int i = 0; i < n; i+=8)
        for (int j = 0; j < n; j++)
        {
            s += multi[i, j];
            s += multi[i+1, j];
            s += multi[i+2, j];
            s += multi[i+3, j];

            s += multi[i+4, j];
            s += multi[i+5, j];
            s += multi[i+6, j];
            s += multi[i+7, j];
        }

watch.Stop();
Console.WriteLine("unroll multi sum time " + watch.ElapsedMilliseconds / p + " ms.");
watch.Reset();

multi = null;
double[][] jagged = new double[n][];

for (int k = 0; k < n; k++)
{
    jagged[k] = new double[n];
    for (int h = 0; h < n; h++)
        jagged[k][h] = 0.01;
}

s = 0;
watch.Start();
for (int o = 0; o < p; o++)
    for (int i = 0; i < n; i+=8)
        for (int j = 0; j < n; j++)
        {
            s += jagged[i][j];
            s += jagged[i+1][j];
            s += jagged[i+2][j];
            s += jagged[i+3][j];

            s += jagged[i+4][j];
            s += jagged[i+5][j];
            s += jagged[i+6][j];
            s += jagged[i+7][j];
        }

watch.Stop();
Console.WriteLine("unroll jagged sum time " + watch.ElapsedMilliseconds / p + " ms.");
watch.Reset();

jagged = null;
double[] linear = new double[n * n];

for (int k = 0; k < n; k++)
    for (int h = 0; h < n; h++)
        linear[k * n + h] = 0.01;

s = 0;
watch.Start();
for (int o = 0; o < p; o++)
    for (int i = 0; i < n; i+=8)
        for (int j = 0; j < n; j++)
        {
            s += linear[i * n + j];
            s += linear[(i + 1) * n + j];
            s += linear[(i + 2) * n + j];
            s += linear[(i + 3) * n + j];

            s += linear[(i + 4) * n + j];
            s += linear[(i + 5) * n + j];
            s += linear[(i + 6) * n + j];
            s += linear[(i + 7) * n + j];
        }

watch.Stop();
Console.WriteLine("unroll linear sum time " + watch.ElapsedMilliseconds / p + " ms.");
watch.Reset();

5:32 PM | Blog it | Microsoft HPC

Comments

To add a comment, sign in with your Windows Live ID.

Trackbacks

Weblogs that reference this entry

None