wren: > 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. >
Yes, agreed. This is the first I've heard of a penalty for fan out. More details please! -- Don _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe