Swift性能:对数组进行排序



Answers

TL; DR :是的,现在唯一的Swift语言实施速度很慢。 如果你需要快速的,数字的(和其他类型的代码,大概是)代码,那就去另一个。 将来,你应该重新评估你的选择。 不过,对于大多数应用程序代码而言,它可能已经足够好了。

从我在SIL和LLVM IR中看到的情况看来,他们似乎需要一系列优化来移除保留和释放,这可能会在Clang (Objective-C)中实现,但他们还没有移植它们。 这就是我正在使用的理论(现在...我仍然需要确认Clang是否做了些什么),因为在这个问题的最后一个测试案例上运行的分析器产生了这个“相当”的结果:

正如许多人所说的, -Ofast是完全不安全的,并改变了语言语义。 对我而言,它是在“如果你要使用它,只是使用另一种语言”阶段。 如果它发生变化,我会在稍后重新评估这一选择。

-O3给我们带来了一堆swift_retainswift_release调用,说实话,看起来他们不应该在这个例子中。 优化器应该已经消除了AFAICT(大部分),因为它知道大部分关于数组的信息,并且知道它至少有一个很强的参考。

当它甚至不调用可能释放对象的函数时,它不应该释放更多的保留。 我不认为一个数组构造函数可以返回一个比要求的数组小的数组,这意味着很多发出的检查都是无用的。 它也知道整数永远不会超过10k,所以溢出检查可以被优化(不是因为-Ofast怪异,而是因为语言的语义(没有其他的东西正在改变那个-Ofast也不能访问它,并且加起来到10k对Int类型是安全的)。

不过,编译器可能无法解开数组或数组元素,因为它们正在传递给sort() ,这是一个外部函数,必须获取它所期望的参数。 这将使我们不得不间接使用Int值,这会使它变慢一点。 如果sort()通用函数(不是以多方法的方式)可用于编译器并被内联,这可能会改变。

这是一种非常新的(公开)语言,并且它正在经历我所做的很多改变,因为有很多人(很大程度上)参与了Swift语言的要求反馈,并且他们都说语言没有完成,并且更改。

使用的代码:

import Cocoa

let swift_start = NSDate.timeIntervalSinceReferenceDate();
let n: Int = 10000
let x = Int[](count: n, repeatedValue: 1)
for i in 0..n {
    for j in 0..n {
        let tmp: Int = x[j]
        x[i] = tmp
    }
}
let y: Int[] = sort(x)
let swift_stop = NSDate.timeIntervalSinceReferenceDate();

println("\(swift_stop - swift_start)s")

PS:我不是Objective-C的专家,也不是来自Cocoa ,Objective-C或Swift运行时的所有设施。 我可能也会假设一些我没有写的东西。

Question

我在Swift中实现了一个算法,并注意到性能非常差。 在深入挖掘之后,我意识到其中一个瓶颈就像排序数组一样简单。 相关部分在这里:

let n = 1000000
var x =  [Int](repeating: 0, count: n)
for i in 0..<n {
    x[i] = random()
}
// start clock here
let y = sort(x)
// stop clock here

在C ++中,类似的操作在我的计算机上需要0.06秒

在Python中,它需要0.6秒 (没有技巧,只是y =整数列表中的排序(x))。

在Swift中,如果使用以下命令编译它,则需要6秒

xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`

如果我使用以下命令编译它,则需要多达88秒的时间

xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`

Xcode的“发布”与“调试”版本的时间类似。

这里有什么问题? 与C ++相比,我可以理解一些性能损失,但与纯Python相比,不会减少10倍。

编辑: mweathers注意到将-O3更改为-Ofast使得此代码几乎与C ++版本一样快! 然而, -Ofast改变了语言的语义 - 在我的测试中,它禁用了对整数溢出和数组索引溢出的检查 。 例如,使用-Ofast ,以下Swift代码默默运行而不会崩溃(并打印出一些垃圾):

let n = 10000000
print(n*n*n*n*n)
let x =  [Int](repeating: 10, count: n)
print(x[n])

所以-Ofast不是我们想要的; Swift的重点在于我们拥有安全网。 当然安全网对性能有一定影响,但不应该使节目慢100倍。 请记住,Java已经检查了数组边界,并且在一般情况下,放缓速度比2小很多。在Clang和GCC中,我们有用于检查(带符号)整数溢出的-ftrapv ,而且速度并不慢。

因此,我们如何在不丢失安全网的情况下在Swift中获得合理的表现?

编辑2:我做了一些更多的基准测试,并且沿着非常简单的循环

for i in 0..<n {
    x[i] = x[i] ^ 12345678
}

(这里的xor操作只是为了让我可以更容易地在汇编代码中找到相关的循环,我试图选择一个易于识别的操作,但也是“无害”的,因为它不需要任何相关的检查到整数溢出。)

再一次, -O3-Ofast之间的性能差异-Ofast 。 所以我看了一下汇编代码:

  • 随着-Ofast我几乎得到了我所期望的。 相关部分是一个包含5条机器语言指令的循环。

  • -O3我得到的东西超出了我最疯狂的想象。 内循环跨越88行汇编代码。 我没有试图理解所有这些,但最可疑的部分是13个“callq _swift_retain”调用和另外13个“callq _swift_release”调用。 也就是说, 在内部循环中调用26个子程序

编辑3:在评论中,Ferruccio要求的基准是公平的,因为他们不依赖内置函数(例如排序)。 我认为下面的程序是一个很好的例子:

let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

没有算术,所以我们不需要担心整数溢出。 我们所做的唯一的事情就是大量的数组引用。 结果在这里 - 与-Ofast相比,Swift -O3几乎损失了500倍:

  • C ++ -O3: 0.05秒
  • C ++ -O0:0.4 s
  • Java: 0.2秒
  • Python与PyPy:0.5秒
  • Python: 12秒
  • 迅速 - 快速:0.05秒
  • Swift -O3: 23 s
  • Swift -O0:443 s

(如果你担心编译器会完全优化无意义的循环,你可以把它改成例如x[i] ^= x[j] ,并添加一个输出x[0]的打印语句,这并不会改变任何东西;时间将非常相似。)

是的,这里的Python实现是一个愚蠢的纯Python实现,带有ints列表和嵌套for循环。 它应该比未优化的Swift慢得多。 Swift和数组索引似乎严重破坏了某些东西。

编辑4:这些问题(以及一些其他性能问题)似乎在Xcode 6 beta 5中得到了修复。

为了排序,我现在有以下时间:

  • 铛++ -O3:0.06秒
  • swiftc - 快:0.1秒
  • swiftc -O:0.1秒
  • swiftc:4秒

对于嵌套循环:

  • 铛++ -O3:0.06秒
  • swiftc - 快速:0.3秒
  • swiftc -O:0.4秒
  • swiftc:540秒

看起来没有理由再使用不安全的-Ofast (又名-Ounchecked ); 平原-O产生同样好的代码。




来自The Swift Programming Language

Sort函数Swift的标准库提供了一个称为sort的函数,它根据您提供的排序闭包的输出对已知类型的值的数组进行排序。 一旦完成排序过程,排序函数将返回一个与旧排序相同类型和大小的新数组,其元素按正确的排序顺序排列。

sort函数有两个声明。

默认声明允许您指定比较闭包:

func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]

