Mutability is an access pattern and not an underlying data layout.
In fact, some structures that lend themselves to immutability represent the hardware better. Take your vector of a billion elements. It probably is too big for L1/L2 cache. Is it actually a billion things next to each other in memory? Not at all.
If you used something like a radix balanced balanced tree to represent your vector, you get amortized O(1) access and mutation can be implemented using copy on write at individual leaves of the tree. And your abstraction is much friendlier with the cache, because it reflects how the hardware works much better than a simple vector.
In practice, immutable data structures can be much more performant at scale than pretty much anything. They're not just convenient for soundness. Trivial data structures like vectors are really only useful when you're talking hundreds to the low thousands of elements, at which point who cares how much memory they take up?
Comments
Mutability is an access pattern and not an underlying data layout.
In fact, some structures that lend themselves to immutability represent the hardware better. Take your vector of a billion elements. It probably is too big for L1/L2 cache. Is it actually a billion things next to each other in memory? Not at all.
If you used something like a radix balanced balanced tree to represent your vector, you get amortized O(1) access and mutation can be implemented using copy on write at individual leaves of the tree. And your abstraction is much friendlier with the cache, because it reflects how the hardware works much better than a simple vector.
In practice, immutable data structures can be much more performant at scale than pretty much anything. They're not just convenient for soundness. Trivial data structures like vectors are really only useful when you're talking hundreds to the low thousands of elements, at which point who cares how much memory they take up?