Tinkering with STL #2 – Functors and examining the compiler output

In Tinkering with STL #1, I briefly described what the C++ Standard Template Library’s Functors and Binders were for. Today, I’m going to show what the compiler does when faced with this with this type of source code.

All code show here will be compiled using the Professional version of Visual Studio 2005 with Service Pack 1 applied. Compiler version 14.00.50727.762.

1a. Static parameters passed to a Functor

In the following code snippet, the integers a and b are statically set to 2 and 1, respectively:

  // 1a. Functor.
  int a=2, b=1;
  if ( std::greater<int>()(a, b) )
    cout << "a is Greater then b." << endl;

So at compile-time, the compiler should be able able to deduce that the condition (whether a is greater than b) is not going to change at runtime, and hopefully eliminate any conditional checks.

Let’s think about that for a minute. The code appears to be making a call to a greater function, and yet I’m expecting the compiler to reason about this call ; that greater is functional – it’s result is conditional only upon it’s parameters, and that if it’s parameters are static, the result will not change – ever. Of course that is not what is actually happening with this templated code – it’s “expanded” and “inlined” before it’s fully compiled. But it’s an interesting concept, none-the-less. I suppose the fact that greater lives in a header file named functional should alert users about this. But that assumes your users are aware of this concept to begin with…

Here is the resulting assembly code, as seen within the Disassembly view in VS2005:

  // 1a. Functor.
  int a=2, b=1;
  if ( std::greater()(a, b) )
    cout << "a is Greater then b." << endl;
1.  00401007  mov         eax,dword ptr [__imp_std::endl (40204Ch)] 
2.  0040100C  push        esi  
3.  0040100D  push        eax  
4.  0040100E  push        ecx  
5.  0040100F  mov         ecx,dword ptr [__imp_std::cout (402044h)] 
6.  00401015  push        offset string "a is Greater then b." (402134h) 
7.  0040101A  push        ecx  
8.  0040101B  call        std::operator<< > (401210h) 
9.  00401020  add         esp,0Ch 
10. 00401023  mov         ecx,eax 
11. 00401025  call        dword ptr [__imp_std::basic_ostream >::operator<< (402048h)] 

Wonderful. No conditional code, at all. Let’s step through the assembly code just this once, so you can get a feel for what it’s doing. (I added the line numbers above).

1. Starting at code address 0x401007, we move the address of the endl function into the eax register. How do I know that this symbol is a pointer to code and not data ?.  I cheated ; I saw how it used later in the program. Similarly, you can use Intellisense or the Code Definition Window within Visual Studio, or given that it’s an import, you can use a tool like Dependency Viewer and check the DLL’s exports.
2. The esi register is pushed onto the stack. It’s not obvious at this point why it is doing this. But after a bit of sleuthing, you soon realise that it’s simply saving the register ; this code just happens to be hard up against the main entry point. Later, just before main exits, the original contents of this esi register is popped back off the stack.
3. This pushes the address of endl (that we got in step 1) onto the stack in preparation for the (second) call to operator<< in step 12 below.
4. The contents of the ecx register is pushed onto the stack. This is just saving the register so it can be used in the next step.
5. The ecx register is loaded with the address of the global cout output stream object.
6. The address of the string we’re going to print out on the console is pushed onto the stack. Thankfully, the debugger shows us the string.
7. The cout object’s address, that we got in step 5, is now pushed onto the stack, ready for the call in the next step.
8. We call operator<<. The parameters it needs are on the stack, in reverse order. That is the output stream (step 7), and the string (step 6).
9. We manually fix-up the stack pointer rather than popping off the parameters passed in the previous call (step 8).
10. We move a copy of the cout object’s address in the ecx register.
11. Finally, we call operator<< again. But curiously, this time it’s an indirect call into msvcp80.dll. This program was compiled to use the standard libraries as DLLs.

1b. Variable parameters passed to a Functor

Next, I add a proper conditional by assigning the result of the rand function to b.

  // 1b. Functor.
  b = (rand() > RAND_MAX/2) ? 2 : 0;
  if ( std::greater<int>()(a, b) )
    cout << "a is Greater then b." << endl;

Here is the assembly code it produces:

  // 1b. Functor.
  b = (rand() > RAND_MAX/2) ? 2 : 0;
 1. 0040102B  mov         esi,dword ptr [__imp__rand (4020D0h)] 
 2. 00401031  call        esi  
 3. 00401033  xor         edx,edx 
 4. 00401035  cmp         eax,3FFFh 
 5. 0040103A  setle       dl   
 6. 0040103D  sub         edx,1 
 7. 00401040  and         edx,2 
  if ( std::greater()(a, b) )
 8. 00401043  cmp         edx,2 
 9. 00401046  jge         main+6Bh (40106Bh) 
    cout << "a is Greater then b." << endl;
10. 00401048  mov         eax,dword ptr [__imp_std::endl (402054h)] 
11. 0040104D  push        eax  
12. 0040104E  push        ecx  
13. 0040104F  mov         ecx,dword ptr [__imp_std::cout (40204Ch)] 
14. 00401055  push        offset string "a is Greater then b." (402134h) 
15. 0040105A  push        ecx  
16. 0040105B  call        std::operator<< > (401240h) 
17. 00401060  add         esp,0Ch 
18. 00401063  mov         ecx,eax 
19. 00401065  call        dword ptr [__imp_std::basic_ostream >::operator<< (402050h)]

Notice how the code from line 10 onwards is almost identical to earlier. Also notice how it uses some creative mathematics to set b (edx register) in lines 3 through to 7. It’s interesting enough, so I’ll step though it.

1. moves the address of the rand function into the esi register.
2. calls the rand function, indirectly, via esi.
3. Zeroes the edx register.
4. compares edx with 0x3fff – half of the maximum range that rand can return.
5. Sets dl to one if the comparison in step 4 was less than or equal, and zero otherwise. dl is the lower 8-bits of the edx register.
6. subtracts one from edx. If edx was zero, all bits become set (minus one).
7. masks edx so that if any bits were set, only bit-1 remains. ie edx will contain the value two or zero.
8. Now we finally get to the code from the greater Functor. edx is compared with two.
9. If the result of the comparison is greater or equal, then it jumps over the cout code.

1c. Volatile parameter passed to a Functor

Finally, I was interested to see how the compiler behaved if I modified the first code snippet by using a parameter that’s been attributed with the volatile keyword.

  // 1c. Functor.
  volatile int v=1;
  if ( std::greater<int>()(a, (int)v) )
    cout << "a is Greater then v." << endl;

Here is the assembly code:

  // 1c. Functor.
  volatile int v=1;
 1. 0040106B  mov         dword ptr [esp+4],1 
  if ( std::greater()(a, (int)v) )
 2. 00401073  cmp         dword ptr [esp+4],2 
 3. 00401078  jge         main+9Dh (40109Dh) 
    cout << "a is Greater then v." << endl;
 4. 0040107A  mov         edx,dword ptr [__imp_std::endl (402054h)] 
 5. 00401080  mov         eax,dword ptr [__imp_std::cout (40204Ch)] 
 6. 00401085  push        edx  
 7. 00401086  push        ecx  
 8. 00401087  push        offset string "a is Greater then v." (40214Ch) 
 9. 0040108C  push        eax  
10. 0040108D  call        std::operator<< > (401240h) 
11. 00401092  add         esp,0Ch 
12. 00401095  mov         ecx,eax 
13. 00401097  call        dword ptr [__imp_std::basic_ostream >::operator<< (402050h)] 

Here we can see that v is given a real memory location, and that it does not optimise away the conditional.