使用Ordering[T]时，Scala的快速排序比普通排序慢10倍

Question

使用Ordering[T]时，Scala的快速排序比普通排序慢10倍

3

我正在对基于自定义排序的整数索引进行排序。我发现这里使用的Ordering[T]使得排序至少比手工快速排序使用直接调用compare方法慢10倍。这看起来代价太高了！

val indices: Array[Int] = ...

class OrderingByScore extends Ordering[Int] { ... }

time { (0 to 10000).par.foreach(x => {
  scala.util.Sorting.quickSort[Int](indices.take(nb))(new OrderingByScore)
})}
// Elapsed: 30 seconds

与手工制作的sortArray相比，这里找到的sortArray经过修改，增加了一个ord: Ordering[Int]参数：

def sortArray1(array: Array[Int], left: Int, right: Int, ord: Ordering[Int]) = ...

time { (0 to 10000).par.foreach(x => {
  sortArray1(indices.take(nb), 0, nb - 1, new OrderingByScore)
})}
// Elapsed: 19 seconds

最后，同样的代码但使用确切类型 (ord: OrderingByScore):

def sortArray2(array: Array[Int], left: Int, right: Int, ord: OrderingByScore) = ...

time { (0 to 10000).par.foreach(x => {
  sortArray2(indices.take(nb), 0, nb - 1, new OrderingByScore)
})}
// Elapsed: 1.85 seconds

我很惊讶看到每个版本之间的差异这么大！

在我的例子中，indices数组基于另一个包含合并分数的Doubles数组中找到的值进行排序。此外，它使用indices本身作为次要比较来保证排序的稳定性。顺便说一下，为了使测试可靠，在并行循环内部我必须“indices.take(nb)” ，因为排序会修改输入数组。与我在这里遇到的问题相比，这种惩罚是微不足道的。完整的代码可以在 gist 这里找到。

欢迎您提出建议以改进...但请不要更改indices和scores数组的基本结构。

注意：我正在scala 2.10 REPL中运行。

- Michel Lemay

也许是装箱和拆箱的成本。 - zakki

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rüdiger Klaehn · Accepted Answer

问题在于scala.math.Ordering没有被专门化。因此，每次使用像Int这样的基本类型调用compare方法时，两个类型为Int的参数都会被装箱到java.lang.Integer中。这会产生大量短暂的对象，严重降低性能。

spire库有一个专门化版本的Ordering叫做spire.algebra.Order，应该会更快。你可以尝试将其替换到你的代码中并重新运行基准测试。

spire还提供了排序算法。所以也可以尝试使用它们。

基本上，每当你想以高性能的方式处理基本类型的数学运算时，spire就是最好的选择。

此外，如果你想信任结果，请使用适当的微基准测试工具，例如Thyme或JMH。