From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id EC81EBC57 for ; Mon, 13 Dec 2010 13:58:12 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AqgAAG2nBU3RVaFEjWdsb2JhbACjdggVAQEBAQkJEw8GJagKiXCCGIRELohWAQEDBYVFBI51 X-IronPort-AV: E=Sophos;i="4.59,335,1288566000"; d="scan'208";a="70395605" Received: from mail-fx0-f68.google.com ([209.85.161.68]) by mail3-smtp-sop.national.inria.fr with ESMTP; 13 Dec 2010 13:58:12 +0100 Received: by fxm16 with SMTP id 16so1720777fxm.3 for ; Mon, 13 Dec 2010 04:58:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:date:from:to:cc:subject :message-id:in-reply-to:references:x-mailer:mime-version :content-type:content-transfer-encoding; bh=LvNQMuxflSruKeunQ0cHJcgHpICA5pVf2MY4Yc/glaw=; b=AcV/klvHSNLvYYRk3dDH6BNFrLyeL8r6h4/WOnyeZFbnA1Xrcv7+ChZWzYaMhwPFVd qRzHW/k0PiR78aGIqGmm4YEOvYPNtUyJKvQine7eD+LLevCrkfkp5pD6XRmFkKB+Ve+f XoklY7Z4QXa/ekTN6P06gJ+dkZ2nlAggjldgA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=date:from:to:cc:subject:message-id:in-reply-to:references:x-mailer :mime-version:content-type:content-transfer-encoding; b=frGC272f0L/CTwrhXegc2cWOyuzNuHEwnIycRZlJMd8oVU8NOuGef4k5yGkYU/h2PA IrShb6/HlHslfqgsZTfndXHwu/9fktFk/LT/R+FMVdRawmH1bha+2eOfx+Bv8PELJwyI rIwFHqRlexHlbjn9mfHD9NuxXSJSTQKiOd7r4= Received: by 10.223.79.4 with SMTP id n4mr4324336fak.69.1292245091065; Mon, 13 Dec 2010 04:58:11 -0800 (PST) Received: from deb0 ([79.114.62.231]) by mx.google.com with ESMTPS id n26sm1660356fam.13.2010.12.13.04.58.10 (version=SSLv3 cipher=RC4-MD5); Mon, 13 Dec 2010 04:58:10 -0800 (PST) Date: Mon, 13 Dec 2010 14:58:06 +0200 From: =?UTF-8?B?VMO2csO2aw==?= Edwin To: Jonathan Kimmitt Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Re: optimize div to right shift (NOT!) Message-ID: <20101213145806.7a6f9ac0@deb0> In-Reply-To: References: <20101212172643.3EF80BC5D@yquem.inria.fr> X-Mailer: Claws Mail 3.7.6 (GTK+ 2.20.1; x86_64-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; compiler:01 'int:01 integers:01 integers:01 ocaml:01 ocaml:01 gcc:01 rax:01 rax:01 gcc:01 edwin:98 $3,:98 wrote:01 caml-list:01 int:01 On Mon, 13 Dec 2010 12:33:33 +0000 Jonathan Kimmitt wrote: > > > A C compiler would optimize this to a right shift. Changing that to > > 'Int64.shift_right n 1' speeds up the code. > > Sorry to be a pedant, but this is not correct. The optimisation is > only possible when the arguments are unsigned integers That particular program never used negative integers. > which I don't > think is specifiable when working in OCAML You are right, there is no way to tell ocaml that. > > # Int64.shift_right (-2L) 1;; > - : int64 = -1L (So far, so good) > # Int64.div (-1L) 2L;; > - : int64 = 0L (Good) > # Int64.shift_right (-1L) 1;; > - : int64 = -1L (Duh) It is still possible to avoid the division, gcc generates this: movq %rdi, %rax shrq $63, %rax addq %rdi, %rax sarq %rax Or a better example with division by 8: leaq 7(%rdi), %rax testq %rdi, %rdi cmovns %rdi, %rax sarq $3, %rax And division by non-power of two integers can optimized by replacing it with multiplication with its inverse (which gcc and llvm don't do for signed divisions, only for unsigned ones): http://www.hackersdelight.org/HDcode/magic.c.txt http://www.hackersdelight.org/HDcode/magicu.c.txt Best regards, --Edwin