So, having broken the back of fast re-combination of hash sets and maps, I
wanted to take a look at doing a similar sort of thing for vectors -
another type of seq that I use very heavily in this sort of situation.
Let's see the cake first:
seqspert.vector=> (def a (into [] (range 10000000)))
#'seqspert.vector/a
seqspert.vector=> (time (def b (into a a)))
"Elapsed time: 3695.682654 msecs"
#'seqspert.vector/b
seqspert.vector=> (time (def c (supervec a a)))
"Elapsed time: 0.253922 msecs"
#'seqspert.vector/c
seqspert.vector=> (= b c)
true
As you can see, the usual method of combining two vectors into a third
takes 3-4 secs to combine two 10M entry vectors.
Using 'supervec' it takes MUCH less time.....
How ?
I looked at vector's impl and quickly realised that I would not be able to
use the same trick that I had used for hash set/map. Then I looked at
subvec and realised that I could do a very similar trick to create supervec.
Subvec provides a view on a subseq of a vector that behaves like a full
vector. Supervec provides a similar view that makes two vectors behave like
a single one:
seqspert.vector=> (supervec [1 2 3] [4 5 6])
[1 2 3 4 5 6]
seqspert.vector=> (type (supervec [1 2 3] [4 5 6]))
clojure.lang.APersistentVector$SuperVector
We can use seqspert (see my other posting this evening) to look inside a
SuperVector:
seqspert.vector=> (decloak (supervec [1 2 3] [4 5 6]))
#seqspert.vector.SuperVector{:left #seqspert.vector.Vector{:cnt 3, :shift
5, :root #seqspert.vector.VectorNode{:array [nil nil nil nil nil nil nil
nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil
nil nil nil nil nil nil]}, :tail [1 2 3]}, :right
#seqspert.vector.Vector{:cnt 3, :shift 5, :root
#seqspert.vector.VectorNode{:array [nil nil nil nil nil nil nil nil nil nil
nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil nil
nil nil nil]}, :tail [4 5 6]}, :middle 3, :count 6}
seqspert.vector=> (p/pprint (decloak (supervec [1 2 3] [4 5 6])))
{:left
{:cnt 3,
:shift 5,
:root
{:array
[nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil]},
:tail [1 2 3]},
:right
{:cnt 3,
:shift 5,
:root
{:array
[nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil
nil]},
:tail [4 5 6]},
:middle 3,
:count 6}
nil
seqspert.vector=>
It looks very complicated - that is the two clojurer vectors held inside !
A SuperVector has fields left, right (the two vectors that we are
combining), middle (the length of the left vector), and count (the sum of
the counts of left and right).
With just this info and very little code, I found myself with a working
impl (except 'pop' but who 'pop's a vector?).
OK - there is a tiny extra runtime overhead associated with using a
supervec - but, when you look at what is involved in dereffing into a
vector, this quickly appears insignificant. It's about the same a using a
subvec.
The SuperVector code is checked into my clojure fork on github - see
beginning of this thread. Seqspert is also at github - see the announcement
I posted this evening.
Finally 'supervec' is currently defined as:
(defn supervec [l r] (APersistentVector$SuperVector. {} l r))
I am thinking or renaming 'splice' from my earlier posting to 'combine' and
creating a Combinable interface, to be implemented by any seq type that is
able to do a fast re-combination with another seq of the same type. This
could be leveraged by e.g. 'into' to deliver significant performance
benefits and footprint reduction.
more as and when,
Jules
On Saturday, 15 February 2014 23:06:24 UTC, 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.
