<< Back to previous view

[CLJ-1010] A left-to-right-variant of `comp` Created: 11/Jun/12  Updated: 08/Sep/14

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Tassilo Horn Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: None

Attachments: Text File 0001-CLJ-1010-Add-a-left-to-right-version-of-comp-comp.patch    
Patch: Code

 Description   

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.



 Comments   
Comment by Tassilo Horn [ 11/Jun/12 5:16 AM ]

Here's an implementation.

Comment by Tassilo Horn [ 11/Jun/12 12:41 PM ]

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

Comment by Tassilo Horn [ 14/Jun/12 2:32 AM ]

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
Comment by Tassilo Horn [ 14/Jun/12 3:40 AM ]

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.

Comment by Andy Fingerhut [ 05/Sep/14 11:45 AM ]

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.

Comment by Tassilo Horn [ 08/Sep/14 4:39 AM ]

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

Generated at Mon Dec 22 14:04:13 CST 2014 using JIRA 4.4#649-r158309.