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

[Goswin von Brederlow <goswin-v-b@web.de>]

Dario Teixeira <darioteixeira@yahoo.com> writes:

> Hi,
>
> In the critical path of an application I need to compute the binary
> logarithm of an int32.  With one nuance: I know the input is always
> a power of 2, which opens the door to bit-trickery (the log2 of a
> power of 2 is simply the position of the sole bit set to '1').
>
> GCC has a builtin function __builtin_ctz which I suppose will translate
> into optimal assembly for all platforms, so my current solution uses a
> small C stub that basically just invokes this builtin (see below).
>
> Still, my question is whether this is indeed the optimal solution.
> Is there some penalty associated with invoking C functions that may
> negate the supposed advantage of __builtin_ctz?

I doubt you can make an ocaml function that does this faster than
invoking a C function. Esspecially with noalloc that gives you verry
little leeway over the optimized __builtin_ctz. I doubt you can
translate the asm tricks gcc does to ocaml without loosing performance.

> Thanks in advance!
> Best regards,
> Dario Teixeira
>
>
> external logbin: int32 -> int = "logbin_stub"
>
> CAMLprim value logbin_stub (value v_num)
>         {
>         CAMLparam1 (v_num);
>         CAMLlocal1 (ml_res);
>
>         int32 num = Int32_val (v_num);
>         int res = __builtin_ctz (num);
>
>         ml_res = Val_int (res);
>         CAMLreturn (ml_res);
>         }

There are 2 improvements you could make:

1) flag the stub as noalloc and drop the CAML*.
2) add a compiler builtin to the ocaml compiler.

Although the 2nd is probably going to far.

MfG
        Goswin