Clojure中快速的复数运算

20
我在Clojure中实现一些基本复数运算时发现,即使有类型提示,它的速度大约比相似的Java代码慢了10倍。
比较:
(defn plus [[^double x1 ^double y1] [^double x2 ^double y2]]
    [(+ x1 x2) (+ y1 y2)])

(defn times [[^double x1 ^double y1] [^double x2 ^double y2]]
    [(- (* x1 x2) (* y1 y2)) (+ (* x1 y2) (* y1 x2))])

(time (dorun (repeatedly 100000 #(plus [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(times [1 0] [0 1])))) 

输出:

"Elapsed time: 69.429796 msecs"
"Elapsed time: 72.232479 msecs"

使用:

public static void main( String[] args ) {
  double[] z1 = new double[] { 1, 0 };
  double[] z2 = new double[] { 0, 1 };
  double[] z3 = null;

  long l_StartTimeMillis = System.currentTimeMillis();
  for ( int i = 0; i < 100000; i++ ) {
    z3 = plus( z1, z2 ); // assign result to dummy var to stop compiler from optimising the loop away
  }
  long l_EndTimeMillis = System.currentTimeMillis();
  long l_TimeTakenMillis = l_EndTimeMillis - l_StartTimeMillis;
  System.out.format( "Time taken: %d millis\n", l_TimeTakenMillis );


  l_StartTimeMillis = System.currentTimeMillis();
  for ( int i = 0; i < 100000; i++ ) {
    z3 = times( z1, z2 );
  }
  l_EndTimeMillis = System.currentTimeMillis();
  l_TimeTakenMillis = l_EndTimeMillis - l_StartTimeMillis;
  System.out.format( "Time taken: %d millis\n", l_TimeTakenMillis );

  doNothing( z3 );
}

private static void doNothing( double[] z ) {

}

public static double[] plus (double[] z1, double[] z2) {
  return new double[] { z1[0] + z2[0], z1[1] + z2[1] };
}

public static double[] times (double[] z1, double[] z2) {
  return new double[] { z1[0]*z2[0] - z1[1]*z2[1], z1[0]*z2[1] + z1[1]*z2[0] };
}

输出:

Time taken: 6 millis
Time taken: 6 millis

事实上,类型提示似乎没有太大的区别:如果我删除它们,我得到的结果大致相同。而真正奇怪的是,如果我在没有 REPL 的情况下运行 Clojure 脚本,我会得到更慢的结果:

"Elapsed time: 137.337782 msecs"
"Elapsed time: 214.213993 msecs"

我的问题是:如何接近Java代码的性能?而且为什么在没有REPL的情况下运行Clojure表达式需要更长的时间来评估?

更新 ==============

使用带有类型提示的deftypedefn中的deftype,以及使用dotimes而不是repeatedly可以实现与Java版本一样或更好的性能。谢谢你们两个。

(deftype complex [^double real ^double imag])

(defn plus [^complex z1 ^complex z2]
  (let [x1 (double (.real z1))
        y1 (double (.imag z1))
        x2 (double (.real z2))
        y2 (double (.imag z2))]
    (complex. (+ x1 x2) (+ y1 y2))))

(defn times [^complex z1 ^complex z2]
  (let [x1 (double (.real z1))
        y1 (double (.imag z1))
        x2 (double (.real z2))
        y2 (double (.imag z2))]
    (complex. (- (* x1 x2) (* y1 y2)) (+ (* x1 y2) (* y1 x2)))))

(println "Warm up")
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1)))))
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1)))))
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1)))))
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1)))))
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1)))))
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1)))))

