[Haskell-cafe] Structural sharing in haskell data structures?

[Vladimir Ivanov]

Wren,

It's not true for Java either.
The idea of "cheap throw-away objects" isn't foreign for modern JVMs.
GC favors short-lived immutable objects since:
 - all collectors are generational;
 - GC cycle duration is proportional to the size of live objects, not
the heap size;
 - object allocation is _very_ cheap, even in parallel;

Moreover, many advanced techniques are used in JVM GCs:
  - there are parallel & concurrent collectors;
  - adaptive ergonomics (e.g. heap resizing, according to some goals
on collection duration);

There are problems with functional languages on top of JVM, but GC
isn't among them.
If you are interested in current work, you may look at mlvm project [1].

-- vi

[1] http://openjdk.java.net/projects/mlvm/

On Thu, May 14, 2009 at 2:58 AM, wren ng thornton <wren at freegeek.org> wrote:
> Jan-Willem Maessen wrote:
>>
>> I wanted to clear up one misconception here...
>>
>> 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!
>
> I was speaking of Java, not Clojure. I believe the costs in Java are well
> documented, though I don't know enough about the JVM to know where the blame
> belongs. (All I know of Clojure is that it's a Lisp-like on the JVM :)
>
>
>> 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.
>
> I was under the impression that the reason datastructures in Haskell tend to
> be limited to 4-fanout had more to do with the cleanliness of the
> implementations--- pattern matching on 64-wide cells is quite ugly, as is
> dealing with the proliferation of corner cases for complex structures like
> finger trees, patricia trees, etc. The use of view patterns could clean this
> up significantly. On the other hand, we do have things like lazy ByteStrings
> and UVector which do have wide fanouts.
>
> --
> Live well,
> ~wren
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>