A left-to-right-variant of `comp`

Question

The function composition function comp is quite inefficient in cases like (apply comp large-seq-of-fns), because its arity-greater-than-3 version reverses the seq.

I would be great if there was an alternative comp** (or whatever) function which is just like comp but composes left-to-right.

Answer 1

Comment made by: tsdh

Here's an implementation.

Answer 2

Comment made by: tsdh

There's something strange with my patch. The creation of a composition of a huge seq of functions is much faster with comp** than with comp, which is expected, because the seq doesn't need to be reversed.

The strange thing however is that the compositions created with comp evaluate about 10-20% faster than those created with comp** although the arbitrary-arity version of comp is defined in terms of comp**: (apply comp* (reverse (list* f1 f2 f3 fs))).

For some benchmarking details, see: https://groups.google.com/d/msg/clojure/MizwTxHwLE4/hGLrMfetlP8J

Answer 3

_Comment made by: tsdh_

Here's some benchmark:


user> (use 'criterium.core)
nil
user> (let [coll (doall (take 1000000 (repeat inc)))
       f1 (apply comp* coll)
       f2 (apply comp coll)]
       (bench (f1 0) :verbose)
       (println "---------------------------------------")
       (bench (f2 0) :verbose))
amd64 Linux 3.4.2-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count             : 600
             Execution time mean : 112.324465 ms  95.0% CI: (112.247218 ms, 112.380682 ms)
    Execution time std-deviation : 6.513809 ms  95.0% CI: (6.477450 ms, 6.553029 ms)
         Execution time lower ci : 105.609401 ms  95.0% CI: (105.609401 ms, 105.622918 ms)
         Execution time upper ci : 122.353763 ms  95.0% CI: (122.353763 ms, 122.405315 ms)
---------------------------------------
amd64 Linux 3.4.2-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count             : 1440
             Execution time mean : 43.519663 ms  95.0% CI: (43.516732 ms, 43.524062 ms)
    Execution time std-deviation : 492.299089 us  95.0% CI: (490.829889 us, 494.198137 us)
         Execution time lower ci : 42.781398 ms  95.0% CI: (42.781398 ms, 42.781398 ms)
         Execution time upper ci : 44.157311 ms  95.0% CI: (44.157311 ms, 44.158513 ms)
nil

Answer 4

Comment made by: tsdh

Ok, I've tracked down the performance difference. This comes from the fact that reverse creates a clojure.lang.PersistentList which can be iterated much faster than a (fully realized) LazySeq. If you provide your fncoll in (apply comp* fncoll) as vector or list, the application of the created composition is as fast as for comp.

So for me, the patch is good and makes sense.

Answer 5

Comment made by: jafingerhut

Patch 0001-CLJ-1010-Add-a-left-to-right-version-of-comp-comp.patch dated Jun 11 2012 no longer applies cleanly to latest master after some commits were made to Clojure on or near Sep 5 2014.

I have not checked whether this patch is straightforward to update. See the section "Updating stale patches" at http://dev.clojure.org/display/community/Developing Patches for suggestions on how to update patches.

Answer 6

Comment made by: tsdh

Here is an updated patch which applies to the git master as of 2014-09-08.

Answer 7

Reference: https://clojure.atlassian.net/browse/CLJ-1010 (reported by tsdh)