python - 为什么 Clojure 频率不比 Python collections.Counter 快？

Question

注意 - 这里是 Clojure 新手。

我预计 Clojure 实现的次数计数器会比 Python 快得多。但事实证明 Python 更快!这是什么解释？如何推断 Python 在哪里更快，Clojure 在哪里更快？

我将 CPython 2.7.8 和 Clojure 1.6.0 与 OpenJDK 64 位服务器 VM 1.7.0_75-b13 结合使用。

Python代码:

from string import ascii_lowercase
import timeit

DATA = list(ascii_lowercase)*100000

def frequencies(items):
    counter = {}
    for item in items:
        counter[item] = counter.setdefault(item, 0) + 1

    return counter

print(timeit.timeit(lambda: frequencies(DATA), number=1))

输出:

0.528199911118

Clojure 代码:

(ns test
  (:gen-class))

(defn -main
  [& args]
  (let
    [data
     (doall (apply concat
                   (repeat 100000 (map char (range (int \a) (+ (int \z) 1))))))]
    (time (frequencies data))))

输出:

"Elapsed time: 861.668743 msecs"

更新#1

我做了一些优化:

(ns test
  (:gen-class))

(defn frequencies2
  [coll]
  (into {} (reduce (fn [^java.util.HashMap counts x]
             (.put counts x
                   (inc (or (.get counts x) 0))) counts)
           (java.util.HashMap. {}) coll)))    

(defn -main
  [& args]
  (let
    [data
     (doall (apply concat
                   (repeat 10000 (map char (range (int \a) (inc (int \z)))))))]
    (time (dotimes [_ 15] (frequencies data)))
    (time (dotimes [_ 15] (frequencies2 data)))))

输出:

"Elapsed time: 1524.498547 msecs"
"Elapsed time: 476.387626 msecs"

所以我补充两个问题:

• 为什么 clojure.core implementation不使用类型提示？
• 如何进一步优化性能？我可以为整数 HashMap 值添加类型提示吗？

Answer 1

在 JVM 上对任何东西进行基准测试是一项棘手的工作。 JVM 会在代码运行时对其进行优化，但很难预测或控制它何时发生。要获得比两个函数(都是 Clojure)之间最一般的性能提示更多的东西，您需要使用专用的基准测试库。 Criterium是 Clojure 社区中为此最常用的库。

关于性能的推理非常棘手，尤其是在两个截然不同的平台之间。我认为对大量代码进行基准测试和测量将是培养两种语言之间直觉的最佳方式。深入研究底层数据结构并了解它们的性能特征将帮助您解决问题。正如您在 frequencies2 中看到的那样，与使用 Clojure 的持久映射相比，使用可变 HashMap 可以获得更好的性能。然而，如果你走那条路，你将失去所有不变性的优点。

出于某些原因，Clojure 版本没有类型提示。

1. Frequencies 是一个通用函数，因此它可以处理任何类型的值。

2. 类型提示 仅对与 Java 类 的互操作具有真正的性能值(value)。来自 Clojure Programming , 第 367 页

   Type hints on function arguments or returns are not signature declarations: they do not affect the types that a function can accept or return. Their only effect is to allow Clojure to call Java methods and access Java fields using compile-time generated code—rather than the much-slower option of using reflection at runtime to search for methods or fields matching the interop form in question. Thus, if a hint doesn’t inform an interop operation, they are effectively no-ops. [...] This is in contrast to signature declarations, which Clojure does provide, but only for primitive arguments and return types.

如果您在函数中专门使用 Java 原语，那么您可以使用类型声明 来优化它。再次来自 Clojure Programming , 第 438 页

When Clojure compiles a function, it generates a corresponding class that implements clojure.lang.IFn, one of Clojure’s Java interfaces. IFn defines a number of invoke methods; these are what are called under the covers when you invoke a Clojure function.

All arguments and return values are Objects at (undecorated) function boundaries. These invoke methods all accept arguments and return values of the root type java.lang.Object. This enables Clojure’s dynamic typing defaults (i.e., your functions’ implementations determine the range of acceptable argument types, not static type declarations that are enforced by the language), but has the side effect of forcing the JVM to box any primitives passed as arguments to or returned as results from those functions. So, if we call a Clojure function with a primitive argument—a long, for example—that argument will be boxed into a Long object in order to conform to the type signature of the Clojure function’s underlying invoke method. Similarly, if a function’s result is a primitive value, the underlying Object return type ensures that such primitives are boxed before the caller receives the result. [...]

(defn round ^long [^double a] (Math/round a))
;= #'user/round
(seq (.getDeclaredMethods (round foo)))
;= (#<Method public java.lang.Object user$round.invoke(java.lang.Object)> 
#<Method public final long user$round.invokePrim(double)>)

如果您想进一步优化它并且您专门处理 Java 原始整数，那么您可以使用 ^int 类型声明作为参数或函数的返回值。但是我认为它对您当前的代码没有任何用处。另一个下降的途径是并行计数并在最后组合它们。你也可以看看 http://java-performance.info/implementing-world-fastest-java-int-to-int-hash-map/以获得更多想法，尽管那时您实际上是在用有趣的领域特定语法编写 Java。