[Haskell-cafe] Structural sharing in haskell data structures?
jmaessen at alum.mit.edu
Wed May 13 07:43:03 EDT 2009
I wanted to clear up one misconception here...
On May 13, 2009, at 12:19 AM, wren ng thornton wrote:
> In heavily GCed languages like Haskell allocation and collection is
> cheap, so we don't mind too much; but in Java and the like, both
> allocation and collection are expensive so the idea of cheap
> throwaway objects is foreign.
Not true! If you look at the internals of Clojure, you'll discover
they're using trees with *very* wide fanout (eg fanout-64 leaf trees
for lists). Why? Because it's so cheap to allocate and GC these
structures! By using shallow-but-wide trees we reduce the cost of
indexing and accessing list elements. I suspect you'd still be hard-
pressed to support this kind of allocation behavior in any of the
present Haskell implementations, and Haskell implementations of the
same kinds of structures have limited fanout to 2-4 elements or so.
Now, if only the Clojure structures supported efficient concatenation...
> Live well,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe