0%

Comparison method violates its general contract! 崩溃分析

最近,公司产品中经常发现有用户报告各种列表突然不见的问题,后来发现是子线程报 IllegalStateException,其中的 message 就是我们的标题。

这个问题还得从 JDK 1.7 开始说起。

1. TimSort

JDK 1.7 之后,Collections.sort 的内部实现从 归并排序 修改成了 Tim排序

TimSort 简单的来说,就是一个优化的归并排序,它结合了插入排序和归并排序,使得每次算法在归并的时候,避免归并数量相差过大的数组片段(我们称之为 run)以提高性能。

首先,为了找到或者构造出这个 run,我们需要找到一个 升序 或者 严格递减 的序列;

而在归并过程中,为了提高归并效率,算法提出了一个 Galloping Mode

首先,基于我们寻找到的 run 都是有序的,那么我们就可以尝试将一个 run 中的元素插入到另一个 run 中,如果找到了该元素,那么在另一个 run 中,该元素之前的元素都满足我们的排序要求。

例如,如果要将 XXYY 两个 run 进行归并:

其中的 temporary 是一个临时存储数组,它是通过较短的那个 run 复制得到的
这里的 temporary 实际上就是 XX

尝试将X[0]插入到Y中

我们会在 YY 中,尝试将 Y[0]Y[0] 插入到 XX 中,那么在 Y[0]Y[0] 的插入位置之前的 xXx \in X 都满足 xY[0]x \le Y[0];

同时,在寻找这个插入位置时,并不是一个一个的寻找,而是间隔寻找,寻找索引为 2k12k-1 的元素,这样比较次数就是 logX\log X,减少比较次数,有时候能比二分查找更快。

经过这样的查找之后,我们寻找到 4 这个元素,将其插入结果中;

随后,我们反转查找目标,在 XX 中尝试将 X[0]X[0] 插入到 YY 中:

将X[0]插入到Y中

随后又反转查找目标,不断进行,直到当次归并完成为止。

2. 出现问题的原因

那么 TimSort 和这个崩溃有什么关系呢?

我们看到,在这个 Galloping 的过程中,我们需要将 XX 中的元素和 YY 中进行比较,又要拿 YY 中的元素和 XX 中的元素进行比较;

因此,对于 XXYY 中的 Comparator 的要求就比较严格,它需要满足以下三条 Comparator 的合约:

1. compare(a, b) = -compare(b, a) (自反性)
2. compare(a, b) > 0 && compare(b, c) > 0 then compare(a, c) > 0 (传递性)
3. if compare(a, b) == 0 then compare(a, x) == compare(b, x),其中 x 为任意值

如果 Comparator 不满足上面的合约,就会导致这个算法在归并的时候,明明还没归并完,但是某一个 run 已经耗尽了,这说明这两个 run 不是均衡的,不符合这个算法的初衷,因此它就会报错。

所以,在升级到 JDK 1.7 之后,需要着重注意 Comparator 的设计,下面会列出几种造成 Comparator 不符合合约的典型情况。

3. 造成崩溃的典型情况

3.1 没有考虑相等的情况

特别是使用 ?: 三目运算符计算出的 compare 结果,尤其会造成这种情况,例如:

a < b ? 1 : -1

在这里,如果 a == b,那就会出现 compare(a, b) = 1 而且 compare(b, a) == 1,违反自反性。

解决办法:
一定要遍历 ab 可能的比较关系的三种情况。

3.2 使用四则计算、强制转换

这种 Comparator 很多书上都会这么写:

return o1 - o2

但是这个写法是不安全的,它会存在 溢出问题,例如 Int.MAX_VAL-1,我们知道,Int.MAX_VAL 是一定大于 -1 的,但是如果使用这种计算方式,那么就会有:

compare(Int.MAX_VAL, -1) = Int.MAX_VAL - (-1) = -2147483648 < 0

compare(-1, Int.MAX_VAL) = -1 - Int.MAX_VAL = -2147483648 < 0

违反自反性。

同理,如果将一个 Long 值强制转换到 Int 值也会出现这样的问题,因为强制转换的过程中丢失了精度,会导致溢出问题。

解决办法:
对于数值型的比较问题,我们可以将这个工作委托给对应的类进行,例如 Integer 就有一个 compare() 方法用于比较两个 int 值。

3.3 线程安全问题

当然,在比较的过程中,我们还要注意线程安全问题,如果线程不安全,那很可能在归并过程中,元素的值被改动了,因此就会导致比较的结果不正确。

解决办法:
对于线程安全,可以用传统的解决线程安全的办法进行解决,也可以让所有的元素都是 不变量,如果一个量永远都不会变,那么它无论多少个线程进行操作,都是安全的。

4. 系统兼容性

这里要特别注意的是,如果上述的解决办法难以实施,也可以通过参数配置使用原先的归并排序,归并排序不要求两个 run 是均衡的,因此就不会出现这个崩溃问题;

但是,只有 JVM 系统才能使用这个 workaround,如果是 Android,它内置的源码就已经去除掉了原先的归并排序,只能迎难而上处理这个问题。

5. 参考资料

Richard Scheiwe——The Case for Timsort