Heavenly delights of hashing numbers under EQUALP

The author experimented with optimizing hash tables and hash functions in ECL. This led to developing a new implementation of hash tables and hash functions. Two main outcomes were achieved: first, bar graphs were generated to compare different benchmarks; second, a few issues with hashing various Common Lisp predicates were addressed, particularly consistent hashing of numbers under the predicate #EQUALP.

The discussion assumes binary floats with a radix of two, which is the float representation used in ECL. The author explains that Common Lisp allows specifying different hash table tests, with #EQUALP being the most interesting one as it considers numbers with different representations equal if they are numerically equal. The hash functions must produce consistent and non-lossy results while being consistent with the #EQUALP test.

The author outlines the mathematical equivalence of numbers in Common Lisp, specifically complex numbers and the relationship between rational and float objects. Several hashing approaches are proposed, ranging from a naive approach that always returns a hash of 42 to a more precise approach that introduces canonicalization rules for FIXNUM and BIGNUM.

The author argues that the latter approach, although more complex, ensures correct correspondence between integers and floats and provides better performance for most workloads.