From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 8996C7FC86 for ; Fri, 20 Mar 2015 09:38:08 +0100 (CET) Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of bmillwood@janestreet.com) identity=pra; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of bmillwood@janestreet.com designates 38.105.200.112 as permitted sender) identity=mailfrom; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.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@mxout1.mail.janestreet.com) identity=helo; client-ip=38.105.200.112; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="postmaster@mxout1.mail.janestreet.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CBAAAX2wtVnHDIaSZchDIEgwrDMAGFfgKBLQdMAQEBAQEBEQEBAQEBBhYJQoQUAQEBAwESER0BASMUAQQLCwQHDSoCAiEBEgEFARwGEyKHeQMJCAOlMj4xikFwhGIBBZAnDYUxAQEBAQEBBAEBAQEBAQEBFAYKiw2CRIItB4ItOxKBM5g/M4FMgRsRjApMhFwSI4EVhBBvgkMBAQE X-IPAS-Result: A0CBAAAX2wtVnHDIaSZchDIEgwrDMAGFfgKBLQdMAQEBAQEBEQEBAQEBBhYJQoQUAQEBAwESER0BASMUAQQLCwQHDSoCAiEBEgEFARwGEyKHeQMJCAOlMj4xikFwhGIBBZAnDYUxAQEBAQEBBAEBAQEBAQEBFAYKiw2CRIItB4ItOxKBM5g/M4FMgRsRjApMhFwSI4EVhBBvgkMBAQE X-IronPort-AV: E=Sophos;i="5.11,435,1422918000"; d="scan'208";a="126884546" Received: from mxout1.mail.janestreet.com ([38.105.200.112]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 20 Mar 2015 09:38:07 +0100 Received: from tot-qpr-mailcore1.delacy.com ([172.27.56.68] helo=tot-qpr-mailcore1) by mxout1.mail.janestreet.com with smtp (Exim 4.82) (envelope-from ) id 1YYsRR-0001m2-7o for caml-list@inria.fr; Fri, 20 Mar 2015 04:38:05 -0400 X-JS-Flow: external Received: by tot-qpr-mailcore1 with JS-mailcore (0.1) (envelope-from ) id BVC9xt-AAAD3y-HC; 2015-03-20 04:38:05.225985-04:00 Received: from mail-qc0-f178.google.com ([209.85.216.178]) by mxgoog1.mail.janestreet.com with esmtps (UNKNOWN:AES128-GCM-SHA256:128) (Exim 4.72) (envelope-from ) id 1YYsRR-0002Ur-2x for caml-list@inria.fr; Fri, 20 Mar 2015 04:38:05 -0400 Received: by qcto4 with SMTP id o4so87613377qct.3 for ; Fri, 20 Mar 2015 01:38:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=Jq3SDZ7kkdng3mmKrinXqcbpDx6P9qYPKG6Yas/UJWY=; b=el7AzCwsR3qmGWwB7RD91SwUddNo0jTqPA0krMGLP9B9CvIB2Iv3OhwdlQXrfBJvVL Zp0Z6e3jNLxOBwnC1NtDwugbB4J72ImZnqx7UpabmWQ9LV8NcGgSa7HjpHAOlJG4cjeS qc2rBG4jxvjJDzjbO0iQAEqbm04HT0pA6X5PI= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=Jq3SDZ7kkdng3mmKrinXqcbpDx6P9qYPKG6Yas/UJWY=; b=VQlqAJw8ad8trfxYRFjIpGYqRcAbdmxvh2pJ9ZUGZ2rZM/QEUxQZ9aTvExDmPs0Fwp OS8yotr2ddkU8JxFxwYnDvSsFqKIuLudn4jeZjbLAp+l/IDyi1IuujFEz7QGGvUH9sLg knvAU1ajAKZ61JWGNeCL3c6JBkXOYpeYv4YqFXd8hQW56bG4af0LGwDEUSS7bBmWohq7 B03lrwv7tJH5eBgFilju9ykTP5lpepIiqGyrjbXCNM0jyYp7rm5hev92lzmrDwVwH78f brnJ7KedTxY7RWniizZ2CqsEjmDPw3nrUkmmUgxOW1jqsJHb31cteN08fYTcrt4vb0Bp Du0Q== X-Gm-Message-State: ALoCoQlsXHCow5zkHMPL1wQLYeCdAWrNn/z87RdcBlouZEgxX3J7qYf8N1lcjKqUwei0RpxZiUsHf6tWPSrno6ksnDeKyqZd2lHLJzLm9lQTrI/LklZ7zPDbnbb9Z14/cc31NCKbG6na X-Received: by 10.55.27.198 with SMTP id m67mr132095901qkh.11.1426840684887; Fri, 20 Mar 2015 01:38:04 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.55.27.198 with SMTP id m67mr132095894qkh.11.1426840684795; Fri, 20 Mar 2015 01:38:04 -0700 (PDT) Received: by 10.96.81.100 with HTTP; Fri, 20 Mar 2015 01:38:04 -0700 (PDT) In-Reply-To: References: Date: Fri, 20 Mar 2015 08:38:04 +0000 Message-ID: From:Ben Millwood To:Gabriel Scherer Cc:Kenneth Adam Miller , caml users Content-Type: multipart/alternative; boundary=001a113ccbc02b2d210511b43c93 X-JS-Processed-by: mailcore Subject: Re: [Caml-list] Compiler Intrinsics question --001a113ccbc02b2d210511b43c93 Content-Type: text/plain; charset=UTF-8 It's worth mentioning that when replacing a single element from a complex immutable datastructure, it's not usually necessary to copy *all* of the rest of the data -- the new data can reuse parts it has in common with the old. For example, if you had a set represented as a balanced binary tree, you will be able to represent that set with one element added -- alongside the original set, even -- with no more than log-size-of-set copying / additional space. On 18 March 2015 at 06:10, Gabriel Scherer wrote: > I think the effect you may be thinking of is to notice that the immutable > structure for which a field update is performed is uniquely owned / > linearly used (the old version before-update is never used again), and to > perform the mutation in place in this case. OCaml does not perform this > optimization. It's not immediate that this could be done at all, because > mutation has a tricky interaction with the GC invariants. > > On Wed, Mar 18, 2015 at 4:16 AM, Kenneth Adam Miller < > kennethadammiller@gmail.com> wrote: > >> So, OCaml uses a lot of immutable data structures by default, and there's >> a way in OCaml to express how to replace everything else in a type with the >> same edition, with the exception of a single variable being updated. >> >> >> But does that mean that the compiler is sufficiently capable to conclude >> side effects that are more efficient rather than just the nieve >> explanation, which is a *copy* of the entire data structure with only the >> specified changed variable updated? Can OCaml conclude that it can update >> only one variable for efficiency, and know that the rest of the data >> structure is safe? >> >> For example, in tail recursion, it's provably equivalent to produce code >> that doesn't blow the stack and is faster, and that's exactly what the >> compiler does. So are side effects a "conclusion"? >> > > --001a113ccbc02b2d210511b43c93 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
It's worth mentioning that when replacing a single ele= ment from a complex immutable datastructure, it's not usually necessary= to copy *all* of the rest of the data -- the new data can reuse parts it h= as in common with the old. For example, if you had a set represented as a b= alanced binary tree, you will be able to represent that set with one elemen= t added -- alongside the original set, even -- with no more than log-size-o= f-set copying / additional space.

