为什么Collections.sort()比Arrays.sort()慢得多？

Question

我尝试了一个与Collection.sort()和Arrays.sort()相关的测试。在测试中，我创建了一个长度为1e5的int数组100次，其中包含从1到1e5的随机数。我还创建了一个类型为Integer的列表，其中包含与数组在同一位置上相同的值。然后使用Arrays.sort()对数组进行排序，并使用Collections.sort()对列表进行排序。

---

更新： 如@Holger指出，我的代码存在错误。现已更正：

import java.util.* ;


class TestClass {
    public static void main(String args[] ) throws Exception {
        double ratSum = 0 ;
        for(int j=0;j<100;j++)
        {
        int[] A = new int[(int)1e5] ;
        List<Integer> L = new ArrayList<Integer>() ;
        for(int i=0;i<A.length;i++)
        {
            int no = (int)(Math.random()*(int)1e5) ;
            A[i] = no ;
            L.add(A[i]) ;
        }

        long startTime = System.nanoTime() ;
        Arrays.sort(A) ;
        long endTime = System.nanoTime() ;
        Collections.sort(L) ;
        long endTime2 = System.nanoTime() ;
        long t1 = (endTime-startTime), t2 = (endTime2-endTime) ;
        ratSum+=(double)t2/t1 ;
        System.out.println("Arrays.sort took :"+t1+" Collections.sort took :"+t2+" ratio :"+((double)t2/t1)) ;
    }
    System.out.println("Average ratio :"+(ratSum/100)) ;
    }
}

输出结果为:

