From mboxrd@z Thu Jan 1 00:00:00 1970 X-Sympa-To: caml-list@inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p4RIkEG7002719 for ; Fri, 27 May 2011 20:46:15 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AugDACHx303RVaE2kGdsb2JhbAA/AQMShEmTNI43CBQBAQEBCQkNBxQEIap/i2KCc4Q8iRsBAQMGgSWDbIEHBJBDiGKCPzuBKoIr X-IronPort-AV: E=Sophos;i="4.65,281,1304287200"; d="scan'208";a="84185226" Received: from mail-fx0-f54.google.com ([209.85.161.54]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 27 May 2011 20:46:09 +0200 Received: by fxm11 with SMTP id 11so3021258fxm.27 for ; Fri, 27 May 2011 11:46:09 -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=guaZmPSzRrVON3VEb92UbWZu7TPtgbOnPA6FGyIF2Ps=; b=SoDBdbnAmGjOsg24RFFqbqKLRCSLF0Ls7twSkraF9Ea151wiCtR+gTqclHIfWUJOUX 1O9Kwr9nQnEpK/iz/HV2TwsC0xsCD7/3+8NdttG9eIrCFOQxTtkJHKItW4oUEgnPODbL rBBuixFaLVnss/q5/wZIe0Fy7RiM+6QuJg2Ys= 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=TzPz4IN0RlsjdiajY4qdjLWizoUvpHFHFJ/MFmwQYAWlggfg0ctVjWSGZ79spNB5dI cfx7AAjdhtkJd0LICKN/XbLttowS3+G+plyFAJXbKgZ4wHfzSIKTiQr9vMe3TWWTAORX +BXGwgP0sjieorPsfkaxzYSko3XtEFam5ka2I= MIME-Version: 1.0 Received: by 10.223.127.210 with SMTP id h18mr2708171fas.46.1306521967661; Fri, 27 May 2011 11:46:07 -0700 (PDT) Sender: till.varoquaux@gmail.com Received: by 10.223.72.13 with HTTP; Fri, 27 May 2011 11:46:07 -0700 (PDT) In-Reply-To: References: <4DDFDC1F.5050605@inria.fr> <165028.34675.qm@web111509.mail.gq1.yahoo.com> Date: Fri, 27 May 2011 14:46:07 -0400 X-Google-Sender-Auth: MaMBUH-OHb3HYLBD4EHKzhSi_iw 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 p4RIkEG7002719 X-Validation-by: till@pps.jussieu.fr Subject: Re: [Caml-list] Re: Binary logarithm of a power of 2 Nevermind. I am actually running slower, bad benchmark. Shameful, Till On Fri, May 27, 2011 at 2:37 PM, Till Varoquaux 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 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 >> >> >