shortening the period of two dimensional dynamic array algorithms in C++

Question

Hello ,

I defined two dimensional dynamic array and allocate memory for arrays.Dimensions of arrays are same as each other(256*256):

    double **I1,**I2;

    int M=256;
    int N=256;
    int i,j;

    I1= new double *[M+1];
    for(i=1;i<=M;i++)
    {I1[i]=new double [N+1];}

    I2= new double *[M+1];
    for(i=1;i<=M;i++)
    {I2[i]=new double [N+1];}

Then,I assigned values elements of arrays.I have to execute mathematical algorithms on these arrays .I used a lot of for loops.And my code worked very very slowly.

For example if I subtract I2 from I1 and asssigned substract array to another I3 two dimensional array,I used this code:

double **I3;
double temp;
//allocate I3;
I3= new double *[M+1];
 for(i=1;i<=M;i++)
{I3[i]=new double [N+1];}


 //I3=I1-I2


for(i=1;i<=M;i++){
    for(j=1;j<=N;j++){
          temp=I1[i][j]-I2[i][j];
          I3[i][j]=temp;}
}

How can I short execution time of C++ without using for loops ? Could you advise me another methods please?

Best Regards..

Answer 1

In order of importance:

• Switch on compiler optimization.
• Allocate a single array for each matrix and use something like M*i+j for indexing. This will allocate faster and perhaps more importantly be more compact and less fragmented than multiple allocations.
• Get used to indexing starting by zero, this will save you one array element and in general zero comparisons have the potential to be faster.
• I see nothing wrong in using for loops.
• If you are willing to spend even more effort, you could either use a vectorized 3rd party linear algebra lib or vectorize yourself by using things like SSE* or GPUs.

Answer 2

Some architectures have hardware support for vector arithmetic, such that a single instruction will sum all the elements of an array of doubles.

However, the first thing you must do to speed up a program is measure it. Have you timed your program to see where the slowdown occurs?

For example, one thing you appear to be doing in a for loop is lots of heap allocation, which tends to be slow. You could combine all your arrays into one array for greater speed.

You are currently doing the logical equivalent of this:

I3 = I1 - I2;

If you did this:

I1 -= I2;

Now I1 would be storing the result. This would destroy the original value of I1, but would avoid allocating a new array-of-arrays.

Also the intention of C++ is that you define classes to represent a data type and the operations on it. So you could write a class to represent your dynamic array storage. Or use an existing one - check out the uBLAS library.

Answer 3

I don't understand why you say that this is very slow. You're doing 256*256 subtractions here. I don't think there is a way to avoid for loops here (even if you're using a matrix library it will probably still do the same).

You might consider allocating 256*256 floats in one go instead of calling new 256 times (and then use some indexing arithmetic because you have only one index) but then it's probably easier to find a matrix library which does this for you.

Answer 4

First of all, in most cases I would advise against manually managing your memory like this. I'm sure you have heard that C++ offers container classes to which "algorithms" can be applied. These containers are less error prone (especially in the case of exceptions), the operations are more expressive, optimized and usually well-tested, so proven to work.

In your case, with the size of array known before, a std::vector can be used with no performance loss (except at creation), since the memory is guaranteed to be continuous and can thus be used like an array. You should also think about flattening your array, calling an allocation routine in a loop is not exactly speedy - allocation is costly. When doing matrix multiplication, consider allocation in row-major / column-major pairs, this helps caching...but I digress.

This is only a general advice, though - I am not advising you to re-implement this using containers, I just felt the need to mention them.

In this specific case, since you mentioned you want to "execute mathematical algorithms" I would suggest you have a look at a numeric library that is able to do matrix / vector operations, as this seems to be what you are after.

For C++, there is Newmat for example, and the (more or less) canonical BLAS/LAPACK implementations (i.e. Netlib, AMD's ACML, ATLAS). These allow you to perform common (and not so common) operations like adding/subtracting vectors, multiplying matrices etc. much faster, both using optimized algorithms and also optimizations as SIMD instructions your processor might offer (i.e. SSE).

Obviously, there is no way to avoid iterating over these values when doing computations, but you can do it in an optimized manner and with a standard interface.

Answer 5

Everything is already in STL, use valarray.

See also: How can I use a std::valarray to store/manipulate a contiguous 2D array?