The author says "In C99 the restrict keyword was added, which we could use
here to encode that src and dst are different from all other references.
This mechanism helps in some cases, but not in our example."
Doesn't the example below show otherwise? Note the presence of movdqu in both
memcopy_normal and memcopy_restrict and how GCC emits five LEA instructions
without restrict, but only two when restrict is present.
This does not support the author's assertion that "Aliasing information is
the only one, where I am certain about speed improvements, because it is
impossible to reach Fortran-speed in C."
Yes, the author is wrong there; restrict is valid and useful in that memcpy example.
It is true though that restrict doesn't solve all of C's aliasing problems though. For example:
#include <stdlib.h>
struct array_3d {
float * restrict data;
size_t xmin, ymin, zmin;
size_t xmax, ymax, zmax;
size_t allocated;
};
static inline float *
array_3d_elem_addr(struct array_3d *a3d, size_t x, size_t y, size_t z) {
return a3d->data + z +
y * (a3d->zmax - a3d->zmin) +
x * (a3d->zmax - a3d->zmin) * (a3d->ymax - a3d->ymin);
}
void array_3d_add(struct array_3d *restrict dst, struct array_3d *restrict src) {
for (size_t x = dst->xmin; x != dst->xmax; ++x)
for (size_t y = dst->ymin; y != dst->ymax; ++y)
for (size_t z = dst->zmin; z != dst->zmax; ++z)
*array_3d_elem_addr(dst, x, y, z) += *array_3d_elem_addr(src, x, y, z);
}
No amount of restrict keywords can tell the compiler that src->data and dst->data don't alias here (putting restrict on the 'data' member declaration inside array_3d doesn't mean anything here, because of the way restrict is defined).
GCC manages to vectorize this loop, but only conditionally, with runtime alias checks. That's ok for this trivial example, but it isn't always viable in more complex examples. It's also worth noting that there are ways to rewrite this code so that it does fully vectorize, though again it's helped by the example being so trivial. The main point is that in Fortran, the alias rules are strong by default, without the programmer having to do acrobatics.
Comments
The author says "In C99 the restrict keyword was added, which we could use here to encode that src and dst are different from all other references. This mechanism helps in some cases, but not in our example."
Doesn't the example below show otherwise? Note the presence of movdqu in both memcopy_normal and memcopy_restrict and how GCC emits five LEA instructions without restrict, but only two when restrict is present.
This does not support the author's assertion that "Aliasing information is the only one, where I am certain about speed improvements, because it is impossible to reach Fortran-speed in C."
Yes, the author is wrong there; restrict is valid and useful in that memcpy example.
It is true though that restrict doesn't solve all of C's aliasing problems though. For example:
No amount of restrict keywords can tell the compiler that src->data and dst->data don't alias here (putting restrict on the 'data' member declaration inside array_3d doesn't mean anything here, because of the way restrict is defined).GCC manages to vectorize this loop, but only conditionally, with runtime alias checks. That's ok for this trivial example, but it isn't always viable in more complex examples. It's also worth noting that there are ways to rewrite this code so that it does fully vectorize, though again it's helped by the example being so trivial. The main point is that in Fortran, the alias rules are strong by default, without the programmer having to do acrobatics.
Edit: formatting fixes
Also note that this restriction is in C itself. This is how restrict is defined in the C standard. It's not specific to GCC or any other compiler.
Sadly, from what I recall, gcc has some internal limitations which prevent it from making significant use of "restrict".
mans or astrange can probably elaborate.
movdq is only used, if appropriate. There is a check, whether the pointer are at least 16 bytes apart.