Performance of `select-keys` variants

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])))

Show details

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

Show details

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])))

Show details

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

Show details

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])))

Show details

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

Show details