C++
C#
VB
JScript
All

# Arrays

Copyright (C) 2005 IENT-RWTH Aachen

Array is a generic word that designs both vector and matrix. Vectors are one-dimensional arrays, matrices are two-dimensional arrays.

Include

array/vector.h array/matrix.h

Generators

Every array has a unique template parameter, called generator. The generator describes completely every characteristic the array has. For instance, the following functions work with any constant vectors or matrices as parameter:

    template<class G>           int f(const Vector<G> &X);
    template<class G1,class G2> int g(const Matrix<G1> &X, const Matrix<G2> &Y);

Interfaces

Some interface structures help to deal with generators. They could be considered as functions that would give a correct type back.

    DenseVector<int>::self X;
    TinyMatrix<4,4,float>::self Y;

Such declarations should be preferred to the following equivalent:

    Vector<dense_vector_generator<int> > X;
    Matrix<tiny_matrix_generator<4,4,float> > Y;

Left-Values

Many calculations on arrays can be used as left-values. This especially applies on adaptors that do not make any calculation, or any copy of the content.

    DenseVector<complex<float> >::self X(4, 0); // X=[(0,0) (0,0) (0,0) (0,0)]
    sub(X,2,2) = complex<float>(2,2); // X=[(0,0) (0,0) (2,2) (2,2)]
    imag(sub(X,0,3)) = 5; // X=[(0,5) (0,5) (2,5) (2,2)]

Automatic promotions

If your arrays deal with different element types, GENIAL will automatically choose the best array type. It applies the same promotion rules than C++ does for scalars.

    DenseVector<int>::self X(4,1); // X=[1 1 1 1]
    DenseVector<float>::self Y(4,1.5); // Y=[1.5 1.5 1.5 1.5]
    cout << X+Y << endl; // [2.5 2.5 2.5 2.5]

Nevertheless, you should try to use identical element types to spare conversion time. If the default conversion is not desired, the value_cast function can be used:

    cout << X+value_cast<int>(Y) << endl; // [2 2 2 2]

Automatic reorganisation

The library automatically reorganizes the calculations.

Suppose you need to calculate:

    C=2*A+3*B

where A, B and C are matrices. The usual way for a library to compute would be to create a temporary matrix for the result of 2*A, another temporary matrix for 3*B, a third for the sum, and to copy the result in C. This needs much memory for the temporary matrices, and much time for every copy in new matrices. Whereas a source code with “for” loops would run much quicker:

    for (int i=0; i<M; ++i)
      for (int j=0; j<N; ++j)
        C(i,j)=2*A(i,j)+3*B(i,j)

Neither temporary memory allocation is needed, nor copies of matrices. Besides, a similar principle becomes very difficult to use when the calculation gets complicated. It cannot evolve with the type of the operands: if A, B, and C would have been vectors instead of matrices, the first code would still be correct.

GENIAL is able to automatically create new array instantiations, appropriated to every calculation. The resulting compiled code runs as quick as the most optimized C code, no matter how difficult the calculation is.

Lazy calculation

The library only calculates what really is needed. It is “lazy”. This principle allows mixing several functions with the assurance that the execution time will not be longer than necessary.

Suppose you are interested in the first column of the multiplication of the matrices A and B :

    X=cols(mul(A,B))[0];

The mul function calculates the multiplication of 2 matrices. (The “*” operator would only calculate an element-wise multiplication of the 2 matrices) In this case the library does not lose its time for the whole calculation of the matrix multiplication.

This technique has some limitations. But in practice, problems rarely occur, and there are easy solutions.

- Aliasing

  The calculation

      A=mul(A,B);

  does not overwrite A with the result that one would actually expect. Because of the automatic reorganisation, the value A(0,0) is first overwritten at the first iteration. Then a second iteration calculates the value A(0,1), but with an already altered A, the result is false. There is a so-called “aliasing”. The solution consists in saving the result in a temporary variable. The dense function converts any array in a dense array.

      A=dense(mul(A,B));

- Temporary arrays occasionally needed

  The library calculates just the needed positions of arrays, but on the other side it could happen that the library calculates many times the same position, resulting in wasted execution time. Avoid giving a complicated array as parameter to a function, especially if this function often needs the same position. Some functions (mostly fft, dct) will automatically do a conversion of the parameters to dense arrays if necessary. You can force the conversion if you estimate the calculation would be quicker:

      D=mul(A,dense(mul(B,C)));

Assertions

To simplify the development of your project, GENIAL has assert statements in its code. This means that many validity tests are made during the execution of your project in debug mode. These tests mostly control the validity domain of accesses in arrays, so that an error message will be displayed if an index is not valid. Of course, no more tests are made in the release mode.

Debug mode VS release mode

There are many template specializations that work as switches. Many things happen differently in release mode in comparison to debug mode. The library tries to optimize the arrangement of your calculation. You should not notice any different behaviour, except a different execution time. If for any reason you want to debug your programme with release behaviour, you can declare

    #define NDEBUG

at the beginning of your file before any include statement. But keep in mind, that in this case no assertions are made.

generator_traits |
Vectors | Vectors represent one-dimensional arrays
Matrices | Matrices represent two-dimensional arrays
External functions | Basic calculation with arrays