我做了两种快速排序的实现:顺序排序和并行排序。第二个是使用 ForkJoinPool 使用 4 个线程编写的(我在下面添加了实现) 排序功能与 ArrayList 一起使用:
override fun sort(array: ArrayList<Int>): ArrayList<Int> {
...
}
我在大小为 1e3-1e7 的数组上测试了它们,对于所有大小的并行实现比顺序实现快约 2.5 倍。但是从大小 = 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) 时才开始表现不佳?
ArrayList<Integer>
每个整数占用 64+64+64 位内存:
Integer
实例。这个实例大约有 128 位大:64 位被对象头占用(除其他外,它将该对象标识为
Integer
类型 - 对象知道它们是什么,这需要一些内存)。
int[]
很简单:每个值占用 32 位。不多也不少。这是
6 倍 - List<Integer>
需要比
int[]
多约 6 倍的内存来存储 Y 整数。 (据我所知,在 kotlin 中,
List<Int>
是
List<Integer>
的别名。因此,此时性能下降的原因很可能是您的主内存已满并且正在进行交换。交换已经很昂贵了;当引入并行性时,它往往会变得
更昂贵。