而第二个声明只需要一个参数(数组),并且“硬编码为使用小于比较器”。

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

我在一个操场上测试了代码的修改版本,添加了闭包,所以我可以更密切地监视函数,并且我发现在n设置为1000时,闭包被称为约11,000次。

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

这不是一个有效的函数,我会建议使用更好的排序功能实现。

编辑:

我看了一下Quicksort维基百科页面,并为它写了一个Swift实现。 这里是我使用的完整程序(在游乐场)

import Foundation

func quickSort(inout array: Int[], begin: Int, end: Int) {
    if (begin < end) {
        let p = partition(&array, begin, end)
        quickSort(&array, begin, p - 1)
        quickSort(&array, p + 1, end)
    }
}

func partition(inout array: Int[], left: Int, right: Int) -> Int {
    let numElements = right - left + 1
    let pivotIndex = left + numElements / 2
    let pivotValue = array[pivotIndex]
    swap(&array[pivotIndex], &array[right])
    var storeIndex = left
    for i in left..right {
        let a = 1 // <- Used to see how many comparisons are made
        if array[i] <= pivotValue {
            swap(&array[i], &array[storeIndex])
            storeIndex++
        }
    }
    swap(&array[storeIndex], &array[right]) // Move pivot to its final place
    return storeIndex
}

