Coder Corner

A quick post about a little-known feature of the “restrict” keyword…

I assume you all know about “restrict” already, but if not, let’s start with a simple example of what it’s useful for.

Say we have a function in some class looking like this:

class RTest
{
public:
RTest() : mMember(0)    {}

void DoStuff(int nb, int* target);

int mMember;
};

void RTest::DoStuff(int nb, int* target)
{
while(nb–)
{
*target++ = mMember;
mMember++;
}
}

Looking at the disassembly in Release mode, you get something like the following (the isolated block in the middle is the loop):

00E9EEA0  mov         eax,dword ptr [esp+4]
00E9EEA4  test        eax,eax
00E9EEA6  je          RTest::DoStuff+1Fh (0E9EEBFh)
00E9EEA8  mov         edx,dword ptr [esp+8]
00E9EEAC  push        esi
00E9EEAD  lea         ecx,[ecx]

00E9EEB0 mov         esi,dword ptr [ecx] // Load mMember
00E9EEB2  mov         dword ptr [edx],esi // *target = mMember
00E9EEB4 inc         dword ptr [ecx] // mMember++
00E9EEB6  dec         eax
00E9EEB7  add         edx,4 // target++
00E9EEBA  test        eax,eax
00E9EEBC  jne         RTest::DoStuff+10h (0E9EEB0h)

00E9EEBE  pop         esi
00E9EEBF  ret         8

So as you can see, there is a read-modify-write operation on mMember each time, and then mMember is reloaded once again to write it to the target buffer. This is not very efficient. Loads & writes to memory are slower than loads & writes to registers for example. But more importantly, this creates a lot of LHS since we clearly load what we just wrote. On a platform like the Xbox, where an LHS is a ~60 cycles penalty on average, this is a killer. Generally speaking, any piece of code doing “mMember++” is a potential LHS, and something to keep an eye on.

There are various ways to do better than that. One way would be to simply rewrite the code so that mMember is explicitly kept in a local variable:

void RTest::DoStuffLocal(int nb, int* target)
{
int local = mMember;
while(nb–)
{
*target++ = local;
local++;
}
mMember = local;
}

This produces the following disassembly:

010AEED0  mov         edx,dword ptr [esp+4]
010AEED4 mov         eax,dword ptr [ecx] // Load mMember
010AEED6  test        edx,edx
010AEED8  je          RTest::DoStuffLocal+1Ch (10AEEECh)
010AEEDA  push        esi
010AEEDB  mov         esi,dword ptr [esp+0Ch]
010AEEDF nop

010AEEE0  mov         dword ptr [esi],eax // *target = mMember
010AEEE2  dec         edx
010AEEE3  add         esi,4 // target++
010AEEE6 inc         eax // mMember++
010AEEE7  test        edx,edx
010AEEE9  jne         RTest::DoStuffLocal+10h (10AEEE0h)

010AEEEB  pop         esi
010AEEEC mov         dword ptr [ecx],eax // Store mMember
010AEEEE  ret         8

This is pretty much what you expect from the source code: you see that the load has been moved outside of the loop, our local variable has been mapped to the eax register, the LHS are gone, and mMember is properly updated only once, after the loop has ended.

Note that the compiler inserted a nop just before the loop. This is simply because loops should be aligned to 16-bytes boundaries to be the most efficient.

Another way to achieve the same result without modifying the main code is to use the restrict keyword. Just mark the target pointer as restricted, like this:

void RTest::DoStuffRestricted(int nb, int* __restrict target)
{
while(nb–)
{
*target++ = mMember;
mMember++;
}
}

This produces the following disassembly:

010AEF00  mov         edx,dword ptr [esp+4]
010AEF04  test        edx,edx
010AEF06  je          RTest::DoStuffRestricted+1Eh (10AEF1Eh)
010AEF08 mov         eax,dword ptr [ecx] // Load mMember
010AEF0A  push        esi
010AEF0B  mov         esi,dword ptr [esp+0Ch]
010AEF0F  nop

010AEF10  mov         dword ptr [esi],eax // *target = mMember
010AEF12  dec         edx
010AEF13  add         esi,4 // target++
010AEF16 inc         eax // mMember++
010AEF17  test        edx,edx
010AEF19  jne         RTest::DoStuffRestricted+10h (10AEF10h)

010AEF1B mov         dword ptr [ecx],eax // Store mMember
010AEF1D  pop         esi
010AEF1E  ret         8

