skykanin (Jan 13 2024 at 11:01): skykanin (Jan 13 2024 at 11:01):So whenever a data structure has a ref count of one and is updated Roc can mutate the underlying representation right? However what happens if the ref count is greater than one? Does it degrade to O(n) copy-on-update? And if so does Roc not implement persistent collections?
Richard Feldman (Jan 13 2024 at 11:56):correct on all counts!
Richard Feldman (Jan 13 2024 at 11:56):we have a hypothesis that in practice refcounts will tend to be 1 when updating, so persistent collections would be a net performance loss in practice
Richard Feldman (Jan 13 2024 at 11:57):the only way to test that hypothesis is to try it out, and so far we haven't found demand in practice for persistent collections yet :big_smile:
skykanin (Jan 13 2024 at 11:58):Thanks! :smile:
skykanin (Jan 13 2024 at 12:22):On second thought it seems that even trivial code will break this assumption. For example:
example : List Int
example =
original = [1, 2, 3]
updated = List.append original 4
List.concat original updated
Since original is being reused we can't mutate it in updated right? So the List.append call will need to copy on update if I understand correctly.
Brian Carroll (Jan 13 2024 at 12:59):The assumption is only that the refcount will tend to be 1, not that it will always be 1!
Brian Carroll (Jan 13 2024 at 12:59):We just expect it to be very common.
Brian Carroll (Jan 13 2024 at 13:00):Yes it is very easy to construct examples with refcounts more than 1. The assumption is that those are less common in practice. Because once you create a clone, the refcount of the clone is 1.
skykanin (Jan 13 2024 at 15:01):Brian Carroll said:
Yes it is very easy to construct examples with refcounts more than 1. The assumption is that those are less common in practice. Because once you create a clone, the refcount of the clone is 1.
so if you're updating a data structure and keeping the intermediate values around half of the updates will be O(n) cloning and half will be constant time in-place mutations
Brendan Hansknecht (Jan 13 2024 at 17:22):How often do you mutate a data structure and still need the old version? That should be pretty rare.
If that is the use case, you probably should be thinking about your exact data structure anyway.
Imagine your code example above in any standard imperative language, you would have to write it as:
let original = vec![1, 2, 3];
let updated = original.clone().append(4);
return original.extend(updated);
If you didn't .clone() and instead wrote this, it would give different results:
let original = vec![1, 2, 3];
original.append(4);
return original.extend(original);
Last updated: Jul 06 2025 at 12:14 UTC