Arrays.sort took :24106021 Collections.sort took :92353602 ratio :3.8311425182944956
Arrays.sort took :8672831 Collections.sort took :50936497 ratio :5.873110752417521
Arrays.sort took :8561227 Collections.sort took :25611480 ratio :2.991566512603859
Arrays.sort took :7123928 Collections.sort took :17368785 ratio :2.4380910362934607
Arrays.sort took :6280488 Collections.sort took :16929218 ratio :2.6955258890710403
Arrays.sort took :6248227 Collections.sort took :16844915 ratio :2.695951187432851
Arrays.sort took :6220942 Collections.sort took :16979669 ratio :2.7294369566538315
Arrays.sort took :6213841 Collections.sort took :17439817 ratio :2.8066081832476883
Arrays.sort took :6286385 Collections.sort took :19963612 ratio :3.175690321225951
Arrays.sort took :6209668 Collections.sort took :17008307 ratio :2.7390042430609816
Arrays.sort took :6286623 Collections.sort took :17007163 ratio :2.705293923303497
Arrays.sort took :6256505 Collections.sort took :16911950 ratio :2.703098614961548
Arrays.sort took :6225031 Collections.sort took :16914494 ratio :2.7171742598550916
Arrays.sort took :6233918 Collections.sort took :17005995 ratio :2.72797861633727
Arrays.sort took :6210554 Collections.sort took :17606028 ratio :2.834856278522013
Arrays.sort took :6239384 Collections.sort took :20342378 ratio :3.260318326296314
Arrays.sort took :6207695 Collections.sort took :16519089 ratio :2.6610664666997974
Arrays.sort took :6227147 Collections.sort took :16605884 ratio :2.666692146499834
Arrays.sort took :6225187 Collections.sort took :16687597 ratio :2.680657946500242
Arrays.sort took :6152338 Collections.sort took :16475373 ratio :2.6779043999208105
Arrays.sort took :6184746 Collections.sort took :16511024 ratio :2.6696365541931715
Arrays.sort took :6130221 Collections.sort took :16578032 ratio :2.7043122915144493
Arrays.sort took :6271927 Collections.sort took :16507152 ratio :2.631910734930429
Arrays.sort took :6232482 Collections.sort took :16562166 ratio :2.657394919070765
Arrays.sort took :6218992 Collections.sort took :16552468 ratio :2.661599821964717
Arrays.sort took :6230427 Collections.sort took :21954967 ratio :3.52383022865046
Arrays.sort took :8204666 Collections.sort took :16607560 ratio :2.024160398485447
Arrays.sort took :6272619 Collections.sort took :22061291 ratio :3.5170781136236715
Arrays.sort took :8618253 Collections.sort took :19979549 ratio :2.3182829513127543
Arrays.sort took :6198538 Collections.sort took :17002645 ratio :2.743008915973412
Arrays.sort took :6265018 Collections.sort took :17079646 ratio :2.7261926462142645
Arrays.sort took :6302335 Collections.sort took :17040082 ratio :2.7037728080148073
Arrays.sort took :6293948 Collections.sort took :17133482 ratio :2.722215372608735
Arrays.sort took :6272364 Collections.sort took :17099717 ratio :2.7261997231028046
Arrays.sort took :6219540 Collections.sort took :17026849 ratio :2.737637992520347
Arrays.sort took :6231000 Collections.sort took :17149439 ratio :2.7522771625742255
Arrays.sort took :6309215 Collections.sort took :17118779 ratio :2.713297771592821
Arrays.sort took :6200511 Collections.sort took :17123517 ratio :2.7616299688848227
Arrays.sort took :6263169 Collections.sort took :16995685 ratio :2.7135919532109063
Arrays.sort took :6212243 Collections.sort took :17101848 ratio :2.7529264389689843
Arrays.sort took :6247580 Collections.sort took :17089850 ratio :2.735435160494143
Arrays.sort took :6283626 Collections.sort took :17088109 ratio :2.7194662763188004
Arrays.sort took :6312678 Collections.sort took :17055856 ratio :2.7018415955954036
Arrays.sort took :6222695 Collections.sort took :17071263 ratio :2.7433873908330715
Arrays.sort took :6300990 Collections.sort took :17016171 ratio :2.7005551508572463
Arrays.sort took :6262923 Collections.sort took :17084477 ratio :2.727875945465081
Arrays.sort took :6256482 Collections.sort took :17062232 ratio :2.7271287602202006
Arrays.sort took :6259643 Collections.sort took :17036036 ratio :2.721566709155778
Arrays.sort took :6248649 Collections.sort took :16944960 ratio :2.711779778316881
Arrays.sort took :6264515 Collections.sort took :16986876 ratio :2.7116027338109974
Arrays.sort took :6241864 Collections.sort took :17367903 ratio :2.782486609769133
Arrays.sort took :6297429 Collections.sort took :17080086 ratio :2.7122316107097038
Arrays.sort took :6184084 Collections.sort took :17584862 ratio :2.843567778186713
Arrays.sort took :6315776 Collections.sort took :22279278 ratio :3.5275598754610678
Arrays.sort took :6253047 Collections.sort took :17091694 ratio :2.7333384828228544
Arrays.sort took :6291188 Collections.sort took :17147694 ratio :2.725668665441249
Arrays.sort took :6327348 Collections.sort took :17034007 ratio :2.6921242517402235
Arrays.sort took :6284904 Collections.sort took :17049315 ratio :2.712740719667317
Arrays.sort took :6190436 Collections.sort took :17143853 ratio :2.7694096183209065
Arrays.sort took :6301712 Collections.sort took :17070237 ratio :2.7088253160411013
Arrays.sort took :6208193 Collections.sort took :17060372 ratio :2.74804149935416
Arrays.sort took :6247700 Collections.sort took :16961962 ratio :2.7149130079869392
Arrays.sort took :6344996 Collections.sort took :17084627 ratio :2.6926143058246215
Arrays.sort took :6214232 Collections.sort took :17150324 ratio :2.759846108095095
Arrays.sort took :6224359 Collections.sort took :17081254 ratio :2.744259127727048
Arrays.sort took :6256722 Collections.sort took :17005451 ratio :2.7179489515436357
Arrays.sort took :6286439 Collections.sort took :17061112 ratio :2.713954911516679
Arrays.sort took :6250634 Collections.sort took :17091313 ratio :2.7343327092899696
Arrays.sort took :6252900 Collections.sort took :17041659 ratio :2.7254008540037424
Arrays.sort took :6222192 Collections.sort took :17125062 ratio :2.75225547524088
Arrays.sort took :6227037 Collections.sort took :17013314 ratio :2.7321684454420296
Arrays.sort took :6223609 Collections.sort took :17086112 ratio :2.745370411283871
Arrays.sort took :6280777 Collections.sort took :17091821 ratio :2.7212908530266238
Arrays.sort took :6254551 Collections.sort took :17148242 ratio :2.741722307484582
Arrays.sort took :6250927 Collections.sort took :17053331 ratio :2.7281283240069834
Arrays.sort took :6270616 Collections.sort took :17067948 ratio :2.721893351466586
Arrays.sort took :6223093 Collections.sort took :17034584 ratio :2.737317922132933
Arrays.sort took :6286002 Collections.sort took :17128280 ratio :2.7248289135129133
Arrays.sort took :6239485 Collections.sort took :17032062 ratio :2.7297224049741287
Arrays.sort took :6191290 Collections.sort took :17017219 ratio :2.748574045150526
Arrays.sort took :6134110 Collections.sort took :17069485 ratio :2.782715830006309
Arrays.sort took :6207363 Collections.sort took :17052862 ratio :2.747199092432648
Arrays.sort took :6238702 Collections.sort took :17056945 ratio :2.734053493819708
Arrays.sort took :6185356 Collections.sort took :17006088 ratio :2.749411351585907
Arrays.sort took :6309226 Collections.sort took :17056503 ratio :2.703422416632405
Arrays.sort took :6256706 Collections.sort took :17082903 ratio :2.7303349398229675
Arrays.sort took :6194988 Collections.sort took :17069426 ratio :2.7553606237816766
Arrays.sort took :6184266 Collections.sort took :17054641 ratio :2.757746998592881
Arrays.sort took :6271022 Collections.sort took :17086036 ratio :2.724601508334686
Arrays.sort took :6246482 Collections.sort took :17077804 ratio :2.733987546910405
Arrays.sort took :6194985 Collections.sort took :17119911 ratio :2.763511291794895
Arrays.sort took :6319199 Collections.sort took :17444587 ratio :2.760569337980969
Arrays.sort took :6262827 Collections.sort took :17065589 ratio :2.7249018693954024
Arrays.sort took :6301245 Collections.sort took :17195611 ratio :2.728922776371971
Arrays.sort took :6214333 Collections.sort took :17024645 ratio :2.739577199998777
Arrays.sort took :6213116 Collections.sort took :17382033 ratio :2.7976353572024086
Arrays.sort took :6286394 Collections.sort took :17124874 ratio :2.7241171965995132
Arrays.sort took :6166308 Collections.sort took :16998293 ratio :2.756640278104824
Arrays.sort took :6247395 Collections.sort took :16957056 ratio :2.7142602636779007
Arrays.sort took :6245054 Collections.sort took :16994147 ratio :2.72121698227109
Average ratio :2.792654880602193

