And I'm pretty sure that if ZFS creates an updated version of some immutable node, under the hood it does this via something that resembles a memcpy() followed by a mutable modification of one or more struct members.
Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.
I'm talking about the internal implementation of those data structures, not about their API. Neither C nor C++ have built-in immutable data structures, so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes.
> Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.
No, you're misunderstanding what I said: For any given abstract functionality or interface (like a key->value map, or a graph composed of vertices and edges), there exists a mutable data structure which is at least as fast as all immutable data structures that provide the same interface. That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.
First of all, yes they do, you can use const on structs and objects and methods to ensure your C/C++ data structure is immutable.
But this is moot anyway:
> so those persistent data structures with their immutable API are implemented using mutable C structs or C++ classes
ZFS isn't something that's in memory, it's a file system… It's a data structure on disk, it's language-agnostic.
> That's because the set of mutable data structures is a strict superset of (i.e., contains all) the set of immutable data structures.
In theory, that's true. It's just a useless fact.
We use immutable data structures because they have benefits. Using the same data structure without immutability may just render it worse as a software tool. So people don't use immutable data structures with the immutability removed.
Immutable data structures are shaped by trade-offs like any other design.
When you need a state that you can rollback, an immutable data structure lets you share the parts of the structure that didn't change between states. That's what ZFS does and that's also how many transactional databases store data.
A mutable data structure would need an entire copy at each state change or it would need to store deltas and apply them backwards when you rollback. Both options are significantly slower than the immutable data structure (where rollback means updating a single pointer).