Re: [CHALLENGE] finding rightmost zero bit

On 2005-08-29, James Van Buskirk <not_valid@xxxxxxxxxxx> wrote:
>
> A solution and some comments:
>
> # 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
> inc %eax
> ret
>
> # End of file: funcs.s

Sorry James, but in my challenges, all programs must be written
in 100% standard-conforming Fortran, no other languages like assembler,
C, whatever... and above all that, the syntax must be
F-compatible :-)

> Your test program doesn't provide for an output so that
> correctness can be verified.

OK. I've added this. Adapted template is as usual at

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

> It's unusual for a Fortran program to count the least significant
> bit as bit 1. The model for integer data considers it to be
> bit 0.

I agree with your comment, but the challenge now takes it as 1
:-)

By the way... would it make a difference in speed if we were counting from 0
and restrict ourselves to 100% standard-conforming F-syntax?
Could somebody come up with a faster algorithm if we were
indexing from 0 instead of 1?

> Your test data might prove to be a bad representative compared
> to real-world data, and is an illustration of why fools often
> consider branchful code to be superior to branchless code.
> If the loop is unrolled a bit, branch prediction will work
> well for your data, because you are testing numbers in
> arithmetic progression. Try a data set where the outputs
> will look more random, and also perhaps a data set where high-
> valued outputs are more common. The g95+as answer given above
> might look better given such a context.

OK. Thanks for this comment. If i have some time to play, i
might... but not now ;-)

Regards,
Bart

--
"Share what you know. Learn what you don't."
.

Relevant Pages

  • Re: Why There are no Asm Apps
    ... I doubt it's much more difficult in ASM than `c`. ... mov D$edi + TSkinProgressBar_Position eax ... mov eax D$edi + TSkinProgressBar_Step ...
    (alt.lang.asm)
  • asm grep
    ... it "saves the call and ret". ... think it was C-the-developer), besides saving the call and ret, has the "advantage" that the "destination" can be any reg - don't need to move eax to wherever you really wanted it. ... %elifidni %1, ebx ...
    (alt.lang.asm)
  • Re: Betovs lies continue
    ... mov eax D$edi + TSkinSection_Text ... sub ecx eax|neg ecx ...
    (alt.lang.asm)
  • New Pos Functions
    ... test eax, eax ... mov ecx, ... cmp al, ...
    (borland.public.delphi.language.basm)
  • Re: Guillermitos Particles
    ... lea eax D$esi + SkinWindow.FreeClientRect ... not reading or copying things I ... Write to this memory, and then use "SetDIBitsToDevice" to output the final thing. ...
    (alt.lang.asm)