蚊子腿优化+1
用了更适合的字符串做键的关联数组结构：Radix Tree，相比 alist 查找效率更高：
(setq keys (let ((res))
(radix-tree-iter-mappings persistent-cached-load-filter--cache
(lambda (k _v)
(push k res)))
res))
(setq alist (let ((res))
(radix-tree-iter-mappings persistent-cached-load-filter--cache
(lambda (k v)
(push (cons k v) res)))
res))
(benchmark-run 1000
(mapc (lambda (k) (radix-tree-lookup persistent-cached-load-filter--cache k))
keys))
(0.1920724 0 0.0)
(benchmark-run 1000
(mapc (lambda (k) (alist-get k alist nil nil #'equal))
keys))
(0.36645849999999996 0 0.0)
我也试了下 avl-tree，和 alist 差别不是很大…
之前的测试结果是 2.5~2.7s，现在最快能做到 2.4s，但只是测很多次才能测到一次 
1 个赞
好问题x
(setq keys (let ((res))
(radix-tree-iter-mappings
persistent-cached-load-filter--cache
(lambda (k _v) (push k res)))
res))
(setq alist (let ((res))
(radix-tree-iter-mappings
persistent-cached-load-filter--cache
(lambda (k v) (push (cons k (list (copy-sequence (car v)))) res)))
res))
(setq hash (map-into alist 'hash-table))
(benchmark-run 10000
(mapc (lambda (k) (radix-tree-lookup persistent-cached-load-filter--cache k))
keys))
(2.3683929 0 0.0)
(benchmark-run 10000
(mapc (lambda (k) (alist-get k alist nil nil #'equal))
keys))
(4.4762091 1 0.06692140000000002)
(benchmark-run 10000
(mapc (lambda (k) (gethash k hash)) keys))
(0.25930749999999997 0 0.0)
哈希表确实快（我换了个机器所以 radix tree 和 alist 用时与上面不一致）
对于字符串常量的key，检索用哈希肯定是最快的，因为用来哈希的可以是字符串指针的值而不是字符串的值。如果字符串是可变的，那么radix tree仍然不是最快选项，因为它储存了太多的额外信息，需要把它变成一个Patricia Trie来减少比较次数。
btw，搜索文件路径的话，因为这些路径前缀重叠太多了，就算用radix tree，也应该优先考虑用后缀而不是前缀编index。这个用fat pointer会比较好做，可以直接定位到字符串末尾
1 个赞
oh, never waste your life and time on a rosetta algorithm.
1 个赞
@include-yy 要不你把equal换成eq试试呢，应该没影响吧
考虑到包名一般不会太长，从字符串 intern 到符号再用 eq 哈希表感觉和直接用字符串的 equal 哈希表差别不大。
我这个包的目的是减少 load-path-filter-cache-directory-files 调用用时，由于这个函数在 Emacs 启动期间总用时很短（我感觉不会超过 0.2s，load-path 比较长可能最多一两秒），别说哈希表，用 alist 做缓存都能到毫秒级别，继续改成哈希表或者其他数据结构差别不大了。
