图解JDK7的Comparison method violates its general contract异常

偏执的太偏执、 2021-09-11 05:16 314阅读 0赞

# 1.摘要 #

前一阵遇到了一个使用Collections.sort()时报异常的问题，跟小伙伴@zhuidawugui 一起排查了一下，发现问题的原因是JDK7的排序实现改为了TimSort，之后我们又进一步研究了一下这个神奇的算法。

# 2.背景 #

先说一下为什么要研究这个异常，前几天线上服务器发现日志里有偶发的异常：

java.lang.IllegalArgumentException: Comparison method violates its general contract!
     at java.util.TimSort.mergeHi(TimSort.java:868)
      at java.util.TimSort.mergeAt(TimSort.java:485)
      at java.util.TimSort.mergeCollapse(TimSort.java:408)
    at java.util.TimSort.sort(TimSort.java:214)
      at java.util.TimSort.sort(TimSort.java:173)
      at java.util.Arrays.sort(Arrays.java:659)
      at java.util.Collections.sort(Collections.java:217)

出错部分的代码如下：

List<Integer> list = getUserIds();
    Collections.sort(list, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1>o2?1:-1;
        }
    });

google了一下：JDK7中的Collections.Sort方法实现中，如果两个值是相等的，那么compare方法需要返回0，否则**可能**会在排序时抛错，而JDK6是没有这个限制的。

这个问题在测试时并没有出现，线上也只是小概率复现，如何稳定的复现这个问题？看了一下源代码，抛出异常的那段源代码让人根本摸不着头脑：

if (len2 == 0) {
        throw new IllegalArgumentException("Comparison method violates its general contract!");
    }

为了解开这个困惑，我们对java实现的Timsort代码做了一些分析。

# 3.Timsort概述 #

TimSort排序是一种优化的归并排序，它将归并排序(merge sort) 与插入排序(insertion sort) 结合，并进行了一些优化。对于已经部分排序的数组，时间复杂度远低于 O(n log(n))，最好可达 O(n)，对于随机排序的数组，时间复杂度为 O(nlog(n))，平均时间复杂度 O(nlog(n))。

它的整体思路是这样的：

1.  遍历数组，将数组分为若干个升序或降序的片段，（如果是降序片段，反转降序的片段使其变为升序），每个片段称为一个Runtask
2.  从数组中取一个RunTask，将这个RunTask压栈。
3.  取出栈中相邻两个的RunTask，做归并排序，并将结果重新压栈。
4.  重复(2),(3)过程，直到所有数据处理完毕。

这篇文章就不再过多的阐述Timsort整体思路了，有兴趣可以参考[\[译\]理解timsort, 第一部分：适应性归并排序(Adaptive Mergesort)][timsort_ _Adaptive Mergesort]

# 4.Timsort的归并 #

重点说一下Timsort中的归并。归并过程相对普通的归并排序做了一定的优化，假如有如下的一段数组：

![Center][]

1.首先把数组拆成两个RunTask，这里称为A段和B段，注意，A段和B段在物理地址上是连续的：

![Center 1][]

2.A段的起点为base1，剩余元素数量为len1；B段起点为base2，剩余元素数量为len2。取B点的起点值B\[base2\]，在A段中进行二分查找，将A段中小于等于B\[base2\]的段作为merge结果的起始部分；再取A段的终点值a\[base1 + len1 – 1\]，在B段中二分查找，将B段中大于等于a\[base1 + len1 – 1\]值的段作为结果的结束部分。

更形象的说，这里把待归并的数据“掐头去尾”，只需要合并中间的数据就可以了：

![Center 2][]

3.之后需要创建一个tmp数组，大小为B段截取后的大小，并把B段剩余的数据拷贝过去，因为合并过程中这些数据会被覆盖掉。

程序会记录corsor1和corsor2，这是待归并数据的指针，初始位置在A段和tmp段的末尾。同时会记录合并后数组的dest指针，位置在原B段的末尾。

这里还有一个小优化：生成dest指针时会直接把A段cursor1指向的数据拷贝到B段末尾，同时cursor–,dest–。因为之前(2)步的时候已经保证了arr\[cursor1\]>arr\[dest\]

![Center 3][]

4.进行归并排序，这里每次归并比较时会记录A和tmp段比较“胜利（大于对方）”的次数，比较失败（小于对方）时会把胜利数清零。当有一个段的数据连续N次胜利时会激活另一个优化策略，在这里假设N为4，下图已经是A段连续胜利了4次的情况：

