Problems with malloc on OS X

Question

Hi there,

I have written a some C code running on OS X 10.6, which happens to be slow so I am using valgrind to check for memory leaks etc. One of the things I have noticed whilst doing this:

If I allocate memory to a 2D array like this:

double** matrix = NULL;
allocate2D(matrix, 2, 2);

void allocate2D(double** matrix, int nrows, int ncols) {
    matrix = (double**)malloc(nrows*sizeof(double*));
    int i;
    for(i=0;i<nrows;i++) {
        matrix[i] = (double*)malloc(ncols*sizeof(double));
    }
}

Then check the memory address of matrix it is 0x0.

However if I do

double** matrix = allocate2D(2,2);

double** allocate2D(int nrows, int ncols) {
    double** matrix = (double**)malloc(nrows*sizeof(double*));
    int i;
    for(i=0;i<nrows;i++) {
        matrix[i] = (double*)malloc(ncols*sizeof(double));
    }
return matrix;
}

This works fine, i.e. the pointer to the newly created memory is returned.

When I also have a free2D function to free up the memory. It doesn't seem to free properly. I.e. the pointer still point to same address as before call to free, not 0x0 (which I thought might be default).

void free2D(double** matrix, int nrows) {
    int i;
    for(i=0;i<nrows;i++) {
        free(matrix[i]);
    }
free(matrix);
}

My question is: Am I misunderstanding how malloc/free work? Otherwise can someone suggest whats going on?

Alex

Answer 1

In C++ You should pass the pointer by reference :)

Allocate2D(double**& matrix...)

As to what's going on - well you have a pointer that is NULL, you pass the copy of that pointer to the function which allocated mamory and initializes the copy of your pointer with the address of the newly allocated memory, but your original pointer remains NULL. As for free you don't need to pass by reference since only the value of the pointer is relevant. HTH

Since there are no references in C, you can pass by pointer, that is

Allocate2D(double*** pMatrix...)
{
   *pMatrix = malloc(...)
}

and later call like

Allocate2D(&matrix ...)

Answer 2

When you free a pointer, the value of the pointer does not change, you will have to explicitly set it to 0 if you want it to be null.

Answer 3

In the first example, you've only stored the pointer returned by malloc in a local variable. It's lost when the function returns.

Usual practice in the C language is to use the function's return value to pass the pointer to an allocated object back to the caller. As Armen pointed out, you can also pass a pointer to where the function should store its output:

void Allocate2D(double*** pMatrix...)
{
   *pMatrix = malloc(...)
}

but I think most people would scream as soon as they see ***.

You might also consider that arrays of pointers are not an efficient implementation of matrices. Allocating each row separately contributes to memory fragmentation, malloc overhead (because each allocation involves some bookkeeping, not to mention the extra pointers you have to store), and cache misses. And each access to an element of the matrix involves 2 pointer dereferences rather than just one, which can introduce stalls. Finally, you have a lot more work to do allocating the matrix, since you have to check for failure of each malloc and cleanup everything you've already done if any of them fail.

A better approach is to use a one-dimensional array:

double *matrix;
matrix = malloc(nrows*ncols*sizeof *matrix);

then access element (i,j) as matrix[i*ncols+j]. The potential disadvantages are the multiplication (which is slow on ancient cpus but fast on modern ones) and the syntax.

A still-better approach is not to seek excess generality. Most matrix code on SO is not for advanced numerical mathematics where arbitrary matrix sizes might be needed, but for 3d gaming where 2x2, 3x3, and 4x4 are the only matrix sizes of any practical use. If that's the case, try something like

double (*matrix)[4] = malloc(4*sizeof *matrix);

and then you can access element (i,j) as matrix[i][j] with a single dereference and an extremely fast multiply-by-constant. And if your matrix is only needed at local scope or inside a structure, just declare it as:

double matrix[4][4];

If you're not extremely adept with the C type system and the declarations above, it might be best to just wrap all your matrices in structs anyway:

struct matrix4x4 {
    double x[4][4];
};

Then declarations, pointer casts, allocations, etc. become a lot more familiar. The only disadvantage is that you need to do something like matrix.x[i][j] or matrix->x[i][j] (depending on whether matrix is a struct of pointer to struct) instead of matrix[i][j].

Edit: I did think of one useful property of implementing your matrices as arrays of row pointers - it makes permutation of rows a trivial operation. If your algorithms need to perform a lot of row permutation, this may be beneficial. Note that the benefit will not be much for small matrices, though, and than column permutation cannot be optimized this way.