How can I reuse a gethash lookup in Common Lisp?

Question

I have a hash table where the keys are rather complex lists, with sublists of symbols and integers, and the value should be modified depending on the already existing value. The table is created with :test #'equal.

I do something similar to this a lot:

(defun try-add (i)
  (let ((old-i (gethash complex-list table nil)))
    (if (may-add old-i)
      (push i (gethash complex-list table)))))

Profiling shows that equal tests take a lot of time. I have an optimization idea, that the amount of gethash lookups could be reduced from two to one. It can be done in C++ by reusing the iterator, but not sure how this would be done in Lisp. Any ideas?

Answer 1

Don't do anything special, because the implementation does it for you.

Of course, this approach is implementation-specific, and hash table performance varies between implementations. (But then optimization questions are always implementation-specific.)

The following answer is for SBCL. I recommend checking whether your Lisp's hash tables perform the same optimization. Complain to your vendor if they don't!

What happens in SBCL is that the hash table caches the last table index accessed by GETHASH.

When PUTHASH (or equivalently, (SETF GETHASH)) is called, it first checks whether the key at that cached index is EQ to the key that you are passing in.

If so, the entire hash table lookup routine is by-passed, and PUTHASH stores directly at the cached index.

Note that EQ is just a pointer comparison and hence extremely fast -- it does not have to traverse the list at all.

So in your code example, the is no overhead at all.