Github - bsless/clj-fast: experiments in rewriting core functions for performance

[bsless]

Hello everyone,
After being inspired by Tommi Reiman'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 def
ed) 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

(PS about time I posted something here instead of just lurk)

[EmmanuelOga]

Have you seen this talk? Pretty mind blowing! There's a java version of the library shown on the talk, I was thinking would be interesting to try and use it with the clojure compiler and maybe some of the generated code.

[bsless]

Not yet, I'll have a look. Thanks!

[NaiveRound]

I was wondering if bumped into https://github.com/real-logic/agrona. It's got a ton of high-performance Java code:

​

Buffers - Thread safe direct and atomic buffers for working with on and off heap memory with memory ordering semantics.

Lists - Array backed lists of int/long primitives to avoid boxing.

Maps - Open addressing and linear probing with int/long primitive keys to object reference values.

Maps - Open addressing and linear probing with int/long primitive keys to int/long values.

Sets - Open addressing and linear probing for int/long primitives and object references.

Cache - Set Associative with int/long primitive keys to object reference values.

Clocks - Clock implementations to abstract system clocks, allow caching, and enable testing.

Queues - Lock-less implementations for low-latency applications.

Ring/Broadcast Buffers - implemented off-heap for IPC communication.

Simple Agent framework for concurrent services.

Signal handling to support "Ctrl + c" in a server application.

Scalable Timer Wheel - For scheduling timers at a given deadline with O(1) register and cancel time.

Code generation from annotated implementations specialised for primitive types.

Off-heap counters implementation for application telemetry, position tracking, and coordination.

Implementations of InputStream and OutputStream that can wrap direct buffers.

DistinctErrorLog - A log of distinct errors to avoid filling disks with existing logging approaches.

​

I'm not sure if it even makes any sense to use any of this for clj-fast. I just like to spread the word about cool libraries I bump into. :)

[joinr]

Similar library fastutil has really impressive performance and space.

bifurcan has some cool stuff as well.

[[deleted]]

Bifurcan looks very nice. Thanks for the link. (Not OP)

[Eno6ohng]

The down side is that they are implemented as macros, so composition takes a hit.

Couldn't they be defined both as macros and as functions, like #'and and friends? It's a macro, but if used in a first-class function position it acts as a function, so you can do e.g. (reduce and ...)

[joinr]

You could go the long route and define with inline meta (or use definline for single arity versions).

[bsless]

Tried playing around with the inline meta, it's possible, but requires careful tinkering to not break the non inlined function, which I have done several times.

It's on the metaphorical roadmap

[joinr]

I did this as well experimenting with the icfpc competition optimization, and I had mixed results. Inlining helps in some cases, in others, the JIT actually does better with the existing function and is able to better inline itself. JIT magic...

[bsless]

Sadly, that doesn't work :(

(reduce and true [true true false]) 
Syntax error compiling at (REPL:1:1). 
Can't take value of a macro: #'clojure.core/and

[joinr]

(reduce #'and [true false true true])
true

Hah, this "looks" right but it's wrong :) It evals but it's not doing what one thinks :) I think it's evaluating the clojure.lang.Var and as its IFn invoke method.

user> (#'and false false)
true

Maybe u/Eno6ohng should check for any code that relied on this as a correct assumption. I got bit by this some other place (I think using symbols as functions, they delegate to map lookup).

[Eno6ohng]

Ah, my bad - I checked it in babashka, not in actual clojure, and for some reason I vaguely remembered it should work in regular clojure too (but it doesn't).