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 0D6DF7EE35 for ; Thu, 21 Apr 2016 17:46:00 +0200 (CEST) IronPort-PHdr: 9a23:hzCULBA+4hl9nqt1q220UyQJP3N1i/DPJgcQr6AfoPdwSP/5oMbcNUDSrc9gkEXOFd2CrakU26yI4+uwCCQp2tWojjMrSNR0TRgLiMEbzUQLIfWuLgnFFsPsdDEwB89YVVVorDmROElRH9viNRWJ+iXhpQAbFhi3DwdpPOO9QteU1JTnkb7isM2CKyxzxxODIppKZC2sqgvQssREyaBDEY0WjiXzn31TZu5NznlpL1/A1zz158O34YIxu38I46Fp34d6XK77Z6U1S6BDRHRjajhtpZ7djgTYVQaE+lcbV2wXlFIIX1mEv1nGWcLAuzH9sKJY2S+BPty+GaExWDK57LZDShbuhTwbLTM07CfcjckmyOp5pxSovFRdzojPbYfdYPh8VqLGZs4HA2FGW5ACeTZGB9aTdYYACPAQdcNRq4T2p1JG+RS7DA2hD+Pm4jBNj37ym6Y91rJyQkn9wAU8EodW4zzvp9LvOfJXDLm4 Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=gmalecha@gmail.com; spf=Pass smtp.mailfrom=gmalecha@gmail.com; spf=None smtp.helo=postmaster@mail-wm0-f46.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of gmalecha@gmail.com) identity=pra; client-ip=74.125.82.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gmalecha@gmail.com"; x-sender="gmalecha@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of gmalecha@gmail.com designates 74.125.82.46 as permitted sender) identity=mailfrom; client-ip=74.125.82.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gmalecha@gmail.com"; x-sender="gmalecha@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-wm0-f46.google.com) identity=helo; client-ip=74.125.82.46; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="gmalecha@gmail.com"; x-sender="postmaster@mail-wm0-f46.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0B/AABj9BhXiC5SfUpeFoN1fakQKotDg3x2AQ2BcySCOoMwAoEyOBQBAQEBAQEBAREBAQEICwsJHzGCLYIUAQEBAwESEQQZARsSCwEDAQsGBQsDCg0dAgIhAQERAQUBChIGARIIChCHcgEDCggOoHmBMT4xizaBaoJXhxUKGScDClGEHwEBAQEBAQEBAQEBAQEBAQEBAQEBAQ8BBQoFhRp4hEuCQYFIY4JTglYFhjMMjF+EQDGFe4J1gy6BdoI0jFyHT4YhL4EODw8BAYI5HoFTPDABiHUBAQE X-IPAS-Result: A0B/AABj9BhXiC5SfUpeFoN1fakQKotDg3x2AQ2BcySCOoMwAoEyOBQBAQEBAQEBAREBAQEICwsJHzGCLYIUAQEBAwESEQQZARsSCwEDAQsGBQsDCg0dAgIhAQERAQUBChIGARIIChCHcgEDCggOoHmBMT4xizaBaoJXhxUKGScDClGEHwEBAQEBAQEBAQEBAQEBAQEBAQEBAQ8BBQoFhRp4hEuCQYFIY4JTglYFhjMMjF+EQDGFe4J1gy6BdoI0jFyHT4YhL4EODw8BAYI5HoFTPDABiHUBAQE X-IronPort-AV: E=Sophos;i="5.24,513,1454972400"; d="scan'208,217";a="215313867" Received: from mail-wm0-f46.google.com ([74.125.82.46]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 21 Apr 2016 17:45:59 +0200 Received: by mail-wm0-f46.google.com with SMTP id 127so4512948wmz.0 for ; Thu, 21 Apr 2016 08:45:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=iwrHPwQShssNRiaqeZPxIsC02u1fAgUsZJ32/WdGO24=; b=gH/GIyaB7fOy6n91VpZEBogMPTgjlNYuoPylfT1udT89rdhkkN66q25LHZ79fOTEy9 BrLKHR+8ROuOzpFtcOCuJsRLL7kZOSQqGepjpYAWXfpiqh/zxTwKrD0Y+nE9P870H5+n SokNqexFVYx0yrIp3b3Z+Wkgt6dbSqmHBRsLgGGxz9g/NNAcC3pRRnMD7saijtAhRNEL idz9rWXuUWco6IcpDVyfcRcJHT68PEhPPdwBNoa3wI/DbA+NhlgkCGrNA4TYzCrlqTRx XoqbKFstWwQev+5nzfVYVzdbFCQUkwxJpm+DUfkdNmekFJaoLUhiG0uRuP84SfTLHmdn B1EA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=iwrHPwQShssNRiaqeZPxIsC02u1fAgUsZJ32/WdGO24=; b=NgidWoJmLs/NLLNJLmd8n73BwqOsURGCnP3WZt3ow22HsIkIIelvq9V5KADwO/iSkq W+ePO0Xva25wyTYoopDAJ4iNonRmJ1nndbVGPpkiIlKoU3nWPvyYlLxVgAv4gYFWUEXH LTQVCKxwQiatyai5yp8z12LNUOv9PLZVGFlt8s6N15K1Biuzy8/P2sLJBA3OMU2y4FFj NhzthV97UFYAG38bwbYScQNwyHliV9oV09XHvRQuNd/FFfgA0ZlACT8F1un7SE6xv091 G5OSPftPeP26wKhM95sxuuzNABjLhjC8JVXOqWw6r1Tued9l2VNAqoxC6XK9Jpy9FcXa bJBA== X-Gm-Message-State: AOPr4FU+uOpKSylT9F/ZMsrUASWt9I8/T8uUd1mlc16THIm4fvj96rA/BOSCFrnoobRghCoUHNNmMEm7wruLmg== X-Received: by 10.194.6.225 with SMTP id e1mr16190574wja.152.1461253559156; Thu, 21 Apr 2016 08:45:59 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Gregory Malecha Date: Thu, 21 Apr 2016 15:45:48 +0000 Message-ID: To: Yaron Minsky , Jonas Jensen Cc: caml users Content-Type: multipart/alternative; boundary=047d7b5d2bfc5209850531009b00 Subject: Re: [Caml-list] Question about Optimization --047d7b5d2bfc5209850531009b00 Content-Type: text/plain; charset=UTF-8 Thanks for the feedback. It sounds like there are reasonable ways to do this if you write your programs in such a way that everything can be done via inlining. While I agree that this works in many cases, it doesn't seem powerful enough to solve everything. For example, equations that are only provable by induction are not optimizable by this strategy (without some pretty fancy tricks). Do you believe that having a rewriting facility is unnecessary? Undersireable (it makes the compiler too complex, too slow, too unpredictable)? Or do you think that it would be useful, but no one has done anything on it? Thanks. On Thu, Apr 21, 2016, 4:45 AM Yaron Minsky wrote: > Also, Core_kernel's Sequence type fills a similar purpose. And Flambda > does a good job of optimizing the iteration in Sequence, from what I've > overheard about our experiments. > > On Thu, Apr 21, 2016 at 5:32 AM, Jonas Jensen wrote: > >> On 21 April 2016 at 09:13, Gregory Malecha wrote: >> > >> > I'm wondering if there is any work (and interest) on supporting >> user-defined optimizations similar to GHC's rewrite rules in the Ocaml >> compiler. For example, a standard example would be specifying map fusion: >> > >> > map f (map g ls) = map (fun x -> f (g x)) ls >> >> A "boring" and practical answer is that you get this optimization by >> writing your long chain of map, filter, bind, etc. using Batteries' >> Enum ( >> http://ocaml-batteries-team.github.io/batteries-included/hdoc2/BatEnum.html >> ) >> or the stand-alone Gen package >> (http://cedeela.fr/~simon/software/gen/Gen.S.html). It looks >> superficially like list map, but the order of execution will be like >> after a fusion, which should improve cache locality and avoid >> allocations of intermediate lists. >> >> Cheers, >> Jonas >> > >> -- >> Caml-list mailing list. Subscription management and archives: >> https://sympa.inria.fr/sympa/arc/caml-list >> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners >> Bug reports: http://caml.inria.fr/bin/caml-bugs >> > -- - gregory malecha gmalecha.github.io --047d7b5d2bfc5209850531009b00 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

