chunked.clj

; there are some obvious micro optimizations, I left them out for clarity
; the relative ordering of read and writes with volatile and plain array should be thread-safe (if not, point it out)

; @wagjo asked "Have you found use for such concept? Must be pretty slow compared to unchunked one"
; The idea came out of a discussion on transducers so not used for real, yet.
; Once you optimize it (remove the boxing induced by the volatile, switch to unchecked math) there should not be much
; of an overhead.
; When you have one big composed reducing fn (eg several mapping stages) then each item is going to be processed in 
; each stage, each stage of the mapping may evict from the data cache stuff used by previous stages. So you have cache
; misses for each item.
; By chunking the processing, a batch of items is going to be processed by a single stage before being passed to
; the next stage, so it reduces cross-stage cache trashing.
; Furthermore smaller "loop" bodies may be more JIT-friendly.
; Theoritically instruction cache trashing may also be an issue with big fns. In practice it's rare to have I$ trashing
; whithout D$ trashing.

(defn chunked
  ([] (chunked 32))
  ([n]
    (fn [f1]
      (let [xs (object-array n)
            nv (volatile! 0)
            flush (fn [acc]
                    (loop [i 0 acc acc]
                      (if (< i @nv) ; read of the volatile BEFORE read of the array
                        (let [acc (f1 acc (aget xs i))]
                          (if (reduced? acc)
                            acc
                            (recur (inc i) acc)))
                        acc)))]
        (fn 
          ([] (f1))
          ([acc] (f1 (flush acc)))
          ([acc x]
            (if (< @nv n)
              (do
                (aset xs @nv x)
                (vswap! nv inc) ; write of the volatile AFTER write of the array
                acc)
              (let [acc (flush acc)]
                (vreset! nv 0)
                acc))))))))