Re: [CHALLENGE] finding rightmost zero bit

Brooks Moses wrote:

(snip)

I believe the challenge is to find a fair way to time that function. 

About the best way to time x86 code is with RDTSC, as a previous
post showed using assembler code.  If used for timing only, it
might not violate the challenge.

(snip)

Also, I'll propose a bit of loop-unrolling, which should get the _right_ answer, though I doubt it will be much faster than the existing solutions:

  function findpos_brooks1(n) result (pos)

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

    ! Test the first 8 bits with hardwired checks

    if (.not. btest(n, 0))
      pos = 0
    elseif (.not. btest(n, 1))
      pos = 1
    elseif (.not. btest(n, 2))
      pos = 2
    elseif (.not. btest(n, 3))
      pos = 3
    elseif (.not. btest(n, 4))
      pos = 4
    elseif (.not. btest(n, 5))
      pos = 5
    elseif (.not. btest(n, 6))
      pos = 6
    elseif (.not. btest(n, 7))
      pos = 7

    ! Test the remaining cases with a loop.

    else
      pos = 8
      do
        if (.not. btest(n, pos)) exit
        pos = pos + 1
      end do
      pos = pos + 1
    end if
  end function findpos_brooks1

It's not as clever as Glen's solution, but I think the fact that most of the time it does only one or two comparisons is likely to be an advantage, given that his always does five. 

If mine can be compiled to use the conditional load instruction
it should be pretty fast, otherwise it has five conditional
branches that won't predict well.

If you fully unroll the loop yours should have only one conditional
branch each, though also not predictable.  It would, then,
depend very much on branch timings and such, and could be
pretty fast.

It also, as you say, depends much on the distribution of
the first zero.   I might assume uniform, but I have no
idea how it is for the real problem.

-- glen

.

Relevant Pages

  • Re: [CHALLENGE] finding rightmost zero bit
    ... > establishes a lower bound on the timing. ... > function findpos_wrong1(n) result ... > elseif (.not. ...
    (comp.lang.fortran)
  • Re: [CHALLENGE] finding rightmost zero bit
    ... Brooks Moses wrote: ... ) pos = 1 elseif (.not. ... Note that, in this version -- unlike the original bart1 -- the incrementing can be done at programming time rather than at runtime, thereby illustrating some of the utility of ...
    (comp.lang.fortran)
  • Re: [CHALLENGE] finding rightmost zero bit
    ... and I suspect that since 50% of your test cases have pos=1 and 25% more pos=2, the function is then so fast that you are measuring only function call overheads. ... btest(n, pos)) exit ... elseif (.not. ...
    (comp.lang.fortran)