Arraymap and hashmap merging benchmarks

2-layer merging
Merge tactics for large hashmaps
Merge tactics for small arraymaps/hashmaps
Merge-with addition tactics for large hashmaps
Merge-with addition tactics for small hashmaps
Merge-with extended arithmetic tactics for large hashmaps
Merge-with extended arithmetic tactics for small hashmaps

Can two hashmaps be merged faster than Clojure's core merge and merge-with?

Observations: Clojure's merge is difficult to beat for hashmaps containing up to 100 key/value pairs. For larger hashmaps, custom implementations using reduce-kv and transients offer 30-40% shorter evaluation times.

clojure.core/merge ultimately delegates to conj buried within a first/next recursive implementation. Also, merge carries with it the variadic machinery to handle more than two hashmaps, some of which could be nil. This is an elegant, general implementation, but perhaps not as efficient as could be if we're in a situation where we know we'll always have exactly two non-nil hashmaps. One example of such a situation is building up an output hashmap in a multi-threaded transducing process.

We can mix and match tactics involving transients, transducers, etc., to see if we can harvest any noticeable performance improvement. So let's run some benchmarks to see if any particular tactic performs objectively faster than the others. Benchmarks are defined here. We'll run benchmarks varying

• Underlying implementation functions (i.e., different compositions of conj, into, transient, etc.).
• Size of the input hashmaps (0 to 16 key/value pairs, and 1 to 1 million key/value pairs).
• merge-with functions (basic addition versus an extended series of arithmetic operations).

In every measurement, the pair of hashmaps to be merged share half their keys, so the final output hashmap contains one-third elements from the left input hashmap, and one-third elements uniquely from the right hashmap, and one-third elements from the right hashmap that 'overwrote' the left's because they shared keys.

As always with JVM benchmarks, don't stare too long at any one data point. Just get a sense for overall trends and the relative magnitudes. Single-digit percentage differences probably aren't significant.

Overall, we make three broad observations.

• For merging smallish hashmaps, Clojure's core merge is difficult to beat. We see the best improvement using transduce and conj, giving 7-14% shorter completion times.

• For merging larger hashmaps, we obtain 30-50% shorter times with a straightforward implementation using reduce-kv and transients.

• No custom implementation beats merge-with for small hashmaps.

• A custom implementation of merge-with using reduce-kv offers 10-20% shorter times.

• A two-layer merge using reduce-kv outperforms the community's deep-merge by 35-50%.

Within the limits of these benchmarks, it does appear that we can write a trio of hashmap merging utilities that complete their tasks in noticeably shorter times. The Smoosh library provides that trio as a dependency.

These benchmarks measure the performance of deep merge variants: functions that combine two hashmaps with descendant hashmaps associated to their top-level keys. These particular tests involve merging only two layers deep, although most implementations would operate to an arbitrary depth. Clojure does not provide a deep-merge function, but CLJ-1468 (gold diamonds), a long-standing, un-accepted proposed implementation, serves as a handy baseline. We also tested several third-party variants.

A straightforward implementation using reduce-kv and transients, named merge-merge below, performed the best (i.e., shortest times), being nearly twice as fast as the baseline deep-merge, particularly for large hashmaps containing one-million elements.

Note: Logarithmic axes.

(fn [n] ((two-layer-merge-tactic) ((map-of-maps n) :left) ((map-of-maps n) :right)))

Show details

Using the same cohort of merge tactics as the small hashmaps benchmarks, we tested input hashmaps ranging up to one-million key/value pairs. In general, we see that larger hashmaps require longer to merge. Most tactics perform similarly up to one-hundred key/value pairs. For inputs larger than that, a handful of alternative implementations notably beat Clojure's merge. In broad strokes, merge functions built with reduce-kv along with transients can provide nearly a 50% reduction in evaluation time.

Note that the log-log axes may visually diminish the differences. Tap the 'Show details' button to see the recorded data, particularly the rightmost column displaying the evaluation times for merging a pair of one-million element hashmaps.

(fn [n] ((merge-tactic) ((large-maps n) :left) ((large-maps n) :right)))

Show details

We'll consider twelve merging tactics, some pulled in from third-party libraries. There's nothing terribly special about any particular implementation. They're each just a different riff on combining standard Clojure functions (reduce, conj, assoc, etc.) in different ways.

We see that execution times are very weakly correlated with input hashmap size up to sixteen elements. We can also see a small bump around five key/value pairs, where the final output requires promoting an arraymap to a hashmap. Clojure's core merge (gold diamonds) performed about the middle of the pack. A handful of implementations are able to perform mildly better (i.e., lower times by <10%).

(fn [n] ((merge-tactic) ((small-maps n) :left) ((small-maps n) :right)))

Show details

These benchmarks extend the merging-with tests to hashmaps up to one-million elements. Unlike with the smaller hashmaps, where the results are fairly indistinguishable, the merge-with variants perform noticeably different with larger hashmaps.

For example, the implementation using reduce-kv (green triangles) offers 10-20% shorter evaluation times, with the improvement increasing as the inputs grow larger.

(fn [n] ((merge-with-tactic) + ((large-maps n) :left) ((large-maps n) :right)))

Show details

These benchmarks measure merging small hashmaps (sixteen elements or fewer) using merge-with behavior, simple addition. Clojure's implementation is pretty much the fastest, but all variants cluster within a few percent. But see what happens when the hashmaps are larger.

(fn [n] ((merge-with-tactic) + ((small-maps n) :left) ((small-maps n) :right)))

Show details

These are the same benchmarks, merging with eighteen mathematical operations, but with hashmaps containing up to one-million elements. As with the simple addition tests, the implementation using reduce-kv offers 10-20% performance improvement (i.e., lower times) compared Clojure's built-in merge-with. The performance improvement increases as the inputs grow larger.

(fn [n] ((merge-with-tactic) extended ((large-maps n) :left) ((large-maps n) :right)))

Show details

These benchmarks explore the performance implications of more expensive value combining. Similar to the earlier ones, but instead of a single addition operation, the values are merged with a series of eighteen mathematical operations, such as cosine, natural logarithm, etc.

As before, Clojure's core merge-with is among the best performers, but all variants perform similarly in absolute terms.

(fn [n] ((merge-with-tactic) extended ((small-maps n) :left) ((small-maps n) :right)))

Show details