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

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的比较时，我没有看到太大的差异。

% 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与带transients的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)))

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


(定义 make-pm [^长 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%）
    低严重性     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]
  (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))
评估次数：在 3 次调用中的 6 个样本中 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 是完美的，尽管我认为它并不是最优的。

如果你事先有对象数组，应该有非常高效的方式创建向量和映射——比创建临时对象然后循环遍历更高效。例如，在映射的情况下，如果你立即创建所有键的哈希码，你应该能够根据哈希码重新排序它们，然后直接创建 HAMT 树，而无需大量的迭代循环，只需从哈希码索引数组中取子集即可。

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

IF 实现得当，那么我可以在 json 解析的情况下让持久数据结构比可变数据结构表现出色或匹配，因为我必须逐个迭代散列表中的项，而不是使用大量创建方法。