Consider for a motivating example a copy-on-write array, which implements a persistent (i.e. immutable) array data type. As an optimisation at runtime, a reference counter 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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Dodd
    Jan 22 at 21:38
  • 1
    $\begingroup$ @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). But there are also various other persistent data structures which other optimisations might apply to. $\endgroup$
    – kaya3
    Jan 22 at 21:46


You must log in to answer this question.

Browse other questions tagged .