For this first blog post, we’ll demonstrate the use of transducers to compute frequencies, show how we can improve performance by using xforms, and work around some issues regarding error handling. If you have no idea what transducers are, you should really start on their official page, play with them a little, and maybe watch some of the great talks dedicated to them, for example this introduction or the explanation of their inner working by Rich Hickey. You good? Alright let’s roll.
The other day, Cognitect released some new datomic videos. At the beginning of the part 4 (query and pull), Stuart Halloway shows a rad example of using transducers to efficiently process a batch of datoms packed in chunks.
The transduction calculates a frequency map of the attributes (:a) of the datoms for each chunk, then incrementally adds those frequency maps to get the frequencies for the entire batch. Pretty cool indeed!
Something struck me in that code though, do we really need to make those intermediary frequency calculations? I’ve tried to wrap my head around the xforms library by Christophe Grand lately. Seems like I have found the perfect pretext to try it out!
But first, let’s measure the performance characteristics of the original code. I have made a few simplifications from the code above. I use the vanilla (i.e clojure.core) version of transduce, not the one from core.async, and to check if we have an error here, we simply check if a chunk has an :error key .
Let’s build some chunks to try it out:
I used a batch of 10 chunks, each containing 999 “datoms”. Here the datoms are simply maps with a single :a key associated with the value 0, 1 or 2 (so a chunk is an alternating sequence that looks like this: ... {:a 0}, {:a 1}, {:a 2}, {:a 0} {:a 1} ...). Each intermediary frequency maps built during the transduction will be {0 333, 1 333, 2 333} , and the final result of the transformation should be {0 3330, 1 3330, 2 3330}.
(If you want to play with it yourself, the code that inspired this post is here: https://github.com/chpill/transducers-deep-dive/, there is a fair bit of noise but you should easily find the parts discussed here). Okay, we now have our point of comparison. Let’s rewrite the transformation using xforms:
The main difference with the original implementation is that we no longer have intermediary calculations. The cat transducer unpacks the chunks into a stream of maps that is then consumed by the (x/by-key :a x/count) transducer.
If you really want to understand what is going on with x/by-key, you should check out this page of xforms’ wiki. In our particular case, x/by-key calls :a on the maps, and for each distinct value it sees, it spawns a new transduction context in which it applies the x/count transducer. So basically, it counts the number of occurrences of each distinct value returned by :a. When x/by-key has consumed the whole batch (that is to say, its input is reduced), it terminates the spawned transduction contexts and start passing downstream the pairs of [distinct value, number of occurrences]. If you look at the inner working of into, you will see that it adds conj as a final step for the transduction. So the pairs produced by x/by-key are incrementally added to our destination empty hash-map {}, producing the frequency map!
If you just read the wiki page, that last paragraph, and still have no idea what is going on, it’s okay. Take your time, it sure took me quite a while grasp… Try to play with it a bit to get a feel of what x/by-key does. For example, consider that (x/by-key :a x/count) achieves the same as (comp (map :a) (x/by-key identity x/count)).
I find that the computation is pretty clean expressed that way, and because it does the frequency calculation in one pass, it is also a good deal faster than the original version. Sadly, there is something I must confess to you now… It does not work when there are errors!
Let’s try a very small batch of chunks with an error at the end:
In the original version, the transduction is interrupted by (halt-when error?) and the value that triggered the interruption is returned, as expected. But in the custom version, we get a very strange error…
Digging in the stack-trace, we quickly pinpoint the problem in the implementation of the into function:
{} being a proper clojure.lang.IEditableCollection, into will try to optimize the construction of the resulting hash-map by making a transient version of it. It then makes conj! the final step of the transduction, and when the transduction finally returns, it casts that transient hash-map back into a persistent one using persistent!.
At first, I was like “is into broken? what is going on?”, but I quickly realized that the real culprit was the new halt-when transducer (freshly baked into the 1.9-alpha versions of clojure!). If you’ve followed this far, I think I do not need to remind you that transducers are all about decoupling transformation from input and output. Well, except for halt-when. When it encounters a value that matches its predicate, not only does it interrupts the transduction, it also sidetracks every transducers downstream of it and returns the value that it matched (in our case, the whole (transduce xform conj! (transient {}) chunks) returns {:error "Something terrible happened!"} instead of the transient expected…). It is a transduction escape hatch.
Because of this, when composing a transducer using halt-when, be very aware that you are now coupling your transducer to its context! This does not play well with many application of transducers like our trusty into.
To fix our “interruptible” transformation, Let’s use transduce directly:
That works… But I’m not quite happy about giving up on the transient here. For example in the case where there a lot of distinct :a values, transient would make the construction of the result noticeably lighter.
In the end, I tried using the x/into transducer, cousin of the clojure.core/into you know and love. The idea is that it will take care of using transients inside the transduction (considering we cannot rely on anything outside of our transducers because of halt-when…).
It seems that even with only 3 distinct values in our final frequency map, this implementation still managed to squeeze a bit more performance out of our transformation.
But I feel kind of uneasy about this last implementation. I had to introduce a kind of hacky transducer to extract the value out of the transduction. Christophe Grand did a great talk at ClojureD about one month ago, where he describes the dangers of writing your own transducers . The video is not yet out there but you can read the slides here. Seems like writing your own transducers is a bit like walking into a minefield! I you have a better solution to my particular problem, please let me know on twitter or r/clojure!
To conclude, I think transducers can definitely be mind-bending at times, but they are really great, and not only for their performance. As Stuart Halloway puts it in another talk, they make “commonality more evident”: as you decouple the transformation from its input and output sources (think about separating the “T” in “ETL”), some simplifications and occasions for reuse will be made obvious. I would argue the xforms library bring these benefits to an even greater level, as it allows you to express even more transformations as transducers. Oh, and, yeah, watch out for halt-when!
