Swift的性能：sorting数组

我在Swift中实现了一个algorithm，注意到性能非常差。 深入挖掘之后，我意识到其中一个瓶颈就像分类数组一样简单。 相关部分在这里：

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 =sorting（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与“释放”与“debugging”构build时间是类似的。

这里有什么问题？ 我可以理解一些与C ++相比的性能损失，但与纯Python相比，不会减less10倍。

---

编辑： mweathers注意到，改变-O3到-Ofast使得这个代码运行几乎一样快的C + +版本！ 然而， -Ofast改变了语言的语义 – 在我的testing中，它禁止了对整数溢出和数组索引溢出的检查 。 例如，用-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中获得合理的performance呢？

---

编辑2：我做了一些更多的基准testing，使用非常简单的循环

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

（这里的异或操作只是为了让我能够更容易地find汇编代码中的相关循环，我试图select一个易于识别的操作，但也是“无害”的，因为它不需要任何相关的检查到整数溢出。）

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

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

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

---

编辑3：在评论中，Ferruccio要求在不依赖内置函数（例如sorting）的意义上公平的基准。 我觉得下面的程序是一个很好的例子：

 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 6testing版5中得到修复。

为了sorting，我现在有以下时间：

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

对于嵌套循环：

• 铛++ -O3：0.06秒
• swiftc – 快：0.3秒
• swiftc -O：0.4 s
• swiftc：540秒

似乎没有理由再使用不安全的-Ofast （又名-Ounchecked ）; 平原-O产生同样好的代码。

Answer 1

tl;通过使用默认版本优化级别[-O]的这个基准testing，Swift现在与C一样快。

这里是一个Swift就地快速sorting：

 func quicksort_swift(inout a:CInt[], start:Int, end:Int) { if (end - start < 2){ return } var p = a[start + (end - start)/2] var l = start var r = end - 1 while (l <= r){ if (a[l] < p){ l += 1 continue } if (a[r] > p){ r -= 1 continue } var t = a[l] a[l] = a[r] a[r] = t l += 1 r -= 1 } quicksort_swift(&a, start, r + 1) quicksort_swift(&a, r + 1, end) } 

和C一样：

 void quicksort_c(int *a, int n) { if (n < 2) return; int p = a[n / 2]; int *l = a; int *r = a + n - 1; while (l <= r) { if (*l < p) { l++; continue; } if (*r > p) { r--; continue; } int t = *l; *l++ = *r; *r-- = t; } quicksort_c(a, r - a + 1); quicksort_c(l, a + n - l); } 

两者都工作：

 var a_swift:CInt[] = [0,5,2,8,1234,-1,2] var a_c:CInt[] = [0,5,2,8,1234,-1,2] quicksort_swift(&a_swift, 0, a_swift.count) quicksort_c(&a_c, CInt(a_c.count)) // [-1, 0, 2, 2, 5, 8, 1234] // [-1, 0, 2, 2, 5, 8, 1234] 

这两个都是写在同一个程序中。

 var x_swift = CInt[](count: n, repeatedValue: 0) var x_c = CInt[](count: n, repeatedValue: 0) for var i = 0; i < n; ++i { x_swift[i] = CInt(random()) x_c[i] = CInt(random()) } let swift_start:UInt64 = mach_absolute_time(); quicksort_swift(&x_swift, 0, x_swift.count) let swift_stop:UInt64 = mach_absolute_time(); let c_start:UInt64 = mach_absolute_time(); quicksort_c(&x_c, CInt(x_c.count)) let c_stop:UInt64 = mach_absolute_time(); 

这将绝对时间转换为秒：

 static const uint64_t NANOS_PER_USEC = 1000ULL; static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC; static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC; mach_timebase_info_data_t timebase_info; uint64_t abs_to_nanos(uint64_t abs) { if ( timebase_info.denom == 0 ) { (void)mach_timebase_info(&timebase_info); } return abs * timebase_info.numer / timebase_info.denom; } double abs_to_seconds(uint64_t abs) { return abs_to_nanos(abs) / (double)NANOS_PER_SEC; } 

