为什么这个看似基本的 clojure 函数这么慢?

Juf*_*ufi 3 clojure

我是 clojure 的新手,作为快速练习,我编写了一个函数,该函数应该遍历斐波那契数列,直到它超过 999999999 10 亿次(也做了一些额外的数学运算,但不是很重要)。我在 Java 中写了一些类似的东西,虽然我知道 Clojure 本质上比 Java 慢,但 java 程序花了 35 秒才能完成,而 Clojure 则花了 27 分钟,我发现这非常令人惊讶(考虑到 Nodejs 是大约8分钟内就能完成)。我使用 repl 编译了该类,并使用此 Java 命令运行它java -cp `clj -Spath` fib。真的不确定为什么这么慢。

(defn fib
  []
  (def iter (atom (long 0)))
  (def tester (atom (long 0)))
  (dotimes [n 1000000000]
    (loop [prev (long 0)
           curr (long 1)]
      (when (<= prev 999999999)
        (swap! iter inc)
        (if (even? @iter)
          (swap! tester + prev)
          (swap! tester - prev))
        (recur curr (+ prev curr)))))
  (println (str "Done in: "  @iter " Test: " @tester))
)
Run Code Online (Sandbox Code Playgroud)

这是我的Java方法供参考

    public static void main(String[] args) {
        long iteration = 0;
        int test = 0;
        for (int n = 0; n < 1000000000; n++) {
            int x = 0, y = 1;
            while (true) {
                iteration += 1;
                if (iteration % 2 == 0) {
                    test += x;
                }
                else {
                    test -=x;
                }
                int i = x + y;
                x = y;
                y = i;
                if (x > 999999999) { break; }
            }
        }
        System.out.println("iter: " + iteration + " " + test);
    }
Run Code Online (Sandbox Code Playgroud)

Did*_* A. 17

许多 Clo​​jure 新手没有意识到的一件事是,Clojure 默认情况下是一种高级语言。这意味着它将迫使您实现处理算术溢出的实现,将数字视为您可以扩展的对象,将阻止您改变任何变量,将迫使您拥有线程安全的代码,并将推动您走向功能解决方案依靠递归进行循环。

它也不会强制您默认输入所有内容,这也很方便,不必关心所有内容的类型并确保所有类型都是兼容的,例如您的向量仅包含整数,Clojure 不这样做不在乎,让你把整数和长整型放进去。

所有这些东西对于编写足够快、正确、可进化和可维护的应用程序来说非常有用,但对于高性能算法来说却不是那么好。

这意味着默认情况下 Clojure 针对实现应用程序进行了优化,而不是针对实现高性能算法进行了优化。

不幸的是,似乎大多数人都会“尝试”一种新语言,因此 Clojure 的新手往往会首先使用该语言来尝试和实现高性能算法。这与 Clojure 默认擅长的领域明显不匹配,许多新手立即面临 Clojure 在这里造成的额外摩擦。Clojure 假设您要实现一个应用程序,而不是某种高性能的 10 亿 N 大小的类似斐波那契的算法。

但不要失去希望,Clojure 也可用于实现高性能算法,但它不是默认的,因此您通常需要成为更有经验的 Clojure 开发人员才能知道如何执行此操作,因为它不太明显。

这是 Clojure 中的算法,其执行速度与 Java 实现一样快,它是对确切 Java 代码的递归重写:

(ns playground
  (:gen-class)
  (:require [fastmath.core :as fm]))

(defn -main []
  (loop [n (long 0) iteration (long 0) test (long 0)]
    (if (fm/< n 1000000000)
      (let [^longs inner
            (loop [x (long 0) y (long 1) iteration iteration test test]
              (let [iteration (fm/inc iteration)
                    test (if (fm/== (fm/mod iteration 2) 0) (fm/+ test x) (fm/- test x))
                    i (fm/+ x y)
                    x y
                    y i]
                (if (fm/> x 999999999)
                  (doto (long-array 2) (aset 0 iteration) (aset 1 test))
                  (recur x y iteration test))))]
        (recur (fm/inc n) (aget inner 0) (aget inner 1)))
      (str "iter: " iteration " " test))))

(println (time (-main)))

"Elapsed time: 47370.544514 msecs"
;;=> iter: 45000000000 0
Run Code Online (Sandbox Code Playgroud)

使用依赖项:

:deps {generateme/fastmath {:mvn/version "2.1.8"}}
Run Code Online (Sandbox Code Playgroud)

如您所见,在我的笔记本电脑上,它在约 47 秒内完成。我还在我的笔记本电脑上运行了您的 Java 版本,以在我的确切硬件上进行比较,对于 Java,我得到:46947.343671 毫秒。

因此,在我的笔记本电脑上,您可以看到 Clojure 和 Java 基本上都一样快,两者的计时时间都在 47 秒左右。

不同的是,在Java中,编程风格总是有利于实现高性能算法。您可以直接使用原始类型和原始算术,没有装箱,没有溢出检查,没有同步或原子性或易失性保护的可变变量等。

因此,要在 Clojure 中获得类似的性能,需要做一些事情:

  1. 使用原始类型
  2. 使用原始数学
  3. 避免使用更高级的托管可变容器,例如atom

显然,我们也需要运行相同的算法,因此实现类似。我并不是想比较是否存在另一种算法可以更快地解决同一问题,而是如何在 Clojure 中实现相同的算法,使其运行得同样快。

为了在 Clojure 中执行原始类型,您必须知道只能在本地上下文中使用letand执行此loop操作,并且所有函数调用都将撤消原始类型,除非它们也被类型化为原始 long 或 double(唯一的支持可以跨越 Clojure 中函数边界的原始类型)。

这是我当时做的第一件事,只需使用 Clojure 重新编写相同的循环loop/recur并声明与您相同的变量,但使用let遮蔽,因此我们不需要托管可变容器。

最后,我使用了 Fastmath,这个库提供了许多算术函数的原始版本,以便我们可以进行原始数学运算。Clojure 核心有一些自己的功能,但它没有 mod,所以我需要引入 Fastmath。

就是这样。

一般来说,这是您需要了解的内容,保留原始类型、保留原始数学(使用 fastmath)、避免反射的类型提示、利用 let 遮蔽、保留原始数组,然后您将获得 Clojure 高性能实现。

这里有一组很好的信息:https ://clojure.org/reference/java_interop#primitives

最后一件事,Clojure 的理念是它旨在实现足够快、正确、可进化和可维护的可扩展应用程序。这就是为什么语言是这样的。正如我所展示的,虽然您可以实现高性能算法,但 Clojure 的理念也不是为 Java 已经擅长的事物重新发明语法。Clojure 可以使用 Java,因此对于需要非常命令式、可变、原始逻辑的算法,它会期望您只需回退到 Java 将其编写为静态方法,然后从 Clojure 中使用它。或者它认为您甚至可以委托给比 Java 性能更高的东西,并使用 BLAS 或 GPU 来执行超快速矩阵数学或类似的东西。这就是为什么它不费心提供自己的命令式构造,或原始内存访问等等,因为它认为它没有比它运行的主机做得更好。