common-lisp - EQ 哈希表真的比 SBCL 中的 EQUAL 哈希表更有效吗？

Question

对于哈希表，我一直认为 EQ 比 EQUAL 快得多。但一个简单的测试却给出了相反的结果。任何见解表示赞赏。

(defun random-string (n)
  "Generate a random string of length n."
  (let ((charset "ABCDEFGHIJKLMNOPQRSTUVWXYZ"))
    (iter (repeat n)
          (collect (char charset (random (length charset)))
                   result-type string))))

首先测试 EQUAL 哈希表:

* (defparameter random-strings (iter (for i from 1 to 5000)
                                     (collect (random-string 5))))
RANDOM-STRINGS

* (defparameter ht (make-hash-table :test #'equal :size 10000))
HT

* (dolist (rs random-strings)
    (setf (gethash rs ht) t))
NIL

* (time (dotimes (i 1000000)
          (dolist (rs random-strings)
            (gethash rs ht))))

Evaluation took:
  14.420 seconds of real time
  8.703125 seconds of total run time (8.687500 user, 0.015625 system)
  60.35% CPU
  51,914,146,826 processor cycles
  0 bytes consed

接下来测试 EQ 哈希表:

* (defparameter random-strings (iter (for i from 1 to 5000)
                                     (collect (intern (random-string 5)))))
RANDOM-STRINGS

* (defparameter ht (make-hash-table :test #'eq :size 10000))
HT

* (dolist (rs random-strings)
    (setf (gethash rs ht) t))
NIL

* (time (dotimes (i 1000000)
          (dolist (rs random-strings)
            (gethash rs ht))))

Evaluation took:
  15.309 seconds of real time
  9.500000 seconds of total run time (9.484375 user, 0.015625 system)
  62.06% CPU
  55,112,812,169 processor cycles
  0 bytes consed

Answer 1

[这个答案确实是一个扩展评论。我最近也没有实现这些事情的经验，欢迎有经验的人指正。]

答案是很复杂。它之所以复杂，至少有两个原因:

对于 eq 哈希表，您可能认为可以通过从对象的地址(或对象本身，如果它是直接的，如固定数)计算它来“免费”获得哈希值。除了......垃圾收集器总是重新定位对象，所以现在每次垃圾收集器运行时都必须重新计算对象的哈希值(每秒可能数百次)？我不知道人们对此做了什么，但我想这是大量复杂的权衡。要点是 eq 哈希表并不像在存在复制垃圾收集器的情况下看起来那么简单，而且这种不简单可能会带来成本。

对于equal哈希表，您可能需要计算更复杂的哈希，除非您想要很多冲突。但是计算直接对象向量的哈希值对于现代机器来说是某种最好的情况，它们绝对喜欢线性地遍历内存并对它们发现的每一个东西做一些事情。对于短字符串，这可能快得令人眼花缭乱。

因此计算短字符串的哈希值可能非常快。

最后，在这两种情况下，一旦您计算了该事物的哈希值，您就可以在哈希表的任何结构中查找它，然后您需要检查那里的事物(如果有的话)是否与你已经计算了哈希值的东西。

对于 eq 哈希表，“是否相同”检查非常快。

但是对于 equal 哈希表，仅检查可能会很慢。特别是，很明显，任何类型的 (equal a b) 调用都以 (or (eq a b) ...) 开头。因此，特别是如果您的对象彼此eq或者不相等，那么相等可以确实很快就能成功(如果要失败，这可能会更慢，因为它当然必须做工作)。

这正是您正在做的事情:两个随机字符串不太可能相等，除非它们是eq，并且您的代码:

1. 用字符串填充哈希表；
2. 检查是否存在相同的 (eq) 字符串。

但是，好吧，它们都都在那里，所以可能在几乎所有情况下，您都会遇到等于的好情况(坏情况是两个字符串散列到同一个存储桶，并且至少一次比较会失败，但是良好的哈希表设计将使这种情况很少发生)。