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 p4RI4Oha001668 for ; Fri, 27 May 2011 20:04:24 +0200 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApEIADvn301ii1tNiGdsb2JhbAA/AwESl3wxjiIBAQEKCQsJEwQiiHCfaI5ggjeEO4kbAQQFAYYYBIZjjhsmilQ X-IronPort-AV: E=Sophos;i="4.65,281,1304287200"; d="scan'208";a="109722383" Received: from nm7.bullet.mail.sp2.yahoo.com ([98.139.91.77]) by mail1-smtp-roc.national.inria.fr with SMTP; 27 May 2011 20:04:18 +0200 Received: from [98.139.91.63] by nm7.bullet.mail.sp2.yahoo.com with NNFMP; 27 May 2011 18:04:17 -0000 Received: from [98.139.91.14] by tm3.bullet.mail.sp2.yahoo.com with NNFMP; 27 May 2011 18:04:17 -0000 Received: from [127.0.0.1] by omp1014.mail.sp2.yahoo.com with NNFMP; 27 May 2011 18:04:17 -0000 X-Yahoo-Newman-Property: ymail-3 X-Yahoo-Newman-Id: 555772.12741.bm@omp1014.mail.sp2.yahoo.com Received: (qmail 36106 invoked by uid 60001); 27 May 2011 18:04:17 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1306519457; bh=fOYiihRRXGSooYHqViVfe6B3VetNwzBnjUbX9VlNOjw=; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=dV947aIo/EbVQ5+E4Ra1ZYImz8lSa3iXdOHA5hTmLrYIYMXtv5qictbKMAaq1rU5v5Umebb+tfDIdhQk0+izMsYwp5QMmVe10bh1rGg1T1rsGaeZ1+bKfoBtS6XhqCUXF/KF/s07BYG/Q49fovGGbzFRY4tkoIEcG4FEshQUJ9s= DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:In-Reply-To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=JGJi3vig+ROBojXEwi21qzsRyfW1FlSahD+/tx+baXaNFyUifPiR+h3bA7XiXQUa2frFC/RbhrWvO94ze4Y2S/RON5KV6iaALF7oubrbXSh5IjYf4KA9P5f3dChPWjdo1wfC6CiYUlCT19IPCGidfJlZN8jbBKFZF1S5is0GcNQ=; Message-ID: <165028.34675.qm@web111509.mail.gq1.yahoo.com> X-YMail-OSG: hKhc058VM1nr53V7gS0hgb9qFJCx08sFpWk72vV8EEHP4wh _eMb2XZj64bfiUMTlzHHr6kxE8egNV1Qp26Y90rSVjRvD_3wzQbe7WTP6YI3 eDRXwNfg2y6dtY62DjYYnUqIQgpoQmLRk_Pnl2tO9LwAL0TCEtf.tjVQcgIr wVLDJp_jOZfuL71hZ0O__vB.OSaaGYIrstyF3pqETzrb9tGyMp10Vag2Gket QZl.QEjBwMyE8OU8xoY5vvwEQOS__2qDiX.vk.2Iqoe.5Uerl4IRUMgoPkql 6UR2uxAQHr8l82j3NnsR_CTPjHq8Obca5w_NK.q5fPv235LcDuYtAFDiAgxP JuXpgmM_XqaU3RE5BB2QsjKIetgZYr8AuWGL2xBP2tci6XSJZfQOy.TU1TD2 vcqRuGeZ0boKDTQ-- Received: from [213.205.70.212] by web111509.mail.gq1.yahoo.com via HTTP; Fri, 27 May 2011 11:04:16 PDT X-Mailer: YahooMailClassic/12.0.2 YahooMailWebService/0.8.111.304355 Date: Fri, 27 May 2011 11:04:16 -0700 (PDT) From: Dario Teixeira To: caml-list@inria.fr In-Reply-To: <4DDFDC1F.5050605@inria.fr> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by walapai.inria.fr id p4RI4Oha001668 Subject: Re: [Caml-list] Re: Binary logarithm of a power of 2 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