以下是编译器优化级别的摘要：

 [-Onone] no optimizations, the default for debug. [-O] perform optimizations, the default for release. [-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks. 

n = 10_000时 ， [-Onone]的秒数 ：

 Swift: 0.895296452 C: 0.001223848 

这里是Swift的内置sorting（） n = 10_000 ：

 Swift_builtin: 0.77865783 

这里是n = 10_000的 [-O] ：

 Swift: 0.045478346 C: 0.000784666 Swift_builtin: 0.032513488 

如你所见，Swift的performance提升了20倍。

根据mweathers的回答 ，设置[-Ofast]会产生真正的差异，导致n = 10_000 ：

 Swift: 0.000706745 C: 0.000742374 Swift_builtin: 0.000603576 

而对于n = 1_000_000 ：

 Swift: 0.107111846 C: 0.114957179 Swift_sort: 0.092688548 

为了比较，这与n = 1_000_000的 [-Onone] ：

 Swift: 142.659763258 C: 0.162065333 Swift_sort: 114.095478272 

所以在没有优化的情况下，Swift在这个基准testing阶段比C慢了将近1000倍。 另一方面，如果两个编译器设置为[-Ofast]，则Swift实际上至less要比C稍好一些。

有人指出[-Ofast]会改变语言的语义，使其可能不安全。 这就是Apple在Xcode 5.0发行说明中所说的：

LLVM中提供了一个新的优化级别-Ofast，可以进行积极的优化。 -Ofast放松了一些保守的限制，主要是为了浮点操作，对于大多数代码来说都是安全的。 它可以从编译器中获得显着的高性能。

他们都提倡它。 不pipe这是否明智，我不能说，但从我可以告诉，如果你没有做高精度的浮点运算，并且你确信没有整数或数组溢出在你的程序中是可能的。 如果你确实需要高性能和溢出检查/精确算术，那么现在select另一种语言。

BETA 3更新：

n = 10_000与[-O] ：

 Swift: 0.019697268 C: 0.000718064 Swift_sort: 0.002094721 

总的来说Swift要快一点，看起来Swift的内置类已经发生了很大的变化。

最终更新：

[-Onone] ：

 Swift: 0.678056695 C: 0.000973914 

[-O] ：

 Swift: 0.001158492 C: 0.001192406 

[-Ounchecked] ：

 Swift: 0.000827764 C: 0.001078914 

Answer 2

TL; DR ：是的，现在唯一的Swift语言执行速度很慢。 如果你需要快速，数字（和其他types的代码，大概是）代码，只需要与另一个代码。 将来，你应该重新评估你的select。 尽pipe如此，对于大多数应用程序代码来说，它可能已经足够了。

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

正如许多人所说， -Ofast是完全不安全的，并改变了语言的语义。 对我来说，就是在“如果你要使用这个，就用另一种语言”的阶段。 如果它改变，我会在稍后重新评估这个select。

-O3得到了一堆swift_retain和swift_release调用，说实话，看起来他们不应该在这个例子中。 优化器应该已经消除了（大部分）AFAICT，因为它知道大部分有关数组的信息，并且知道它至less有一个强烈的引用。

当它甚至不调用可能释放对象的函数时，它不应该释放更多的保留。 我不认为一个数组构造函数可以返回一个小于要求的数组，这意味着大量的检查是无用的。 它也知道整数永远不会超过10k，所以溢出检查可以被优化（不是因为-Ofast古怪，而是因为语言的语义（没有别的东西正在改变那个var也不能访问它，并且加起来到10K对Inttypes是安全的）。

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

这是一个非常新的（公开的）语言，它正在经历我所假设的许多变化，因为有人（重）涉及到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运行时的所有设备。 我也可能会假设一些我没有写的东西。

Answer 3

我决定看看这个有趣的，这里是我得到的时机：

 Swift 4.0.2 : 0.83s (0.74s with `-Ounchecked`) C++ (Apple LLVM 8.0.0): 0.74s 

迅速

 // Swift 4.0 code import Foundation func doTest() -> Void { let arraySize = 10000000 var randomNumbers = [UInt32]() for _ in 0..<arraySize { randomNumbers.append(arc4random_uniform(UInt32(arraySize))) } let start = Date() randomNumbers.sort() let end = Date() print(randomNumbers[0]) print("Elapsed time: \(end.timeIntervalSince(start))") } doTest() 

结果：

Swift 1.1

 xcrun swiftc --version Swift version 1.1 (swift-600.0.54.20) Target: x86_64-apple-darwin14.0.0 xcrun swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 1.02204304933548 

Swift 1.2

 xcrun swiftc --version Apple Swift version 1.2 (swiftlang-602.0.49.6 clang-602.0.49) Target: x86_64-apple-darwin14.3.0 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.738763988018036 

Swift 2.0

 xcrun swiftc --version Apple Swift version 2.0 (swiftlang-700.0.59 clang-700.0.72) Target: x86_64-apple-darwin15.0.0 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.767306983470917 

如果我使用-Ounchecked编译，这似乎是相同的性能。

Swift 3.0

 xcrun swiftc --version Apple Swift version 3.0 (swiftlang-800.0.46.2 clang-800.0.38) Target: x86_64-apple-macosx10.9 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.939633965492249 xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift ./SwiftSort Elapsed time: 0.866258025169373 

从Swift 2.0到Swift 3.0似乎已经有了一个性能的回归，而且我也第一次看到了-O和-Ounchecked之间的区别。

Swift 4.0

 xcrun swiftc --version Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38) Target: x86_64-apple-macosx10.9 xcrun -sdk macosx swiftc -O SwiftSort.swift ./SwiftSort Elapsed time: 0.834299981594086 xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift ./SwiftSort Elapsed time: 0.742045998573303 

Swift 4再次提高性能，同时保持-O和-Ounchecked之间的差距。 -O -whole-module-optimization似乎没有什么区别。

