From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p4QJSRfi013671
	for <caml-list@sympa-roc.inria.fr>; Thu, 26 May 2011 21:28:28 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AhsEAKep3k3ZSMDjkWdsb2JhbABVl3eOOxQBAQEBCQsLBxQDI4hwvRuGHASUcoQlhjQ
X-IronPort-AV: E=Sophos;i="4.65,275,1304287200"; 
   d="scan'208";a="109648757"
Received: from fmmailgate02.web.de ([217.72.192.227])
  by mail1-smtp-roc.national.inria.fr with ESMTP; 26 May 2011 21:28:28 +0200
Received:  from smtp01.web.de  ( [172.20.0.243])
	by fmmailgate02.web.de (Postfix) with ESMTP id 08C2B1A0534D4;
	Thu, 26 May 2011 21:28:28 +0200 (CEST)
Received: from [78.43.204.177] (helo=frosties.localnet)
	by smtp01.web.de with asmtp (TLSv1:AES256-SHA:256)
	(WEB.DE 4.110 #2)
	id 1QPgEN-0005XP-00; Thu, 26 May 2011 21:28:28 +0200
Received: from mrvn by frosties.localnet with local (Exim 4.72)
	(envelope-from <goswin-v-b@web.de>)
	id 1QPgEN-0002Lc-15; Thu, 26 May 2011 21:28:27 +0200
From: Goswin von Brederlow <goswin-v-b@web.de>
To: Dario Teixeira <darioteixeira@yahoo.com>
Cc: caml-list@inria.fr
References: <707567.2845.qm@web111505.mail.gq1.yahoo.com>
Date: Thu, 26 May 2011 21:28:26 +0200
In-Reply-To: <707567.2845.qm@web111505.mail.gq1.yahoo.com> (Dario Teixeira's
	message of "Thu, 26 May 2011 08:51:04 -0700 (PDT)")
Message-ID: <87wrhdtg6d.fsf@frosties.localnet>
User-Agent: Gnus/5.110009 (No Gnus v0.9) XEmacs/21.4.22 (linux, no MULE)
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: goswin-v-b@web.de
X-Sender: goswin-v-b@web.de
X-Provags-ID: V01U2FsdGVkX1/T1p1fYPvYS/Wmo0R49o3g115jK2XjzkDBK0Nm
	3Dsm4X/fJAeXZMN01Z0VvEp1FKfWifYe01gaYLZ4MsHKYEOYLS
	9UwfquJG8=
Subject: Re: [Caml-list] Binary logarithm of a power of 2

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