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

Question

在寻找应用程序的执行速度时，当在构建映射和向量时，都会倾向于使用 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

尝试找到根本问题——是关于构建性能吗？还是具体关于数组到持久向量的转换？对于映射，我假设是从数组kv到持久映射的转换？

已经存在一个数组到向量的接口 (into [] arr)，所以这也许真的是关于让它更快（这实际上与我在做的另一件事有关）。对于map，最佳的等效方法可能是 (apply hash-map arr)，但正如你所说，这样会选择一个实现。

Comments

主要是关于提升效率。在处理 data.json 文件时，从 @cnuernber 最近对 dtype-next 的研究中获得灵感，我正在考虑使用 java.util.ArrayList 而不是瞬态的 clojure 数据结构。

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

---

比较 ArrayList 与带有瞬态的 PV，我没有看到多少差异

% java -version
openjdk version "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))))

;; drop 10
(dotimes [_20](time(make-pv 10000000)))
"经过时间：238.714966 毫秒"
"经过时间：139.776764 毫秒"
"经过时间：287.93457 毫秒"
"经过时间：212.816761 毫秒"
"经过时间：337.137074 毫秒"
"经过时间：386.315848 毫秒"
"经过时间：208.427246 毫秒"
"经过时间：291.750425 毫秒"
"经过时间：321.466389 毫秒"

但与使用瞬态的 PersistentMap 相比，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] (时间 (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))
      (recur (inc i) (conj! out i)))

(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> (快速测试 (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> (快速测试 (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> (快速测试 (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> (快速测试 (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> (快速测试 (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]
  (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;
    }
```

---

我认为这与瞬态（transients）比 ArrayList 快或慢的问题无关，但看起来在处理 ArrayList 时，Clojure 编译器能够生成更快的代码（这似乎只对较小的集合大小很重要？）

---

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

---

对于我各种用例，拥有从object[]数据快速构建路径将是有帮助的。对于持久化向量，createOwning执行完美，尽管我认为这并非最优。

如果你事先有对象数组，应该会有创建向量或映射的非常高效的方法 - 比创建临时对象和循环遍历它们更高效。例如，在映射的情况下，如果你立即创建所有键的哈希码，你应该根据哈希码重新排序它们，然后通过仅从hashcode-index数组取子部分，直接创建HAMT树而无需大量迭代循环。

对于持久化向量的情况，应该简单地归结为从输入数组中提取长度为32的子部分，并直接从中创建HAMT，而无需逐元素迭代。此路径允许客户从其他来源快速构建这些数据结构，而无需涉及手动迭代循环。

如果上述实现得当，那么我可以在具有是从迭代数组元素到使用批量创建方法的JSON解析案例中，将持久数据结构的表现优化或与可变数据结构匹配。