Does D have "structural sharing" of immutable collections?
Jonathan M Davis
jmdavisProg at gmx.com
Wed May 23 14:11:54 PDT 2012
On Wednesday, May 23, 2012 20:51:31 Roman D. Boiko wrote:
> On Wednesday, 23 May 2012 at 18:39:02 UTC, Stewart Gordon wrote:
> > On 23/05/2012 16:05, Roman D. Boiko wrote:
> > <snip>
> >
> >> I need some immutable collections for my D Compiler Tools
> >> project, namely linked list,
> >> red-black tree, and possibly some others.
> >
> > <snip>
> >
> > What's the point of an immutable red-black tree?
> >
> > The whole point of a red-black tree is to facilitate fast
> > dynamic addition, removal and lookup of elements.
> >
> > When the tree is immutable, only lookup speed is of any real
> > relevance, so you might as well create a perfectly balanced
> > binary tree. Or even better, an array.
> >
> > Stewart.
>
> Immutable collections in most cases have the same performance
> characteristics as mutable ones. Space consumption may be higher,
> but not necessarily.
>
> Instead of mutating a collection, a new one is returned each time
> you add or remove an element. It shares most nodes with a
> previous one.
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
More information about the Digitalmars-d
mailing list