安全构建持久性数据结构的接口

Question

在寻找应用程序中的执行速度时，构造映射和向量时都会倾向于使用java.util.ArrayList。然而，这样会有一些陷阱。例如，对于向量，并不明显使用LazilyPersistentVector/createOwning（前者工作正常）会比使用如PersistentVector/adopt（只有当向量大小小于32时才有效）更合适。

同理，对于映射，如果有少于9个条目，可以选择创建一个PersistentArrayMap；如果条目有9个或更多，则应使用PersistentHashMap。

我不打算指定解决方案，但有一些在clojure.core中的函数，它们接受数组作为参数并返回适当的数据结构
(array->vector arr) ;; 与LazyPersistentVector/createOwning的功能相同 (array->map arr) ;; 根据大小返回PAM或PHM

Answer 1

在这里尝试找到根本问题 - 是关于构建性能，还是具体关于数组 -> 持久向量？对于映射，我假设它是一个kv数组的映射 -> 持久映射？

已经有一个数组 -> 向量的接口 (into [] arr)，所以可能真正的问题是让它更快（这实际上与我目前正在进行的其他工作有所交集）。可能最好的映射等价是(apply hash-map arr)，但是它会像你说的那样选择实现。

Comments

主要关于让事物更快。在玩弄 data.json 并从 @cnuernber 就最近的 dtype-next 工作中获得一些灵感后，我检查了使用 java.util.ArrayList 而不是瞬态 clojure 数据结构。

在存储映射的数据时，我以 [k1, v1, k2, v2...] 格式存储数据

---

观察 ArrayList 与 PV hole 的透明度，我看不到太大的差异

% java -version
openjdk 版本 "17.0.1" 2021-10-19
OpenJDK 运行时环境 Temurin-17.0.1+12 (build 17.0.1+12)
OpenJDK 64 位服务器 VM Temurin-17.0.1+12 (build 17.0.1+12，混合模式，共享)
% clj -Sdeps '{:deps {org.clojure/clojure {:mvn/version "1.11.1"}}}'
Clojure 1.11.1

(defn make-al [^long c]
  (loop [i 0
         out (java.util.ArrayList.)]
    (if (< i c)
      (do
        (.add ^java.util.ArrayList out i)
          recur (inc i) out))
       out)))

(dotimes [_ 20] (time (make-al 10000000)))
   
;; drop 10
"已过时间：118.936307 毫秒"
"已过时间：378.941495 毫秒"
"已过时间：451.090741 毫秒"
"已过时间：231.632739 毫秒"
"已过时间：533.601017 毫秒"
"已过时间：178.208623 毫秒"
"已过时间：566.648574 毫秒"
"已过时间：223.109572 毫秒"
"已过时间：404.011696 毫秒"
"已过时间：374.543087 毫秒"

(defn make-pv [^long c]
  (loop [i 0
         out (transient [])]
    (if (< i c)
      (recur (inc i) (conj! out i))
       (persistent! out))))

(dotimes [_ 20] (time (make-pv 10000000)))

;; drop 10
"已过时间：238.714966 毫秒"
"已过时间：139.776764 毫秒"
"已过时间：287.93457 毫秒"
"已过时间：212.816761 毫秒"
"已过时间：337.137074 毫秒"
"已过时间：386.315848 毫秒"
"已过时间：208.427246 毫秒"
"已过时间：291.750425 毫秒"
"已过时间：321.466389 毫秒"
已用时间：251.875222 毫秒

但是，对比 HashMap 和 PersistentMap（使用瞬态属性），我确实看到了显著的差异（慢了10倍）

(defn make-hm [^long c]
  (loop [i 0
         out (java.util.HashMap.)]
    (if (< i c)
      (do
        (.put ^java.util.HashMap out i i)
          recur (inc i) out))
       out)))

(dotimes [_ 20] (time (make-hm 10000000)))

