What “restrict” really means

I recently stumbled across a web page claiming to be “Demystifying The Restrict Keyword“, a claim which I consider dubious at best. Of the semantics of C99’s restrict, the page (written by a Mike Acton) says:

[when declaring a restrict-qualified pointer] I promise that the pointer declared along with the restrict qualifier is not aliased. I certify that writes through this pointer will not effect the values read through any other pointer available in the same context which is also declared as restricted.

Err, wrong. Firstly, a pointer declared with restrict is allowed to have aliases, it’s just that restrictions are placed on how those aliases are used or created. The C99 standard as always makes use of completely inaccessible language to describe the semantics of “restrict” – see 6.7.3.1, “Formal definition of restrict” – but in this case we can wade through the cruft and extract some actual meaning. The key point is that if a value pointed at by a restrict-qualified pointer is accessed through that pointer in any way, and is also modified through some pointer expression, then the latter pointer expression must be “based on” the restrict-qualified pointer. “Based on” means what it sounds like it means – essentially, that the value of the expression depends on the value of the pointer on which it is based. Here’s a counter-example to the restriction on aliasing expressed by Mike Acton above:

int * restrict p = ...;
int a = *p;   // here we have used 'p' for access
int * q = p;  // q aliases p
*q = 4;       // q is "based on" p, so this is allowed

The second part – “I certify that writes through this pointer will not effect the values read through any other pointer available in the same context which is also declared as restricted” – is also wrong (and not just grammatically). What restrict means is (and I’m simplifying just a little) that – if the restrict-qualified pointer is used to access an object, and the object is modified through any pointer, then the latter pointer and all other pointers (regardless of whether they are qualified with restrict or not) which are used to access the object will be “based on” the restrict-qualified pointer. Because we are allowed (with some restrictions) to assign the value of one restrict-qualified pointer to another, we can easily devise another counter-example to Mike Acton’s contract:

int * restrict p = ...;
{
    int * restrict q = p;  // q aliases p, both are restricted
    // Note that both q and p are "available in [this] context"
    *q = 4;  // this writes through q and affects the value read through p,
             // and yet is perfectly legal! (because q is based on p).
}
(*p);  // note the read through p must occur outside the block above, because
       // p is not based on q.

“restrict” does have some tricky semantics and it’s a shame that someone would “demystify” them so misleadingly. It could be a grave mistake to think that a non-restrict-qualified pointer can always safely alias a restrict-qualified pointer for instance.

It doesn’t quite stop there; the page goes on with a length example of using restrict to improve optimisation of a small function. The solution presented goes too far, assigning the address of each member of three different objects of the same structure type to different restrict-qualified pointers before performing calculations on them. This shouldn’t really be necessary; qualifying the structure pointers themselves with restrict should suffice, since the compiler should already know that different members of the same struct cannot legally alias (however, I’ve done some testing with gcc 4.6.3 and I’m not sure that this is the case with this compiler). Also, I’m fairly certain the solution invokes undefined behaviour via the odd and unnecessary pointer arithmetic involving a ‘stride’; A better version follows:

void
move( vector3* restrict velocity, 
      vector3* restrict position, 
      vector3* restrict acceleration, 
      float             time_step,  
      size_t            count)
{

  for (size_t i=0;i<count;i++)
  {
    float* restrict acceleration_x = &acceleration[i].x;
    float* restrict velocity_x     = &velocity[i].x;
    float* restrict position_x     = &position[i].x;
    float* restrict acceleration_y = &acceleration[i].y;
    float* restrict velocity_y     = &velocity[i].y;
    float* restrict position_y     = &position[i].y;
    float* restrict acceleration_z = &acceleration[i].z;
    float* restrict velocity_z     = &velocity[i].z;
    float* restrict position_z     = &position[i].z;
    
    const float ax  = *acceleration_x;
    const float ay  = *acceleration_y;
    const float az  = *acceleration_z;
    const float vx  = *velocity_x;
    const float vy  = *velocity_y;
    const float vz  = *velocity_z;
    const float px  = *position_x;
    const float py  = *position_y;
    const float pz  = *position_z;

    const float nvx = vx + ( ax * time_step );
    const float nvy = vy + ( ay * time_step );
    const float nvz = vz + ( az * time_step );
    const float npx = px + ( vx * time_step );
    const float npy = py + ( vy * time_step );
    const float npz = pz + ( vz * time_step );

    *velocity_x   = nvx;
    *velocity_y   = nvy;
    *velocity_z   = nvz;
    *position_x   = npx;
    *position_y   = npy;
    *position_z   = npz;
  }
}

From my tests this was by far the most performant (on a core-i7 based machine) with gcc (compilation options: -std=c99 -O3 -march=core2). When using the clang compiler, there wasn’t much variation in results between any version, including the naive version which didn’t use restrict at all (a slight performance benefit can be noticed when simply introducing restrict qualification into the parameter declarations, but no further benefit comes from using the code above, and only a negligible benefit comes from Mike Acton’s code which I believe invokes undefined behaviour anyway).

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s