29

我试图证明 Clojure 的性能可以与 Java 平起平坐。我发现的一个重要用例是快速排序。我写了一个实现如下：

(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)

此外，这有助于调用 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[] [J@3ae34094>
user> (def ys (long-array xs))
user> (time (jqsort ys))
"Elapsed time: 13.895 msecs"
#<long[] [J@1b2b2f7f>

性能是天壤之别（一个数量级，然后是一些）。

有什么我遗漏的，我可能使用过的任何 Clojure 功能吗？我认为性能下降的主要来源是当我需要从循环中返回多个值并且必须为此分配一个向量时。这可以避免吗？

顺便说一句，运行 Clojure 1.4。另请注意，我已多次运行基准测试以预热 HotSpot。这些是他们安定下来的时候。

更新

我的代码中最可怕的弱点不仅仅是向量的分配，而是它们强制装箱并破坏原始链的事实。另一个弱点是使用结果，loop因为它们也会破坏链条。是的，Clojure 中的性能仍然是一个雷区。

4

4 回答 4

45

这个版本基于@mikera，速度一样快，不需要使用丑陋的宏。在我的机器上，java.util.Arrays/sort 需要 ~12ms 而 ~9ms：

(set! *unchecked-math* true)
(set! *warn-on-reflection* true)

(defn swap [^longs a ^long i ^long j]
  (let [t (aget a i)]
    (aset a i (aget a j))
    (aset a j t)))

(defn ^long apartition [^longs a ^long pivot ^long i ^long j]
  (loop [i i j j]
    (if (<= i j)
      (let [v (aget a i)]
        (if (< v pivot)
          (recur (inc i) j)
          (do 
            (when (< i j) 
              (aset a i (aget a j))
              (aset a j v))
            (recur i (dec j)))))
      i)))

(defn qsort 
  ([^longs a]
     (qsort a 0 (long (alength a))))
  ([^longs a ^long lo ^long hi]    
     (when
         (< (inc lo) hi)
       (let [pivot (aget a lo)
             split (dec (apartition a pivot (inc lo) (dec hi)))]
         (when (> split lo)
           (swap a lo split))
         (qsort a lo split)
         (qsort a (inc split) hi)))
     a))

(defn ^longs rand-long-array []
  (let [rnd (java.util.Random.)] 
    (long-array (repeatedly 100000 #(.nextLong rnd)))))

(comment
  (dotimes [_ 10]
    (let [as (rand-long-array)]
      (time
       (dotimes [_ 1] 
         (qsort as)))))
  )

从 Clojure 1.3 开始，几乎不需要手动内联。仅在函数参数上提供一些类型提示，JVM 将为您执行内联。对于数组操作，不需要将索引参数强制转换为 int - Clojure 会为您执行此操作。

需要注意的一件事是嵌套循环/递归确实会给 JVM 内联带来问题，因为循环/递归（此时）不支持返回原语。所以你必须把你的代码分解成单独的 fns。这是最好的，因为无论如何嵌套循环/递归在 Clojure 中变得非常丑陋。

要更详细地了解如何始终如一地实现 Java 性能（当您真正需要它时），请检查并理解test.benchmark。

于 2012-08-29T16:27:46.127 回答
11

由于宏，这有点可怕，但是使用这段代码，我认为您可以匹配 Java 速度（基准测试大约需要 11 毫秒）：

(set! *unchecked-math* true)

(defmacro swap [a i j]
  `(let [a# ~a
         i# ~i
         j# ~j
         t# (aget a# i#)]
     (aset a# i# (aget a# j#))
     (aset a# j# t#)))

(defmacro apartition [a pivot i j]
  `(let [pivot# ~pivot]
     (loop [i# ~i
            j# ~j]
       (if (<= i# j#)
         (let [v# (aget ~a i#)]
           (if (< v# pivot#)
             (recur (inc i#) j#)
             (do 
               (when (< i# j#) 
                 (aset ~a i# (aget ~a j#))
                 (aset ~a j# v#))
               (recur i# (dec j#)))))
         i#))))

(defn qsort 
  ([^longs a]
    (qsort a 0 (alength a)))
  ([^longs a ^long lo ^long hi]    
    (let [lo (int lo)
          hi (int hi)]
      (when
        (< (inc lo) hi)
        (let [pivot (aget a lo)
              split (dec (apartition a pivot (inc lo) (dec hi)))]
          (when (> split lo) (swap a lo split))
          (qsort a lo split)
          (qsort a (inc split) hi)))
      a)))

主要技巧是：

  • 用原始算术做所有事情
  • 对数组索引使用整数（这可以避免一些不必要的强制转换，没什么大不了的，但每一点都有帮助....）
  • 使用宏而不是函数来分解代码（避免函数调用开销和参数装箱）
  • 在内部循环中使用循环/递归以获得最大速度（即分区子阵列）
  • 避免在堆上构造任何新对象（因此避免使用向量、序列、映射等）
于 2012-08-29T13:48:55.003 回答
10

Clojure 的乐趣，第 6.4 章描述了一种惰性快速排序算法。惰性排序的美妙之处在于它只会做尽可能多的工作来找到第一个 x 值。所以如果 x << n 这个算法是 O(n)。

(ns joy.q)

(defn sort-parts
  "Lazy, tail-recursive, incremental quicksort.  Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
   (loop [[part & parts] work]
     (if-let [[pivot & xs] (seq part)]
       (let [smaller? #(< % pivot)]
         (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
       (when-let [[x & parts] parts]
         (cons x (sort-parts parts)))))))

(defn qsort [xs]
    (sort-parts (list xs)))
于 2012-08-29T15:32:34.557 回答
7

通过检查 mikera 回答的要点，您可以看到它们主要集中在消除使用惯用的（而不是经过调整的）Clojure 引入的开销，这在惯用的 Java 实现中可能不存在：

  • 原始算术- 在 Java 中稍微更容易和更惯用，你更可能使用ints 而不是Integers
  • 数组索引的整数 - 相同
  • 使用宏而不是函数来分解代码（避免函数调用开销和装箱） - 修复了使用语言引入的问题。Clojure 鼓励函数式风格，因此函数调用开销（和装箱）。
  • 在内部循环中使用循环/递归以获得最大速度- 在 Java 中，您会习惯性地使用普通循环（据我所知，无论如何循环/递归都是编译成的）

话虽如此，实际上还有另一个简单的解决方案。编写（或找到）快速排序的有效 Java 实现，用这样的签名说一些东西：

Sort.quickSort(long[] elems)

然后从 Clojure 调用它：

(Sort/quickSort elems)

清单：

  • 与 Java 一样高效 -是的

  • Clojure 中的惯用语 -可以说是的，我会说 Java 互操作是 Clojure 的核心功能之一。

  • 可重用 -是的，您很有可能很容易找到已经编写的非常高效的 Java 实现。

我不是要拖钓，我理解你想通过这些实验找出什么我只是为了完整起见添加这个答案。让我们不要忽视显而易见的！:)

于 2012-08-29T14:13:57.510 回答