(println "Try with dorun")
(time (dorun (repeatedly 100000 #(plus (complex. 1 0) (complex. 0 1)))))
(time (dorun (repeatedly 100000 #(times (complex. 1 0) (complex. 0 1)))))

(println "Try with dotimes")
(time (dotimes [_ 100000]
        (plus (complex. 1 0) (complex. 0 1))))

(time (dotimes [_ 100000]
        (times (complex. 1 0) (complex. 0 1))))

输出:

Warm up
"Elapsed time: 92.805664 msecs"
"Elapsed time: 164.929421 msecs"
"Elapsed time: 23.799012 msecs"
"Elapsed time: 32.841624 msecs"
"Elapsed time: 20.886101 msecs"
"Elapsed time: 18.872783 msecs"
Try with dorun
"Elapsed time: 19.238403 msecs"
"Elapsed time: 17.856938 msecs"
Try with dotimes
"Elapsed time: 5.165658 msecs"
"Elapsed time: 5.209027 msecs"

你尝试过设置*warn-on-reflection*来查看是否有任何反射 sneaking in 吗? - DaoWen
@DaoWen:不,我从未使用过那个设置。我刚刚在脚本顶部加入了(set! *warn-on-reflection* true)并再次运行了脚本,但是没有警告打印到标准输出,这意味着没有使用反射,对吗?只是想确保我使用得正确。 - OpenSauce
2个回答

25
你的性能缓慢很可能是由于以下原因:
  • Clojure 向量是比 Java 的 double[] 数组更重的数据结构。因此,在创建和读取向量时会有相当多的额外开销。
  • 你将双精度数作为参数传递给函数时,还包装了它们并放入向量中。在这种低级数值计算中,装箱/拆箱的代价相对较高。
  • 类型提示(^double)并没有起到帮助作用:虽然可以在普通 Clojure 函数上使用基本类型提示,但它们对于向量不起作用。

查看此博客文章以获得更多详细信息。

如果你真的想要在 Clojure 中快速处理复数,你可能需要使用 deftype 来实现它们,类似于以下代码:

(deftype Complex [^double real ^double imag])

然后使用这种类型来定义所有复杂函数。 这将使您能够始终使用原始算术,并且应该大致等同于编写良好的Java代码的性能。


我认为对于像这样的简单类型,推荐使用defrecord而不是deftype - DaoWen
1
@DaoWen - 我可能错了,但我相信你会从deftype中获得更好的性能 - 它比defrecord的开销要小一些。defrecord实现了完整的类似于映射的行为,并且更适用于“业务对象数据”,而deftype更适用于稍微低级的数据类型。 - mikera
1
谢谢,我对deftype/defrecord有些疑惑,担心它们会引入更多的开销,但我会尝试使用deftype(以及博客文章中提到的内容),并回报结果。 - OpenSauce
@mikera - 你说的deftype确实是更低级别的,但我认为使用defrecord代替deftype不一定会引入任何额外的开销。实现额外的接口(例如IPersistentMap)如果您不调用任何方法,则不会对您造成伤害。在代码的性能不那么关键的部分中,使用deftype代替defrecord将阻止您对实例进行关键字查找和解构,这可能是有用的。 - DaoWen
“^:static” 对类型提示并不相关,至少从1.2版本开始就不再相关了。从1.3版本开始,您可以在函数参数中使用原始类型提示;但是,OP没有这个选项,因为他接受的是向量而不是原始类型,而双精度数必须被装箱才能适应。除此之外,我同意您最终使用deftype的建议。 - amalloy
谢谢Alan - 我关于^:static的信息有些过时了,我已经更新了答案。你知道这种东西在哪里有文档记录吗? - mikera

4
  • 我对基准测试不是很了解,但似乎在开始测试时需要预热jvm。所以当你在REPL中进行测试时,它已经被预热了。而当你作为脚本运行时,它还没有被预热。

  • 在Java中,您可以在一个方法中运行所有循环。除plustimes之外,没有其他方法会被调用。在Clojure中,您创建匿名函数并重复调用以调用它。这需要一些时间。您可以使用dotimes来替换它。

(println "Warm up")
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(times [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(times [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(times [1 0] [0 1]))))

(println "Try with dorun")
(time (dorun (repeatedly 100000 #(plus [1 0] [0 1]))))
(time (dorun (repeatedly 100000 #(times [1 0] [0 1]))))

(println "Try with dotimes")
(time (dotimes [_ 100000]
        (plus [1 0] [0 1])))

(time (dotimes [_ 100000]
        (times [1 0] [0 1])))

结果:

Warm up
"Elapsed time: 367.569195 msecs"
"Elapsed time: 493.547628 msecs"
"Elapsed time: 116.832979 msecs"
"Elapsed time: 46.862176 msecs"
"Elapsed time: 27.805174 msecs"
"Elapsed time: 28.584179 msecs"
Try with dorun
"Elapsed time: 26.540489 msecs"
"Elapsed time: 27.64626 msecs"
Try with dotimes
"Elapsed time: 7.3792 msecs"
"Elapsed time: 5.940705 msecs"

谢谢,那很有道理。我得到了类似的结果。 - OpenSauce

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接