此外，我在本地运行了代码1000次（而不是100次），平均比率为：3.0616。因此，这个比率仍然很显著，值得讨论。

问题：Collections.sort() 为什么要比 Arrays.sort() 慢大约3倍来对相同的值进行排序？是因为现在我们不再比较原始类型吗？为什么那需要更多时间呢？

- Mooncrater

---

Collections.sort() 有开销，因为 Integer 是一个类（有额外的操作），而 Arrays.sort() 的操作较少，因为元素是 int 原始类型。 - The Scientific Method

@TheScientificMethod 额外的运行时间会导致开销增加。但是具体是哪些呢？Collections.sort() 到底是什么让它变慢了呢？ - Mooncrater

https://dev59.com/YVwY5IYBdhLWcg3wq5fl#32334651 - Vivek Swansi

Java有原始类型，而包装类型在内存和CPU方面的开销更高。 - Peter Lawrey

正如Holger指出的那样，int no = (int)Math.random()*(int)1e5 ;将始终将no设置为0。这是因为Math.random()返回0到1之间的浮点数，所以当强制转换为int时，它总是被截断为0。 - Kevin

@BuhBuh完成。现在请查看问题。 - Mooncrater

Answer 1

这里有两种完全不同算法的方法：

Arrays.sort(int[]) 使用双轴快速排序算法。

