access time for small array vs small struct in c#

Question

I need to process about 500,000 data points each consisting of 4 decimals. I'd like to use and array of structs to do this. Would this be much slower than using an array of arrays? It seems that memory won't be an issue, but speed will - it needs to be fast.

Quick code sample of two options:

Option 1:

public struct Struct
{
    public decimal A { get; set; }
    public decimal B { get; set; }
    public decimal C { get; set; }
    public decimal D { get; set; }
}

Usage:

private Struct[] data;

Option 2:

private decimal [][] data;

Also, is decimal the right data type to use? The data points are money...

Thanks! Brian

Answer 1

If you are processing A,B,C,D at the exact same time, the array of structs method should have better spatial locality - since the data is clumped together it will be paged into memory and the same time (fewer page faults) and fetched into the CPU cache at the same time. If you process all of A, then all of B, etc., then the opposite will be true and you should use array of arrays.

If not terribly difficult, I suggest you try both options and measure and see what one is better. If this is too difficult, use whichever approach is simpler and easy to understand and then measure to see if it meets your performance goals.

Answer 2

1. Decimal is the correct type to be using, if you're dealing with currency values.
2. An array of structs will be quite fast.

Be aware, though, that when you're dealing with an array of structs, individual struct elements (especially since you have each value as a property) will need to be treated as a single, immutable object. This means that, if you want to change C in array element 4, you'll need to do:

MyStruct val = array[5];
val.C = newValue;
array[5] = val;

Switching to public fields can reduce some of this, but adds its own problems. Mutable structs make things more complicated, at times...

Answer 3

hmm... If you replace the array of arrays with a two-dimensional array, the resulting memory layout should be more or less equivalent:

private Struct[] data = new Struct[x];
private decimal[,] data = new decimal[x,4];

Unless you were hoping to pass around one of the arrays to other methods...

Answer 4

Just a side comment to the previous post about using two-dimensional arrays:

An array of arrays (sometimes called a jagged array) provides better performance than a two dimensional array because the two-dimensional address translation requires a multiply and an add whereas the jagged array only requires two adds.

Of course the difference only shows up after millions of look-ups.

Answer 5

When dealing with money, it is often faster and far more efficient to use integers if you are performing comparisons or simple addition and subtraction, and don't need to worry about rounding errors.

Answer 6

Struct array and jagged arrays are laid out in memory pretty much the same way, so you shouldn't get a performance hit from using it.

public struct Struct
{
    // Unless you're filling your get/set blocks with anything,
    // these properties will be in-lined in compilation time
    // and will have the same performance/behavior as using public fields

    public decimal A { get; set; }
    public decimal B { get; set; }
    public decimal C { get; set; }
    public decimal D { get; set; }
}

So I'd consider using public fields. But that's just my opinion, I like to know explicitly how things are going to behave.

About using decimal for money, that's not always true. decimal is a 128-bit data field, it has VERY high precision, but it's integer part has a narrow range of values. If you need high precision for calculating rates or something like this but you don't need really high values, go for decimal. If you need higher values and not so much precision, go for double. If you're dealing with small values and just need a fair amount of precision, go for float.

Remember that the closer the data type is to 32-bit (or the width of your bus), the less time it will take for the data to be loaded.

Hope this helps!