Optimising C for performance vs memory optimisation using multidimensional arrays

Question

I am struggling to decide between two optimisations for building a numerical solver for the poisson equation.

Essentially, I have a two dimensional array, of which I require n doubles in the first row, n/2 in the second n/4 in the third and so on...

Now my difficulty is deciding whether or not to use a contiguous 2d array grid[m][n], which for a large n would have many unused zeroes but would probably reduce the chance of a cache miss. The other, and more memory efficient method, would be to dynamically allocate an array of pointers to arrays of decreasing size. This is considerably more efficient in terms of memory storage but would it potentially hinder performance?

I don't think I clearly understand the trade-offs in this situation. Could anybody help?

For reference, I made a nice plot of the memory requirements in each case:

Answer 1

There is no hard and fast answer to this one. If your algorithm needs more memory than you expect to be given then you need to find one which is possibly slower but fits within your constraints.

Beyond that, the only option is to implement both and then compare their performance. If saving memory results in a 10% slowdown is that acceptable for your use? If the version using more memory is 50% faster but only runs on the biggest computers will it be used? These are the questions that we have to grapple with in Computer Science. But you can only look at them once you have numbers. Otherwise you are just guessing and a fair amount of the time our intuition when it comes to optimizations are not correct.

Answer 2

Build a custom array that will follow the rules you have set.

The implementation will use a simple 1d contiguous array. You will need a function that will return the start of array given the row. Something like this:

int* Get( int* array , int n , int row )   //might contain logical errors
{
    int pos = 0 ;
    while( row-- )
    {
        pos += n ;
        n /= 2 ;
    }

    return array + pos ;
}

Where n is the same n you described and is rounded down on every iteration.

You will have to call this function only once per entire row.

This function will never take more that O(log n) time, but if you want you can replace it with a single expression: http://en.wikipedia.org/wiki/Geometric_series#Formula

Answer 3

You could use a single array and just calculate your offset yourself

size_t get_offset(int n, int row, int column) {
    size_t offset = column;
    while (row--) {
        offset += n;
        n << 1;
    }
    return offset;
}

double * array = calloc(sizeof(double), get_offset(n, 64, 0));

access via

array[get_offset(column, row)]