Почему эта циклическая функция настолько медленная по сравнению с картой?

Question

Я посмотрел на исходный код карт, который в основном продолжает создавать ленивые последовательности. Я бы подумал, что итерация по коллекции и добавление к переходному вектору будет быстрее, но это явно не так. Что я не понимаю о поведении производительности clojures?

;=> (time (do-with/(range 1 1000) (range 1 1000))) 
;"Elapsed time: 23.1808 msecs" 
; 
; vs 
;=> (time (doall (map #(/ %1 %2) (range 1 1000) (range 1 1000)))) 
;"Elapsed time: 2.604174 msecs" 
(defn do-with 
    [fn coll1 coll2] 
    (let [end (count coll1)] 
    (loop [i 0 
      res (transient [])] 
     (if 
      (= i end) 
      (persistent! res) 
      (let [x (nth coll1 i) 
        y (nth coll2 i) 
        r (fn x y)] 
       (recur (inc i) (conj! res r))) 
       )))) 

Answer 1

В порядке высказал гипотезу влияния на относительные результаты:

1. Ваш do-with функция использует nth для доступа отдельных элементов во входных коллекциях. nth работает в линейном режиме по диапазонам, делая do-with квадратным. Излишне говорить, что это убьет производительность в больших коллекциях.

2. range производит секционные секции и map обрабатывает их чрезвычайно эффективно. (По сути, он создает фрагменты длиной до 32 элементов - на самом деле это будет ровно 32 - путем выполнения жесткой петли над внутренним массивом каждого входного блока по очереди, помещая результаты в внутренние массивы выходных блоков.)

3. Бенчмаркинг с time не дает вам устойчивого состояния. (Вот почему один должен действительно использовать правильную библиотеку бенчмаркинга, в случае Clojure, Criterium является стандартным решением.)

Кстати, (map #(/ %1 %2) xs ys) просто можно записать в виде (map/xs ys).

Update:

Я протестированные версии map, оригинальный do-with и новая версия do-with с критериум, используя (range 1 1000) как оба входа в каждом конкретном случае (как и в тексте вопроса), получая следующее Среднее время выполнения:

;;; (range 1 1000) 
new do-with   170.383334 µs 
(doall (map ...))  230.756753 µs 
original do-with  15.624444 ms 

кроме того, я повторил тест с использованием вектора, хранящийся в Var в качестве входных данных, а не диапазонов (то есть с (def r (vec (range 1 1000))) на запуске d с использованием r как обоих аргументов в каждом эталоне). Неудивительно, что оригинал do-with вошел в первую очередь - nth очень быстр на векторах (плюс использование nth с вектором позволяет избежать всех промежуточных распределений, участвующих в пересечении seq).

;;; (vec (range 1 1000)) 
original do-with  73.975419 µs 
new do-with   87.399952 µs 
(doall (map ...))  153.493128 µs 

Вот новая do-with с линейной временной сложностью:

(defn do-with [f xs ys] 
    (loop [xs (seq xs) 
     ys (seq ys) 
     ret (transient [])] 
    (if (and xs ys) 
     (recur (next xs) 
      (next ys) 
      (conj! ret (f (first xs) (first ys)))) 
     (persistent! ret))))