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

Cinnamon. WTF is it?

Check out the Cinnamon web site.

It’s not so bad, as web sites go, in terms of appearance. Nice width, good text/background contrast. They’re probably using WordPress in the backend. That transition between screenshots (if that’s what they are) effect is really nice, I like it.

Notice they had a release recently – up to version 1.4 now, it seems, and 1.3.1 was … well, I don’t know how long ago, because the news items aren’t dated, which does seem like a serious omission, but at least I can click the links to get the full story with date: 1.4 was released 14/3/2012 and 1.3.1 was 20/2/2012, less than a month earlier. Ok, I can live with that. Hmm, fast release schedule! Usually a sign of a project in its infancy: enthusiastic developers, and plenty of low-hanging fruit in terms of bugs to fix and features to add. Which makes the next observation even more puzzling.

No – mention – anywhere – of – what – the – heck – it – is.

How exactly do you manage to put together a website with flashy screenshots and monthly news items and still neglect this most basic, this most essential of details? I can only assume that the webmaster is some form of greater ape. Possibly an orangutang. Don’t get me wrong, I like orangutangs, they have an odd graceful sobriety about them, and you can train them to wash clothes and (apparently) bang up a quick website, but they just don’t have the intelligence of a real human.

So please, Cinnamon, ditch the ape, get a human, and put an “about” page on your crappy website.

(For anyone who’s just itching to know, LWN has an entry here which explains what Cinnamon is).

Floating point comparisons, by someone who doesn’t understand math.

A link to the following page was posted on Slashdot today:

http://floating-point-gui.de/errors/comparison/

Although the author asks Slashdot for comments (urgh) I’m not willing to comment there as whatever I will say will be lost in the noise. (yep, there are some clever people who post to Slashdot, it’s just hard to see them behind all the trolls and idiots). I would just send the author an email but they have for some reason neglected to include their name and contact details anywhere.

Anywya, the assertion is made that you shouldn’t compare floating point values using an epsilon, specifically:

if( Math.abs(a-b) < 0.00001) // wrong - don't do this

The reasoning however is difficult to follow:

This is a bad way to do it because a fixed epsilon chosen because it “looks small” could actually be way too large when the numbers being compared are very small as well.

Geez. If both numbers are small, then they are in fact close together in value and the above comparison is perfectly valid. It is in fact the whole point of the comparison. You don’t need to take the magnitude of the values into account unless, well, you have a good reason for it. And in general, if the magnitude is significant, you don’t want to be doing an equality comparison anyway. The key is not to have a dynamic epsilon (which is ultimately what the convoluted piece-of-filth code the author then presents ultimately, er, fails to achieve) but rather to have an epsilon value which is meaningful in the context of the comparison (i.e. how much of a difference in value are you willing to tolerate, taking error into account?).

Yes, larger magnitudes have less precision, but that doesn’t necessarily mean you want to widen the range of what is considered equal. Somtimes, exactly what you want in such cases is for the comparison to always fail (unless of course the values are actually identical).

Incidentally if you did want to take magnitude into account, it would probably be much simpler to do something like:

float d = a / b;
if (d > 0.999 && d < 1.001) {
    // near enough to equal
}

… though of course you may (depending on language and environment, and specifically divide-by-zero behaviour) still need to handle the case of “b” being 0 (most likely by considering the values unequal, unless “a” is also zero).

The point is, consider your needs when doing floating point comparison. It’s true that you’ll rarely want to compare floats for exact equality, but exactly how you test for “inexact equality” is dependent on the situation. Think about what you are trying to achieve, and don’t believe what some monkey’s web page says.

Where is the Rails bug tracker?

The Ruby-on-Rails website has a link (“Get involved”) with a speech bubble picture, in which the words “bug tracker” (among other things) are contained. However, the link takes you to another page which links to a whole bunch of stuff, none of which is a bug tracker.

Hmm, there seems to be a tracker here:

http://rails.lighthouseapp.com/projects/8994-ruby-on-rails/overview

… but that doesn’t seem to have bug #3231 which was mentioned here:

http://www.ruby-forum.com/topic/39270

… and which I recently stumbled on.

It’s all very chaotic and unsatisfying. Much like Ruby programming…

Re-thinking the website sign-up

There are a bunch of websites where you have to sign up as a user, a proces which normally requires that you hand over an email address which the site will validate by sending you an email with some sort of secret token (a URL) that you need to actually activate the account. As it happens, I’m implementing such a feature at the moment. Assuming that these sites aren’t actually harvesting the addresses for purposes of on-selling them or spamming them directly, it’s usually because they need a way to do things like:

  • prevent a single person from creating an unlimited number of accounts
  • prevent all but the most clever bots from creating accounts
  • permanently ban troublesome users

All of these are perfectly valid concerns. Most sites that I am aware of require you to provide an email address when you create your account, at which time you also choose your username and password (and provide whatever other details are deemed necessary). However, there are problems with this approach, and I think there’s a better way to do it.

Continue reading