Example

• The x86 architecture includes instructions that determine the positions of the least significant set bit and the most significant set bit in a word.
• The processor can execute these instructions quite efficiently. In contrast, implementing the same operation in C requires a loop and a bit shift.
• The bsrl assembly instruction computes the position of the most significant bit set in its first operand, and places the bit position (counting from 0, the least significant bit) into its second operand.
• To place the bit position for number into position, we could use this asm statement:

  asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
  

  One way you could implement the same operation in C is using this loop:

  long i;
  for (i = (number >> 1), position = 0; i != 0; ++position)
  i >>= 1;
  

• To test the relative speeds of these two versions, we'll place them in a loop that computes the bit positions for a large number of values.
• The http://siber.cankaya.edu.tr/SystemsProgramming/cfiles/bit-pos-loop.c program in Fig. 9.1 does this using the C loop implementation.The program loops over integers, from 1 up to the value specified on the command line. For each value of number, it computes the most significant bit that is set.
• The http://siber.cankaya.edu.tr/SystemsProgramming/cfiles/bit-pos-asm.c program in Fig. 9.2 does the same thing using the inline assembly instruction.
  • Note that in both versions, we assign the computed bit position to a volatile variable result.
  • This is to enforce the compiler's optimizer so that it does not eliminate the entire bit position computation; if the result is not used or stored in memory, the optimizer eliminates the computation as "dead code".

  Figure 9.1: Find Bit Position Using a Loop.

  

  Figure 9.2: Find Bit Position Using bsrl.

  

  $ gcc -O2 -o bit-pos-loop bit-pos-loop.c
  $ gcc -O2 -o bit-pos-asm bit-pos-asm.c
  $ time ./bit-pos-loop 250000000
  $ time ./bit-pos-asm 250000000
  

• Notice that the version that uses inline assembly executes a great deal faster.