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

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)，所以这可能真的是关于让它更快（这实际上与我现在正在工作中的一些事情相交集）。对于映射来说，可能最好的等效操作是 (apply hash-map arr)，但这会根据您所说的选择一个实现。

Comments

主要是关于让事情更快。通过对 data.json 进行操作并从 @cnuernber 的最近工作 dtype-next 中获得一些灵感，我在考虑使用 java.util.ArrayList 而不是临时的 clojure 数据结构。

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

---

比较 ArrayList 与 PV 的 transient 差异，我看不出很大的区别

% java -version
openjdk version "17.0.1" 2021-10-19
OpenJDK 运行时环境 Temurin-17.0.1+12 (构建 17.0.1+12)
OpenJDK 64 位服务器 VM Temurin-17.0.1+12 (构建 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)))
   
;; 丢弃 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)))

;; 丢弃 10
"经过时间: 238.714966 毫秒"
"经过时间: 139.776764 毫秒"
"经过时间: 287.93457 毫秒"
"经过时间: 212.816761 毫秒"
"经过时间: 337.137074 毫秒"
"经过时间: 386.315848 毫秒"
"经过时间: 208.427246 毫秒"
"经过时间: 291.750425 毫秒"
"经过时间: 321.466389 毫秒"
"经过时间: 251.875222 毫秒"

但在比较 HashMap 与 PersistentMap 的 transient 时，我确实看到了一个显著的差异（慢了 10 倍）

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

（dotimes [_ 20] (时间（创建-hm 10000000））

;; 丢弃 10
“已用时间：949.351029毫秒”
“已用时间：719.626631毫秒”
“已用时间：664.274403毫秒”
“已用时间：718.46743毫秒”
“已用时间：880.380957毫秒”
“已用时间：735.682114毫秒”
“已用时间：611.627886毫秒”
“已用时间：775.128433毫秒”
“已用时间：537.130159毫秒”
“已用时间：775.980626毫秒”


（defn 创建-pm [^long c]
  (loop [i 0
         out (临时 {}）
    (if (< i c)
      （递归（inc i）（assoc! out i i））
        (persistent! out))))

（dotimes [_ 20] (时间（创建-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> (快速测试（创建-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> (快速测试（创建-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> (快速测试（创建-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> (快速测试（创建-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> (快速测试（创建-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 样本中 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))
```

因此，对于较小的尺寸，将 ArrayList 从循环中移出似乎很重要？

---

反编译 `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> (快速测试（创建-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次调用。
执行时间平均值：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 是完美的，虽然我认为它并不完美。

如果您事先就有对象的数组，应该有极高效的方式来创建向量或映射，比创建 transient 并遍历它们更高效。例如，在映射的情况下，如果您立即创建所有键的哈希码，您应该能够根据哈希码重新排序它们，然后直接通过仅采用哈希码索引数组的子部分来创建 HAMT 树，而无需进行大量迭代循环。

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

如果以上实现良好，那么我可以在 JSON 解析用例中将持久数据结构的表现或匹配可变数据结构，因为我必须逐项遍历哈希表，而不是使用批量创建方法。