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

来自 Swift 编程语言：

排序函数 Swift 的标准库提供了一个名为 sort，它根据 您提供的排序闭包的输出。一旦完成 排序过程中，sort 函数返回一个相同的新数组 type 和 size 与旧类型相同，其元素排序正确 次序。

该函数有两个声明。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 = 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. 大约有 10,000 个比较

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

tl;dr Swift 1.0 现在与 C 一样快，使用默认版本优化级别 [-O]。

---

以下是 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 = 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 内置的 sort（） for n=10_000：

Swift_builtin:    0.77865783

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

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

正如你所看到的，Swift 的性能提高了 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 在其开发的这个阶段几乎比 C 慢 1000 倍。另一方面，当两个编译器都设置为 [-Ofast] 时，Swift 实际上的性能至少和 C 一样好，甚至略好。

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

LLVM 中提供了新的优化级别 -Ofast，可实现积极的优化。-Ofast 放宽了一些保守的限制，主要针对浮点运算，这些限制对大多数代码都是安全的。它可以从编译器中产生显著的高性能胜利。

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

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

TL;DR：是的，目前唯一的 Swift 语言实现速度很慢。如果您需要快速的数字（和其他类型的代码，大概）代码，只需使用另一个代码即可。将来，您应该重新评估您的选择。不过，对于大多数在更高级别编写的应用程序代码来说，它可能已经足够好了。

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

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

-O3让我们一堆，并打电话给我们，老实说，看起来他们不应该出现在这个例子中。优化器应该省略（大部分）它们 AFAICT，因为它知道有关数组的大部分信息，并且知道它（至少）对数组有很强的引用。swift_retainswift_release

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

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

这是一种非常新的（公开的）语言，它正在经历很多变化，因为有人（大量）参与 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")

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

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

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()

结果：

斯威夫特 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

斯威夫特 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

斯威夫特 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

斯威夫特 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

斯威夫特 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 的排序速度很快，但在使用上述编译器和库编译时还不如 C++ 的排序快。有了，它似乎和 Swift 4.0.2 和 Apple LLVM 9.0.0 中的 C++ 一样快。-O-Ounchecked

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

重新审视 Swift Array 性能：

我编写了自己的基准测试，将 Swift 与 C/Objective-C 进行了比较。我的基准测试计算质数。它使用先前的质数数组来寻找每个新候选者的质因数，因此速度非常快。但是，它执行了大量的数组读取，并且较少地写入数组。

我最初是针对 Swift 1.2 进行此基准测试的。我决定更新项目并针对 Swift 2.0 运行它。

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

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

测试结果似乎与最快、最小的代码优化 （[-0s]） 或最快、最激进的 （[-0fast]） 优化非常相似。

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

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

当使用最快、最小的代码优化时，带有不安全缓冲区的 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 更快。它们的性能非常接近 Swift 基于不安全缓冲区的数组，以至于使用不安全的内存缓冲区似乎不再值得麻烦了，这已经很大了。DRAMATICALLY

顺便说一句，Objective-C NSArray 性能很糟糕。如果你打算在两种语言中使用原生容器对象，那么 Swift 会快得多。

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

它有一个简单的用户界面，使收集统计数据变得非常容易。

有趣的是，现在 Swift 中的排序似乎比 C 中的排序略快，但这种质数算法在 Swift 中仍然更快。

其他人提到但未被充分提及的主要问题是它在 Swift 中根本没有做任何事情（而且从来没有），所以当它编译时，它实际上是非优化的（）。-O3-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 = 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 示例快速排序

您可以在 Partitioning the list 中查看 Lomuto 的分区算法。用 Swift 编写。

Swift 4.1 引入了新的优化模式。-Osize

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

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

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

延伸阅读 ： https://swift.org/blog/osize/