+1 for this approach - I've wanted something like this several times.
It's only an "optimisation", but it's a very useful one. Same technique can
probably be used to accelerate "merge" significantly which is a pretty
common operation when you are building map-like structures.
On Sunday, 16 February 2014 07:06:24 UTC+8, Jules wrote:
>
> Guys,
>
> I've been playing with reducers on and off for a while but have been
> frustrated because they don't seem to fit a particular usecase that I have
> in mind... specifically: getting as many associations into a hash-map as as
> I can in as short a time as possible.
>
> My understanding of the reason for this is that reducers practice a divide
> and conquer strategy. The incoming sequence is divided up. Each
> sub-sequence is reduced into a sub-result (possibly in parallel) and then
> the sub-results are combined into the the final outgoing result.
>
> Unfortunately, there does not seem to be a better way of combining two
> hash-maps other than to read each entry from one and create a new
> corresponding association in the other. This means that each recombination
> in the above process essentially repeats most of the work already performed
> in the previous reduction stage.
>
> Hash-sets are implemented via hash-maps, and simpler with which to
> demonstrate this problem:
>
> user=> (def a (doall (range 10000000)))
> #'user/a
> user=> (def b (doall (range 5000000 15000000)))
> #'user/b
> user=> (time (def c (into #{} a)))
> "Elapsed time: 6319.392669 msecs"
> #'user/c
> user=> (time (def d (into #{} b)))
> "Elapsed time: 5389.805233 msecs"
> #'user/d
> user=> (time (def e (into c d)))
> "Elapsed time: 8486.032191 msecs"
> #'user/e
>
>
> In the example above, you can see that the reduction into hash-sets of two
> overlapping lists of 10,000,000 elements takes 6.3 and 5.4 seconds. This
> stage can be carried out in parallel i.e. time elapsed for this stage would
> be 6.3 seconds - but we now have two hash-sets and we want one, so we have
> to combine them.
>
>
> user=> (time (def e (into c d)))
> "Elapsed time: 8486.032191 msecs"
> #'user/e
>
> As you can see, all the advantages of splitting the original sequence into
> 2 and processing the two halves in parallel are lost since the
> recombination or their results takes 8.5 seconds - more than we saved by
> doing the reduction in parallel.
>
> So, what can we do about it ?
>
> I had a look at the code for PersistentHashMap (PersistentHashSet uses
> PersistantHashMap internally). I realised that it was possible to "splice"
> together the internal structure of two hash maps into a single one without
> repeating most of the work required to build one from scratch. So, I had a
> go at implementing it:
>
>
> user=> (time (def f (clojure.lang.PersistentHashSet/splice c d)))
> "Elapsed time: 3052.690911 msecs"
> #'user/f
>
> and:
>
> user=> (= e f)
> true
>
> Whilst this is still adding 3 seconds to our time, that 3 seconds is half
> the time that we would have added had we executed the second reduction in
> serial, rather than in parallel.
>
> This means that we can now reduce large datasets into sets/maps more
> quickly in parallel than we can in serial :-) As an added benefit, because
> splice reuses as much of the internal structure of both inputs as possible,
> it's impact in terms of heap consumption and churn is less - although I
> think that a full implementation might add some Java-side code complexity.
>
> If you would like to give 'splice' a try out, you will need to clone my
> fork of clojure at github
>
> https://github.com/JulesGosnell/clojure
>
> Please let me know if you try out the code. I would be interested to hear
> if people think it is worth pursuing.
>
> I was also thinking that it should be possible to use a similar trick to
> quickly and cheaply split a map/set into [roughly] equal sized pieces
> (assuming an good hash distribution). This would enable the use of a
> map/set as an input sequence into the parallel reduction process outlined
> above. Currently, I believe that only a vector can be used in this way. It
> would be harder to arrange that 'count' could be implemented efficiently on
> these sub-maps/sets, but this is not important for the reduction process.
>
> BTW - benchmarks were run on a 3.2ghz Phenom II / clojure/master /
> openjdk-1.7.0_51 / Fedora 20 with min and max 4gb ram.
>
> regards,
>
>
>
> Jules
>
>
>
--
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
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to clojure+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
