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

Question

在寻找应用程序的执行速度时， constructing maps and vectors时使用 java.util.ArrayList 是诱人的。但这样做的确有一些陷阱。例如，对于向量，不清楚是否应该使用 LazilyPersistentVector/createOwning 而不是 PersistentVector/adopt，前者可以正确工作，而后者只能处理小于32个元素的向量。

类似地，对于映射，如果映射中少于9个条目，可以选择创建一个 PersistentArrayMap，但如果有9个或更多条目，则应使用 PersistentHashMap。

我不希望在这里规定解决方案，但 clojure.core 中有几个函数，它们接受数组作为参数并返回适当的数据结构
(array->vector arr) ;; 与LazilyPersistentVector/createOwning做同样的工作 (array->map arr) ;; 根据大小返回PAM或PHM

Answer 1

试图找到根本问题——这是关于构建性能吗，或者专门是关于array -> 持久向量？对于映射，我假设它是数组 kv -> 持久映射？

已有 array -> vector 的接口 (into [] arr)，所以也许这实际上关于使其更快（这实际上与我现在正在工作的另一个项目有关）。对于映射，最好的等效操作可能是 (apply hash-map arr)，但它选择实施方式，正如您所说。

Comments

主要关于使 things 更快的问题。我在 data.json 上进行了一些试玩，并从 @cnuernber 在 dtype-next 上的近期工作中获得了一些灵感，检查了一下使用 java.util.ArrayList 而不是瞬态 clojure 数据结构。

在存储 maps 的东西时，我按照 [k1, v1, k2, v2...] 格式存储数据

---

を見ると，ArrayList 与を渡す瞬态と JSON レスポンス形式、HTTP レスポンスステータスを変更するGitHubでのコミットで、いくつかの重要な計画が進展しています

% java -version
openjdk 版本 "17.0.1" 2021-10-19
OpenJDK Runtime Environment Temurin-17.0.1+12 (build 17.0.1+12)
OpenJDK 64-Bit Server VM Temurin-17.0.1+12 (build 17.0.1+12, mixed mode, sharing)
% 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 msecs"
"消耗时间: 287.93457 msecs"
"消耗时间: 212.816761 msecs"
"消耗时间: 337.137074 msecs"
"消耗时间: 386.315848 msecs"
"消耗时间: 208.427246 msecs"
"消耗时间: 291.750425 msecs"
"消耗时间: 321.466389 msecs"
"消耗时间: 251.875222 msecs"

但是，在查看 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 msecs"
"消耗时间: 719.626631 msecs"
"消耗时间: 664.274403 msecs"
"消耗时间: 718.46743 msecs"
"消耗时间: 880.380957 msecs"
"消耗时间: 735.682114 msecs"
"消耗时间: 611.627886 msecs"
"消耗时间: 775.128433 msecs"
"消耗时间: 537.130159 msecs"
已过时间：775.980626 毫秒


(定义 make-pm [^long c]
  (loop [i 0
         out (transient {})]
      (if (< i c)
      (递归 (inc i) (assoc! out i i))
      (persistent! out))))

(dotimes [_ 20] (时间 (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 %)
    低严重级别     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 %)
    低严重级别     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))
评估次数：12 在 6 个样本中的 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]
  (创建一个音频利链表 [out (java.util.ArrayList.)])
    (循环 [i 0])
      (当 (< i c) 时)
          (.add ^java.util.ArrayList out i)
        (递归 (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;
    }
```

---

我认为这关于瞬态是否比.ArrayLists 快或慢是正交的，但似乎与用.ArrayLists 工作一样，让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))
评估次数：18次，来自3个调用样本的6个样本。
             执行时间平均值：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对于持久向量来说已经很理想了，但我认为它还不是最优化。

如果你有对象数组在前面，应该有非常高效的方法来创建向量或映射 - 比创建短暂并循环它们更有效率。例如，在映射的情况下，如果你立即创建所有键的哈希码，你应该能够根据哈希码来排序它们，然后直接通过简单从哈希码索引数组的子部分创建HAMT树而不需要太多的迭代循环。

对于持久向量的情况，应该简化为从输入数组中取长度为32的子部分，并直接从这些创建hamt，而不进行逐个元素的迭代。

如果上述实现得当，那么我可以使持久数据结构在JSON解析情况下优于或匹配可变数据结构，因为我在哈希表的情况下必须逐个元素迭代，而不是使用批量创建方法。