Clojure Set 与 Map Lookup 性能差异

Question

我有一个 uid 列表，想要检查某个 uid 是否是该列表的成员

实现它的自然方法是创建一组 (clojure.set) uids 并在该列表中搜索该成员

我发现映射键查找要快得多 - 我使用以下代码片段对两种方法进行基准测试:

(def uids #{:a :b :c :d :e :f :g :h :i :j :k :l :m :n :o :p :a1 :b1 :c1 :d1 :e1 :f1 :h1 :i1 :j1 :k1 :l1 :m1 :n1 :o1 :p1})
(def uids-map (reduce (fn [acc v] (assoc acc v true)) {} uids))
(time (dotimes [i 1000000] (:o1 uids)))
;user=> "Elapsed time: 191.076266 msecs"
(time (dotimes [i 1000000] (:o1 uids-map)))
;user=> "Elapsed time: 38.159388 msecs"

各次调用的结果非常一致 - 映射查找大约占集合查找的 1/5

那么设置对于键查找不是最佳的还是我使用它的方式错误？

此外，这些基准测试存在差异的原因是什么？

我的印象是，在 clojure 中，集合是作为类似于向量的关联数据结构实现的 - 那么为什么键查找比简单的映射慢得多？

Answer 1

我从未研究过 clojure 的源代码，但从我看到的 set 实现 actually uses a map inside :

protected APersistentSet(IPersistentMap impl){
    this.impl = impl;
}

它还委托(delegate) invoke调用内部 map 。

在 APersistentSet :

public Object invoke(Object arg1) {
    return get(arg1);
}

// ....

public Object get(Object key){
    return impl.valAt(key);
}

在 APersistentMap :

public Object invoke(Object arg1) {
    return valAt(arg1);
}

public Object invoke(Object arg1, Object notFound) {
    return valAt(arg1, notFound);
}

所以这无法解释差异。

如mentioned in the comments作者@cgrand，当我们反转参数时，速度更快(并且大约相同，因为我们立即调用 set 的 invoke )。于是我抬头看Keyword的invoke这可能是用于 (:k obj):

final public Object invoke(Object obj, Object notFound) {
    if(obj instanceof ILookup)
        return ((ILookup)obj).valAt(this,notFound);
    return RT.get(obj, this, notFound);
}

需要注意的重要一点是ILookup在 APercientMap 中实现(通过 Associative )，但不在 APercientSet 中实现。也可以在clojure中验证:

(instance? clojure.lang.ILookup #{}) ;; false
(instance? clojure.lang.ILookup {})  ;; true

所以 map 会经过“快乐路径”并最终到达 RT.get我相信这是运行时。

让我们看看运行时。

它最初尝试做与关键字几乎相同的事情:

static public Object get(Object coll, Object key){
    if(coll instanceof ILookup)
        return ((ILookup) coll).valAt(key);
    return getFrom(coll, key);
}

但是由于我们知道集合没有实现 ILookup 我们知道它们会转到 RT.getFrom :

static Object getFrom(Object coll, Object key){
    if(coll == null)
        return null;
    else if(coll instanceof Map) {
        Map m = (Map) coll;
        return m.get(key);
    }
    else if(coll instanceof IPersistentSet) {
        IPersistentSet set = (IPersistentSet) coll;
        return set.get(key);
    }
    else if(key instanceof Number && (coll instanceof String || coll.getClass().isArray())) {
        int n = ((Number) key).intValue();
        if(n >= 0 && n < count(coll))
            return nth(coll, n);
        return null;
    }
    else if(coll instanceof ITransientSet) {
        ITransientSet set = (ITransientSet) coll;
        return set.get(key);
    }

    return null;
}

这让我相信主要区别是由于集合未实现 ILookup 而导致额外的委托(delegate)和 instanceof 调用。

作为奖励，我在一组实现 ILookup 上添加了一个测试，并立即将 valAt 委托(delegate)给内部映射(使用 proxy)这稍微缩小了差距:

(def uids #{:a :b :c :d :e :f :g :h :i :j :k :l :m :n :o :p :a1 :b1 :c1 :d1 :e1 :f1 :h1 :i1 :j1 :k1 :l1 :m1 :n1 :o1 :p1})
(def uids-map (into {} (for [k uids] [k k])))
(def lookupable-set (proxy [clojure.lang.APersistentSet clojure.lang.ILookup] [uids-map]
                      (valAt [k] (get uids-map k))))

;; verify
(instance? clojure.lang.APersistentSet lookupable-set) ;; true
(instance? clojure.lang.ILookup lookupable-set) ;; true

(time (dotimes [i 1000000] (:o1 uids))) ;; 134.703101 msecs
(time (dotimes [i 1000000] (:o1 lookupable-set))) ;; 63.187353 msecs  <-- faster
(time (dotimes [i 1000000] (:o1 uids-map))) ;; 35.802762 msecs <-- still fastest

总结:在性能很重要的地方 - 调用集合 (#{...} k) 而不通过关键字 (k #{...}) 是和 map 一样快。

但我可能是错的:)