Performance of `select-keys` variants

How does Clojure's select-keys performance compare to alternatives?

Observation: A straightforward, idiomatic implementation with reduce, conj!, and transients offers performance improvements across a wide range of conditions.

Clojure's select-keys is implemented with recursive loop pattern. Let's write six variants that mix-and-match components and compare their performance.

We'll use the Criterium benchmarking facility to objectively measure the evaluation times of a range of conditions. We'll explore two regimes of hashmap sizes: zero to sixteen key/values pairs stepping by ones, and one to one-million key/value pairs stepping by decades. Further, we'll investigate the effects of the different flavors of key sequences (labeled all keys, half keys, and no keys, explained later).

Overall, three variants demonstrated improved performance over Clojure's select-keys. Variant six, labeled as fselect-keys-6, displayed 5–20% improved performance over a wide range of hashmap sizes and fractions of key sequence matches. This implementation is straightforward and maintains idiomatic style. It is provided by see-sharp's core namespace, named fselect-keys.

Let's consider selecting keys from hashmaps where the elements of the key sequence are all present in the hashmap. For example, this hashmap…

{:a 11 :b 22 :c 33 :d 44 :e 55 :f 66}

…fully contains the elements of this key sequence.

[:a :b :c :d :e :f]

If we stack them, we can see the matches.

{:a 11 :b 22 :c 33 :d 44 :e 55 :f 66} ;; hashmap
[:a    :b    :c    :d    :e    :f]    ;; key sequence

The hashmap contains every keyword contained in the key sequence, :a through :f. The output hashmap would be identical to the input hashmap. Though we are using keywords as keys for this illustration, during benchmarking, the keys are integers.

We'll test hashmaps in two size regimes. The first regime is 'large': hashmaps containing one, ten, one-hundred, …up to one-million key-value pairs. The second regime is 'small': hashmaps containing one to sixteen key/value pairs. We will compare the Clojure's select-keys (magenta diamonds) to six alternative implementations.

The upper chart shows that variants 2 (orange diamonds), 4 (green squares), and 6 (gold circles) demonstrate 20-25% speedups across a wide range of hashmap sizes. The lower chart shows that most of the variants perform similarly, with 2, 4, and 6 again performing among the speediest by a small margin.

(fn [n] ((select-keys-tactic) (get-in large-maps [n :map]) (get-in large-maps [n :all-keys])))

(fn [n] ((select-keys-tactic) (get-in small-maps [n :map]) (get-in small-maps [n :all-keys])))

The next two charts involve scenarios where the hashmap contains half of the elements of the key sequence. For example, the following hashmap contains only half the keys of the key sequence.

{:a 11 :b 22 :c 33 :d 44 :e 55 :f 66}          ;; hashmap
[:a          :c          :e          :g :h :i] ;; key sequence

The hashmap contains keywords :a, :c, and :e, but not :b, :d, nor :f. Furthermore, the key sequence contains three keywords that are not in the hashmap. The output hashmap would be half the size of the input hashmap.

Variants 4 (green triangles) and 6 (gold circles) show 15-20% speedups for both large hashmaps (first chart below) and small hashmaps (second chart below).

(fn [n] ((select-keys-tactic) (get-in large-maps [n :map]) (get-in large-maps [n :half-keys])))

(fn [n] ((select-keys-tactic) (get-in small-maps [n :map]) (get-in small-maps [n :half-keys])))

These final two charts show scenarios when none of elements of the key sequence are keys of the hashmap. For example, the following hashmap and key sequence contain zero keys in common.

{:a 11 :b 22 :c 33 :d 44 :e 55 :f 66}                   ;; hashmap
[                                    :g :h :i :j :k :l] ;; key sequence

The hashmap contains keys :a through :f, while the key sequence contains keys :g through :l. In this case, though the select-keys variants must handle all the elements of the key sequence, the output hashmap would be empty.

Variant 6 (gold circles) shows about a 5% speedup over Clojure's built-in select-keys (magenta diamonds) for large hashmaps (first chart) and pretty much matches it performance for small hashmaps (second chart).

(fn [n] ((select-keys-tactic) (get-in large-maps [n :map]) (get-in large-maps [n :none-keys])))

(fn [n] ((select-keys-tactic) (get-in small-maps [n :map]) (get-in small-maps [n :none-keys])))