Heavenly delights of hashing numbers under EQUALP

Written on 2026-10-26 by Daniel Kochmański. Tagged as: lisp, c.

Some time ago I decided to dust off my fast generic function dispatch work for ECL. But before merging that, I decided to optimize the table-based dispatch to have a good measure of how much better or worse it is and that opened a whole can of worms, including a new implementation of hash tables and hash functions.

I know, that's a new level of traversing absurdly nested rabbit holes. There are two good outcomes of this:

Regarding the first point, here are a few bar graphs generated using polyclot, a work-in-progress McCLIM tool for plotting data (less is better):

Figure 1: SLOT-ACCESS/READER - standard reader benchmark (work in progress).

Figure 2: HTABLE-MIXBAG - EQUALP benchmark with randomized keys.

Figure 3: HTABLE-SETREM - benchmark for interleaved insert and remove.

Figure 4: HTABLE-SMALL-STRING - EQUALP benchmark with short strings.

As for the second point, while working on hashing under various Common Lisp predicates, I decided to bite the bullet and fix a few ugly parts of ECL. Most notably consistent hashing of numbers under the predicate #'EQUALP. The topic is interesting enough to deserve a separate note. In this post I'm assuming binary floats (the float radix is two). This is the float representation used in ECL.

A quick recap about Common Lisp and hash tables. The standard prescribes that conforming implementations must allow specifying the hash table tests EQ, EQL, EQUAL and EQUALP. The last test is interesting, because numbers with different representations are considered to be EQUALP when they are =. For example:

