Re: [CHALLENGE] finding rightmost zero bit - C programmer's take



Bart Vandewoestyne wrote: 
OK folks, time for a new challenge...

My profiler tells me that findpos(n) is a function which my code
seems to be using.  The function looks like:

  function findpos(n) result (pos)

    integer(kind=i4b), intent(in) :: n
    integer(kind=i4b)             :: pos

    ... do your private stuff here ...

  end function findpos

and its purpose is to find the index of the rightmost zero bit in the
base 2 representation of a number n.  The least significant bit has
position 1.

The exact `Mission' of the challenge and a template-file can be
found at

http://www.cs.kuleuven.ac.be/~bartv/stuff/time_findpos.f95

<... SNIP ...>
Challenge ends this sunday at 23h59 your local time :-)

This task seemed one that was made for C, so here are my comments from that end (I program in C and Fortran).

Using the source below with van Buskirk's assembler functions, I found that with gcc-3.4,

	gcc -O2 -march=athlon-xp bit.c funcs.s
	294967286 bits counted, 1.6388 s
and

	gcc -DPUREC -O2 -march=athlon-xp bit.c funcs.s
	294967286 bits counted, 1.2171 s

With a different C compiler (IBM VAC-4, ca 1998), I got

	iccv4 /O+ /qarch=pentium2 bit.c funcs.obj
	294967286 bits counted, 1.3668 s
and

	iccv4 /O+ /DPUREC /qarch=pentium2 bit.c funcs.obj
	294967286 bits counted, 1.2113 s

Comments:

1. A good C compiler can produce inline code that beats assembler code; one reason: function call overhead in using the assembler functions.
2. The heart of the program (lines 12 and 13) is simple and natural in C. (This statement is in no way meant to be derogatory to Fortran.)
3. Had the loop on i been reversed (31 to 0), the timings could well be quite different. Bart can exploit whatever he knows about the patterns in the arguments that his real program will call findpos() with.
4. The five significant digits that I show in the run-time are more than one can vouch for.

N. Shamsundar
University of Houston

____________________________________________________
/* File bit.c */
#include <stdio.h>
main(int argc,char *argv[]){
unsigned register x,y; register int i,tot;
double cycle=0.6523e-9;		// 1.53 GHz CPU
unsigned t0,t1;
extern int timer(void),findpos(unsigned);
t0=timer();
for(tot=0, y=1; y< 147483648; y++){
#ifdef PUREC
   for(x=y, i=0; i<32; i++){
      if(! (x & 1))break;
      x=x >> 1;
      }
   i++;	// 1 offset
#else
   i=findpos(y);
#endif
   tot+=i;
//   printf("The rightmost bit of %u has index %d\n",y,i);
   }
t1=timer();
printf("%08.8X\n%8.8X\n",t0,t1);
printf("%d bits counted, %.4f s\n",tot,(t1-t0)*cycle);
}
.