If I may make a sweeping overgeneralisation and phrase it poorly, immutable data structures tend to be logarithmically worse (esp. in terms of allocations) than

If I may make a sweeping overgeneralisation and phrase it poorly, immutable data structures tend to be logarithmically worse (esp. in terms of allocations) than mutable structures. But if your language or runtime can prove that a reference is unique, then that overhead can be eliminated because the runtime can simply mutate with no one the wiser. And these languages tend to use GCs in which allocations are cheap, besides the fact that sharing saves you on copying. There are many factors at play. Source: professional Haskell and C++ programmer extraordinaire.