From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 4FFA97EE51 for ; Wed, 24 Apr 2013 18:57:39 +0200 (CEST) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of anthony.tavener@gmail.com) identity=pra; client-ip=74.125.83.51; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of anthony.tavener@gmail.com designates 74.125.83.51 as permitted sender) identity=mailfrom; client-ip=74.125.83.51; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="anthony.tavener@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ee0-f51.google.com) identity=helo; client-ip=74.125.83.51; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="anthony.tavener@gmail.com"; x-sender="postmaster@mail-ee0-f51.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AugDABsOeFFKfVMzk2dsb2JhbABQgzy2KgGINHgIFg4BAQEBBwsLCRQEJIIgAQVAARsdAQMMBgUEBzsiAREBBQEcBogUAQMPoRqMMIJ7hHcKGScNWYdLAQUMjyQHg0sDiRCODIEljhYWKYRTHQ X-IPAS-Result: AugDABsOeFFKfVMzk2dsb2JhbABQgzy2KgGINHgIFg4BAQEBBwsLCRQEJIIgAQVAARsdAQMMBgUEBzsiAREBBQEcBogUAQMPoRqMMIJ7hHcKGScNWYdLAQUMjyQHg0sDiRCODIEljhYWKYRTHQ X-IronPort-AV: E=Sophos;i="4.87,542,1363129200"; d="scan'208";a="14707849" Received: from mail-ee0-f51.google.com ([74.125.83.51]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/RC4-SHA; 24 Apr 2013 18:57:38 +0200 Received: by mail-ee0-f51.google.com with SMTP id c4so855797eek.24 for ; Wed, 24 Apr 2013 09:57:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; bh=PPXAceWgrsKAJlpW+rCAD8cScJ4xbhBcT92Hfai+xA0=; b=LfLqRcdOsS2YhIDsi1ijnAATu0UZ8wSXTa2xczbe70EdecJPrvY5saDBYnakYXhZoI kxs6pIdXc4QMCssBXc5PcycwqXW6gdwINLl+xxk7lhJ9KyIOcGc+SjhUgJDZfMvPogtX dj9DPwlmiGSnrJgHFbwyZJ6seXW3aDkSsZiZf/gVmC0p6wMHL7gmq7OEhMNxAl9ZfzBY Dvop2sqq2diuyd98VXCsrR6m3VtGWjFBNvbK2MGV/O2PKE0YwErW8uCpGQuTlh+Id8Rh OWlc8w40oBBwLYO87vpXKIOt0hvyvld0xShFw4Niqv+Nd9BaV01nGKrT+D2H6x5C+Pu0 o5zQ== MIME-Version: 1.0 X-Received: by 10.15.83.73 with SMTP id b49mr65107827eez.25.1366822658565; Wed, 24 Apr 2013 09:57:38 -0700 (PDT) Received: by 10.14.118.12 with HTTP; Wed, 24 Apr 2013 09:57:38 -0700 (PDT) In-Reply-To: <51780360.3020607@frisch.fr> References: <20130424183543.e3a4290382f7f9ce7b522a57@gmail.com> <201304241557.r3OFvT9a012995@outgoing.mit.edu> <51780360.3020607@frisch.fr> Date: Wed, 24 Apr 2013 10:57:38 -0600 Message-ID: From: Anthony Tavener To: Alain Frisch Cc: John Carr , ygrek , "caml-list@inria.fr" Content-Type: multipart/alternative; boundary=089e016344880911a704db1e3365 Subject: Re: [Caml-list] ackermann microbenchmark strange results --089e016344880911a704db1e3365 Content-Type: text/plain; charset=ISO-8859-1 Ackermann function! That's a familiar beast, but I only thought I knew it by name (heard of it, never "saw" it). Now that I see it, it was part of a puzzle that I extracted from asm, translated into OCaml, converted to a recursive loop without global state... and ended up with almost exactly that definition. I tried optimizing it for a day... and my notes look like the Wikipedia page, now that I know what to look for. The challenge involved computing A(4,1,p), discovering 'p' which results in '6' (word-wrapped on a 15-bit virtual machine). Eventually I gave up on reducing or optimizing and memoized... churning through over 20k values of 'p' in less than an hour to find my answer. I get slightly different, but very consistent, timing (OCaml 4.00.0). In particular, the timing of ack1 and ack3 are "toggled" compared to yours: ack1.ml 0:04.89 ack2.ml 0:04.89 ack3.ml 0:03.98 ack4.ml 0:03.98 ack5.ml 0:05.23 I'd also expect this kind of result due to alignment. And for fun I added ack5, which is the non-match implementation I ended up deriving from some disassembly: let test r7 = let rec loop x y = if x = 0 then y+1 else if y = 0 then loop (x-1) r7 else loop (x-1) (loop x (y-1)) in loop 4 1 let _ = test 1 I didn't compare asm outputs, but looks like this version adds a small "something". --089e016344880911a704db1e3365 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Ackermann function! That's a familiar beast, but I onl= y thought I knew it by name (heard of it, never "saw" it). Now th= at I see it, it was part of a puzzle that I extracted from asm, translated = into OCaml, converted to a recursive loop without global state... and ended= up with almost exactly that definition. I tried optimizing it for a day...= and my notes look like the Wikipedia page, now that I know what to look fo= r. The challenge involved computing A(4,1,p), discovering 'p' which= results in '6' (word-wrapped on a 15-bit virtual machine). Eventua= lly I gave up on reducing or optimizing and memoized... churning through ov= er 20k values of 'p' in less than an hour to find my answer.

I get slightly different, but very consistent, timing = (OCaml 4.00.0). In particular, the timing of ack1 and ack3 are "toggle= d" compared to yours:

--089e016344880911a704db1e3365--