In other words, this is almost exactly the same disassembly as for the solution using the local variable - but without the need to actually modify the main source code.

What happened here should not be a surprise: without __restrict, the compiler had no way to know that the target pointer was not potentially pointing to mMember itself. So it had to assume the worst and generate “safe” code that would work even in that unlikely scenario. Using __restrict however, told the compiler that the memory pointed to by “target” was accessed through that pointer only (and pointers copied from it). In particular, it promised the compiler that “this”, the implicit pointer from the RTest class, could not point to the same memory as “target”. And thus, it is now safe to keep mMember in a register for the duration of the loop.

So far, so good. This is pretty much a textbook example of how to use __restrict and what it is useful for. The only important point until now, really, is this: as you can see from the disassembly, __restrict has a clear, real impact on generated code. Just in case you had any doubts…

Now the reason for this post is something more subtle than this: how do we “restrict this”? How do we restrict the implicit “this” pointer from C++ ?

Consider the following, modified example, where our target pointer is now a class member:

class RTest
{
public:
RTest() : mMember(0), mTarget(0) {}

int DoStuffClassMember(int nb);

int mMember;
int*  mTarget;
};

int RTest::DoStuffClassMember(int nb)
{
while(nb–)
{
*mTarget++ = mMember;
mMember++;
}
return mMember;
}

Suddenly we can’t easily mark the target pointer as restricted anymore, and the generated code looks pretty bad:

0141EF60  mov         eax,dword ptr [esp+4]
0141EF64  test        eax,eax
0141EF66  je          RTest::DoStuffClassMember+23h (141EF83h)
0141EF68  push        esi
0141EF69  mov         edx,4
0141EF6E  push        edi
0141EF6F  nop

0141EF70  mov         esi,dword ptr [ecx+4] // mTarget
0141EF73  mov         edi,dword ptr [ecx] // mMember
0141EF75  mov         dword ptr [esi],edi // *mTarget = mMember;
0141EF77  add         dword ptr [ecx+4],edx // mTarget++
0141EF7A  inc         dword ptr [ecx] // mMember++
0141EF7C  dec         eax
0141EF7D  test        eax,eax
0141EF7F  jne         RTest::DoStuffClassMember+10h (141EF70h)

0141EF81  pop         edi
0141EF82  pop         esi
0141EF83  mov         eax,dword ptr [ecx]
0141EF85  ret         4

That’s pretty much as bad as it gets: 2 loads, 2 read-modify-writes, 2 LHS for each iteration of that loop. This is what Christer Ericson refers to as the “C++ abstraction penalty”: generally speaking, accessing class members within loops is a very bad idea. It is usually much better to load those class member to local variables before the loop starts, or pass them to the function as external parameters.

As we saw in the previous example, an alternative would be to mark the target pointer as restricted. In this particular case though, it seems difficult to do since the pointer is a class member. But let’s try this anyway, since it compiles:

class RTest
{
public:
RTest() : mMember(0), mTarget(0)   {}

int DoStuffClassMember(int nb);

int mMember;
int*  __restrict mTarget;
};

Generated code is:

00A8EF60  mov         eax,dword ptr [esp+4]
00A8EF64  test        eax,eax
00A8EF66  je          RTest::DoStuffClassMember+23h (0A8EF83h)
00A8EF68  push        esi
00A8EF69  mov         edx,4
00A8EF6E  push        edi
00A8EF6F  nop

00A8EF70  mov         esi,dword ptr [ecx+4]
00A8EF73  mov         edi,dword ptr [ecx]
00A8EF75  mov         dword ptr [esi],edi
00A8EF77  add         dword ptr [ecx+4],edx
00A8EF7A  inc         dword ptr [ecx]
00A8EF7C  dec         eax
00A8EF7D  test        eax,eax
00A8EF7F  jne         RTest::DoStuffClassMember+10h (0A8EF70h)

00A8EF81  pop         edi
00A8EF82  pop         esi
00A8EF83  mov         eax,dword ptr [ecx]
00A8EF85  ret         4

Nope, didn’t work, this is exactly the same code as before.

What we really want here is to mark “this” as restricted, since “this” is the pointer we use to access both mTarget and mMember. With that goal in mind, a natural thing to try is, well, exactly that:

int RTest::DoStuffClassMember(int nb)
{
RTest* __restrict RThis = this;
while(nb–)
{
*RThis->mTarget++ = RThis->mMember;
RThis->mMember++;
}
return RThis->mMember;
}

