On Sun, Mar 21, 2010 at 6:37 PM, Jarkko Oranen <chous...@gmail.com> wrote: > > Rich has done some work on using the JDK7 ForkJoin Library to > parallelise map and reduce over vectors, since they are already > internally structured as trees. It hasn't been touched in a while, but > as far as I know the code lives in the 'par' branch of the clojure > repository, and works with JDK6 if you install an additional jar.
Thank you. I'll keep an eye on it. Yesterday I looked at the implementation of the PersistentVector class, trying to figure out how to exploit its internal structure to decompose the vector. I hit several issues though: 1. The trees are not balanced. So in order to split the vector roughly in half one would have to deal with the root node _and_ nodes at one level below it. 2. Node structure doesn't have a "cnt" field but PersistentVector does. When splitting the vector, length of each part would have to be calculated, which could be costly. Assuming there are no holes in the tree it might be enough to look at the depth of the tree and the number of fully occupied slices in the root node. 3. Apparently PersistentVector doesn't allow an empty tail array (for lenghts > 0). I.e. tail can have a length of 1 to 32. This would have to be changed (i.e. 0 to 31) if the partitioning is going to work fast. 4. Should partitioning stop once the vector is destructured down to a single chunk (32 values)? Destructuring vectors to single values would be more convenient to use but would only add overhead without any reduction in the access time. 5. With all this we can get subvectors with very fast access times _but_ the destructuring process itself can still trigger a lot of allocation (each subvector needs at least one new node - a root). So I'm not sure whether this would give any net performance gain, perhaps not. Andrzej -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en To unsubscribe from this group, send email to clojure+unsubscribegooglegroups.com or reply to this email with the words "REMOVE ME" as the subject.
