Swift Beta性能：对数组进行排序

我在Swift Beta中实现了一个算法，注意到性能非常差。深入挖掘后，我意识到其中一个瓶颈是排序数组这样简单的东西。相关部分在这里：

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

C++，类似的操作在我的计算机上执行0.06s。

在Python中，它需要0.6s（没有技巧，只是y=sorted（x）作为整数列表）。

在Swift中，如果我使用以下命令编译它，则需要6s：

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

如果我使用以下命令编译它，它需要尽可能多的88s：

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

Xcode中带有“发布”和“调试”版本的时间是相似的。

这里有什么问题？与C++相比，我可以理解一些性能损失，但与纯Python相比，速度下降了10倍。

编辑：天气注意到，将-O3更改为-Ofast使此代码的运行速度几乎与C++版本一样快！然而，-Ofast改变了该语言的语义学很多-在我的测试中，它禁用整数溢出和数组索引溢出检查。例如，使用-Ofast，以下Swift代码静默运行而不崩溃（并打印出一些垃圾）：

let n = 10000000print(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，我几乎得到了我所期望的。相关部分是包含5条机器语言指令的循环。

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

编辑3：在评论中，Ferruccio要求基准测试是公平的，因为它们不依赖于内置函数（例如排序）。我认为以下程序是一个相当好的例子：

let n = 10000var 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.2s
  • Python与PyPy：0.5 s
  • python：12秒
  • Swift-OFast：0.05秒
  • Swift-O3：23秒
  • Swift-O0:443 s

（如果您担心编译器可能会完全优化无意义的循环，您可以将其更改为例如x[i] ^= x[j]，并添加输出x[0]的print语句。这不会改变任何事情；时间将非常相似。）

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

编辑4：这些问题（以及其他一些性能问题）似乎已在Xcode 6 beta 5中得到修复。

对于排序，我现在有以下时间：

  • clang++-O3:0.06 s
  • Swiftc-OFast：0.1 s
  • Swiftc-O：0.1 s
  • Swiftc：4秒

对于嵌套循环：

  • clang++-O3:0.06 s
  • Swiftc-OFast：0.3 s
  • Swiftc-O：0.4 s
  • Swiftc：540秒

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

117574 次浏览
小开

从The Swift Programming Language：

Sort Function Swift的标准库提供了一个名为排序，它对已知类型的值数组进行排序，基于您提供的排序闭包的输出。一旦它完成了排序过程中，排序函数返回相同的新数组类型和大小与旧的一样，其元素排序正确命令。

sort函数有两个声明。

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

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

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

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

我在Playground中测试了代码的修改版本，并添加了闭包，以便我可以更密切地监控函数，我发现当n设置为1000时，闭包被调用了大约11,000次。

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

它不是一个高效的函数，我建议使用更好的排序函数实现。

编辑：

我查看了快速排序维基百科页面并为其编写了一个Swift实现。这是我使用的完整程序（在Playground中）

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 + 1let pivotIndex = left + numElements / 2let pivotValue = array[pivotIndex]swap(&array[pivotIndex], &array[right])var storeIndex = leftfor i in left..right {let a = 1 // <- Used to see how many comparisons are madeif array[i] <= pivotValue {swap(&array[i], &array[storeIndex])storeIndex++}}swap(&array[storeIndex], &array[right]) // Move pivot to its final placereturn storeIndex}
let n = 1000var 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. 大约有10,000个比较

似乎内置的排序方法是（或接近）快速排序，而且真的很慢…

小开
最佳答案

TL； dr Swift 1.0现在使用默认的发布优化级别[-O]与C一样快。

这是Swift Beta中的一个就地快速排序：

func quicksort_swift(inout a:CInt[], start:Int, end:Int) {if (end - start < 2){return}var p = a[start + (end - start)/2]var l = startvar r = end - 1while (l <= r){if (a[l] < p){l += 1continue}if (a[r] > p){r -= 1continue}var t = a[l]a[l] = a[r]a[r] = tl += 1r -= 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.

时间以秒为单位，[-Onone]为n=10_000：

Swift:            0.895296452C:                0.001223848

这是Swift对n=10_000的内置排序（）：

Swift_builtin:    0.77865783

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

Swift:            0.045478346C:                0.000784666Swift_builtin:    0.032513488

如您所见，Swift的性能提高了20倍。

根据麦威瑟斯的回答，设置[-奥法斯特]产生了真正的差异，导致n=10_000的这些时间：

Swift:            0.000706745C:                0.000742374Swift_builtin:    0.000603576

对于n=1_000_000：

Swift:            0.107111846C:                0.114957179Swift_sort:       0.092688548

为了比较，这是[-Onone] forn=1_000_000：

Swift:            142.659763258C:                0.162065333Swift_sort:       114.095478272

因此，在这个开发阶段，没有优化的Swift在这个基准测试中比C慢了近1000倍。另一方面，当两个编译器都设置为[-OFast]时，Swift实际上的表现至少与C一样好，甚至略好于C。

有人指出[-OFast]改变了语言的语义学，使其具有潜在的不安全性。这是Apple在Xcode 5.0发行说明中的声明：

一个新的优化级别-OFast，可在LLVM中使用，支持积极的优化。-OFast放宽了一些保守的限制，主要用于浮点运算，这些限制对大多数代码来说是安全的。它可以从编译器中获得显着的高性能胜利。

他们几乎都提倡这样做。我不能说这是否明智，但据我所知，如果你不做高精度浮点运算，并且你有信心在你的程序中不可能出现整数或数组溢出，那么在版本中使用[-OFast]似乎足够合理。如果你确实需要高性能和溢出检查/精确算术，那么现在选择另一种语言。

BETA 3更新：

n=10_000和[-O]：

Swift:            0.019697268C:                0.000718064Swift_sort:       0.002094721

一般来说，Swift的速度要快一些，看起来Swift的内置排序已经发生了相当大的变化。

最后更新：

[-Onone]：

Swift:   0.678056695C:       0.000973914

[-O]：

Swift:   0.001158492C:       0.001192406

[-未选中]：

Swift:   0.000827764C:       0.001078914
小开

现在。如果你需要快速的数字（大概还有其他类型的代码）代码，那就用另一种代码。以后，你应该重新评估你的选择。不过，对于大多数在更高级别编写的应用程序代码来说，这可能已经足够了。

从我在SIL和LLVM IR中看到的情况来看，似乎他们需要一系列优化来删除保留和发布，这可能在Clang（用于Objective-C）中实现，但他们还没有移植它们。这就是我要采用的理论（目前……我仍然需要确认Clang对此做了些什么），因为在这个问题的最后一个测试用例上运行分析器会产生这个“漂亮”的结果：

-O3上的时间分析-OFast上的时间分析

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

-O3为我们提供了一堆swift_retain和swift_release调用，老实说，它们看起来不应该出现在这个例子中。优化器应该省略（大部分）它们AFAICT，因为它知道有关数组的大部分信息，并且知道它有（至少）对它的强引用。

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

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

这是一种非常新的（公开的）语言，它正在经历我认为是很多变化，因为有人（大量）参与了Swift语言，要求反馈，他们都说语言还没有完成，将改变。

使用的代码：

import Cocoa
let swift_start = NSDate.timeIntervalSinceReferenceDate();let n: Int = 10000let 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")

附言：我不是Objective-C的专家，也不是可可、Objective-C或Swift运行时的所有工具。我也可能假设一些我没有写的东西。

小开

我决定为了好玩而看看这个，以下是我得到的时间：

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

Swift

// Swift 4.0 codeimport Foundation
func doTest() -> Void {let arraySize = 10000000var 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()

结果：

Swift1.1

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

Swift1.2

xcrun swiftc --versionApple 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./SwiftSortElapsed time: 0.738763988018036

Swift2.0

xcrun swiftc --versionApple 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./SwiftSortElapsed time: 0.767306983470917

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

Swift3.0

xcrun swiftc --versionApple 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./SwiftSortElapsed time: 0.939633965492249
xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift./SwiftSortElapsed time: 0.866258025169373

从Swift 2.0到Swift 3.0似乎出现了性能倒退，我也第一次看到了-O和-Ounchecked之间的差异。

Swift4.0

xcrun swiftc --versionApple 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./SwiftSortElapsed time: 0.834299981594086
xcrun -sdk macosx swiftc -Ounchecked SwiftSort.swift./SwiftSortElapsed time: 0.742045998573303

Swift 4再次提高了性能，同时保持了-O和-Ounchecked之间的差距。

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++ --versionApple LLVM version 6.0 (clang-600.0.54) (based on LLVM 3.5svn)Target: x86_64-apple-darwin14.0.0Thread model: posix
clang++ -O3 -std=c++11 CppSort.cpp -o CppSort./CppSortElapsed time: 0.688969

Apple Clang 6.1.0

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

苹果叮当7.0.0

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

苹果叮当8.0.0

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

苹果叮当9.0.0

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

判决

在撰写本文时，Swift的排序速度很快，但还没有使用-O编译时C++的排序速度快，使用上述编译器和库。使用-Ounchecked，它似乎与Swift 4.0.2和Apple LLVM 9.0.0中的C++一样快。

小开

从Xcode 7开始，您可以打开Fast, Whole Module Optimization。这应该会立即提高您的性能。

输入图片描述

小开

重新审视Swift Array性能：

我编写了自己的基准测试来比较Swift和C/Objective-C。我的基准测试计算素数。它使用以前的素数数组来查找每个新候选者中的素数因子，所以速度相当快。然而，它读取数组的量很大，对数组的写入较少。

我最初是针对Swift 1.2做这个基准测试的。我决定更新项目并在Swift 2.0上运行它。

该项目允许您在使用普通的Swift数组和使用数组语义学的Swift不安全内存缓冲区之间进行选择。

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

测试结果似乎与最快、最小的代码优化（[-0]）或最快、积极的（[-0Fast]）优化非常相似。

关闭代码优化后，Swift 2.0的性能仍然很糟糕，而C/Objective-C的性能只是稍微慢一点。

最重要的是，基于C malloc的数组计算速度最快，幅度不大

当使用最快、最小的代码优化时，带有不安全缓冲区的Swift比C malloc的数组长1.19倍-1.20倍。快速、激进的优化（Swift比C长1.18倍到1.16倍）

如果您使用常规Swift数组，则与C的差异要大略。（Swift需要大约1.22到1.23的时间。）

普通的Swift数组比Swift 1.2/Xcode 6快DRAMATICALLY。它们的性能非常接近基于Swift不安全缓冲区的数组，以至于使用不安全的内存缓冲区似乎不再值得麻烦，这是很大的。

顺便说一句，Objective-C NSArray性能很差。如果您要在两种语言中使用本机容器对象，Swift的速度要快0。

您可以在GitHub上查看我的项目Swift性能基准

它有一个简单的UI，使收集统计数据非常容易。

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

小开

其他人提到但没有充分指出的主要问题是-O3在Swift中什么都不做（而且从来没有），所以当使用它编译时，它实际上是未优化的（-Onone）。

选项名称随着时间的推移而变化，因此其他一些答案的构建选项具有过时的标志。正确的当前选项（Swift 2.2）是：

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

整个模块优化的编译速度较慢，但可以优化模块内的文件，即每个框架内和实际应用程序代码内的文件，但不能在它们之间进行优化。您应该将此用于任何性能关键的事情）

您还可以禁用安全检查以获得更快的速度，但所有断言和先决条件不仅要禁用，还要在它们正确的基础上进行优化。如果您遇到断言，这意味着您进入了未定义的行为。要格外谨慎地使用，并且只有在您确定速度提升对您来说是值得的（通过测试）时才使用。如果您确实发现它对某些代码有价值，我建议将该代码分离到一个单独的框架中，并且只禁用该模块的安全检查。

小开 
func partition(inout list : [Int], low: Int, high : Int) -> Int {let pivot = list[high]var j = lowvar i = j - 1while 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写的。

小开

Swift4.1引入了新的-Osize优化模式。

在Swift 4.1中，编译器现在支持一种新的优化模式启用专用优化以减小代码大小。

Swift编译器带有强大的优化功能。编译时使用-O，编译器尝试转换代码以使其执行具有最大的性能。然而，运行时的这种改进性能有时会伴随着代码大小增加的权衡。使用新的-Osize优化模式，用户可以选择为最小的代码大小而不是最大的速度编译。

要在命令行上启用大小优化模式，请使用-Osize而不是-O。

更多阅读：https://swift.org/blog/osize/


提交答案