Clojure

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

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • 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.

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Tassilo Horn added a comment -

Here's an implementation.

Show
Tassilo Horn added a comment - Here's an implementation.
Hide
Permalink
Tassilo Horn added a comment -

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

Show
Tassilo Horn added a comment - 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
Hide
Permalink
Tassilo Horn added a comment -

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
Show
Tassilo Horn added a comment - 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
Hide
Permalink
Tassilo Horn added a comment - - edited

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.

Show
Tassilo Horn added a comment - - edited 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.

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated:
Atlassian JIRA (v4.4#649-r158309) | Report a problem
Powered by a free Atlassian JIRA open source license for Clojure. Try JIRA - bug tracking software for your team.