![Center 4][]

5.如果连续胜利N次，那么可以假设A段的数据平均大于B段，此时会用tmp\[cursor2\]的值在A\[base0\]至A\[cursor1\]中查找第一个小于tmp\[cursor2\]的索引k，并把A\[k+1\]到A\[cursor1\]的数据直接搬移到A\[dest-len,dest\]。

对于例子中的数据，tmp\[cursor2\]=8，在A数组中查找到小于8的第一个索引（-1），之后把A\[0,1\]填充到A\[dest-1,dest\]，cursor1和dest指针左移两个位置。

![Center 5][]

6.如果cursor1>=0，之后会再用curosr1指向的数据在tmp数组中查找，由于这里cursor1已经是-1了，循环结束。

7.最后把tmp里剩余的数据拷贝到A数组的剩余位置中，结束。

# 5.异常情况下Timsort的归并 #

假设这里实现的compare(obj o1,obj o2)如下：

public int compare(Integer o1, Integer o2) {
        return o1>o2?1:-1;
    }

1.仍然是分成A，B两段：  
![Center 6][]

2.在“掐头去尾”的时候，这时会有一些变化，程序执行到compare(B\[base2\],A\[base1\])时返回-1，A的左侧留下了两个应该被切走的“5”。

![Center 7][]

3.接下来是正常的归并过程。

![Center 8][]

4.这里同样会触发“胜利”>N次逻辑

![Center 9][]

5.在A\[base1,cursor1\]中查找小于tmp\[cursor2\]的元素，复制，cursor1和dest左移两位。

![Center 10][]

6.此时再用A\[cursor1\]在tmp中查找，tmp中所有的数据都被移入A数组，cursor2、dest左移4位。tmp2剩余元素的数量（len2）为0。

![Center 11][]

注意！

在第6步查找的时候，有`A[base1+1]<tmp[0]`（tmp\[0\]的值等于没有合并之前的B\[base2\]）。  
而第2步时，有`B[base2]<A[base1]`  
而最初生成RunTask的时候，有`A[base1]<=A[base1+1]`  
连起来就是`B[base2]<A[base1]<=A[base1+1]<B[base2]`，这显然是有问题的。

所以，当len2==0时，会抛出“Comparison method violates its general contract”异常。问题复现的条件是触发“胜利N次”的优化，并且存在类似(A\[base1\]==A\[base1+x\])&&(A\[base1+x\]==B\[base2\])的数据排列。这里应该还有几种另外的触发条件，精力有限，就不再深究了。

# 6.参考 #

[TimSort in Java 7][] [OpenJDK 源代码阅读之 TimSort][OpenJDK _ TimSort]（http://blog.csdn.net/on\_1y/article/details/30109975）

[timsort_ _Adaptive Mergesort]: http://blog.kongfy.com/2012/10/%E8%AF%91%E7%90%86%E8%A7%A3timsort-%E7%AC%AC%E4%B8%80%E9%83%A8%E5%88%86%EF%BC%9A%E9%80%82%E5%BA%94%E6%80%A7%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8Fadaptive-mergesort/
[Center]: /images/20210511/80312020151f464f961d1bf383d8440b.png
[Center 1]: /images/20210511/ca21e0c03a5d4c76bcf685926c870a05.png
[Center 2]: /images/20210511/7c9b5c92c9924a398713fbd1a0cb0711.png
[Center 3]: /images/20210511/4b7a200765d74b7884f0b8af5f21f71e.png
[Center 4]: /images/20210511/f18a3c945d23459aa915f0d96adee877.png
[Center 5]: /images/20210511/d75cb240311c4aa3a0f982e5a1df6afa.png
[Center 6]: /images/20210511/ed4f466c32e045c5b725f0af7a5a4bf2.png
[Center 7]: /images/20210511/7ae824810c67493e9caa4d2bc4c060da.png
[Center 8]: /images/20210511/45b380945cdb4960baaab65b9a2d1489.png
[Center 9]: /images/20210511/7357c40099684548829efc13bdfe7b11.png
[Center 10]: /images/20210511/4deeeb89526b46e6872846bdba7d2b89.png
[Center 11]: /images/20210511/5953237841a94c169d7d5e12d7b63724.png
[TimSort in Java 7]: http://www.lifebackup.cn/timsort-java7.html
[OpenJDK _ TimSort]: http://blog.csdn.net/on_1y/article/details/30109975