Common Lisp中哈希表键相等性测试的性能优化问题

Let me walk through the performance problem I'm tackling with hash tables in Common Lisp, along with the attempts I've made so far and the roadblocks I've hit.

The Initial Problem: Costly Hash Table Equality Checks #

Originally, I was using (equalp ht1 ht2) to verify if two hash tables are equivalent. As we know, equalp checks four things:

• Matching :test parameters for the hash tables
• Identical element counts
• Matching key-value pairs
• Values that are equalp-equivalent

But after profiling with SBCL, I found this check was eating up ~40% of my program's runtime. The kicker? I only need to verify that the two hash tables have identical keys—checks 1, 4, and even parts of 3 are completely unnecessary for my use case.

First Optimization Attempt: Minimal Key-Checking Function #

I wrote a stripped-down function that only validates key consistency:

(defun hash-table-equal-keys (ht1 ht2)
  "Determines if all the keys of two hash tables are the same."
  (and (= (hash-table-count ht1) (hash-table-count ht2))
       (loop for key1 being the hash-keys of ht1
             always (gethash key1 ht2))))

Unfortunately, this barely moved the needle on performance. The optimization was negligible, so I knew I needed to dig deeper into how I'm using hash table keys in the first place.

The Root Issue: Inefficient Key Construction #

My hash table keys are generated from variables that pull values from a fixed set of symbols (like sym1, sym2, etc.). Up until now, I've been using a macro to generate access logic that looks like this:

(gethash (list sym1 sym2 ...) ht)

This approach forces me to use a #'equal hash table (since lists require structural equality checks), and every access involves constructing a new list—adding unnecessary memory allocation and overhead.

Failed Experiment: Switching to Symbol Keys #

I tried reworking the macro to generate key access using concatenated symbol names instead of lists, thinking this would let me use a faster #'eq hash table:

(gethash (intern (concatenate 'string (symbol-name sym1) (symbol-name sym2) ...)) ht)

But this backfired hard—performance dropped drastically. It turns out the cost of dynamically creating symbols via intern and string concatenation is way higher than building lists.

Potential Next Steps I'm Considering #

I'm still brainstorming better approaches, but here are a few ideas I'm looking into:

• Use structs as keys: Define a lightweight struct to hold the symbol combinations, then implement custom hash and equality functions so I can use a #'eq-based test (or a custom fast test) for the hash table. This would eliminate both list construction and string concatenation overhead.
• Precompute symbol combinations: Since my symbols come from a fixed set, I could pre-generate all possible combined symbols at startup. Then runtime access would just reference these pre-made symbols instead of creating them on the fly.
• Try arrays as keys: Arrays can be used with #'equalp (or custom tests), and their construction might have lower overhead than lists. Using a fixed-type array (e.g., :element-type 'symbol) could also speed up hash calculations.

内容的提问来源于stack exchange，提问作者davypough