Я пытаюсь доказать, что производительность Clojure может быть на равной основе с Java. Важным вариантом использования, который я нашел, является Quicksort. Я написал реализацию следующим образом:
(set! *unchecked-math* true)
(defn qsort [^longs a]
(let [qs (fn qs [^long low, ^long high]
(when (< low high)
(let [pivot (aget a low)
[i j]
(loop [i low, j high]
(let [i (loop [i i] (if (< (aget a i) pivot)
(recur (inc i)) i))
j (loop [j j] (if (> (aget a j) pivot)
(recur (dec j)) j))
[i j] (if (<= i j)
(let [tmp (aget a i)]
(aset a i (aget a j)) (aset a j tmp)
[(inc i) (dec j)])
[i j])]
(if (< i j) (recur i j) [i j])))]
(when (< low j) (qs low j))
(when (< i high) (qs i high)))))]
(qs 0 (dec (alength a))))
a)
Кроме того, это помогает вызвать quicksort Java:
(defn jqsort [^longs a] (java.util.Arrays/sort a) a))
Теперь, для эталона.
user> (def xs (let [rnd (java.util.Random.)]
(long-array (repeatedly 100000 #(.nextLong rnd)))))
#'user/xs
user> (def ys (long-array xs))
#'user/ys
user> (time (qsort ys))
"Elapsed time: 163.33 msecs"
#<long[] [[email protected]>
user> (def ys (long-array xs))
user> (time (jqsort ys))
"Elapsed time: 13.895 msecs"
#<long[] [[email protected]>
Производительность - это миры (на порядок, а затем и некоторые).
Есть ли что-нибудь, что мне не хватает, любая функция Clojure, которую я, возможно, использовал? Я думаю, что основным источником снижения производительности является то, что мне нужно вернуть несколько значений из цикла и выделить для этого вектор. Можно ли этого избежать?
BTW running Clojure 1.4. Также обратите внимание, что я несколько раз запускал тест, чтобы разогреть HotSpot. Это время, когда они оседают.
Update
Самая страшная слабость в моем коде - это не просто распределение векторов, а то, что они заставляют бокс и разрушают примитивную цепочку. Другая слабость заключается в использовании результатов loop
, поскольку они также разрушают цепочку. Да, производительность в Clojure по-прежнему остается минным полем.