From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <bhurt@spnz.org>
X-Original-To: caml-list@yquem.inria.fr
Delivered-To: caml-list@yquem.inria.fr
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by yquem.inria.fr (Postfix) with ESMTP id 62CF5BC57
	for <caml-list@yquem.inria.fr>; Sun, 12 Dec 2010 20:53:45 +0100 (CET)
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Aq0AACa3BE3RVdi2kGdsb2JhbACjfQgVAQECCQkMBxEEJaY6mQiFSgSDd22HDQ
X-IronPort-AV: E=Sophos;i="4.59,333,1288566000"; 
   d="scan'208";a="82477951"
Received: from mail-qy0-f182.google.com ([209.85.216.182])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-MD5; 12 Dec 2010 20:53:44 +0100
Received: by qyk36 with SMTP id 36so4884741qyk.6
        for <caml-list@inria.fr>; Sun, 12 Dec 2010 11:53:43 -0800 (PST)
Received: by 10.224.37.18 with SMTP id v18mr3169941qad.383.1292183623195;
        Sun, 12 Dec 2010 11:53:43 -0800 (PST)
Received: from sergyar.local (pool-96-246-0-211.nycmny.east.verizon.net [96.246.0.211])
        by mx.google.com with ESMTPS id m14sm1797925qcu.44.2010.12.12.11.53.41
        (version=TLSv1/SSLv3 cipher=RC4-MD5);
        Sun, 12 Dec 2010 11:53:42 -0800 (PST)
Date: Sun, 12 Dec 2010 14:53:39 -0500 (EST)
From: Brian Hurt <bhurt@spnz.org>
X-X-Sender: bhurt@sergyar
To: Jon Harrop <jon@ffconsultancy.com>
Cc: caml-list@inria.fr
Subject: Re: Value types (Was: [Caml-list] ocamlopt LLVM support)
In-Reply-To: <036001cb9a0c$725acef0$57106cd0$@com>
Message-ID: <alpine.DEB.2.00.1012121442290.2391@sergyar>
References: <036001cb9a0c$725acef0$57106cd0$@com>
User-Agent: Alpine 2.00 (DEB 1167 2008-08-23)
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Spam: no; 0.00; ocamlopt:01 ocaml:01 ocaml:01 int's:01 captain:98 0.82:98 wrote:01 rec:01 rec:01 ints:01 caml-list:01 int:01 int:01 div:97 therefor:03 


I'm going to regret this.  I know I'm going to regret this.

On Sun, 12 Dec 2010, Jon Harrop wrote:

> Here?s the equivalent OCaml code:
>
>  let rec collatzLen(c, n) : int =
>    if n = 1L then c else
>      collatzLen (c+1, if Int64.rem n 2L = 0L then Int64.div n 2L else
> Int64.add (Int64.mul 3L n) 1L);;
>
>  let rec loop(i, (nlen, n)) =
>    if i = 1L then n else
>      let ilen = collatzLen(1, i) in
>      let nlen, n = if ilen > nlen then ilen, i else nlen, n in
>      loop (Int64.sub i 1L, (nlen, n));;

Congratulations, Jon, you win today's Captain Obvious award.  Using 
Int64's, which are forced to be boxed, really slows things down.  Also, 
uncurrying all your arguments also slows things down.  Running your 
original code on my 64-bit laptop, it took 6.35s to run the 1M example. 
The following alternate code only took 0.82s, for a speed up of almost 
7.75x.  Scaling your timings by a similar amount gives Ocaml a running 
speed of 3.14s in your set up, or competitive with F#.

My code:
   let rec collatzLen c n =
     if n = 1 then c else
       collatzLen (c+1)
         (if (n land 1) == 0 then (n lsr 1) else ((n * 3) + 1))
   ;;

   let rec loop i nlen n =
     if i = 1 then n else
       let ilen = collatzLen 1 i in
       if (ilen > nlen) then
         loop (i - 1) ilen i
       else
         loop (i - 1) nlen n
   ;;

   loop 1000000 0 0


Here is where you insert a lecture about how Ocaml int's being on 63 (or 
31) bits aren't "real" ints, and that therefor this isn't a valid 
comparison at all.

Brian