Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What are the semantics of C99's "restrict" with regards to pointers to pointers?

I am doing lots of matrix arithmetic and would like to take advantage of C99's restrict pointer qualifier.

I'd like to setup my matrices as pointers to pointers to allow for easy subscripting, like so:

int **A = malloc (ncols * sizeof(int *));
A[0] = malloc (nrows * ncols * sizof(int));
for (int i=1; i < ncols; i++) {
    A[i] = A[0] + i*nrows;
}

Now, for a matrix multiplication function

void mmultiply ( int nrows, int ncols, int **Out, int **A, int **B);

must I qualify both pointers of the arguments as restricted? It's valid syntax, but I'm having a hard time determining if int *restrict *restrict behaves any differently than int **restrict.

Then, with the pointers properly restricted, is accessing elements through A[0][col*nrows + row] undefined? (ie, will the compiler assume that I only access the matrix through A[col][row] for values of row such that row < nrow)? Or must I simply remain consistent?

like image 902
mbauman Avatar asked Sep 19 '09 23:09

mbauman


2 Answers

For the first question, "yes", it will mean something different if you use both restrict qualifiers, specifically, that the pointers also won't be aliased. As to whether it makes any difference: theoretically yes, in practice, it depends on the optimizer.

For the second question, "yes", it will assume that anything accessed through a row pointer is only accessed through the row pointer.

You could throw const in there too.

Finally, if this is gcc at -O2, -O3, or -Os, the compiler is already doing an alias analysis based on types. I'm sure other compilers do this also. This means that restricting the pointers vs the ints is already understood, leaving only the arrays that could possibly store to each other.

In sum, the optimizer will assume that the pointers aren't being stored into as ints, and it knows it isn't doing any pointer writes during the loop.

So you will probably get the same code with only the one restrict.

like image 77
DigitalRoss Avatar answered Sep 29 '22 04:09

DigitalRoss


The outer (second) restrict tells the compiler that none of the arrays of pointers (A, B, and out) alias. The inner (first) restrict tells the compiler that none of the arrays of ints (pointed to by elements of the arrays of pointers) alias.

If you access both A[0][col*nrows + row] and A[col][row] then you're violating the inner restrict, so things might break.

like image 39
Chris Dodd Avatar answered Sep 29 '22 05:09

Chris Dodd