Clojure

take transducer optimization

Details

  • Type: Enhancement Enhancement
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: Release 1.8
  • Fix Version/s: None
  • Component/s: None
  • Patch:
    Code
  • Approval:
    Triaged

Description

A basic refactoring to remove the let form and only requires a single counter check for each iteration, yields an 25% performance increase. With the patch, 2 checks are only required for the last iteration (in case counter arg was <= 0)...

;; master
(quick-bench (into [] (take 1000) (range 2000)))
WARNING: Final GC required 34.82584189073624 % of runtime
Evaluation count : 13050 in 6 samples of 2175 calls.
             Execution time mean : 46.921254 µs
    Execution time std-deviation : 1.904733 µs
   Execution time lower quantile : 45.124921 µs ( 2.5%)
   Execution time upper quantile : 49.427201 µs (97.5%)
                   Overhead used : 2.367243 ns

;; w/ patch
(quick-bench (into [] (take 1000) (range 2000)))
WARNING: Final GC required 34.74448252054369 % of runtime
Evaluation count : 18102 in 6 samples of 3017 calls.
             Execution time mean : 34.301193 µs
    Execution time std-deviation : 1.714105 µs
   Execution time lower quantile : 32.341349 µs ( 2.5%)
   Execution time upper quantile : 37.046851 µs (97.5%)
                   Overhead used : 2.367243 ns
  1. clj-1804-1.patch
    25/Aug/15 10:35 AM
    2 kB
    Karsten Schmidt
  2. clj-1804-2.patch
    26/Aug/15 6:01 AM
    2 kB
    Karsten Schmidt

Activity

Hide
Karsten Schmidt added a comment -

Proposed patch, passes all existing tests

Show
Karsten Schmidt added a comment - Proposed patch, passes all existing tests
Hide
Alex Miller added a comment -

From a superficial skim, I see checks for pos? and then neg? which both exclude 0 and that gives me doubts about that branch. That may actually be ok but I will have to read it more closely.

Show
Alex Miller added a comment - From a superficial skim, I see checks for pos? and then neg? which both exclude 0 and that gives me doubts about that branch. That may actually be ok but I will have to read it more closely.
Hide
Karsten Schmidt added a comment -

Hi Alex, try running the tests... AFAICT it's all still working as advertised: For (take 0) or (take -1) then the pos? check fails, but we must ensure to not call rf for that iteration. For all other (take n) cases only the pos? check is executed apart from the last iteration (which causes a single superfluous neg? call) The current path/impl always does 2 checks for all iterations and hence is (much) slower.

Show
Karsten Schmidt added a comment - Hi Alex, try running the tests... AFAICT it's all still working as advertised: For (take 0) or (take -1) then the pos? check fails, but we must ensure to not call rf for that iteration. For all other (take n) cases only the pos? check is executed apart from the last iteration (which causes a single superfluous neg? call) The current path/impl always does 2 checks for all iterations and hence is (much) slower.
Hide
Alex Miller added a comment -

The only time that neg? case will be hit is if take is passed n <= 0, so I think this is correct. However, you might consider some different way to handle that particular case - for example, it could be pulled out of the transducer function entirely and be created as a separate transducer function entirely. I'm not sure that's worth doing, but it's an idea.

Show
Alex Miller added a comment - The only time that neg? case will be hit is if take is passed n <= 0, so I think this is correct. However, you might consider some different way to handle that particular case - for example, it could be pulled out of the transducer function entirely and be created as a separate transducer function entirely. I'm not sure that's worth doing, but it's an idea.
Hide
Karsten Schmidt added a comment - - edited

Good idea, Alex! This 2nd patch removes the neg? check and adds a quick bail transducer for cases where n <= 0. It also made it slightly faster still:

(quick-bench (into [] (take 1000) (range 2000)))
Evaluation count : 20370 in 6 samples of 3395 calls.
             Execution time mean : 30.302673 µs

(now ~35% faster than original)

Show
Karsten Schmidt added a comment - - edited Good idea, Alex! This 2nd patch removes the neg? check and adds a quick bail transducer for cases where n <= 0. It also made it slightly faster still:
(quick-bench (into [] (take 1000) (range 2000)))
Evaluation count : 20370 in 6 samples of 3395 calls.
             Execution time mean : 30.302673 µs
(now ~35% faster than original)

People

Vote (0)
Watch (3)

Dates

  • Created:
    Updated: