Try reducers

[miner]

I found that reducers can be pretty fast with large collections. You could try something like this. I pulled the predicate out as an argument. It would probably make sense to try some slow predicates as well to see how much time is overhead.

(require '[clojure.core.reducers :as r])

(defn tally-by [pred xs]
  (let [total (count xs)
        cnt (r/fold + (r/map (fn [_] 1) (r/filter pred xs)))]
    [cnt (- total cnt)]))

 (quick-bench (tally-by odd? xs))

[rauhs]

I have just tried it out. Seems to be a little bit quicker (like 25%).