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

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而非transient clojure数据结构。

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

---

查看ArrayList与transients的对比，我并没有发现太多的差异

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))))

(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的transients对比时，我确实看到了显著的差异（慢了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)
      (递归 (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小于c时）
        (.add ^java.util.ArrayList out i)
        ；（递归增加i）
    
```

所以，对于较小的数组大小，从循环中移出ArrayList似乎很重要？

---

反编译`make-al-2`
```
    公共静态对象 invokeStatic（final long c）{
        final 对象 out = new ArrayList();
        对于（long i = 0； i < c； i = Numbers.inc（i））{
            final布尔值 b = ((ArrayList)out).add（Numbers.num（i））？布尔值。真实：布尔值。假；
        }
        返回 out;
    }
```
反编译`make-al`
```
    公共静态对象 invokeStatic（final long c）{
        长 i = 0L；
        对象 out = new ArrayList();
        当（i < c）{
            final布尔值 b = ((ArrayList)out).add（Numbers.num（i））？布尔值。真实：布尔值。假；
            final long inc = Numbers.inc（i）；
            out = out；
            i = inc；
        }
        返回 out;
    }
```

---

我想这与应用程序是正交的，但似乎在ArrayList中使用会产生更快的代码（这似乎只为较小的集合大小有关？）

---

最后，希望当向列表添加一个常数而不是`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))
```

---

对于我的各种用例，如果能够提供从 object[] 数据快速构造路径将会很有帮助。对于持久化向量，创建Owning是完美的，但我认为它不是最优的。

如果你有一个对象数组，应该有非常高效的方式去创建一个向量或者映射 - 比创建transient并遍历它们更有效。例如在映射的情况下，如果你立即创建所有键的哈希码，你应该能够根据哈希码重新排序它们，然后直接通过取哈希码索引数组的子部分来创建HAMT树，而无需大量的迭代循环。

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

如果以上实现良好，那么我可以在json解析的情况下，使持久数据结构优于或与可变数据结构相当，因为我在散列表的情况下必须逐个迭代项目，而不是使用批量创建方法。