Fork me on GitHub
#clojure-dev
<
2020-11-13
>
Ben Sless18:11:42

Out of curiosity I poked around clojure.walk/walk and it looks like its performance can be improved, with one change requiring almost no care, and another plenty of care: The quick win is changing the coll? case to use a transducer:

(coll? form) (outer (into (empty form) (map inner form)))
   (coll? form) (outer (into (empty form) (map inner) form))
Another more elaborate change which will require lots of care is replacing the entire cond with a protocol then extending that protocol to all of Clojure's collections. I ran a few benchmarks and it seems like most of the gain is from switching to a transducer. Should I post it on ask.clojure?

noisesmith18:11:18

that would reverse lists

noisesmith18:11:29

which I don't think any consumer of walk actually wants

Ben Sless18:11:37

lists are covered by

(list? form) (outer (apply list (map inner form)))

noisesmith18:11:11

I see now, it was already using into / empty

Alex Miller (Clojure team)18:11:45

you can post it on ask, please make sure to include the tests you're using

šŸ‘ 3
Ben Sless18:11:10

The performance difference is very noticeable with maps and vectors. The protocol saves about 5% from that (give or take)

Alex Miller (Clojure team)18:11:40

in general, a single transducer is not necessarily faster and can even be slower vs chunked seqs for small seqs.

Ben Sless18:11:25

Won't chunked seqs be caught before the coll? case in

(seq? form) (outer (doall (map inner form)))

noisesmith18:11:05

(map f [...]) operates on a chunked seq of the vector

Alex Miller (Clojure team)18:11:17

sorry, not looking at the code, just talking generally of things to consider

Alex Miller (Clojure team)18:11:32

the next step of analysis is to get a sense of what people use walk for and a rough frequency of that

Alex Miller (Clojure team)18:11:04

basically toward answering the question of whether this change is usually a win

Ben Sless18:11:03

Alright. I'll organize the results and post everything on ask

Ben Sless07:11:09

Done, I think another patch for https://clojure.atlassian.net/browse/CLJ-1239 would be nice

Ben Sless19:11:12

Asked https://ask.clojure.org/index.php/9801/clojure-walk-walk-can-use-transducers Looks like protocols won't give any performance gains there, focused only on transducers

Ben Sless19:11:02

Had a typo in the implementation, let me rerun the tests

borkdude20:11:21

@ben.sless How do you explain speedups with protocols? How can they be faster than instance checks?

borkdude20:11:51

(btw, I haven't read through the benchmarks)

borkdude20:11:34

A summary of the benchmark would help, it's a bit difficult to read imo. I don't see significant differences?

Ben Sless20:11:28

1. The speedup with protocols isn't dramatic 2. They may be faster in a REPL environment but won't be in a direct-linked AOTed jar 3. It isn't just one instance check. To get to coll? you need 5 instance checks and non-taken branches. In a heterogeneous collection does that mean branch prediction goes out the window?

Alex Miller (Clojure team)20:11:44

protocols cache at the call-site

Alex Miller (Clojure team)20:11:38

I think there is actually an existing ticket about clojure.walk and protocols btw

Ben Sless20:11:05

A summary of the benchmarks: tested a few use cases: ā€¢ (1 2 [3 4 5] {:a 6 7 8} [9 [10]] #{:b 7}) a heterogeneous collection ā€¢ (defn walk* ,,,) a big collection with lots of lists and symbols ā€¢ {1 {2 {3 {4 {5 {6 {7 {8 {9 {10 11}}}}}}}}}} a deeply nested map ā€¢ [1 [2 [3 [4 [5 [6 [7 [8 [9 [10 11]]]]]]]]]] a deeply nested vector

souenzzo01:11:27

@ben.sless if you need a "walk but fast and impl via protocols" take a look at #specter

Ben Sless08:11:25

Now that I have a new patch prepared, do I just upload it to the ticket and comment, or is any other action required? Already made sure to follow the https://clojure.org/dev/developing_patches and run tests.

Alex Miller (Clojure team)14:11:07

Upload and comment is great

Ben Sless15:11:30

thanks, will do

Ben Sless16:11:09

Done, thanks Alex šŸ™‚

Alex Miller (Clojure team)20:11:15

prob predates transducers though

Ben Sless20:11:31

speaking of transducers, core.set is full into which predates the transducers API.

Ben Sless08:11:25

Now that I have a new patch prepared, do I just upload it to the ticket and comment, or is any other action required? Already made sure to follow the https://clojure.org/dev/developing_patches and run tests.