在 EQUALP 下对数字进行哈希运算的妙处

# 在 EQUALP 下对数字进行哈希的乐趣 来源: https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html ## 目录 - 1\. 数字哈希——热身 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#orgc9159c9) - 1\.1. 回顾：哈希表测试与哈希函数 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org1e02788) - 1\.2. 回顾：数值塔与数学等价 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org6847aae) - 1\.3. 建立基线 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#orgcc320c4) - 2\. 数字哈希——第一回合 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#orgf18e8f8) - 2\.1. 实现中的坑 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org74c831a) - 3\. 数字哈希——第二回合 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org1e8be0b) - 3\.1. 回到现实 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org4b7d2a6) - 3\.2. 细节如砾石 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org8aecedd) - 4\. 基准测试——淘汰赛 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org8189bc0) - 4\.1. ECL 对阵 ECL (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org3eeb8ee) - 4\.2. ECL 对阵世界 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#org0636259) - 5\. 总结 (https://turtleware.eu/posts/Heavenly-delights-of-hashing-numbers-under-EQUALP.html#orgcd0728b) 前段时间，我决定重新拾起在 ECL 中做快速泛函数分发的工作。但在合并那之前，我打算先优化基于表的分发，以便有一个好的衡量标准来看它到底变好了还是变差了，结果却捅开了一个马蜂窝，包括重新实现哈希表和哈希函数。没错，这就是在荒诞嵌套的兔子洞里又深了一层。 这带来了两个好结果： 1. 哈希表和泛函数分发很快就会**大幅**提速 2. 我获得了灵感，决定再写一篇关于 Common Lisp 的博客文章 关于第一点，以下是几张使用 polyclot 生成的柱状图——这是 McCLIM 的一个用于绘制数据的在研工具（数值越小越好）： cherry-picking.png **图 1：** SLOT-ACCESS/READER——标准 reader 基准测试（进行中）。 htable-mixbag.png **图 2：** HTABLE-MIXBAG——使用随机键的 EQUALP 基准测试。 htable-setrem.png **图 3：** HTABLE-SETRM——交替插入和删除的基准测试。 htable-string.png **图 4：** HTABLE-SMALL-STRING——使用短字符串的 EQUALP 基准测试。 关于第二点，在各种 Common Lisp 谓词下研究哈希的过程中，我决定硬着头皮去修复 ECL 中一些丑陋的部分。其中最突出的就是在谓词 `#'EQUALP` 下对数字进行一致性哈希。这个话题足够有趣，值得单独写一篇记录。在这篇文章中，我假设使用二进制浮点数（浮点基数为二）。这也是 ECL 中使用的浮点表示方式。 ## 1\. 数字哈希——热身 ### 1\.1. 回顾：哈希表测试与哈希函数 快速回顾一下 Common Lisp 中的哈希表。标准规定，合规实现必须允许指定哈希表的测试函数为 `EQ`、`EQL`、`EQUAL` 和 `EQUALP`。最后一个测试很有趣，因为表示形式不同的数字在它们 `=` 相等时被视为 `EQUALP`。例如： ``` (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 ``` 值得注意的是，哈希可以是有损的，但不能与测试不一致。换句话说，以下是 `#'EQUALP` 下的一个合规哈希函数： ``` ;; (equalp 1 1.0) ; 为真 ;; (= (hash-equalp 1) (hash-equalp 1.0)) ; 为真 (defun hash-equalp (x) (typecase x (real 42) (complex (if (zerop (imagpart x)) (hash-equalp (realpart x)) 13)) (otherwise 15))) ``` 而以下这个函数则不合规，因为存在在测试下相同但哈希值不同的对象： ``` ;; (equalp 1 1.0) ; 为真 ;; (= (hash-equalp 1) (hash-equalp 1.0)) ; 为假 (defun hash-equalp (x) (typecase x (rational 1337) (float 7117) (complex (if (zerop (imagpart x)) (hash-equalp (realpart x)) 13)) (otherwise 15))) ``` 换句话说，当两个对象在给定测试下相等时，它们必须产生相同的哈希值；但两个对象哈希值相同并不意味着它们在给定测试下相等。朴素的哈希虽然合规，但没有抓住要点。一个好的哈希函数会试图为在谓词下不等价的对象产生不同的哈希值，并且具有良好的位分布，以确保哈希表的良好性能。 ### 1\.2. 回顾：数值塔与数学等价 Common Lisp 拥有完整的数值塔： numeric-tower.png **图 5：** Common Lisp 数值塔。注意，当复数浮点数有专门化表示时，可能会有多个专门化到 `single-float`、`double-float` 等的子类型。 当数字的值在数学上相同时，无论底层表示如何，它们都是 `#'=` 的。当你做数学运算时，这是一个美妙的特性 `:-)`。当你想在谓词 `#'EQUALP`（对数字而言归结为 `#'#'=`）下产生高质量的哈希时，这个特性就不那么美妙了。我们需要构造一个函数，能够为相等的对象产生相同的哈希值，同时具有良好的质量。 最大的障碍来自 `RATIONAL` 和 `FLOAT` 对象之间表示形式的差距。按惯例，表示形式如下： | 类型 | 表示方式 | |---|---| | **fixnum** | 一个机器字，截去几位以容纳标签 | | **bignum** | 一个"limb"（整数的部分，不含符号）的数组 | | **ratio** | 一对整数 | | **float** | 一对 N 位尾数和 K 位指数（含符号） | | **（复有理数）** | 一对有理数 | | **（复浮点数）** | 一对相同类型的浮点数 | `FIXNUM`、`BIGNUM` 和 `RATIO` 在 `#'#'=` 下是互不相交的。这留下了一些问题： 1. 什么时候两个复数在数学上相等？这很简单。当两个复数的实部相等且虚部相等时。 2. 什么时候两个浮点数在数学上相等？为了解决这个问题，我们可以将精度较低的浮点数转换为精度较高的那个，然后比较位。这里有个陷阱——`-0.0` 与 `+0.0` 不是 `EQL` 的，但它永远是 `=` 的，所以我们应该先对零进行规范化。 3. 什么时候一个整数在数学上与一个浮点数相等？当浮点数没有小数部分且整数相等时。 4. 什么时候一个 `RATIO` 与一个浮点数 `#'#'=` 相等？这是最有趣的问题。要回答它，我们需要深入了解浮点表示。 有限二进制浮点值在概念上表示为： ``` (* sign mantissa (expt 2 exponent)) ``` 这对应于*二进有理数*，即分母为二的幂的有理数： ``` (/ n (expt 2 k)) ``` 换句话说，浮点数和一个比值只有在该比值是二进有理数时才可能相等，否则该比值的值无法表示为二进制浮点数（本文假设我们使用二进制浮点数——基数为 2）。 以上就是关于 Common Lisp 中数学等价和数值塔的回顾总结。 ### 1\.3. 建立基线 最简单但无用的方法是永远返回哈希值 `42`。这是充分的，因为这是对最重要问题的标准回答。 简单而实用的方法基于哈希是有损的这一观察。所有实数都被强制转换为浮点精度后进行哈希。当有理数无法在浮点精度内表示时，我们对它的近似值进行哈希。我们需要记住将 `-0.0` 规范化为 `+0.0`，并为溢出和下溢等情况禁用浮点异常。 ``` #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; } ``` 这个模型概念上很直观，非常易于维护，速度也相当快，在常规工作负载下碰撞相对较少。我们在以下几个方面付出了代价： 1. 在审美上并不令人愉悦——甚至可以说是粗糙的。 2. "相对较少的碰撞"仅适用于玩具示例，一旦我们开始使用更大的整数和更精确的比值，问题就开始显现。例如，`2^60` 和 `2^60+1` 会产生相同的哈希值，而这对 64 位 ID 和时间戳来说很重要。 3. 在性能方面，对于整数和有理数我们表现不佳——即使可以直接对一段内存进行哈希，我们仍在不同格式之间转换数字。 这个列表按照我看到的重要性排序。我继续深挖的主要原因是它不合我的口味。然后是对于实际工作负载的不实用性，最后是微优化。我相信普通读者对这些优先级的看法是相反的。 ## 2\. 数字哈希——第一回合 在谓词 `#'EQUALP` 下对数字进行哈希的一种更困难但更精确的方法是引入规范化规则： 1. **整数按整数哈希** 对于 `FIXNUM`，我们对它的值（去掉标签的机器字）进行哈希；对于 `BIGNUM`，我们对符号和它的 limb 进行哈希。 2. **没有小数部分的有限浮点数按整数哈希** 确保 INTEGER ↔ FLOAT 的对应关系。我们不能将 `LONG-FLOAT` 转换为 `DOUBLE-FLOAT` 然后再转换为整数，因为这样会丢失许多 `BIGNUM` 的值。 **注意：** 使用这种方法，大浮点数可能会构造完整的 bignum。 3. **不是整数的浮点数转换为 DOUBLE-FLOAT 后哈希** 确保 X-FLOAT ↔ Y-FLOAT 的对应关系。如果长浮点数的位数多于双精度浮点数，这种方法对其是有损的，但它简化了实现，因为 long double 有一些"松散"的位，在数值相同的不同数之间可能不同。NaN 和无穷大与其他双精度数一样哈希，因为无穷大是精确的，而 NaN 永远不与任何东西 `#'#'=` 相等。 4. **二进有理数比值按 DOUBLE-FLOAT 哈希** 确保 FLOAT ↔ RATIO 的对应关系。为了简单起见，我们不尝试判断 `RATIO` 是否可以表示为 `DOUBLE-FLOAT`——如果它太大或太小，它将被表示为 0 或无穷大。 5. **其他比值按对哈希** 我们分别对分子和分母进行哈希。 6. **虚部为零的复浮点数按 `(HASH (REALPART X))` 哈希** 因为 `(= 3 #c(3.0 0.0))`，我们需要对 `(complex float)` 进行规范化，而有理复数则被隐式地规范化。其他复数按对哈希，即我们分别对实部和虚部进行哈希。 这种方法导致更少的碰撞，并且相当直接。以下是伪代码： ``` (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 和 +0.0 按整数哈希。 (hash-data state (coerce number 'double-float)))) (ratio (if (dyadic-ratio-p number) ;; INV 可能产生无穷大或零（这没关系） ;; 禁用浮点上溢和下溢陷阱。 (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. 实现中的坑 我最初的实现将所有浮点数都转换为整数。当我将 ECL 与其他实现进行比较时，我一直在想为什么我们比其他实现慢那么多。关键发现来自一个认识——形如 `(random 20.0)` 的随机键被折叠为只有 20 个不同的哈希值。修复这个问题并给非整数浮点数赋予不同的哈希值后，ECL 在 HTABLE-MIXBAG 基准测试（开头已包含）中获得了最明显的提升——新版本比旧版本快 100 倍。 在实现一套测试来确保大整数、二进有理数以及相应浮点数的哈希值一致时，我发现了一个与双精度浮点数转换为整数相关的非显而易见的 bug。代码看起来像这样： ``` if (d<=MOST_POSITIVE_FIXNUM && d>=MOST_NEGATIVE_FIXNUM) return to_fixnum(d); else return to_bignum(d); ``` 但在 x86-64 上 `MOST_POSITIVE_FIXNUM` 的值是 `2^61-1`。换句话说，要精确表示这个数字为双精度浮点数，我们需要 61 位有效位。这很遗憾，因为 double 只有 53 位有效位，所以 `MOST_POSITIVE_FIXNUM` 转换为 double 后四舍五入为 `2^61`，而它无法装入 fixnum。宏展开后，错误的代码等价于： ``` if (d<=(1LL<<61) && d>=MOST_NEGATIVE_FIXNUM) return to_fixnum(d); else return to_bignum(d); ``` 糟糕，当 double 值恰好为 `2^61` 时，它被意外地转换为 fixnum。这显然是个问题！ 找到问题后，解决方案很简单。我们需要找到作为边界的精确 double 值。注意整数是以补码实现的，所以最负的 fixnum 在我们的情况下没有问题： ``` 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); ``` 这个修复是正确的，但它揭示了另一个 bug。不过那是另一个故事了。 ## 3\. 数字哈希——第二回合 上面的方法正确且不错，但有几个重要的缺陷： - 对于大整数浮点数会产生大量内存分配（最坏情况下每个浮点数 2KB） - 有一整类二进有理数比值无法装入 long float - 长浮点数转换为 double 后会损失精度，特别小和特别大的值会坍缩为 0 和无穷大 在最初实现之后，这些问题足够困扰我，以至于我决定为谓词 EQUALP 下的数字设计一种新的哈希方案。规则也更简单（至少在概念上是）： 1. 二进有理数按三元组（符号、尾数、指数）哈希 2. 其他数字根据其类型哈希（它们是互不相交的） 表示形式 `[SIGN MANTISSA EXPONENT]` 不需要我们在类型之间进行转换，并且非常紧凑。此外，它非常精确，不会产生不必要的碰撞。另一方面，它需要额外的工作来规范化三元组。以下是伪代码： ``` (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 number)) (hash-equalp-number state (imagpart number))))))) ``` 实现方式不那么直接，因为我们现在需要能够从数字计算尾数。