[kephasp]

> It's literally not possible for this to be true

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).

[adwn]

Those immutable data structures of ZFS are implemented in C and C++, where everything is mutable. You're actually confirming kadoban's point: Mutable data structures can pretend to be immutable or partially immutable, so there can never be an immutable data structure that's faster than all possible mutable data structures.

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.

[kephasp]

You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something.

Also no one claims there's one immutable data structure that's faster than all mutable data structures. That's a ridiculous strawman argument.

[adwn]

> You're misunderstanding ZFS' persistent data structure. It's the whole point that it's not doing a copy then modifying something.

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.

[kephasp]

> Neither C nor C++ have built-in 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.