3 ms·

It's not just a cost in terms of memory, it's a cost in terms of performance as well. Persistent data structures tend to result in a fair bit of pointer chasing

It's not just a cost in terms of memory, it's a cost in terms of performance as well. Persistent data structures tend to result in a fair bit of pointer chasing, and the cache miss penalty ain't getting any less expensive. I find oftentimes when I'm working in F# I do the initial versions of a module using persistent data structures, but eventually the profiler tells me it's time to bite the bullet and switch to mutable structures. The change tends to end up being relatively painless because a huge portion of the time I wasn't relying on persistence anyway, the code does not explode into a confetti of bugs, and run times improve considerably.

kqr 11y ago
I think that's a healthy way to view mutability. It's an amazing performance optimisation, but like any optimisation, it's not to be performed prematurely...
- bunderbunder 11y ago
  I think, though, that this case really highlights the extent to which Knuth's quote gets used in a much wider context than he intended. In the context he was explicitly talking about micro-optimization, not large-scale performance-impacting decisions. The use of the word "prematurely" combined with the tendency to forget the context of that quote means it takes on connotations of implying that if you do something for performance from the get-go, that's bad. That just ain't so; sometimes you really do know what you're doing, and know that one option won't be workable and other one will. Choice of data structures is a case where this often happens. If you know up front that you're going to need O(1) random access and replacement, and O(1) typical case and O(N) worst case appending, and that persistence is not necessary, then you already know you want a mutable list. In that case starting with a persistent equivalent and planning to rework things later is likely just a waste of time and, assuming you're doing this at work, money.

kqr 11y ago

I think that's a healthy way to view mutability. It's an amazing performance optimisation, but like any optimisation, it's not to be performed prematurely...

bunderbunder 11y ago
I think, though, that this case really highlights the extent to which Knuth's quote gets used in a much wider context than he intended. In the context he was explicitly talking about micro-optimization, not large-scale performance-impacting decisions. The use of the word "prematurely" combined with the tendency to forget the context of that quote means it takes on connotations of implying that if you do something for performance from the get-go, that's bad. That just ain't so; sometimes you really do know what you're doing, and know that one option won't be workable and other one will. Choice of data structures is a case where this often happens. If you know up front that you're going to need O(1) random access and replacement, and O(1) typical case and O(N) worst case appending, and that persistence is not necessary, then you already know you want a mutable list. In that case starting with a persistent equivalent and planning to rework things later is likely just a waste of time and, assuming you're doing this at work, money.