Collections.sort(List<T>) 调用 list.sort(null)，进而调用 Arrays.sort(T[])。这使用了 Timsort 算法。

那么，让我们比较 Arrays.sort(int[]) 和 Arrays.sort(T[])。

1. T[] 是装箱数组，因此多了一层间接性：对于每个调用，您必须解包 Integer。这肯定会导致额外的开销。另一方面，int[] 是原始数组，因此所有元素都可以“立即”使用。
2. TimSort 是经典归并排序算法的变体。它比归并排序更快，但仍然比快速排序慢，因为
   • 快速排序在随机数据上具有更少的数据移动
   • 快速排序需要 O(log(n)) 的额外空间，而 TimSort 需要 O(n) 来提供稳定性，这也会导致额外的开销。

- ZhekaKozlov

---

最终这就变得非常合理了。在原始类型的情况下，稳定性并不重要。因此，快速排序显然更好。但是，在非原始类型的情况下，稳定性确实很重要。所以不能只使用快速排序，而应该使用最快的稳定算法——TimSort。 - Mooncrater

“quicksort requires O(1) extra space” — 不，这是错误的。快速排序至少需要O(log n)额外的空间。这是一个非常常见的误解。 - Konrad Rudolph

他们选择使用两种不同的算法，因为他们想要一个稳定的排序。显然，原始类型在相等元素之间是无法区分的，所以在那里使用稳定算法没有意义。但是对于通用对象算法来说情况并非如此。此外，TimSort非常擅长利用部分有序的数据，在实际场景中非常常见...... 因此，基本上3.7倍是这两种算法之间的最坏差异情况，考虑到基本类型与拆箱开销也不算太糟糕。 - Giacomo Alzetta

需要注意的是，OP的测试代码在根本上有问题。它使用了(int)Math.random()*(int)1e5这样的表达式，这个表达式总是会被计算为零，因为(int)Math.random()总是等于零。这是一个很好的例子，说明当程序员不使用惯用的构造方式（例如在Random上调用nextInt((int)1e5)，或者更简单地在Random上调用nextInt(100_000)，如ThreadLocalRandom.current().nextInt(100_000)）而不是首先使用真正的基准框架时，他们可能会犯什么样的错误。仅仅使用实际的随机数已经显著改变了结果。 - Holger

@KonradRudolph 栈空间经常被忽略，因为栈在像HotSpot JVM这样的实现中已经预分配了。如果没有足够的空间，那就倒霉了。 - Holger

Answer 2

这里涉及到两个问题：

问题 #1：

Collections.sort底层的实现是将集合拷贝到一个数组中，对该数组排序，然后再将数组拷贝回集合。

Arrays.sort只是在原地对数组进行排序。

当数组/集合足够大时，排序的成本（O(NlogN)）将支配复制的成本（O(N)）。对于小数组/集合，复制的成本变得非常重要。

（此行为可能取决于集合类型。对于 ArrayList，Java 8 及更高版本的 Collections.sort 实现可以在不需要复制数据的情况下对支持数组进行排序。我需要查看源代码。更新 - 确认 ArrayList 支持原地排序）

问题 #2：

您正在比较对 int[] 进行排序与对 List<Integer> 进行排序。

这就像比较苹果和橙子。因为：

1. 使用关系运算符比使用 compareTo(Integer) 比较两个 int 值更快。
2. Arrays.sort(int[]) 使用不同（更快）的算法，而 Arrays.sort(Object[])使用不同的算法。

如果您想进行更公正的比较，请将 Collections.sort 应用于 ArrayList<Integer>，并将 Arrays.sort(Object[]) 应用于 Integer[]。

- Stephen C

---

自Java 8起，Collections.sort方法不再进行复制操作，而是直接就地对内部数组进行排序。 - ZhekaKozlov

如果是针对 ArrayList 的情况，我们应该这样说。虽然这也适用于此处，但是 List.sort 的默认实现仍会进行复制。 - Holger