;; drop 10
已用时间：949.351029 毫秒
已用时间：719.626631 毫秒
已用时间：664.274403 毫秒
已用时间：718.46743 毫秒
已用时间：880.380957 毫秒
已用时间：735.682114 毫秒
已用时间：611.627886 毫秒
已用时间：775.128433 毫秒
已用时间：537.130159 毫秒
已用时间：775.980626 毫秒


(defn make-pm [^long c]
  (loop [i 0
         out (transient {})]
    (if (< i c)
      (recur (inc i) (assoc! out i i))
       (persistent! out))))

(dotimes [_ 20] (time (make-pm 10000000)))

已用时间：5129.976085 毫秒
已用时间：5626.573669 毫秒
已用时间：5337.985317 毫秒
已用时间：5151.215195 毫秒
已用时间：5175.246837 毫秒
已用时间：5636.8717 毫秒
已用时间：5136.285851 毫秒
已用时间：5270.226782 毫秒
已用时间：5018.800694 毫秒
已用时间：5394.596752 毫秒

据此，我认为考虑如何使后者更快是有意义的。

---

列表示例似乎更有趣
```
clojure.data.json-perf-test> (quick-bench (make-pv 20))
评估次数：2706714 次，在 6 个样本中，每个样本 451119 次。
              平均执行时间：218.595632 纳秒
    执行时间标准差：1.125857 纳秒
   执行时间下四分位数：216.403707 纳秒 ( 2.5%)
   执行时间上四分位数：219.447999 纳秒 (97.5%)
             开销使用：2.124369 纳秒

在 6 个样本中找到 1 个异常值（16.6667 %）
    low-severe     1 (16.6667 %)
 异常值方差：13.8889 %，方差因异常值而适度膨胀
;; => nil
clojure.data.json-perf-test> (quick-bench (make-al 20))
评估次数：5192388 次，在 6 个样本中，每个样本 865398 次。
             平均执行时间：116.527862 纳秒
    执行时间标准差：5.242512 纳秒
   执行时间下四分位数：113.078599 纳秒 ( 2.5%)
   执行时间上四分位数：125.437194 纳秒 (97.5%)
             开销使用：2.124369 纳秒

在 6 个样本中找到 1 个异常值（16.6667 %）
    low-severe     1 (16.6667 %)
 异常值方差：13.8889 %，方差因异常值而适度膨胀
;; => nil
clojure.data.json-perf-test> (quick-bench (make-al-2 20))
评估次数：8299938 次，在 6 个样本中，每个样本 1383323 次。
             平均执行时间：73.889678 纳秒
    执行时间标准差：4.373601 纳秒
   执行时间下四分位数：70.739550 纳秒 ( 2.5%)
   执行时间上四分位数：80.056859 纳秒 (97.5%)
             开销使用：2.124369 纳秒
;; => nil
clojure.data.json-perf-test> (quick-bench (make-pv 10000000))
评估次数：6 次，在 6 个样本中，每个样本 1 次。
             平均执行时间：167.649450 毫秒
    执行时间标准差：50.505810 毫秒
   执行时间下四分位数：105.608206 毫秒 ( 2.5%)
   执行时间上四分位数：228.341248 毫秒 (97.5%)
             开销使用：2.124369 纳秒
;; => nil
clojure.data.json-perf-test> (quick-bench (make-al 10000000))
评估次数：6 次，在 6 个样本中，每个样本 1 次。
             执行时间平均值：149.405623 毫秒
    执行时间标准差：146.660162 毫秒
   执行时间下四分位数：64.432956 毫秒（2.5%）
   执行时间上四分位数：332.819503 毫秒（97.5%）
             开销使用：2.124369 纳秒
;; => nil
clojure.data.json-perf-test> (quick-bench (make-al-2 10000000))
评估次数：在6个样本中的12次，平均每次调用2次。
             执行时间平均值：145.689554 毫秒
    执行时间标准差：71.749785 毫秒
   执行时间下四分位数：46.855186 毫秒（2.5%）
   执行时间上四分位数：223.408978 毫秒（97.5%）
             开销使用：2.124369 纳秒
;; => nil

```
定义 `make-al-2` 如下
```
(defn make-al-2 [^long c]
  (let [out (java.util.ArrayList.)]
    (loop [i 0]
      (when (< i c)
        (.add ^java.util.ArrayList out i)
        (recur (inc i))))
    out))
```