let n = 1000
var x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = Int(arc4random())
}

quickSort(&x, 0, x.count - 1) // <- Does the sorting

for i in 0..n {
    x[i] // <- Used by the playground to display the results
}

使用n = 1000,我发现

  1. quickSort()被调用约650次,
  2. 进行了大约6000次掉期交易,
  3. 并有大约10000个比较

看起来内置的排序方法是(或接近)快速排序,而且非常慢...




func partition(inout list : [Int], low: Int, high : Int) -> Int {
    let pivot = list[high]
    var j = low
    var i = j - 1
    while j < high {
        if list[j] <= pivot{
            i += 1
            (list[i], list[j]) = (list[j], list[i])
        }
        j += 1
    }
    (list[i+1], list[high]) = (list[high], list[i+1])
    return i+1
}

func quikcSort(inout list : [Int] , low : Int , high : Int) {

    if low < high {
        let pIndex = partition(&list, low: low, high: high)
        quikcSort(&list, low: low, high: pIndex-1)
        quikcSort(&list, low: pIndex + 1, high: high)
    }
}

var list = [7,3,15,10,0,8,2,4]
quikcSort(&list, low: 0, high: list.count-1)

var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quikcSort(&list2, low: 0, high: list2.count-1)

var list3 = [1,3,9,8,2,7,5]
quikcSort(&list3, low: 0, high: list3.count-1) 

这是我的关于快速排序的博客 - Github示例快速排序

您可以在分区列表中查看Lomuto的分区算法。 写在Swift中




Swift Array性能重新审视:

我写了自己的基准,比较Swift和C / Objective-C。 我的基准计算素数。 它使用以前的素数数组来寻找每个新候选人的素数因子,所以它非常快。 但是,它会进行数组读取,而不会写入数组。

我原先是对Swift 1.2做这个基准的。 我决定更新该项目并针对Swift 2.0运行它。

该项目让您选择使用普通的swift数组和使用数组语义的Swift不安全内存缓冲区。

对于C / Objective-C,您可以选择使用NSArrays或C malloc'ed数组。

测试结果与最快,最小的代码优化([-0s])或最快,最积极(最快(最快)]优化似乎非常相似。

在关闭代码优化的情况下,Swift 2.0的性能仍然很糟糕,而C / Objective-C的性能只是稍微慢一些。

底线是C malloc'd基于数组的计算速度最快,幅度不大

使用最快,最小的代码优化时,带有不安全缓冲区的Swift比C malloc'd数组长1.19X - 1.20X。 与快速,积极的优化相比,差异似乎稍微小一些(Swift比C更长1.18倍到1.16倍。

如果你使用普通的Swift数组,与C的差别稍大 。 (Swift花费大约1.22到1.23。)

普通的Swift数组比DRAMATICALLY速度上要快于在Swift 1.2 / Xcode 6中的速度。它们的性能非常接近Swift不安全的基于缓冲区的数组,使用不安全的内存缓冲区看起来并不值得麻烦,这很大。

顺便说一句,Objective-C的NSArray性能很糟糕。 如果你打算在两种语言中使用本地容器对象,Swift的运行速度会更快。

您可以在SwiftPerformanceBenchmark上的github上查看我的项目

它有一个简单的用户界面,使收集统计很容易。

有趣的是,Swift中的排序似乎比C中的稍快,但这个素数算法在Swift中仍然更快。




Links