performance - 使用 Ordering[T] 时 Scala quickSort 慢 10 倍

Question

我正在根据自定义排序对整数索引进行排序。我发现此处使用的 Ordering[T] 使排序比使用直接调用比较方法的手工快速排序至少慢 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 相比 here但修改为添加 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

看到每个版本之间的差异，我感到非常惊讶!

在我的示例中，索引数组根据在另一个包含组合分数的 double 组中找到的值进行排序。此外，排序是稳定的，因为它使用索引本身作为二次比较。附带说明一下，为了使测试可靠，我不得不在并行循环中执行“indices.take(nb)”，因为排序会修改输入数组。与将我带到这里的问题相比，这种惩罚可以忽略不计。要点上的完整代码 here .

非常欢迎您提出改进建议。但尽量不要更改索引和分数数组的基本结构。

注意:我在 scala 2.10 REPL 中运行。

Answer 1

问题是 scala.math.Ordering 不是特化的。因此，每次您使用 Int 等原语调用比较方法时，Int 类型的两个参数都会被装箱到 java.lang.Integer。这会产生大量短暂的对象，这会大大减慢速度。

spire library有一个特殊版本的 Ordering 称为 spire.algebra.Order那应该快得多。您可以尝试在您的代码中替换它并再次运行您的基准测试。

还有sorting algorithms在尖顶。所以也许只是尝试那些。

基本上，只要您想以高性能的方式使用原语进行数学运算，spire 就是您的不二之选。

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