Motoko immutable data structures

Developers
1

Are the immutable data structures is Motoko full copy on write or are they persistent functional data structures (Okasaki)?

2 Likes
2

The latter (Okasaki style)

1 Like
3

Ok, thanks. So structural sharing is implemented for all collections types including arrays, not just lists etc? What are the performance characteristics compared to the immutable types?

Scala for example has both mutable and immutable collections. Immutable are default and mutable are only used where really needed which is rare. “don’t use immutable [collection] types” because they are slow is commonly heard in the Motoko universe. There seems to be an impression that changes to mutable structures incur a full copy cost.

What is the recommendation?

1 Like
4

Ok, thanks. So structural sharing is implemented for all collections types including arrays, not just lists etc? What are the performance characteristics compared to the immutable types?

I think Motoko is just fine for implementing Okasaki style persistent data structure, provided they are well implemented. I think our implementations of those data structures have in the past been incomplete (with leaky logical rather than proper physical deletion) and poorly optimized. But that’s more of a reflection on the state of the base library rather than Motoko as a language.
For example, we recently implement proper, physical deletion for persistent RBTrees (and identified future improvements) and also improved deletion for Tries.

Scala for example has both mutable and immutable collections. Immutable are default and mutable are only used where really needed which is rare. “don’t use immutable [collection] types” because they are slow is commonly heard in the Motoko universe. There seems to be an impression that changes to mutable structures incur a full copy cost.

Did you mean to write:

There seems to be an impression that changes to immutable structures incur a full copy cost.

Unfortunately, I just discovered that that was true some of our persistent data structures. For example, AssocList.replace re-allocates the entire the list on modification rather than being optimized for sharing.
That’s just a problem with the implementation of that library, not the language per se, and we are working on reducing allocation and preserving more sharing.

Many of our imperative data structures are just wrappers around the persistent ones (e.g. the stateful TrieMap class).

My hunch is that imperative user data structures would be better served with proper imperative implementations under the hood, but I’d be curious to hear if the Scala experience advises otherwise.

1 Like