Низкая производительность факториальной функции, написанной на Clojure

Question

Я новичок в Clojure. В эксперименте с ним я написал функцию I для вычисления n!. Мой код Clojure выглядит следующим образом:

(defn factorial 
    [n] 
    (reduce * (biginteger 1) (range 1 (inc n)))) 

Затем я запустил следующее в реплике.

(time (factorial 100)) 

И это был результат:

"Elapsed time: 0.50832 msecs" 
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N 

Затем я создал подобное решение в Ruby:

def factorial(n) 
    start = Time.now.to_f 
    (2..n).inject(1) { |p, f| p * f } 
    finish = Time.now.to_f 
    time_taken = finish - start 
    puts "It took: #{(time_taken * 1000)} msecs" 
end 

с IRB я побежал factorial(100) Результирующее в:

It took: 0.06556510925292969 msecs 
=> 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 

Производительность версии Ruby, по-видимому, значительно выше, несмотря на большинство доказательств, которые я видел, предполагая, что Clojure должен иметь превосходную производительность. Есть ли что-то, что я недопонимаю или какой-то элемент моего решения Clojure, который замедлит его?

Answer 1

Миро-бенчмаркинг очень часто вводит в заблуждение и в целом это довольно трудно получить это право. Самый простой способ получить достаточно близко в Clojure (что я нашел это библиотека критериума (спасибо Hugo!). Если я начну с некрасивой версией вычисления факториала просто перекручиванием я получаю около 3 нс.

user> (defn loopy-fact [x] 
     (loop [y x 
       answer-so-far 1] 
      (if (pos? y) 
      (recur (dec y) (*' answer-so-far y)) 
      answer-so-far))) 
#'user/loopy-fact 

user> (loopy-fact 100) 
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N 

а потом давайте бенчмарк его:

user> (criterium.core/bench #(loopy-fact 100)) 
WARNING: Final GC required 11.10521514596218 % of runtime 
WARNING: Final GC required 1.069604210579865 % of runtime 
Evaluation count : 12632130300 in 60 samples of 210535505 calls. 
      Execution time mean : 2.978360 ns 
    Execution time std-deviation : 0.116043 ns 
    Execution time lower quantile : 2.874266 ns (2.5%) 
    Execution time upper quantile : 3.243399 ns (97.5%) 
        Overhead used : 1.844334 ns 

Found 4 outliers in 60 samples (6.6667 %) 
    low-severe 2 (3.3333 %) 
    low-mild  2 (3.3333 %) 
Variance from outliers : 25.4468 % Variance is moderately inflated by outliers 

Если мы затем сделать код выглядеть лучше, используя обычный Clojure стиль, с картой и уменьшить и без усилий сделать это быстро.

user> (defn mapy-fact [x] 
     (reduce *' (range 1 (inc x))) 
#'user/mapy-fact 

user> (mapy-fact 100) 
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000N 

Теперь давайте выясним, как это сравнивает:

user> (criterium.core/bench #(mapy-fact 100)) 
Evaluation count : 8674569060 in 60 samples of 144576151 calls. 
      Execution time mean : 5.208031 ns 
    Execution time std-deviation : 0.265287 ns 
    Execution time lower quantile : 5.032058 ns (2.5%) 
    Execution time upper quantile : 5.833466 ns (97.5%) 
        Overhead used : 1.844334 ns 

Found 4 outliers in 60 samples (6.6667 %) 
    low-severe 1 (1.6667 %) 
    low-mild  3 (5.0000 %) 
Variance from outliers : 36.8585 % Variance is moderately inflated by outliers 

Это немного медленнее, но только медленнее двух наносекунд.

Это намного лучше, чем было показано в вашем тесте, потому что критерий выполняет достаточно много времени для компилятора Jots of JVM, чтобы обойти его компиляцию и встраивание всех частей. Это демонстрирует, почему микросхемы могут вводить в заблуждение на JVM. и вы почти наверняка будете придерживаться критерия для таких случаев.

PS: *' является «авто продвижение» Умножение opperator, это будет способствовать его типы в большом целого числа или биг-десятичного требуется

Answer 2

BigInteger происходит от java, тогда как BigInt реализован в ядре Clojure. С самого начала, это связано с некоторыми расходами, связанными с interopability.

---

Кроме того, BigInt представлена ​​либо как a long or a BigInteger. По возможности, the long is used. Однако, если какая-либо операция делает ее overflow, в результате получается новый BigIntwill use it's BigInteger. Java long отображает реализацию собственной архитектуры, следовательно, значительно быстрее. Это похоже на магическое преобразование Руби между Fixnum и Bignum.

Поскольку вы используете небольшие номера почти исключительно (от 1 до 100 и хороший кусок промежуточных продуктов), вы можете получить значительное повышение производительности.

Answer 3

Дальше @ndn's answer:

Вы можете получить дополнительную скорость по типу-намекая аргумент n:

(defn factorial [^long n] 
    (reduce * (bigint 1) (range 1 (inc n))))