README.md

Benchmark of first vs first'

We benchmarked the performance of the following two functions for various sequence types (and some other collection types):

• (first (filter <pred> <coll>))
• (first' (filter <pred>) <coll>) where first' is defined as follows:

  (defn first' [xform coll]
    (transduce xform (completing (fn [_ x] (reduced x))) nil coll))

The benchmark code used is here.

As a result, we confirmed that first' makes linear search several times more efficient for many collection types. The following chart shows the elapsed time ratio of first to first':

The following are the detailed figures.

range

size	10	20	50	100	200	500	1000	2000	5000	10000
first	1.69e-07	2.62e-07	5.31e-07	1.09e-06	1.76e-06	4.01e-06	8.04e-06	1.59e-05	3.94e-05	7.84e-05
first'	3.88e-08	6.71e-08	1.50e-07	2.85e-07	6.69e-07	1.68e-06	3.24e-06	6.53e-06	1.58e-05	3.12e-05
first / first'	4.36	3.90	3.55	3.82	2.63	2.38	2.48	2.43	2.49	2.51

iterate

size	10	20	50	100	200	500	1000	2000	5000	10000
first	3.89e-07	7.28e-07	2.06e-06	4.05e-06	7.93e-06	1.96e-05	3.90e-05	7.83e-05	1.95e-04	3.95e-04
first'	9.55e-08	1.98e-07	4.10e-07	7.75e-07	1.67e-06	4.10e-06	8.22e-06	1.56e-05	3.66e-05	6.91e-05
first / first'	4.07	3.68	5.01	5.23	4.74	4.79	4.75	5.02	5.34	5.71

vector

size	10	20	50	100	200	500	1000	2000	5000	10000
first	1.59e-07	2.86e-07	5.79e-07	1.15e-06	1.91e-06	4.24e-06	8.80e-06	1.65e-05	4.14e-05	8.17e-05
first'	6.58e-08	1.26e-07	2.88e-07	5.44e-07	1.05e-06	2.62e-06	5.12e-06	1.04e-05	2.58e-05	5.22e-05
first / first'	2.42	2.27	2.01	2.11	1.81	1.62	1.72	1.58	1.60	1.56

chunked seq

size	10	20	50	100	200	500	1000	2000	5000	10000
first	3.52e-07	5.52e-07	1.13e-06	2.23e-06	3.74e-06	8.37e-06	1.72e-05	3.25e-05	8.14e-05	1.61e-04
first'	2.95e-07	4.94e-07	9.82e-07	1.88e-06	3.48e-06	8.11e-06	1.63e-05	3.24e-05	8.01e-05	1.62e-04
first / first'	1.19	1.12	1.15	1.19	1.07	1.03	1.05	1.01	1.02	0.995

lazy seq (cons)

size	10	20	50	100	200	500	1000	2000	5000	10000
first	4.83e-07	9.23e-07	2.33e-06	5.05e-06	9.87e-06	2.36e-05	4.61e-05	9.25e-05	2.28e-04	4.62e-04
first'	3.24e-07	8.10e-07	1.88e-06	3.83e-06	7.45e-06	1.89e-05	3.69e-05	7.41e-05	1.87e-04	3.65e-04
first / first'	1.49	1.14	1.24	1.32	1.32	1.25	1.25	1.25	1.22	1.27

iterable

size	10	20	50	100	200	500	1000	2000	5000	10000
first	2.58e-07	4.12e-07	7.84e-07	1.52e-06	2.67e-06	6.02e-06	1.19e-05	2.39e-05	5.86e-05	1.15e-04
first'	7.49e-08	1.33e-07	2.81e-07	5.32e-07	9.97e-07	2.48e-06	4.98e-06	9.61e-06	2.48e-05	4.95e-05
first / first'	3.44	3.11	2.80	2.85	2.68	2.42	2.38	2.48	2.36	2.33

array seq

size	10	20	50	100	200	500	1000	2000	5000	10000
first	4.22e-07	8.53e-07	2.00e-06	4.41e-06	1.01e-05	2.44e-05	4.52e-05	8.57e-05	2.59e-04	4.31e-04
first'	8.84e-08	1.82e-07	4.00e-07	7.65e-07	1.49e-06	3.57e-06	7.18e-06	1.43e-05	3.52e-05	7.04e-05
first / first'	4.77	4.67	5.00	5.77	6.79	6.85	6.29	5.99	7.34	6.13

bench.clj

(ns bench
  (:require [criterium.core :as cr]))

(defn first' [xform coll]
  (transduce xform (completing (fn [_ x] (reduced x))) nil coll))

(defn range-bench [n]
  (let [m (* 2 n)]
    (printf "# range (%d) - first\n" n)
    (cr/quick-bench (first (filter #(>= % n) (range m))))
    (newline)
    (printf "# range (%d) - first'\n" n)
    (cr/quick-bench (first' (filter #(>= % n)) (range m)))
    (newline)))

(defn iterate-bench [n]
  (printf "# iterate (%d) - first\n" n)
  (cr/quick-bench (first (filter #(>= % n) (iterate inc 0))))
  (newline)
  (printf "# iterate (%d) - first'\n" n)
  (cr/quick-bench (first' (filter #(>= % n)) (iterate inc 0)))
  (newline))

(defn vector-bench [n]
  (let [m (* 2 n)
        xs (vec (range m))]
    (printf "# vector (%d) - first\n" n)
    (cr/quick-bench (first (filter #(>= % n) xs)))
    (newline)
    (printf "# vector (%d) - first'\n" n)
    (cr/quick-bench (first' (filter #(>= % n)) xs))
    (newline)))

(defn chunked-seq-bench [n]
  (let [m (* 2 n)]
    (printf "# chunked seq (%d) - first\n" n)
    (cr/quick-bench (first (filter #(>= % n) (map identity (range m)))))
    (newline)
    (printf "# chunked seq (%d) - first'\n" n)
    (cr/quick-bench (first' (filter #(>= % n)) (map identity (range m))))
    (newline)))
    
(defn lazy-range [n]
  (letfn [(step [i]
            (if (< i n)
              (cons i (lazy-seq (step (inc i))))
              ()))]
    (step 0)))

(defn lazy-seq-bench [n]
  (let [m (* 2 n)]
    (printf "# lazy seq (%d) - first\n" n)
    (cr/quick-bench (first (filter #(>= % n) (lazy-range m))))
    (newline)
    (printf "# lazy seq (%d) - first'\n" n)
    (cr/quick-bench (first' (filter #(>= % n)) (lazy-range m)))
    (newline)))

(defn iterable-bench [n]
  (let [m (* 2 n)
        xs (java.util.List/of (object-array (range m)))]
    (printf "# iterable (%d) - first\n" n)
    (cr/quick-bench (first (filter #(>= % n) xs)))
    (newline)
    (printf "# iterable (%d) - first'\n" n)
    (cr/quick-bench (first' (filter #(>= % n)) xs))
    (newline)))

(defn array-seq-bench [n]
  (let [m (* 2 n)
        xs (object-array (range m))]
    (printf "# array seq (%d) - first\n" n)
    (cr/quick-bench (first (filter #(>= % n) (seq xs))))
    (newline)
    (printf "# array seq (%d) - first'\n" n)
    (cr/quick-bench (first' (filter #(>= % n)) (seq xs)))
    (newline)))

(defn -main []
  (doseq [f [range-bench
             iterate-bench
             vector-bench
             chunked-seq-bench
             lazy-seq-bench
             iterable-bench
             array-seq-bench]]
    (run! f [10 20 50 100 200 500 1000 2000 5000 10000])))

deps.edn

{:paths ["."]
 :deps {criterium/criterium {:mvn/version "0.4.6"}}}