Hacker News new | ask | show | jobs
by jriddycuz 5475 days ago
I think you'd be surprised.

Persistent data structures allow the VM or compiler to determine when things need to be copied. Mutable structures require programmers to worry about copies, so they will make copies when they feel they might be necessary. In very well-defined cases a smart programmer can optimize this to a point where it probably uses less memory than a persistent data structure, but in the average case (and with the average programmer), the VM will likely do a better job of knowing when to copy and when to not bother.
2 comments
eru 5475 days ago
Persistent data structures will win, when your structures have (potentially) multiple futures. If you use your objects in a linear way, then the best you can hope for is your compiler to be smart enough to do something that's as fast as in-place updates.
link
lemming 5475 days ago
You're right, I would absolutely be surprised.

Persistent data structures intrinsically involve copying on updates, and no amount of compiler cleverness can avoid that. I can see the possibility for compiler magic with stream fusion, for example, but I'm not seeing it for data structures. The only win I can see is if you have multiple clients of your data structure holding references to multiple versions, but even there the compiler doesn't help you. Am I missing something?

link
eru 5473 days ago
> Persistent data structures intrinsically involve copying on updates, and no amount of compiler cleverness can avoid that.

The compiler magic can help you there. You are looking for linear types.

link