This produces the following code:

0114EF60  push        esi
0114EF61  mov         esi,dword ptr [esp+8]
0114EF65  test        esi,esi
0114EF67  je          RTest::DoStuffClassMember+26h (114EF86h)
0114EF69 mov         edx,dword ptr [ecx] // mMember
0114EF6B mov         eax,dword ptr [ecx+4] // mTarget
0114EF6E  mov         edi,edi

0114EF70  mov         dword ptr [eax],edx // *mTarget = mMember
0114EF72  dec         esi
0114EF73 add         eax,4 // mTarget++
0114EF76 inc         edx // mMember++
0114EF77  test        esi,esi
0114EF79  jne         RTest::DoStuffClassMember+10h (114EF70h)

0114EF7B mov         dword ptr [ecx+4],eax // Store mTarget
0114EF7E mov         dword ptr [ecx],edx // Store mMember
0114EF80  mov         eax,edx
0114EF82  pop         esi
0114EF83  ret         4
0114EF86  mov         eax,dword ptr [ecx]
0114EF88  pop         esi
0114EF89  ret         4

It actually works! Going through a restricted this, despite the unusual and curious syntax, does solve all the problems from the original code. Both mMember and mTarget are loaded into registers, kept there for the duration of the loop, and stored back only once in the end.

Pretty cool.

If we ignore the horrible syntax, that is. Imagine a whole codebase full of “RThis->mMember++;”, this wouldn’t be very nice.

There is actually another way to “restrict this”. I thought it only worked with GCC, but this is not true. The following syntax actually compiles and does the expected job with Visual Studio as well. Just mark the function itself as restricted:

class RTest
{
public:
RTest() : mMember(0), mTarget(0)   {}

int DoStuffClassMember(int nb)   __restrict;

int mMember;
int*  mTarget;
};

int RTest::DoStuffClassMember(int nb)    __restrict
{
while(nb–)
{
*mTarget++ = mMember;
mMember++;
}
return mMember;
}

This generates exactly the same code as with our fake “this” pointer:

0140EF60  push        esi
0140EF61  mov         esi,dword ptr [esp+8]
0140EF65  test        esi,esi
0140EF67  je          RTest::DoStuffClassMember+26h (140EF86h)
0140EF69  mov         edx,dword ptr [ecx]
0140EF6B  mov         eax,dword ptr [ecx+4]
0140EF6E mov         edi,edi

0140EF70  mov         dword ptr [eax],edx
0140EF72  dec         esi
0140EF73  add         eax,4
0140EF76  inc         edx
0140EF77  test        esi,esi
0140EF79  jne         RTest::DoStuffClassMember+10h (140EF70h)

0140EF7B  mov         dword ptr [ecx+4],eax
0140EF7E  mov         dword ptr [ecx],edx
0140EF80  mov         eax,edx
0140EF82  pop         esi
0140EF83  ret         4
0140EF86  mov         eax,dword ptr [ecx]
0140EF88  pop         esi
0140EF89  ret         4

This is the official way to “restrict this”, and until recently I didn’t know it worked in Visual Studio. Yay!

A few closing comments about the above code…. Astute readers would have noticed a few things that I didn’t mention yet:

The curious “mov edi, edi” clearly doesn’t do anything, and it would be easy to blame the compiler here for being stupid. Well, the compiler is stupid and does generate plenty of foolish things, but this is not one of them. Notice how it happens right before the loop starts? This is the equivalent of the “nop” we previously saw. The reason why the compiler chose not to use nops here is because nop takes only 1 byte (its opcode is “90”), so we would have needed 2 of them here to align the loop to 16-bytes. Using a useless 2-bytes instruction achieves the same goal, but with a single instruction.

Finally, note that the main loop actually touches 3 registers instead of 2:

• esi, the loop counter (nb–)
• eax, the target address mTarget
• edx, the data member mMember

This is not optimal, there is no need to touch the loop counter there. It would probably have been more efficient to store the edx limit within esi, something like:

add        esi, edx                // esi = loop limit
Loop :
mov       dword ptr [eax], edx
add        eax, 4
inc          edx
cmp       edx, esi
jne         Loop

This moves all ‘dec esi’ operations out of the loop, which might have been a better strategy. Oh well. Maybe the compiler is stupid after all

This entry was posted on Tuesday, November 20th, 2012 at 6:18 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.