Re: [Caml-list] Re: Binary logarithm of a power of 2

[Till Varoquaux <till@pps.jussieu.fr>]

Nevermind. I am actually running slower, bad benchmark.

Shameful,
Till

On Fri, May 27, 2011 at 2:37 PM, Till Varoquaux <till@pps.jussieu.fr> wrote:
> And you can probably gain on XL by dropping down to ints and not using refs:
>
> let lb5 n i = if n >= 0x2 then i+1 else i
>
> let lb4 n i =
>  if n >= 0x4 then lb5 (n asr 2) (i+2)
>  else lb5 n i
>
> let lb3 n i =
>  if n >= 0x10 then lb4 (n asr 4) (i+4)
>  else lb4 n i
>
> let lb2 n i =
>  if n >= 0x100 then lb3 (n asr 8) (i+8)
>  else lb3 n i
>
> let logbin n =
>  if n >= 0x10000 then lb2 (n asr 16) 16
>  else lb2 n 0
>
> (note that you can drop to ints right in logbin itself if you really
> need your input to be int32s and you aren't on a 32 bit machine).
>
> This is thoroughly untested.
>
> Till
>
> On Fri, May 27, 2011 at 2:04 PM, Dario Teixeira <darioteixeira@yahoo.com> wrote:
>> Hi,
>>
>>> Simpler and maybe faster:
>>>
>>> let logbin (n: int32) =
>>>   let n = ref (Int32.add n 0l) and i = ref 0 in
>>>   if !n >= 0x10000l then (n := Int32.shift_right !n 16; i := 16);
>>>   if !n >= 0x100l then (n := Int32.shift_right !n 8; i := !i + 8);
>>>   if !n >= 0x10l then (n := Int32.shift_right !n 4; i := !i + 4);
>>>   if !n >= 0x4l then (n := Int32.shift_right !n 2; i := !i + 2);
>>>   if !n >= 0x2l then !i + 1 else !i
>>
>> Thanks!  In my synthetic benchmark, this pure Ocaml solution comes very
>> close to the C-based "noalloc" one (the record holder so far), at least
>> on an x86_64.
>>
>> Note that __builtin_ctz actually translates into a single opcode where
>> available (BSFL in x86_64), and I expect that a modern CPU will do a
>> decent job with it.  Therefore, despite that a C-based solution will
>> most likely prevent inlining (right?), it may be hard to beat...
>>
>> Cheers,
>> Dario Teixeira
>>
>>
>>
>> --
>> Caml-list mailing list.  Subscription management and archives:
>> https://sympa-roc.inria.fr/wws/info/caml-list
>> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>>
>