<p>Consider for a motivating example a <a href="https://en.wikipedia.org/wiki/Copy-on-write" rel="noreferrer">copy-on-write</a> array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a <a href="https://en.wikipedia.org/wiki/Reference_counting" rel="noreferrer">reference counter</a> can be used to avoid the copy in the common case that the old array would become garbage after the modification occurs. By eliding copies (where allowed), the &quot;immutable&quot; copy-on-write data structure is effectively mutable &quot;under the hood&quot;.</p>
<p>The above optimisation occurs at runtime. What analogous optimisations can be done at compile-time? By &quot;analogous&quot; I mean that code using some persistent data structure gets optimised into code which uses a mutable data structure instead. I'm particularly interested if there is a class of persistent data structures which can leverage existing compiler optimisations (e.g. in LLVM) to achieve this in common cases.</p>

<compilers><optimization><data-structures><immutable>
How can a compiler optimise persistent data structures to use mutable data structures "under the hood"?
CC BY-SA 4.0
2024-01-22T21:38:11.140Z
Generally, by just calculating the reference count statically at compile time.  The compiler can then know precisely when the reference count is 1 or >1 as well as knowing when it drops to 0 and the object can be freed.  This is basically what rust borrowing is -- tracking the reference count fully at compile time, so there's no need to maintain it at run time.
Chris Dodd
CC BY-SA 4.0
2024-01-22T21:46:32.167Z
@ChrisDodd That works for copy-on-write data structures, if you have a way to do it. Rust can do it because it requires the programmer to specify which values are owned vs. borrowed; other languages don't burden the programmer with that, so you'd need to infer it ([related question](https://langdev.stackexchange.com/q/835/89)). But there are also various other persistent data structures which other optimisations might apply to.
kaya3
# How can a compiler optimise persistent data structures to use mutable data structures "under the hood"?
Posted by: username_0 on 2024-01-22
Consider for a motivating example a [copy-on-write](https://en.wikipedia.org/wiki/Copy-on-write) array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a [reference counter](https://en.wikipedia.org/wiki/Reference_counting) can be used to avoid the copy in the common case that the old array would become garbage after the modification occurs. By eliding copies (where allowed), the "immutable" copy-on-write data structure is effectively mutable "under the hood".

The above optimisation occurs at runtime. What analogous optimisations can be done at compile-time? By "analogous" I mean that code using some persistent data structure gets optimised into code which uses a mutable data structure instead. I'm particularly interested if there is a class of persistent data structures which can leverage existing compiler optimisations (e.g. in LLVM) to achieve this in common cases.
**Tags:** compilers optimization data-structures immutable
> **Comments:**
> **username_1**: Generally, by just calculating the reference count statically at compile time.  The compiler can then know precisely when the reference count is 1 or >1 as well as knowing when it drops to 0 and the object can be freed.  This is basically what rust borrowing is -- tracking the reference count fully at compile time, so there's no need to maintain it at run time.  
> **username_0**: @ChrisDodd That works for copy-on-write data structures, if you have a way to do it. Rust can do it because it requires the programmer to specify which values are owned vs. borrowed; other languages don't burden the programmer with that, so you'd need to infer it ([related question](https://langdev.stackexchange.com/q/835/89)). But there are also various other persistent data structures which other optimisations might apply to.  
---
## 0 answers