因此，对于较小的尺寸，将数组列表移出循环似乎很重要？

---

反编译 `make-al-2`
```
    public static Object invokeStatic(final long c) {
        final Object out = new ArrayList();
        for (long i = 0L; i < c; i = Numbers.inc(i)) {
            final Boolean b = ((ArrayList)out).add(Numbers.num(i)) ? Boolean.TRUE : Boolean.FALSE;
        }
        return out;
    }
```
反编译 `make-al`
```
    public static Object invokeStatic(final long c) {
        long i = 0L;
        Object out = new ArrayList();
        while (i < c) {
            final Boolean b = ((ArrayList)out).add(Numbers.num(i)) ? Boolean.TRUE : Boolean.FALSE;
            final long inc = Numbers.inc(i);
            out = out;
            i = inc;
        }
        return out;
    }
```

---

我认为这和临时实例比 ArrayList 更快或更慢的问题无关，但似乎与处理 ArrayList 有关，使得 Clojure 编译器可以生成更快的代码（这似乎只对较小的集合大小有影响？）

---

最后，当向列表添加一个常量而不是`i`时，事情会变得更多。
```
clojure.data.json-perf-test> (quick-bench (make-pv 10000000))
评估次数：6 次，在 6 个样本中，每个样本 1 次。
             平均执行时间：112.911790 毫秒
    执行时间标准差：16.622923 毫秒
   执行时间下四分位数：100.571915 毫秒（2.5%）
   执行时间上四分位数：132.719706 毫秒（97.5%）
             开销使用：2.124369 纳秒
;; => nil
clojure.data.json-perf-test> (quick-bench (make-al-2 10000000))
评估次数：在6个样本中的3个调用，共18次。
             平均执行时间：48.052989 毫秒
    执行时间标准差：7.951804 毫秒
   执行时间下四分位数：39.031470 毫秒（2.5%）
   执行时间上四分位数：58.394364 毫秒（97.5%）
             开销使用：2.124369 纳秒
;; => nil
clojure.data.json-perf-test＞;
```

```
(defn make-pv [^long c]
   (let [])
   (loop [i 0
          out (transient [])]
     (if (< i c)
       (recur (inc i) (conj! out "3"))
       (persistent! out))))
```
```
 (defn make-al-2 [^long c]
   (let [out (java.util.ArrayList.)]
     (loop [i 0]
       (when (< i c)
         (.add ^java.util.ArrayList out "3")
         (recur (inc i))))
     out))
```

---

对于我各种用例，拥有从对象[]数据中快速构建路径将非常有用。虽然createOwning对于持久向量来说是完美的，但我认为它还不是最优的。

如果你提前有对象数组，应该有极其高效的方式创建向量或映射——比创建transient然后遍历它们更有效。例如，在映射的情况下，如果你立即创建所有键的哈希码，你应该能够根据哈希码重新排序它们，然后通过直接从哈希码索引数组的子段中创建HAMT树，而无需太多的迭代循环。

对于持久向量的情况，应该减少为从输入数组中使用长度为32的子段，并直接从这些子段中创建hamt，无需逐元素迭代。该路径允许客户端从其他来源快速构建这些数据结构，而不涉及手动迭代循环。

如果以上实现良好，那么我可以使持久数据结构在JSON解析场景下超越或匹配可变数据结构，因为我必须在哈希表场景下逐项迭代，而不是使用批量创建方法。