On 18 March 2015 at 06:10, Gabriel Scherer <gabriel.scherer@gmail.com> wrote:
I think the effect you may be thinking of is to no= tice that the immutable structure for which a field update is performed is = uniquely owned / linearly used (the old version before-update is never used= again), and to perform the mutation in place in this case. OCaml does not = perform this optimization. It's not immediate that this could be done a= t all, because mutation has a tricky interaction with the GC invariants.
=
On Wed, Mar 18, 2015 at 4:16 AM, Kenneth Ada= m Miller <kennethadammiller@gmail.com> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px= #ccc solid;padding-left:1ex">
So, OCaml uses a lot of immu= table data structures by default, and there's a way in OCaml to express= how to replace everything else in a type with the same edition, with the e= xception of a single variable being updated.


<= div>But does that mean that the compiler is sufficiently capable to conclud= e side effects that are more efficient rather than just the nieve explanati= on, which is a *copy* of the entire data structure with only the specified = changed variable updated? Can OCaml conclude that it can update only one va= riable for efficiency, and know that the rest of the data structure is safe= ?

For example, in tail recursion, it's provabl= y equivalent to produce code that doesn't blow the stack and is faster,= and that's exactly what the compiler does. So are side effects a "= ;conclusion"?


--001a113ccbc02b2d210511b43c93--