From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p4RIbaNj002411 for ; Fri, 27 May 2011 20:37:36 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AugDAHHu303RVaE2kGdsb2JhbAA/AQMShEmTM443CBQBAQEBCQkNBxQEIap3i2KCc4Q8iRsBAQMGgSWDbIEHBJBDiGKCPzuBKoIr X-IronPort-AV: E=Sophos;i="4.65,281,1304287200"; d="scan'208";a="95591399" Received: from mail-fx0-f54.google.com ([209.85.161.54]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 27 May 2011 20:37:31 +0200 Received: by fxm11 with SMTP id 11so3013552fxm.27 for ; Fri, 27 May 2011 11:37:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=6vI5a47NLIBerxtPIU3cTbHERx+f/tLxgJUQ39ngcXA=; b=Ks/qWQZtAYipU7INzEEwkoAjJqyk+QhjZB44og95M45LrxzSFgC5gemxe0rC/s2dRR fxqXYiKjIK7qphGw6CfEON6CTL91eMOR1M8Sy/FA6orfk9uWAkOcli5+USWUpvQkKmuK pXd1O6GAZHg560KnH1uKLnWwYAXjo2IfVo1jY= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type :content-transfer-encoding; b=Z48iaRDqC1qgge6pntIEOXpAQXqANALcB7mH01oQ20InJjZUFdEPSyRBFz4wIib6Qj 4gppfeVvihagR6jiRhJZkAUgp8M2MSuMXJyIS5ALo7Jg3CoIAvusm47kzY7EGwzvDV3b 5HRv+UviqaUeOcqsgNzeHO0RuabQQiAzsI2hU= MIME-Version: 1.0 Received: by 10.223.25.201 with SMTP id a9mr2663921fac.141.1306521450901; Fri, 27 May 2011 11:37:30 -0700 (PDT) Sender: till.varoquaux@gmail.com Received: by 10.223.72.13 with HTTP; Fri, 27 May 2011 11:37:30 -0700 (PDT) In-Reply-To: <165028.34675.qm@web111509.mail.gq1.yahoo.com> References: <4DDFDC1F.5050605@inria.fr> <165028.34675.qm@web111509.mail.gq1.yahoo.com> Date: Fri, 27 May 2011 14:37:30 -0400 X-Google-Sender-Auth: ey6607Ddi9zIdO2Gg8fVHc_mTLM Message-ID: From: Till Varoquaux To: Dario Teixeira Cc: caml-list@inria.fr Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p4RIbaNj002411 X-Validation-by: till@pps.jussieu.fr Subject: Re: [Caml-list] Re: Binary logarithm of a power of 2 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 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 > >