(equalp 1 1.0) ; -> T (equalp 1/2 0.5) ; -> T (equalp 1/3 (float 1/3)) ; -> NIL (equalp 42 #C(42.0 0.0)) ; -> T

It is worth noting, that hashing can be lossy, but it can't be inconsistent with the test. In other words this is a conforming hash function under #'EQUALP:

;; (equalp 1 1.0) ; is true ;; (= (hash-equalp 1) (hash-equalp 1.0)) ; is true

(defun hash-equalp (x) (typecase x (real 42) (complex (if (zerop (imagpart x)) (hash-equalp (realpart x)) 13)) (otherwise 15)))

While this function is not conforming, because there are objects that are the same under the test and have different hashes:

;; (equalp 1 1.0) ; is true ;; (= (hash-equalp 1) (hash-equalp 1.0)) ; is false

(defun hash-equalp (x) (typecase x (rational 1337) (float 7117) (complex (if (zerop (imagpart x)) (hash-equalp (realpart x)) 13)) (otherwise 15)))

In other words, when two objects are equal under the supplied test, they must produce the same hash, but two objects having the same hash does not imply that they are equal under the supplied test.

Naive hashes, while conforming, miss the point. A good hashing function tries to produce different hashes for objects that are not equivalent under the predicate with a good bit distribution to ensure good hash table performance.

Note that when complex floats have specialized representation, then there may be multiple subtypes specialized to single-float, double-float etc. Numbers are #'= to each other when their value is mathematically the same, regardless of the underlying representation. That's a wonderful quality when you do math :-).

This quality is not so wonderful, when you want to produce good hashes under the predicate #'EQUALP (that boils down to #'= for numbers). We need to construct a function that will produce the same hashes with good quality for equal objects.

The biggest hurdle comes from the gap between representations of RATIONAL and FLOAT objects. Conventionally representations are

Fixnums, bignums and ratios are disjoint under #'=. That leaves us with questions:

When are two complex numbers mathematically equal?

This one is easy. Two complex numbers are equal when their real parts are equal and their imaginary parts are equal.

When are two floats mathematically equal?

To resolve this question we can cast the float with smaller precision to the float with bigger one and compare bits. There is a gotcha in that -0.0 is not EQL to +0.0, but it is always = to it, so we should canonicalize zeros first.

When is an integer mathematically equal to a float?

When the float has no fractional part and integers are equal.

This is the most interesting question. To answer it, we need to dive a bit deeper into float representation.

Finite binary float values conceptually are represented as:

This corresponds to dyadic rationals, that is rational numbers whose denominator is a power of two:

In other words a float and a ratio may be equal only when the ratio is dyadic, otherwise the ratio value can't be represented as a binary float (this post assumes that we operate on binary floats - with radix=2).

That sums up the recap about mathematical equivalence and numeric tower in Common Lisp.

The easiest, yet useless, approach is to always return a hash 42. It is adequate because that is the canonical answer to the most important question.

The easy and useful approach relies on the observation that hashing is lossy. All real numbers are coerced to a float precision and hashed. When the rational number does not fit in the float precision, then we hash its approximation. We need to remember to canonicalize -0.0 to +0.0 and to disable floating point exceptions for cases like overflows and underflows.

#define hash_single_float(h,v) hash_float((h), (double)(v)) #define hash_double_float(h,v) hash_float((h), (double)(v))

static inline void hash_float(cl_hashstate *h, double v) { if (v==-0.0) v=0.0; hash_data(h, &v, sizeof(v)); }

static inline void hash_long_float(cl_hashstate *h, long double v) { ECL_WITHOUT_FPE_BEGIN { hash_float(h, (double)(v)); } ECL_WITHOUT_FPE_END; }

#define hash_fixnum(h,x) hash_float((h),(double)ecl_fixnum(x)) #define hash_bignum(h,x) hash_rational((h),(x)) #define hash_ratio(h,x) hash_rational((h),(x))

static inline void hash_rational(cl_hashstate *h, cl_object x) { ECL_WITHOUT_FPE_BEGIN { double v = ecl_to_double(x); hash_float(h, v); } ECL_WITHOUT_FPE_END; }

This model is conceptually obvious, very maintainable, reasonably fast, and there are relatively few collisions under the usual workload. We pay for it in a few ways:

This list is ranked by importance as I see it. The main reason I've kept digging deeper is that it was not to my taste. Then we had impracticality for serious workloads, finally microoptimizations. I believe that the general audience has these priorities in a reversed order.

A harder but more precise way to hash numbers under the predicate #'EQUALP is to introduce canonicalization rules:

In the case of FIXNUM we hash its value (a word without the tag) and in the case of BIGNUM we hash the sign and its limbs.

Finite floats without the fractional part are hashed as integers

Ensures INTEGER <-> FLOAT correspondence. We can't cast LONG-FLOAT to DOUBLE-FLOAT and then cast to integer, because we'd miss many BIGNUM values. Caveat: with this approach big floats may cons full bignums.

Floats that are not integers are cast to DOUBLE-FLOAT and hashed

Ensures X-FLOAT <-> Y-FLOAT correspondence. This approach is lossy for long floats if they have more bits than double floats, but simplifies the implementations because long double has a few "loose" bits that may differ between numbers with the same value.

NaNs and infinities are hashed like other doubles because infinities are exact and NaN is never #'= to anything.

Ensures FLOAT <-> RATIO correspondence. For simplicity we don't try to determine whether RATIO is representable as DOUBLE-FLOAT – if it is too big or too small, it will be represented either as a 0 or as an infinity.

We hash the numerator and denominator separately.

Complex floats with (ZEROP (IMAGPART X)) are hashed as (HASH (REALPART X))

Because (= 3 #c(3.0 0.0)) we need to canonicalize (complex float) while rational complex numbers are canonicalized implicitly. Other complexes are hashed as pairs, that is we hash the real part and imaginary part separately.

This approach results in fewer collisions and is fairly straightforward. Here is the pseudocode:

(defun hash-equalp-number (state number) (typecase number (fixnum (hash-word state number)) (bignum (hash-data state (signum number) (limbs number))) (float (if (and (finitep number) (is-integer-p number)) (hash-equalp-number state (rational number)) ;; INV -0.0 and +0.0 are hashed as integers. (hash-data state (coerce number 'double-float)))) (ratio (if (dyadic-ratio-p number) ;; INV may produce infinity or zero (that's fine) ;; Disable float overflow and underflow traps. (hash-data state (coerce number 'double-float)) (progn (hash-equalp-number state (numerator number)) (hash-equalp-number state (denominator number))))) (complex (if (zerop (imagpart number)) (hash-equalp-number state (realpart number)) (progn (hash-equalp-number state (realpart number)) (hash-equalp-number state (imagpart number)))))))

2.1. Implementation bites

My initial implementation cast all floats to integers. When I was comparing ECL to other implementations I was wondering why we are so slow compared to others. The key insight came after the realization that randomized keys in the form (random 20.0) were collapsed to only 20 distinct hashes.

Fixing that and giving non-integer floats distinct hashes gave ECL the most noticeable boost on the HTABLE-MIXBAG benchmark (included at the beginning) – the new version is 100x faster than the old one.

While implementing a test suite that ensured that hashes for bignums, dyadic ratios, and corresponding floats matched, I've discovered a non-obvious bug pertaining to casting double floats to integers. The code looked like this:

if (d<=MOST_POSITIVE_FIXNUM && d>=MOST_NEGATIVE_FIXNUM) return to_fixnum(d); else return to_bignum(d);

But the MOST_POSITIVE_FIXNUM value on x86-64 is 261-1. In other words, to represent this number exactly as a double, we need 61 significant bits. That's a shame because double has 53 significant bits, so MOST_POSITIVE_FIXNUM, when converted to double, rounds to 261 and that can't fit in a fixnum. After promotion the incorrect code is equivalent to:

if (d<=(1LL<<61) && d>=MOST_NEGATIVE_FIXNUM) return to_fixnum(d); else return to_bignum(d);

Oops, double is accidentally cast to fixnum when it is 261. That's clearly a problem! After finding the issue, the solution is easy. We need to find an exact double that is the boundary. Note that integers are implemented as two's complement, so the most negative fixnum was alright in our case:

double limit = ldexp(1.0, ECL_FIXNUM_BITS-ECL_TAG_BITS-1); if (d<limit && d>=-limit) return to_fixnum(d); else return to_bignum(d);

This fix is correct, yet it revealed another bug. But that's a different story to tell.

The approach above is correct and nice, but has a few important flaws:

After the initial implementation it bugged me enough that I've decided to come up with a new hashing scheme for numbers under the predicate EQUALP. The rules are also simpler (at least conceptually):

The representation [SIGN MANTISSA EXPONENT] does not require us to convert between types and it is very compact. Moreover it is very precise and doesn't produce unnecessary collisions. On the other hand it requires extra work to normalize tuples. Here is the pseudocode:

(defun hash-equalp-number (state number) (typecase number (integer (multiple-value-bind (s m e) (compute-integer-dyad number) (hash-dyad state s m e))) (float (multiple-value-bind (s m e) (compute-float-dyad number) (hash-dyad state s m e))) (ratio (if (dyadic-ratio-p number) (multiple-value-bind (s m e) (compute-ratio-dyad number) (hash-dyad state s m e)) (progn (hash-datatype-tag state :ratio) (hash-equalp-number state (numerator number)) (hash-equalp-number state (denominator number))))) (complex (if (zerop (imagpart number)) (hash-equalp-number state (realpart number)) (progn (hash-datatype-tag state :complex) (hash-equalp-number state (realpart