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

Question

我是Clojure的新手，作为快速练习，我编写了一个应该通过斐波那契序列进行的函数，直到超过999999999的99999999.1亿次（也做一些额外的数学，但不是很重要）。我已经写了一些在Java中做的东西，尽管我知道本质上的clojure比Java慢，但Java程序花费了35秒才能完成，而Clojure则花了27分钟，我发现这非常令人惊讶（考虑到Nodejs是很令人惊讶的能够在大约8分钟内完成它。我用reque编辑了该类，并使用此Java命令Java -cp`Clj -spath` fib conter java -cod>。真的不确定为什么这么慢。

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

这是我的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);
    }

Answer 1

许多 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

使用 deps：

:deps {generateme/fastmath {:mvn/version "2.1.8"}}

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

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

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

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

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

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

为了在 Clojure 中执行基本类型，您必须知道只能在本地上下文中使用 let 和 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 来执行超快速矩阵数学或类似的东西。这就是为什么它不费心提供自己的命令式构造，或原始内存访问等等，因为它认为它没有比它运行的主机做得更好。

Answer 2

您的代码可能看起来像一个“基本功能”，但有两个主要问题：

• 您使用了 atom。 Atom 并不像您在 Java 中所了解的那样是可变的，但它是用于管理同步状态的构造，不受竞争条件的影响。所以重置！ 和 swap! 是原子操作，而且速度很慢。看这个例子：

(let [counter (atom 0)]
  (dotimes [x 1000]
    (-> (Thread. (fn [] (swap! counter inc)))
        .start))
  (Thread/sleep 2000)
  @counter)
=> 1000

启动了 1000 个线程，计数器的值增加了 1000 倍，结果是 1000，这并不奇怪。但将其与 易失性！，这不是线程安全的：

(let [counter (volatile! 0)]
  (dotimes [x 1000]
    (-> (Thread. (fn [] (vswap! counter inc)))
        .start))
  (Thread/sleep 2000)
  @counter)
=> 989

另请参阅有关原子的 Clojure 参考。

• 除非您确实需要atoms和易失性，否则您不应该使用它们。也不鼓励使用loop，因为通常有一些更好的函数，它可以完全满足您的需求。您尝试将 Java 函数从字面上重写为 Clojure。 Clojure 需要不同的方法来解决问题，并且您的代码绝对不符合习惯。我建议你不要逐行将Java代码重写为Clojure，而是找到一些简单的问题并学习如何以Clojure的方式解决它们，而不需要atom、易失性！和<代码>循环。

顺便说一下，有 memoize，它可以用于像你这样的例子。

Answer 3

如果您是编程的初学者，我建议您始终假设您的代码是错误的，然后才假设语言/lib/Framework/Platform错误。

看看 fibonacci sequence 在Java和Clojure中的各种实现，您可能会学到一些东西。

Answer 4

正如其他人所指出的那样，将Java代码转换为Clojure的直接翻译相当缓慢地运行。但是，如果我们编写一个斐波那契号生成器，该数字生成器利用了Clojure的优势，我们可以得到一些简短的东西，并且更加惯用其工作。

首先，假设我们需要一个函数，该函数将计算斐波那契序列的第一个数字（1、1、2、3、5、8、13、21、34、55，...）。为此，我们可以使用：

(defn fib [n]
  (loop [a   1
         b   0
         cnt n]
    (if (= cnt 1)
      a
      (recur (+' a b) a (dec cnt)))))

迭代地重新计算“下一个”斐波那契值，直到达到所需的值。

鉴于此函数，我们可以开发一个功能，该功能通过在一系列索引值中映射此函数来创建斐波那契序列值的集合：

(defn fib-seq [n]
  (map #(fib %) (range 1 (inc n))))

但是，这当然是一种计算斐波那契值序列的惊人方法，因为对于每个值，我们都有要计算所有上述值，然后我们只保存最后一个值。如果我们想要一种更有效的方法来计算整个序列，我们可以循环通过可能性，并在集合中收集结果：

(defn fib-seq [n]
  (loop [curr   1
         prev   0
         c      '(1)]
    (if (= n (count c))
      (reverse c)
      (let [new-curr  (+' curr prev)]
        (recur new-curr curr (cons new-curr c))))))

这为我们提供了一种相当有效的方法来收集斐波那契序列的值。对于您通过（FIB 45）（序列的第45个任期是第一个超过999,99999999）的测试：我使用的第一个序列是：

(time (dotimes [n 1000000000](fib-seq 45)))

在我的硬件和操作系统上在17.5秒内完成（Windows 10 ，双处理器Intel I5 @ 2.6 GHz）。