@Holger 有没有其他类型的 List 子类型？ :) - ZhekaKozlov

@ZhekaKozlov 没有太多有意义的东西... 不可变列表是无关紧要的，因为它们不能排序，Arrays.asList(...)返回的列表以及 Vector 都有一个类似的方法来原地排序，所以主要是使用 LinkedList，如果你敢使用它，就会带来性能方面的缺点。或者使用未更新的第三方可变列表（不知道任何相关的示例）。 - Holger

Answer 3

沿途没有提到的一件事是“指针追踪”，它与“取消装箱”部分有关。对于这种小尺寸的数组，无论你使用timsort还是quicksort都不应该有显著的区别（对于当前CPU速度的原始数组来说，这很可能不会影响速度）。

虽然在您的示例中，拆箱操作只发生在初始化时，但重要的差异发生在读取数据的地方。

由于int是基本类型，因此int[]只是包含数据本身的连续内存块，而Integer[]则是包含对各个数据对象的引用（即指针）的连续内存块，而且Integer对象本身可以散布在整个内存中。

因此，在对int[]进行排序操作时，CPU将获取一个内存块，并直接对其进行操作。但是，在对Integer[]进行排序时，CPU必须追踪每个单独对象的指针，并从内存中获取它，然后才能比较并对数组进行操作和重新排列。这就是所谓的“指针追踪”。

并不是说每个数据片段都需要Integer[]更多的操作，例如读取值、将头长度添加到基地址并从那里获取值（CPU对这些指令进行了非常好的流水线处理，这隐藏了大部分的影响），而是内存延迟会影响性能。从随机内存位置获取每个单独的Integer对象几乎是决定性的。

通常，这不是什么大问题，因为通常您在紧密循环中初始化相当小的Integer[]，并且后台没有太多操作，因此Integer对象很可能在内存中靠近并可以快速地从缓存中获取和访问，但对于创建和修改整个繁忙应用程序中的巨大数组和列表，这可能会产生显著的影响，并且可能会伴随着意外的延迟峰值。如果需要可靠的低延迟，则应避免这种情况。然而，对于大量应用程序来说，如果排序需要多几毫秒，没人会注意到。

【编辑】

由于您在评论中要求，以下是代码，以证明这不是timsort与quicksort之间的区别：

import java.util.Arrays;
import java.util.Random;

public class Pointerchasing1 {

    public static void main(String[] args) {

        //use the exact same algorithm implementation (insertionSort), to show that slowness is not caused by timsort vs quicksort.
        //expect that the object-version is slower.

        final int[] direct = new int[1024]; 
        final Integer[] refs = new Integer[direct.length];

        final Random rnd = new Random(0);
        for (int t = 0; t < 1000; ++t) {
            Arrays.setAll(direct, index -> rnd.nextInt());
            Arrays.setAll(refs, index -> direct[index]); // boxing happens here

            //measure direct:
            long t1 = System.nanoTime();
            insertionSortPrimitive(direct);
            long e1 = System.nanoTime()-t1;
            //measure refs:         
            long t2 = System.nanoTime();
            insertionSortObjects(refs);
            long e2 = System.nanoTime()-t2;

            // use results, so compiler can't eliminate the loops
            System.out.println(Arrays.toString(direct));
            System.out.println(Arrays.toString(refs));
            System.out.println("-");            
            System.out.println(e1);
            System.out.println(e2);
            System.out.println("--");           
        }
    }

