Exploring merge performance in a reducing situation

We'll consider three reduction functions.

• reduce-kv, the single-threaded baseline.
• fold, off-the-shelf multi-threaded reducing function.
• transduce-kv, a third-party, multi-threaded -kv variant of Clojure's transduce.

Execution times increase with vector length as we should expect. For all sizes of hashmaps, single-threaded reduce (gold diamonds) provides the fastest performance. In fact, the multi-threaded reducing functions, whose only purpose is to reduce faster, require four to ten times as long to generate the output hashmaps.

(fn [n] ((tactics (project-version-lein)) n))

Show details

To put the merging performance penalty into context, we'll look at two similar reductions that do not involve merge-ing hashmaps.

Combining with addition.

The upper of the two following charts (and showable table) compares the evaluation times of summing the numbers within vectors. This task consumes a collection, but does not build up an output collection, merely a running total: a single number. The multi-threaded fold and transduce aren't hobbled by having to combine the built-up collections created by the partitioning.

The task performed is something like this.

(reduce (fn [acc x] (+ acc (lots-of-math x))) 0 [1.23 2.34 3.45...])

lots-of-math being eighteen different arithmetic operations involving logarithms, trig functions, etc., that ought to resist optimization by the JVM.

For vectors containing less than one-thousand elements, performance is nearly identical, as expected. The multi-threaded reducing functions do not partition when the input collection contains fewer than 512 elements. In the middle regime, around one-thousand elements, single-threaded reduce performs somewhat faster because of the overhead imposed by the threading and partitioning machinery. Once the vectors contain ten-thousand elements or more, that overhead starts to pay off as the multi-threaded reducing functions perform about three times as fast as the single-threaded reduce.

Keep in mind that this task involves partitioning the input collection, but the combine phase is mere addition (i.e., computationally cheap).

Combining with concatenation.

The lower chart compares the evaluation times of computing eighteen arithmetic values per vector element, building up a new output vector with the results. Something like this.

                     v----------------------------v
(reduce (fn [acc x] (conj acc (lots-of-math x))) [] [1.23 2.34 3.45...])

Notice that instead of merely summing the lots-of-math result with an accumulating number, we are conjoining onto an ever-growing output collection, a vector. In principle, building an output collection should be a more costly operation.

In contrast to the previous subsection that involved basic summation, building up that output vector requires more involved machinery. The multi-threaded reducing variants, fold and transduce, must partition the input vector, manage a thread pool, distribute and collect the results from the partitions, then finally re-assemble the sub-collections into a single final collection.

Compared to the upper chart which showed a three times speedup over single-threaded reduce, the multi-threaded variants only showed about a two times speedup. We might attribute this decrease in speedup to the necessity to assemble an output collection. In this case with vectors, we are assembling with concat.

(fn [n] ((plus-tactics (project-version-lein)) n))

Show details

(fn [n] ((vtactics (project-version-lein)) n))

Show details