take-nth transducer could be faster without rem

Question

The take-nth transducer is calling rem on each index, which is relatively expensive compared to a zero? test. It could just count down from N instead as the step size is fixed.

Answer 1

Comment made by: steveminer@gmail.com

Patch attached. It's about 25% faster on a simple test like:

(time (transduce (take-nth 13) + (range 1e7)))

Answer 2

Comment made by: steveminer@gmail.com

I didn't worry about (take-nth 0) case, but my patch does give a different result. The current implementation gets a divide by zero error (from rem). My patched version returns just the first element once. The regular collection version returns an infinite sequence of the first element. I doubt anyone expects a sensible answer from the 0 case so I didn't try to do anything special with it.

Answer 3

Comment made by: michaelblume

Nice =)

I would say that the transducer version really ought to match the collection version as closely as possible, but I don't think there's actually a way to write a transducer that transforms a finite sequence into an infinite sequence, so no luck there.

Maybe while we're at it we should change both the transducer and the collection arities to throw on zero?

Answer 4

_Comment made by: reborg_

GIGO case, but rem is also responsible for:


user=> (take-nth 2.5 (range 10))
(0 3 6 9)
user=> (sequence (take-nth 2.5) (range 10))
(0 5)


The patch by Steve (CLJ-1665-faster-take-nth-transducer-without-rem.patch) is just missing a cast to int to solve the above:


(defn take-nth [n]
  (fn [rf]
    (let [n (int n)
          iv (volatile! 1)]
      (fn
        ([] (rf))
        ([result] (rf result))
        ([result input]
         (let [i (vswap! iv dec)]
           (if (zero? i)
             (do (vreset! iv n)
                 (rf result input))
             result)))))))

Answer 5

Reference: https://clojure.atlassian.net/browse/CLJ-1665 (reported by steveminer@gmail.com)