Thanks for the feedback. It sounds like there are reasonable= ways to do this if you write your programs in such a way that everything c= an be done via inlining. While I agree that this works in many cases, it do= esn't seem powerful enough to solve everything. For example, equations = that are only provable by induction are not optimizable by this strategy (w= ithout some pretty fancy tricks).

Do you believe that having a rewriting facility is unnecessa= ry? Undersireable (it makes the compiler too complex, too slow, too unpredi= ctable)? Or do you think that it would be useful, but no one has done anyth= ing on it?

Thanks.


On Thu, Apr 21, 2016, 4:45 = AM Yaron Minsky <yminsky@janes= treet.com> wrote:
Also, Core_kernel's Sequence type fills a similar purpose.=C2= =A0 And Flambda does a good job of optimizing the iteration in Sequence, fr= om what I've overheard about our experiments.

On Thu, Apr 21, 2016 at 5:32 AM, Jonas Jensen = <jj@= issuu.com> wrote:
<= div class=3D"gmail_quote">
On 21 April = 2016 at 09:13, Gregory Malecha <gmalecha@gmail.com> wrote:
>
> I'm wondering if there is any work (and interest) on supporting us= er-defined optimizations similar to GHC's rewrite rules in the Ocaml co= mpiler. For example, a standard example would be specifying map fusion:
>
> map f (map g ls) =3D map (fun x -> f (g x)) ls

A "boring" and practical answer is that you get this optim= ization by
writing your long chain of map, filter, bind, etc. using Batteries'
Enum (http://ocaml-batter= ies-team.github.io/batteries-included/hdoc2/BatEnum.html)
or the stand-alone Gen package
(http://cedeela.fr/~simon/software/gen/Gen.S.html). It looks
superficially like list map, but the order of execution will be like
after a fusion, which should improve cache locality and avoid
allocations of intermediate lists.

Cheers,
Jonas

--
Caml-list mailing list.=C2=A0 Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocam= l_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
= --

- gregory malecha
=C2=A0 gmalecha.github.io

--047d7b5d2bfc5209850531009b00--