[Mono-list] Re: Time problems on Mono

[Jonathan Gilbert]

At 09:42 PM 12/12/2004 +0900, Shudo Kazuyuki wrote:
[snip]
>Note that the ported C# version still uses jagged 2-dimentional arrays
>in the same way as the original Java version, not rectangular arrays.
>The Java version achieves the pivoting (row exchange) by an exchange
>of pointer values in an array.  Pivoting by a pointer exchange is
>possible because the arrays are jagged arrays.  In C#, arrays can be
>rectangular arrays (similar to C and FORTRAN), and performance of
>array accesses will be improved.  On the other hand, pivoting gets
>slow a little with rectangular arrays.  I expect the C# version will
>be improved with rectangular arrays.
[snip]

Actually, my understanding is that jagged arrays tend to perform better.
Rectangular arrays have the following points that make them useful in
certain situations:

- They are a single object, and not a tree of objects like jagged arrays.
- Their memory overhead is O(1), not O(n^(d - 1)).
- They are created in a single allocation operation, whereas jagged arrays
require many allocations.

Therefore, rectangular arrays will tend to be allocated more quickly and
use less memory overall, but their actual use is slower because two
dimensions must be checked on every access. With jagged arrays, an
optimizing compiler can often separate out the different bounds checks. For
instance:

int[][] array = ...;
int sum = 0;
for (int i=0; i < array.Length; i++)
  for (int j=0; j < array[i].Length; j++)
    sum += array[i][j];

The compiler can eliminate all bounds checks from this because the loop
fits a pattern guaranteed to stay within bounds. Also, the "array[i]"
access can be "hoisted", so that the compiler acts as if the code were as
follows:

int[][] array = ...;
int sum = 0;
for (int i=0; i < array.Length; i++)
{
  int[] inner_array = array[i];
  for (int j=0; j < inner_array.Length; j++)
    sum += inner_array[j];
}

These optimizations are harder to perform for rectangular arrays, and more
importantly, regardless of the difficulty level, the Microsoft runtime opts
not to perform them. As such, rectangular arrays should usually be avoided.

By the way, does anyone know where mono stands with rectangular array
optimization? In particular, is mono able to eliminate the bounds checks
from something like this?:

int[,] array = ...;
int sum = 0;
for (int i=0; i < array.GetLength(0); i++)
  for (int j=0; j < array.GetLength(1); j++)
    sum += array[i,j];

Jonathan Gilbert