[Caml-list] Compiler Intrinsics question

[Caml-list] Compiler Intrinsics question

[Kenneth Adam Miller]

[-- Attachment #1: Type: text/plain, Size: 790 bytes --]

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"?

[-- Attachment #2: Type: text/html, Size: 900 bytes --]

Re: [Caml-list] Compiler Intrinsics question

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 1331 bytes --]

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"?
>

[-- Attachment #2: Type: text/html, Size: 1722 bytes --]

Re: [Caml-list] Compiler Intrinsics question

[Ben Millwood]

[-- Attachment #1: Type: text/plain, Size: 1908 bytes --]

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 <gabriel.scherer@gmail.com>
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"?
>>
>
>

[-- Attachment #2: Type: text/html, Size: 2617 bytes --]