与 IntArray 相比，ArrayList<Int> 对于大量元素的性能极其糟糕

Question

我做了两种快速排序的实现：顺序排序和并行排序。第二个是使用 ForkJoinPool 使用 4 个线程编写的（我在下面添加了实现）排序函数与 ArrayList 一起使用：

override fun sort(array: ArrayList<Int>): ArrayList<Int> { 
   ...
}

我在大小为 1e3-1e7 的数组上测试了它们，对于所有大小的并行实现比顺序执行快约 2.5 倍。但从size=1e8 开始，并行算法的运行速度比顺序算法慢约 2 倍。

class ParQuickSort(
    private val seqBlockSize:Int = 1000,
    nThreads: Int = 4
) : QuickSort {

    private val threadPool = ForkJoinPool(nThreads)

    override fun sort(array: IntArray): IntArray {
        threadPool.invoke(
            SortTask(array, 0, array.size - 1, seqBlockSize)
        )
        return array
    }

    fun shutdown() {
        threadPool.shutdownNow()
    }

    private class SortTask(
        val array: IntArray,
        val l: Int,
        val r: Int,
        val seqBlockSize: Int
    ) : RecursiveTask<Unit>() {

        private val rand = Random()

        private val seqSort = SeqQuickSort()

        override fun compute() {
            if (l < r) {
                if (r - l <= seqBlockSize) {
                    seqSort.quickSortInterval(array, l, r)
                    return
                }
                val m = partition(array, l, r)

                invokeAll(
                    SortTask(array, l, m, seqBlockSize),
                    SortTask(array, m + 1, r, seqBlockSize)
                )
            }
        }

        private fun partition(array: IntArray, l: Int, r: Int): Int {
            ...
        }

        private fun swap(array: IntArray, first: Int, second: Int) {
            ...
        }

    }
}

当我将ArrayList 更改为 IntArray 时，并行实现对于 1e8 数组大小显示出更好的结果（对于较小的数组来说，比顺序快约 2.5 倍），正如我所预期的那样。

我知道 ArrayList 的缺点 - 自动装箱、拆箱等，并且 IntArray 相当于 int[]，因此它可以与基元一起使用。但是为什么使用 ArrayList 的并行实现仅在处理大量元素 (1e8) 时才开始表现不佳？

Answer 1

ArrayList<Integer>每个整数占用大约 64+64+64 位内存：

• 列表中的每个值Integer都会创建一个实例。这个实例大约有 128 位大：64 位被对象头占用（除其他外，它将该对象标识为该Integer类型 - 对象知道它们是什么，这需要一些内存）。
• ...并且该实例有一个包含该值的字段。您可能会认为这只是 32 位。事实并非如此：在 64 位处理器上，对内存执行的操作没有很好地位于可被 64 位整除的位置，这是非常烦人的。因此，实际上，64 位内存被该 32 位变量“占用”（在“不再可用于其他内容”的意义上）。
• 列表本身是一个指针序列，指向那些整数对象（用java的说法，“引用”。它们是指针）。根据 JVM 的各个方面，每个指针都是 64 位或 32 位（压缩 OOPS 和 JVM 用来压缩指针的其他技巧可能适用于此）。

相比之下，一个int[]很简单：每个值占用 32 位。不多也不少。

这是6 倍-List<Integer>存储 Y 整数需要大约 6 倍的内存int[]。List<Int>（据我所知，在 kotlin 中，是List<Integer>，是.

因此，此时性能下降的原因很可能是主内存已满并且交换正在进行。交换已经很昂贵了；当引入并行性时，它往往会变得更加昂贵。