Clojure
basic

Clojure transient data structure

2026-02-17 22:00:0020min

Clojure 是一個深受函式編程啟發的程式語言。在函式編程中，有一個很重要的概念：不可變（Immutable）。

因為所有的變數都是不可變的，每次需要改變一個變數的值，都必須要「複製」一份資料後，修改改變的值，並且回傳一個新的結構。

不可變的好處在現代的程式語言開發中已經多次被提及：應用程式的錯誤有很大一部份出現在共享資料改變的副作用上。如果我們可以使用 不可變範式，將每一次的操作限制在一個預期、可控的範圍內，那可以大大的減少這類錯誤的發生時機。

在 Clojure 內操作所有 collection 的方法，都是屬於這一類操作。如：hash map, vector, hash set 等等。

The problem

大多數時候，應用程式內為了不可變性造成的一些效能損失是可以接受的。然而，當效能變成一個非常重大的瓶頸時，無謂的複製可能就變成必須優化的開銷。

不可變範式中一體兩面的問題是，如何兼顧效能？在多數的函數式的編譯器中，會透過類似 linked list 的資料結構，盡可能的減少無 謂的複製發生蘋率。而在 Clojure 當中，除了使用資料結構避免多餘的複製外，另外提出了 transient 這個方法。

什麼是 transient

「如果在一片森林中，倒下一棵樹，會造成聲響嗎？」

「如果在函式內修改函式中的區域變數，並保證產生不可變的結果，這樣可以嗎？」

這是 Clojure 給出的答案。在 clojure 的實作中，當你在呼叫一個函式時（如 assoc），它內部的實作其實是變異（mutate）的， Clojure 會先創件一些array，對它進行變異，最終對它進行持久化（persist）。這麼做的原因當然是為了效能。官網解釋，所有Clojure core 內的變異操作非常小而集中。外部沒辦法看到這些 array 操作。

然而，有某些情況下，你會必須要用非常指令化的方式操作資料。可能是對一個非常巨大的資料結構做轉換、或是複雜的初始化操作，必須分 多個步驟。在這樣的情況下，Clojure 提供的函式可能會造成過多無謂的複製。

clojure 為了這樣的情況提供了 persistent 方法。

怎麼使用用 transient?

transient 是一個一般的函式，支援常見的clojure 集合，如 map、vector 等。

使用時，直接呼叫即可。

;; 宣告一個 transient 版本的 vector。
(transient [])

clojure 中對於collection 的操作函式多數都有一個 transient 臣版本。transient 版本的函式以!結尾。如 conj!。

簡單的對照表如下

persistenttransientmeaning
conjconj!結合函式。將元素新增至 collection中。新增的位置由collection決定。
assocassoc!關聯函式，將 給定的 key & value 關聯至給定的 map 中。
dissocdissoc!回傳不包函給定 key 的 map
disjdisj!回傳 set，刪除指定的元素
poppop!回傳一個 vector，刪除最後一個元素

transient 的用法大致上跟 persistent 版本的用法一模一樣。

  1. 使用 transient 函式宣告 transient 版本的 collection
  2. 使用 transient 版本的函式操作 collection
  3. 最後使用 persistent 函式將 transient 版本的 collection 轉成 persistent 版本。
(defn vrange2 [n]
  (loop [i 0 v (transient [])]
    (if (< i n)
      (recur (inc i) (conj! v i))
      (persistent! v))))

要注意的是，

  1. transient 並非設計來做 bash in place 的操作。所有的操作函式，都不保證結果會與 transient宣告的函式相同，因此， 要記得所有的操作的回傳值都要接住，做為下一次操作的對象。

benchmark

剛好在網路上看到一篇討論 Clojure collection assoc 的效能問題，雖然OP的問題不太一樣，但我借用了這個費佈那希數列的例 子來測試 transient 的效能。


(defn fib
  [s]
  {:pre [(number? s)]}
  (loop [prev 0
         curr 1
         idx 0
         fib-list []]
    (if (< idx s)
      (recur curr (+' curr prev) (+' idx 1) (conj fib-list curr))
      fib-list)))

(defn fib2
  [s]
  {:pre [(number? s)]}
  (loop [prev 0
         curr 1
         idx 0
         lt (transient [])]
    (if (< idx s)
      (recur curr (+' curr prev) (+' idx 1) (conj! lt curr))
      (persistent! lt))))

(defn vrange [n]
  (loop [i 0 v []]
    (if (< i n)
      (recur (inc i) (conj v i))
      v)))

(defn vrange2 [n]
  (loop [i 0 v (transient [])]
    (if (< i n)
      (recur (inc i) (conj! v i))
      (persistent! v))))

(defn -main
  "I don't do a whole lot ... yet."
  [& args]
  (println "vrange 400000 times, transient structuer.")
  (time (vrange2 400000))
  (println "vrange 400000 times, persistent structure.")
  (time (vrange 400000))
  (println "fib 100000 times, using persistent structue.")
  (time (fib 100000))
  (println "fib 100000 times, using transient structure.")
  (time (fib2 100000)))

結果：

vrange 400000 times, transient structuer.
"Elapsed time: 24.316921 msecs"
vrange 400000 times, persistent structure.
"Elapsed time: 42.990531 msecs"
fib 100000 times, using persistent structue.
"Elapsed time: 266.715841 msecs"
fib 100000 times, using transient structure.
"Elapsed time: 186.885538 msecs"

跟 node for loop 版本比較一下。

function fib() {
  const lt = [];
  let prev = 0n;
  let curr = 1n;
  for (let i = 0; i < 100000; i++) {
    lt.push(curr);
    prev = curr;
    curr = curr + prev;
  }
  return lt;
}

console.time("test");
const lt = fib();
console.timeEnd("test");

結果

test: 514.51ms

跟 ava for loop 版本比較

public class FibBigInt {

    public static List<BigInteger> fib(int n) {
        List<BigInteger> lt = new ArrayList<>(n);

        BigInteger prev = BigInteger.ZERO;
        BigInteger curr = BigInteger.ONE;

        for (int i = 0; i < n; i++) {
            lt.add(curr);

            BigInteger next = curr.add(prev);
            prev = curr;
            curr = next;
        }

        return lt;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        List<BigInteger> lt = fib(100000);

        long end = System.currentTimeMillis();

        System.out.println("test: " + (end - start) + " ms");
    }
}

結果：

test: 323 ms

很簡單的比較，可以看到

  1. transient 的確速度有 persistent 快，但小樣本、小資料量來看，其實差距不明顯。
  2. clojure 的速度很優秀。

Conclusion

其實transient 和 persistent 的效能差距比我原本想得還要不明顯。在軟體開發中，過早的思考優化手段有可能是阻礙快速疊代的原。兇。這次的 benchmark 反而讓我有這樣的感覺。

不論如何，clojure 在性能的表現上，得益於執行在 jvm 平台上，可以有跟java 差不多的表現，我覺得另人印象深刻。

Reference