🚀 go-pugleaf

hrubin@pop.stat.purdue.edu (Herman Rubin) writes:

  awpaeth@watpix.waterloo.edu (Alan Wm Paeth) writes:

    An elegant and efficient MSB-finding algorithm has been forwarded to me by
    Dean Inada (dmi@peregrine.com). It has a constant running time proportional
    to Log2(machine int size):

  This is a good example of 

  1.  Why the instruction is needed as hardware, if it is important at all;

  2.  Why condition codes should be user-available.


  Now check the number of operations.  Assuming that all the constants are in
  registers, and there is total inlining, we have at least 9 arithmetic
  operations of the same type (&) one zeroing, and 5 conditional adds.  This
  is very definitily slow; if the operation is needed that rarely, a crude
  algorithm is probably almost as good as far as total time goes.

  Now the conditional operations can be eliminated if a condition bit can be
  introduced into an arithmetic register.  If we take a true statement to be
  1, then the above algorithm would be better as 

  msbpos(i)
      {
      int p;
      p = (i & 0xFFFF0000  >  0 /* 0x0000xxxx */ ) ;
      (p <<= 1) += (i & 0xFF00FF00  >  i &  0x00ff00ff    ) ;
      (p <<= 1) += (i & 0xF0F0F0F0  >  i &  0x0f0f0f0f    ) ;
      (p <<= 1) += (i & 0xCCCCCCCC  >  i &  0x33333333    ) ;
      (p <<= 1) += (i & 0xAAAAAAAA  >  i &  0x55555555    ) ;
      return(;

  This has a few more instructions, but no conditional operations.

There are several problems with this code.  For one thing it is not legal
C.  Several compilers I have  tried all agree  that '(p <<= 1)' is  not a
valid  lhs.   Here is  a  rewrite,  which  I  will  use in  the following
discussion.

  unsigned long
  msbpos1 ( i )
      unsigned long       i;
  {
      unsigned long       p;
      p = (i & 0xffff0000) > 0;
      p = (p << 1) + ((i & 0xff00ff00) > (i & 0x00ff00ff));
      p = (p << 1) + ((i & 0xf0f0f0f0) > (i & 0x0f0f0f0f));
      p = (p << 1) + ((i & 0xcccccccc) > (i & 0x33333333));
      p = (p << 1) + ((i & 0xaaaaaaaa) > (i & 0x55555555));
      return p;
  }

Note  that on a MIPS  processor this function  will *not* use conditional
branches on the  MIPS, the results of the comparisons are directly stored
into registers with the 's<cc>' instruction.   However this  code uses  9
32bit constants.   On  the  MIPS (and  many other modern RISC processors)
loading a 32bit constant into a register takes 2 cycles.  All in all this
function  takes  about 44 cycles  on  a MIPS  (18  loads  +  9  ands +  5
comparisons + 4 shifts + 4 adds + 4 return etc.).

The  following function  works  quite a bit faster,  because it only uses
16bit  constants,  which, at least on the MIPS, can  be used as immediate
operands (of the  'and' instructions).  Thus  they  need no extra time to
load.  (Actually the Sparc only has  13 bit immediate operands, and  this
function is slower on a Sun 4 than 'msbpos1').

  unsigned long
  msbpos2 ( i )
      unsigned long       i;
  {
      if ( i <= 0xffff ) {
          return (((i & 0xff00)  >  (0         ))  <<  3)
               + (((i & 0xf0f0)  >  (i & 0x0f0f))  <<  2)
               + (((i & 0xcccc)  >  (i & 0x3333))  <<  1)
               + (((i & 0xaaaa)  >  (i & 0x5555))  <<  0);
      }
      else {
          i >>= 16;
          return 16
               + (((i & 0xff00)  >  (0         ))  <<  3)
               + (((i & 0xf0f0)  >  (i & 0x0f0f))  <<  2)
               + (((i & 0xcccc)  >  (i & 0x3333))  <<  1)
               + (((i & 0xaaaa)  >  (i & 0x5555))  <<  0);
      }
  }

However on all machines I tried (DECstation 5000, Sun 4, HP 9000/730) the
following function is even faster.  This may be surprising, because  this
function  executes 4 conditional branches.  However, it does very  little
else, and this is what makes it fast.

  unsigned long
  msbpos3 ( i )
      unsigned long       i;
  {
      if ( i >> 16 )
          if ( i >> 24 )
              if ( i >> 28 )
                  if ( i >> 30 )  return 30 + (i >> 31);
                  else            return 28 + (i >> 29);
              else
                  if ( i >> 26 )  return 26 + (i >> 27);
                  else            return 24 + (i >> 25);
          else
              if ( i >> 20 )
                  if ( i >> 22 )  return 22 + (i >> 23);
                  else            return 20 + (i >> 21);
              else
                  if ( i >> 18 )  return 18 + (i >> 19);
                  else            return 16 + (i >> 17);
      else
          if ( i >> 8 )
              if ( i >> 12 )
                  if ( i >> 14 )  return 14 + (i >> 15);
                  else            return 12 + (i >> 13);
              else
                  if ( i >> 10 )  return 10 + (i >> 11);
                  else            return  8 + (i >>  9);
          else
              if ( i >> 4 )
                  if ( i >>  6 )  return  6 + (i >>  7);
                  else            return  4 + (i >>  5);
              else
                  if ( i >>  2 )  return  2 + (i >>  3);
                  else            return  0 + (i >>  1);
  }

It is  important to  note  however, that the following function is on all
machines I tried the  fastest (though  it is  not  much  faster  than the
previous on the MIPS).  Especially if this routine is used a lot, so that
'msbpostab' is in the cache.

  unsigned char   msbpostab [256] = {
      0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
      5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
      6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
      6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
      7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 };

  unsigned long
  msbpos4 ( i )
      unsigned long       i;
  {
      if ( i >> 16 )
          if ( i >> 24 )
              return 24 + msbpostab[i>>24];
          else
              return 16 + msbpostab[i>>16];
      else
          if ( i >> 8 )
              return  8 + msbpostab[i>>8];
          else
              return  0 + msbpostab[i];
  }

All in  all this function is 5 times faster than 'msbpos1' on the MIPS, 4
times faster on the Sun 4, and 5 times faster on the HP 9000/730.

Martin.

--
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,  +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany