CODEWITHSUNDEEP
cmatrixmatrix-multiplication
Slaven Glumac
Slaven Glumac

Reputation: 553

Matrix representation in C

I want to find out what is the best representation of a m x n real matrix in C programming language.

What are advantages of matrix representation as a single pointer:

double* A;

With this representation you could allocate memory:

A = (double* )malloc(m * n * sizeof(double));

In such representation matrix access requires an extra multiplication:

aij = A[i * m + j];

What are disadvantages of matrix representation as a double pointer:

double** B;

Memory allocation requires a loop:

double** B = (double **) malloc(m * sizeof(double*));
for (i = 0; i < m; i++)
    A[i] = (double *) malloc(n * sizeof(double))

In such representation you could use intuitive double indexing `bij = B[i][j], but is there some drawback that would affect performance. I would want to know what is the best presentation in terms of performance.

These matrices should be used in numerical algorithms such as singular value decomposition. I need to define a function:

void svd(Matrix A, Matrix U, Matrix Sigma, Matrix V);

and I am looking for the best way to represent Matrix. If there is any other efficient way to represent a matrix in C, please, let me know.

I have seen that most people use single pointer representation. I would like to know if there are some performance benefits as opposed to double array representation?

Upvotes: 3

Views: 4947

Answers (2)

Rob Lyndon
Rob Lyndon

Reputation: 12661

Here are a couple of articles about row major format.

http://en.wikipedia.org/wiki/Row-major_order

http://fgiesen.wordpress.com/2011/05/04/row-major-vs-column-major-and-gl-es/

These are common constructs in CUDA programming; hence my interest.

Upvotes: 0

Jonathan Leffler
Jonathan Leffler

Reputation: 753795

Look at the memory accesses required.

For the single-pointer case, you have:

  1. read a pointer (the base address), probably from a register
  2. read the four integers, probably from registers or hard-coded into instruction set. For array[i*m+j], the 4 values are i, m, j and sizeof(array[0]).
  3. multiply and add
  4. access the memory address

For the double-pointer case, you have:

  1. read a pointer (the base address), probably from a register
  2. read an index, probably from a register
  3. multiply the index by the size of a pointer and add.
  4. fetch the base address from memory (unlikely to be a register, might be in cache with luck).
  5. read another index, probably from a register
  6. multiply by the size of the object and add
  7. access the memory address

The fact that you have to access two memory locations probably makes the double-pointer solution quite a bit slower than the single-pointer solution. Clearly, caching will be critical; that's one reason why it is important to access arrays so that the accesses are cache-friendly (so you access adjacent memory locations as often as possible).

You can nit-pick about details in my outline, and some 'multiplication' operations may be shift operations, etc, but the general concept remains: the double-pointer requires two memory accesses versus one for the single-pointer solution, and that will be slower.

Upvotes: 5

Related Questions