take transducer optimization

Question

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

Answer 1

Comment made by: toxi

Proposed patch, passes all existing tests

Answer 2

Comment made by: alexmiller

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.

Answer 3

Comment made by: toxi

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.

Answer 4

Comment made by: alexmiller

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.

Answer 5

_Comment made by: toxi_

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)

Answer 6

Reference: https://clojure.atlassian.net/browse/CLJ-1804 (reported by toxi)