C ++

 #include <chrono> #include <iostream> #include <vector> #include <cstdint> #include <stdlib.h> using namespace std; using namespace std::chrono; int main(int argc, const char * argv[]) { const auto arraySize = 10000000; vector<uint32_t> randomNumbers; for (int i = 0; i < arraySize; ++i) { randomNumbers.emplace_back(arc4random_uniform(arraySize)); } const auto start = high_resolution_clock::now(); sort(begin(randomNumbers), end(randomNumbers)); const auto end = high_resolution_clock::now(); cout << randomNumbers[0] << "\n"; cout << "Elapsed time: " << duration_cast<duration<double>>(end - start).count() << "\n"; return 0; } 

结果：

苹果铿锵6.0

 clang++ --version Apple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn) Target: x86_64-apple-darwin14.0.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.688969 

苹果铿锵6.1.0

 clang++ --version Apple LLVM version 6.1.0 (clang-602.0.49) (based on LLVM 3.6.0svn) Target: x86_64-apple-darwin14.3.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.670652 

苹果铿锵7.0.0

 clang++ --version Apple LLVM version 7.0.0 (clang-700.0.72) Target: x86_64-apple-darwin15.0.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.690152 

苹果铿锵8.0.0

 clang++ --version Apple LLVM version 8.0.0 (clang-800.0.38) Target: x86_64-apple-darwin15.6.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.68253 

苹果铿锵9.0.0

 clang++ --version Apple LLVM version 9.0.0 (clang-900.0.38) Target: x86_64-apple-darwin16.7.0 Thread model: posix clang++ -O3 -std=c++11 CppSort.cpp -o CppSort ./CppSort Elapsed time: 0.736784 

判决书

截至本文写作之时，Swift的sorting很快，但还不及C ++用-O编译时的sorting速度，还有上面的编译器和库。 通过-Ounchecked ，它在Swift 4.0.2和Apple LLVM 9.0.0中似乎与C ++一样快。

Answer 4

从The Swift Programming Language ：

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

sort函数有两个声明。

默认声明允许你指定一个比较闭包：

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

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

 func sort<T : Comparable>(array: T[]) -> T[] Example: sort( _arrayToSort_ ) { $0 > $1 } 

我在一个操作系统中testing了代码的修改版本，添加了闭包，所以我可以更仔细地监视这个函数，而且我发现在n设置为1000的情况下，闭包被称为大约11000次。

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

这不是一个有效的函数，我会build议使用更好的sortingfunction实现。

编辑：

我看了一下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个比较

看来，内置的sorting方法是（或接近）快速sorting，真的很慢…

Answer 5

从Xcode 7开始，您可以打开Fast, Whole Module Optimization 。 这应该立即增加您的performance。

Answer 6

Swiftarrays性能重新审视：

我写了自己的基准比较Swift和C / Objective-C。 我的基准计算素数。 它使用以前的素数数组来寻找每个新候选人的素数因子，因此速度相当快。 但是，它会读取数组的TONS，而不会写入数组。

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

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

对于C / Objective-C，您可以select使用NSArrays或C malloc'ed数组。

testing结果看起来与最快，最小的代码优化（[-0s]）或最快，最积极的（[-0fast]）优化非常相似。

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

底线是C malloc'd基于数组的计算速度最快，幅度适中

使用快速，最小的代码优化时，带有不安全缓冲区的Swift比C malloc'd数组长1.19X – 1.20X。 与快速，积极的优化，差异似乎略有减less（Swift需要比1.18x长1.16倍多。

如果你使用普通的Swift数组，与C的区别稍大 。 （Swift花费大约1.22至1.23。）

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

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

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

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

有趣的是，Swift中的sorting似乎比C中的要快一些，但是这个素数algorithm在Swift中仍然更快。

Answer 7

其他人提到的主要问题是， -O3在Swift中根本就没有做任何事情，所以在编译的时候它并没有被优化（ -Onone ）。

选项名称随着时间的推移已经改变了，所以一些其他的答案对于构build选项来说已经过时了。 正确的当前选项（Swift 2.2）是：

 -Onone // Debug - slow -O // Optimised -O -whole-module-optimization //Optimised across files 

整个模块优化有一个较慢的编译，但可以优化模块内的文件，即在每个框架内和实际的应用程序代码，但不是在他们之间。 你应该使用这个任何关键的性能）

您还可以禁用安全检查，以获得更高的速度，但所有断言和先决条件不仅仅是禁用，而是基于它们是正确的进行了优化。 如果你打了一个断言，这意味着你陷入了未定义的行为。 只有当你确定速度提升对你来说是值得的（通过testing）时，要特别谨慎使用。 如果你确实发现它对于某些代码是有价值的，我build议把这个代码分离到一个单独的框架中，并且只对这个模块禁用安全检查。

Answer 8

 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) 

这是我的博客快速sortinghttps://github.com/ahmad-atef/Algorithms-DataStructures/wiki/Quick-Sort

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