Clj-fast: experiments in rewriting core functions for performance

Showcase Your Projects and Libraries
1

Hello everyone,
After being inspired by @ikitommi’s talk about performance I decided to pick up the glove and see if some core functions could be rewritten better performance.
The TL;DR is yes, with some caveats, with significant speedups.

The meat of things:
Plenty of core functions walk sequences, but if these sequences are known in advance (on call site or defed) the walk can be expanded to other functions, giving better performance.
The functions I tackled and their respective speedups:

  • get-in: 4-8x speedup (depending on depth)
  • assoc-in: ~2x speedup
  • select-keys: ~8x speedup
  • update-in: some speedup, but still needs refinement

There are some other implementations but the speedups gained by them are less significant.

The down side is that they are implemented as macros, so composition takes a hit. Also, there’s slight deviation from core function’s behavior, for example select keys will add nils if the keys don’t exist.

The repo also serves as an educational resource, and contains benchmarks of different ways to get keys from records and maps, shedding some light on their performance characteristics, and a few profiling scenarios to characterize these tests.

I also attempted to make these benchmarks reproducible by anyone who clones the repo.

Looks like there are similar efforts tackling this issue from another direction as well: https://github.com/joinr/structural/

In the future:

  • There’s more work to be done with merge and memoize
  • Provide functions which invoke the underlying data structure’s methods wherever possible
  • Dispatch based on type hints?

Check it out here: https://github.com/bsless/clj-fast
Results: https://github.com/bsless/clj-fast/blob/master/doc/results.md

Cheers,
Ben

5 Likes
2

Those fast-assoc and fast-map-merge are not nil-tolerant :thinking:

1 Like
3 
(defn fast-assoc
  [a k v]
  (let [a (or a {})]
    (.assoc ^clojure.lang.Associative a k v)))

(defn fast-map-merge
  [x y]
  (reduce-kv fast-assoc (or x {}) y))
1 Like
4

I’ll bench it and see how it affects performance. thanks!

5

Interesting that this fast-assoc is not compatible with the result of fast-map :slight_smile:

1 Like
6

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.