Does D have "structural sharing" of immutable collections?

[Jonathan M Davis]

On Wednesday, May 23, 2012 23:58:42 Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 21:12:04 UTC, Jonathan M Davis wrote:
> > In my personal experience, that's not true at all. I've seen
> > _huge_
> > performance problems in Haskell when using a map. There may be
> > cases where an
> > immutable container may not pose large performance problems,
> > but I would be
> > _very_ wary of using immutable containers, and _very_ careful
> > with them when I
> > did.
> > 
> > - Jonathan M Davis
> 
> I expect problems with eliminating tail calls (especially for
> mutually recursive functions), but cannot find any other reason,
> theoretical or implementation, that would necessarily make it
> execute slowly in D. I think that cache friendliness is possible
> to achieve, at least in my use cases. What else could go wrong?

As part of my thesis work, I wrote a program which was counting possible 
tokens in code (as part of an AI attempting to learn about a programming 
language), which required a map of tokens to the number of times that they'd 
been seen. Because I had previously been doing stuff in Haskell for my thesis, 
I continued to use Haskell for that portion, and it was a _huge_ mistake, 
because the performance was _terrible_ - as in it could only process a few 
files in a day kind of terrible. I ultimately had to switch over to another 
language to get it to work (it ended up being Java, but I could have used a 
variety of other languages).

Maybe if I had simply been adding elements to the map, it wouldn't have been 
anywhere near as bad, but since I had to mutate them (and both the map and its 
elments were technically immutable), that become _insanely_ expensive.

So, it's quite possible that you have a use case where using immutable 
containers works really well and isn't a problem, but in what I've dealt with 
personally, I've found it to be a huge performance problem and so am very 
leery of immutable containers.

- Jonathan M Davis