    private static void insertionSortPrimitive(final int[] arr) {
        int i, key, j;
        for (i = 1; i < arr.length; i++) {
            key = arr[i];
            j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    private static void insertionSortObjects(final Integer[] arr) {
        int i, key, j;
        for (i = 1; i < arr.length; i++) {
            key = arr[i];
            j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

}

这个“测试”表明了unboxing可能是罪魁祸首。

[EDIT2]

现在这个测试旨在表明"unboxing"不是问题所在。Unboxing只是将一些字节的对象头添加到地址（乱序执行和流水线使得成本几乎消失），然后从该位置获取值。在这个测试中，我使用了两个原始数组，一个用于引用，一个用于值。因此，每个访问都是间接的。这非常类似于unboxing，只是没有为对象头添加额外的几个字节。主要区别在于“间接”版本不需要为堆上的每个值追踪指针，它可以加载两个数组并从refs数组中索引到values数组。

如果指针追踪造成了差异，而不是unboxing，则间接版本应该比执行unboxing的对象版本更快。

import java.util.Arrays;
import java.util.Random;

public class Pointerchasing2 {

    public static void main(String[] args) {

        // use indirect access (like unboxing, but just chasing a single array pointer) vs. Integer objects (chasing every object's pointer).
        // expect that the object-version is still slower.

        final int[] values = new int[1024];
        final int[] refs = new int[1024];
        final Integer[] objects = new Integer[values.length];

        final Random rnd = new Random(0);
        for (int t = 0; t < 1000; ++t) {
            Arrays.setAll(values, index -> rnd.nextInt());
            Arrays.setAll(refs, index -> index);
            Arrays.setAll(objects, index -> values[index]); // boxing happens here

            // measure indirect:
            long t1 = System.nanoTime();
            insertionSortPrimitiveIndirect(refs, values);
            long e1 = System.nanoTime() - t1;
            // measure objects:
            long t2 = System.nanoTime();
            insertionSortObjects(objects);
            long e2 = System.nanoTime() - t2;

            // use results, so compiler can't eliminate the loops
            System.out.println(Arrays.toString(indirectResult(refs, values)));
            System.out.println(Arrays.toString(objects));
            System.out.println("-");
            System.out.println(e1);
            System.out.println(e2);
            System.out.println("--");
        }
    }

    private static void insertionSortPrimitiveIndirect(final int[] refs, int[] values) {
        int i, keyIndex, j;
        for (i = 1; i < refs.length; i++) {
            keyIndex = refs[i];
            j = i - 1;
            while (j >= 0 && values[refs[j]] > values[keyIndex]) {
                refs[j + 1] = refs[j];
                j = j - 1;
            }
            refs[j + 1] = keyIndex;
        }
    }

    private static void insertionSortObjects(final Integer[] arr) {
        int i, key, j;
        for (i = 1; i < arr.length; i++) {
            key = arr[i];
            j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    private static int[] indirectResult(final int[] refs, int[] values) {
        final int[] result = new int[1024];
        Arrays.setAll(result, index -> values[refs[index]]);
        return result;
    }

}

结果: 在这两个测试中，“原始”和“间接”版本都比访问堆上的对象更快。预计自动拆箱不会影响速度，而是通过指针追踪导致内存延迟。

另请参见项目Valhalla的视频： （“JVM内部的值类型和通用专业化技术承诺给我们更好的JIT代码、数据局部性和消除指针追踪的暴政。”） https://vimeo.com/289667280

- Brixomatic

---

我理解你的观点。但是你能用一些代码来证明吗？那样会更加清晰和强调你的观点！ - Mooncrater

@Mooncrater 我已经添加了代码和视频链接来解释这一点。希望能有所帮助。 - Brixomatic

谢谢@Brixomatic！现在不在，一会儿再看看。 - Mooncrater

Answer 4

Collection.sort()使用归并排序算法，而Arrays.sort()使用快速排序。 当涉及到非原始数据类型时，快速排序存在主要缺点，即不稳定。 因此，根据需求，我们将使用Arrays.sort()或Collection.sort()来比较对象或原始数据类型。

- John

Answer 5

如果你看到 Collections.sort() 这里是Oracle文档，它的作用是将指定的列表转储到一个数组中，对该数组进行排序，并遍历该列表，从相应位置重置每个元素。这意味着它执行了数组排序和额外的迭代，这暗示了Collections.sort()比arrays.sort慢。具体来说，它执行以下操作：

1. 将指定的列表转储到一个数组中
2. 对该数组进行排序 ~ arrays.sort
3. 遍历该列表，从相应位置重置每个元素

- The Scientific Method