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

"N. Shamsundar" <shamsundar_at_@xxxxxx> wrote in message
news:df1nvl$219p$1@xxxxxxxxxxxxxxxxxxx

> 1. A good C compiler can produce inline code that beats assembler code;
> one reason: function call overhead in using the assembler functions.

Bzzzt. The problem is that you aren't using a reasonable data
set. I seem to be a voice crying in the wilderness here, but...

C:\g95_MINGW\clf\findpos>type funcs.s
# File: funcs.s
# Public domain 2005 James Van Buskirk

..globl _timer_
..globl _findpos_

..data

..text
..align 4

_timer_:
rdtsc
ret

_findpos_:
movl 4(%esp), %eax
movl 0(%eax), %eax
not %eax
bsf %eax, %eax
jz no_bits
inc %eax
ret

no_bits:
movl $33, %eax
ret

# End of file: funcs.s

C:\g95_MINGW\clf\findpos>type time_findpos.f90
! File: time_findpos.f90
! Public domain 2005 James Van Buskirk

module mykinds
implicit none
integer, parameter :: ik8 = selected_int_kind(18)
integer, parameter :: dp = selected_real_kind(15,300)
end module mykinds

module mymod
implicit none
contains
! Bart Vandewoestyne's function (1).
!
function findpos_bart1(n) result (pos)

integer, intent(in) :: n
integer :: pos

pos = 0
do
if (.not. btest(n, pos)) exit
pos = pos + 1
end do
pos = pos + 1

end function findpos_bart1
end module mymod

program time_findpos
use mykinds
use mymod
implicit none
interface
function timer()
use mykinds
implicit none
integer(ik8) timer
end function timer
end interface
interface
function findpos(x)
implicit none
integer, intent(in) :: x
integer findpos
end function findpos
end interface
integer number
integer(ik8) t0, t1
real(dp), parameter :: freq = 1.4e9_dp
integer i, j
integer(ik8) total
integer :: test_data(100) = not(ishft(1, (/ &
18, 15, 26, 5, 17, 6, 19, 18, 20, 19, 18, 26, 10, 11, 23, 15, &
13, 0, 20, 2, 19, 16, 30, 19, 20, 18, 17, 11, 10, 24, 16, 20, &
1, 30, 18, 29, 29, 28, 6, 5, 29, 9, 19, 14, 4, 16, 29, 30, &
6, 14, 29, 5, 14, 13, 30, 13, 4, 29, 23, 14, 6, 29, 17, 0, &
26, 1, 28, 17, 18, 17, 6, 6, 6, 29, 20, 28, 8, 8, 22, 13, &
28, 25, 24, 26, 22, 17, 1, 17, 26, 4, 12, 24, 20, 21, 25, 24, &
18, 20, 20, 1 &
/) ) )


write(*,'(a)',advance='no') ' Enter number of tests:> '
read(*,*) number
total = 0
t0 = timer()
do i = 1, number-size(test_data)+1, size(test_data)
do j = 1, size(test_data)
total = total+findpos(test_data(j))
end do
end do
j = 0
do i = i, number
j = j+1
total = total+findpos(test_data(j))
end do
t1 = timer()
write(*,'(a)') ' Results for assembly code:'
write(*,'(a,i0)') ' Total bits counted = ', total
write(*,'(a,f0.3)') ' Total time = ', (t1-t0)/freq
total = 0
t0 = timer()
do i = 1, number-size(test_data)+1, size(test_data)
do j = 1, size(test_data)
total = total+findpos_bart1(test_data(j))
end do
end do
j = 0
do i = i, number
j = j+1
total = total+findpos_bart1(test_data(j))
end do
t1 = timer()
write(*,'(a)') ' Results for findpos_bart1:'
write(*,'(a,i0)') ' Total bits counted = ', total
write(*,'(a,f0.3)') ' Total time = ', (t1-t0)/freq
end program time_findpos

! End of file: time_findpos

C:\g95_MINGW\clf\findpos>as funcs.s -ofuncs.o

C:\g95_MINGW\clf\findpos>g95 -std=f95 time_findpos.f90
funcs.o -otime_findpos

C:\g95_MINGW\clf\findpos>time_findpos
Enter number of tests:> 50000000
Results for assembly code:
Total bits counted = 895500000
Total time = 1.340
Results for findpos_bart1:
Total bits counted = 895500000
Total time = 5.308

--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end


.

Relevant Pages