Зачем редуктор выполняет гораздо неоптимально, чем повторение в этом случае?

Question

Один из интуитивно понятных способов вычисления π в полиномиальной сумме выглядит следующим образом:

π = (1/1 - 1/3 + 1/5 - 1/7 + 1/9 ...) × 4

Следующая функция ρ или ρ 'обозначает полиномиальную сумму , и потребляемое время τ для вычисления π измеряется соответственно,

 (defn term [k]                                                                                                        
   (let [x (/ 1. (inc (* 2 k)))]                                                                                       
     (if (even? k)                                                                                                     
       x                                                                                                               
       (- x))))                                                                                                        

 (defn ρ [n]                                                                                                           
   (reduce                                                                                                             
     (fn [res k] (+ res (term k)))                                                                                     
     0                                                                                                                 
     (lazy-seq (range 0 n))))                                                                                          

 (defn ρ' [n]                                                                                                          
   (loop [res 0 k 0]                                                                                                   
     (if (< k n)                                                                                                       
       (recur (+ res (term k)) (inc k))                                                                                
       res)))                                                                                                          

 (defn calc [P]                                                                                                        
   (let [start (System/nanoTime)                                                                                       
         π (* (P 1000000) 4)                                                                                           
         end (System/nanoTime)                                                                                         
         τ (- end start)]                                                                                              
     (printf "π=%.16f τ=%d\n" π τ)))                                                                                   

 (calc ρ)                                                                                                              
 (calc ρ')       

Результат говорит о том, что ρ примерно на половину больше времени, чем ρ ', поэтому базовое сокращение выполняет намного неоптимально, чем recur в это случай, но почему?

Answer 1

Дополнительно к другим ответам. Производительность может быть значительно увеличена при устранении математического бокса (исходные версии были около 25 мс). И вариант с loop/recur в 2 раза быстрее.

(set! *unchecked-math* :warn-on-boxed)

(defn term ^double [^long k]
  (let [x (/ 1. (inc (* 2 k)))]
    (if (even? k)
      x
      (- x))))

(defn ρ [n]
  (reduce
    (fn [^double res ^long k] (+ res (term k)))
    0
    (range 0 n)))

(defn ρ' [^long n]
  (loop [res (double 0) k 0]
    (if (< k n)
      (recur (+ res (term k)) (inc k))
      res)))

(criterium.core/quick-bench
    (ρ 1000000))
Evaluation count : 42 in 6 samples of 7 calls.
             Execution time mean : 15,639294 ms
    Execution time std-deviation : 371,972168 µs
   Execution time lower quantile : 15,327698 ms ( 2,5%)
   Execution time upper quantile : 16,227505 ms (97,5%)
                   Overhead used : 1,855553 ns

Found 1 outliers in 6 samples (16,6667 %)
    low-severe   1 (16,6667 %)
 Variance from outliers : 13,8889 % Variance is moderately inflated by outliers
=> nil
(criterium.core/quick-bench
    (ρ' 1000000))
Evaluation count : 72 in 6 samples of 12 calls.
             Execution time mean : 8,570961 ms
    Execution time std-deviation : 302,554974 µs
   Execution time lower quantile : 8,285648 ms ( 2,5%)
   Execution time upper quantile : 8,919635 ms (97,5%)
                   Overhead used : 1,855553 ns
=> nil

Answer 2

Переписывание вашего кода и использование более точного таймера показывает, что нет существенной разницы. Этого следует ожидать, так как loop/recur и reduce являются очень базовыми c формами, и мы ожидаем, что они оба будут довольно оптимизированы.

(ns tst.demo.core
  (:use demo.core tupelo.core tupelo.test)
  (:require
    [criterium.core :as crit] ))

(def result (atom nil))

(defn term [k]
  (let [x (/ 1. (inc (* 2 k)))]
    (if (even? k)
      x
      (- x))))

(defn ρ [n]
  (reduce
    (fn [res k] (+ res (term k)))
    0
    (range 0 n)) )

(defn ρ' [n]
  (loop [res 0 k 0]
    (if (< k n)
      (recur (+ res (term k)) (inc k))
      res)) )

(defn calc [calc-fn N]
  (let [pi (* (calc-fn N) 4)]
    (reset! result pi)
    pi))

Мы измеряем время выполнения для обоих алгоритмов с использованием критерия :

(defn timings
  [power]
  (let [N (Math/pow 10 power)]
    (newline)
    (println :-----------------------------------------------------------------------------)
    (spyx N)
    (newline)
    (crit/quick-bench (calc ρ N))
    (println :rho @result)
    (newline)
    (crit/quick-bench (calc ρ' N))
    (println :rho-prime N @result)
    (newline)))

, и мы пробуем его для 10 ^ 2, 10 ^ 4 и 10 ^ 6 значений N:

(dotest
  (timings 2)
  (timings 4)
  (timings 6))

с результатами для 10 ^ 2:

-------------------------------
   Clojure 1.10.1    Java 14
-------------------------------

Testing tst.demo.core

:-----------------------------------------------------------------------------
N => 100.0

Evaluation count : 135648 in 6 samples of 22608 calls.
             Execution time mean : 4.877255 µs
    Execution time std-deviation : 647.723342 ns
   Execution time lower quantile : 4.438762 µs ( 2.5%)
   Execution time upper quantile : 5.962740 µs (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 31.6928 % Variance is moderately inflated by outliers
:rho 3.1315929035585537

Evaluation count : 148434 in 6 samples of 24739 calls.
             Execution time mean : 4.070798 µs
    Execution time std-deviation : 68.430348 ns
   Execution time lower quantile : 4.009978 µs ( 2.5%)
   Execution time upper quantile : 4.170038 µs (97.5%)
                   Overhead used : 2.165947 ns
:rho-prime 100.0 3.1315929035585537

с результатами за 10 ^ 4:

:-----------------------------------------------------------------------------
N => 10000.0

Evaluation count : 1248 in 6 samples of 208 calls.
             Execution time mean : 519.096208 µs
    Execution time std-deviation : 143.478354 µs
   Execution time lower quantile : 454.389510 µs ( 2.5%)
   Execution time upper quantile : 767.610509 µs (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 65.1517 % Variance is severely inflated by outliers
:rho 3.1414926535900345

Evaluation count : 1392 in 6 samples of 232 calls.
             Execution time mean : 431.020370 µs
    Execution time std-deviation : 14.853924 µs
   Execution time lower quantile : 420.838884 µs ( 2.5%)
   Execution time upper quantile : 455.282989 µs (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
:rho-prime 10000.0 3.1414926535900345

с результатами за 10 ^ 6:

:-----------------------------------------------------------------------------
N => 1000000.0

Evaluation count : 18 in 6 samples of 3 calls.
             Execution time mean : 46.080480 ms
    Execution time std-deviation : 1.039714 ms
   Execution time lower quantile : 45.132049 ms ( 2.5%)
   Execution time upper quantile : 47.430310 ms (97.5%)
                   Overhead used : 2.165947 ns
:rho 3.1415916535897743

Evaluation count : 18 in 6 samples of 3 calls.
             Execution time mean : 52.527777 ms
    Execution time std-deviation : 17.483930 ms
   Execution time lower quantile : 41.789520 ms ( 2.5%)
   Execution time upper quantile : 82.539445 ms (97.5%)
                   Overhead used : 2.165947 ns

Found 1 outliers in 6 samples (16.6667 %)
    low-severe   1 (16.6667 %)
 Variance from outliers : 81.7010 % Variance is severely inflated by outliers
:rho-prime 1000000.0 3.1415916535897743

Обратите внимание, что время для Rho и Rho-Prime триггер для 10 ^ 4 и 10 ^ 6 случаев. В любом случае, не стоит сильно верить или беспокоиться о временах, которые различаются менее чем в 2 раза.

---

Обновление

Я удалил lazy-seq в исходном коде, начиная с clojure.core/range уже ленивый. Кроме того, я никогда не видел, чтобы lazy-seq использовался без cons и рекурсивного вызова генерирующей функции.

Re clojure.core/range, у нас есть документы:

range

Возвращает ленивую последовательность чисел от начала (включительно) до конца (исключая), шаг за шагом, где начало по умолчанию равно 0, шаг к 1 и конец до бесконечности. Когда шаг равен 0, возвращает бесконечную последовательность запуска. Когда начало равно концу, возвращает пустой список.

В исходном коде он вызывает Java impl из clojure.core:

  ([start end]
   (if (and (instance? Long start) (instance? Long end))
     (clojure.lang.LongRange/create start end)
     (clojure.lang.Range/create start end)))

& the Java код указывает, что он разделен на части:

    public class Range extends ASeq implements IChunkedSeq, IReduce {
      private static final int CHUNK_SIZE = 32;
      <snip>

Answer 3

Ниже улучшенная версия, чтобы быть более представительной. По-видимому, производительность варьируется от случая к случаю, но не так сильно.

 (defn term [k]                                                                                                        
   (let [x (/ 1. (inc (* 2 k)))]                                                                                       
     (if (even? k)                                                                                                     
       x                                                                                                               
       (- x))))                                                                                                        

 (defn ρ1 [n]                                                                                                          
   (loop [res 0 k 0]                                                                                                   
     (if (< k n)                                                                                                       
       (recur (+ res (term k)) (inc k))                                                                                
       res)))                                                                                                          

 (defn ρ2 [n]                                                                                                          
   (reduce                                                                                                             
    (fn [res k] (+ res (term k)))                                                                                      
    0                                                                                                                  
    (range 0 n)))                                                                                                      

 (defn ρ3 [n]                                                                                                          
   (reduce + 0 (map term (range 0 n))))                                                                                

 (defn ρ4 [n]                                                                                                          
   (transduce (map term) + 0 (range 0 n)))                                                                             

 (defn calc [ρname ρ n]                                                                                                
   (let [start (System/nanoTime)                                                                                       
         π (* (ρ n) 4)                                                                                                 
         end (System/nanoTime)                                                                                         
         τ (- end start)]                                                                                              
     (printf "ρ=%8s n=%10d π=%.16f τ=%10d\n" ρname n π τ)))                                                            

 (def args                                                                                                             
   {:N (map #(long (Math/pow 10 %)) [4 6])                                                                             
    :T 10                                                                                                              
    :P {:recur ρ1 :reduce ρ2 :mreduce ρ3 :xreduce ρ4}})                                                                

 (doseq [n (:N args)]                                                                                                  
   (dotimes [_ (:T args)]                                                                                              
     (println "---")                                                                                                   
     (doseq [kv (:P args)] (calc (key kv) (val kv) n))))