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

Question

我在使用Swift Beta实现一个算法时发现性能非常差。经过深入挖掘，我意识到其中一个瓶颈是像排序数组这样简单的事情。相关部分如下：

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中，对于一个整数列表，执行y = sorted(x)这个操作需要0.6秒（没有任何技巧）。

在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倍的减速。

---

编辑：weather注意到将-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
}

(这里使用异或操作只是为了更容易地在汇编代码中找到相关的循环。我尝试选择一种易于识别但也“无害”的操作，这意味着它不应需要与整数溢出相关的任何检查。)

同样，-O3和-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秒
• Java: 0.2秒
• Python with PyPy: 0.5秒
• Python: 12秒
• Swift -Ofast: 0.05秒
• Swift -O3: 23秒
• Swift -O0: 443秒

(如果您担心编译器可能会完全优化掉无意义的循环，您可以将其更改为例如 x[i] ^= x[j]并添加一个打印输出x[0]的语句。这不会改变任何内容;计时将非常相似。)

是的，在这里，Python 实现是一个愚蠢的纯 Python 实现，使用 int 的列表和嵌套的 for 循环。它应该比未经优化的 Swift 慢得多。Swift 和数组索引似乎存在严重问题。

---

Edit 4: 这些问题（以及其他一些性能问题）似乎已在 Xcode 6 beta 5 中得到解决。

对于排序，我现在有以下计时:

• clang++ -O3: 0.06秒
• swiftc -Ofast: 0.1秒
• swiftc -O: 0.1秒
• swiftc: 4秒

对于嵌套循环:

• clang++ -O3: 0.06秒
• swiftc -Ofast: 0.3秒
• swiftc -O: 0.4秒
• swiftc: 540秒

看来现在没有理由再使用不安全的 -Ofast（也称为-Ounchecked）了；普通的-O 产生的代码同样出色。

- Jukka Suomela

---

这里是另一个关于“Swift比C慢100倍”的问题：https://dev59.com/R2Af5IYBdhLWcg3w9mps。 - Jukka Suomela

这是有关苹果公司在Swift中的好性能方面所做的营销材料的讨论：http://programmers.stackexchange.com/q/242816/913 - Jukka Suomela

这个链接展示了一些基本操作，与Objective-C进行对比。 - Wold

@sjeohp，在生产过程中需要“安全网”，因为输入值是变化的。处理1-10范围内的数值并将它们相乘与处理2^31范围内的数值并将它们相乘是不同的。例如，臭名昭著的心脏出血漏洞就是由于缺乏范围检查而导致的。 - bestsss

随着Beta 5的发布，Swift的速度有了相当大的提升 -- 欲了解更多详细信息，请参见Jesse Squires的这篇文章。 - Nate Cook

Answer 1

简而言之，按照默认的发布优化级别[-O]，Swift 1.0现在已经与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 = 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.

使用[-Onone]选项，n=10_000时的时间（秒）：

Swift:            0.895296452
C:                0.001223848

这里是Swift内置的sort()函数，对于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

作为比较，这是使用[-Onone]时n=1_000_000的结果：

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

在这个基准测试中，未经优化的Swift几乎比C慢了1000倍，在其开发阶段。另一方面，如果两个编译器都设置为[-Ofast]，Swift实际上至少与C同样表现得好，甚至略微更好。

有人指出[-Ofast]会改变语言的语义，使其潜在地不安全。这是苹果在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

- Joseph Mark

---

使用“-emit-sil”输出中间的SIL代码可以显示正在保留什么（唉，堆栈溢出使格式化变得不可能）。这是Array中的一个内部缓冲对象。这绝对听起来像是一个优化器的Bug，ARC优化器应该能够在没有“-Ofast”的情况下删除保留。 - Catfish_Man

请将以下与编程有关的内容从英语翻译成中文。仅返回已翻译的文本：如果您能告诉我可能存在哪些无效之处，请告诉我。我总是喜欢学习更多。 - Joseph Mark

最终更新完成，使用标准优化后，Swift 在此基准测试中已经和 C 一样快。 - Joseph Mark

提示：如果您先递归处理较小的分区，则可以改进快速排序的Swift和C实现！（而不是总是先递归左分区。）即使在最坏情况下使用简单的轴选择，快速排序也需要O(n^2)时间，但是即使在这种最坏情况下，通过先递归较小的分区，您只需要O(log n)堆栈空间。 - Macneil Shonle

检查在对排序数组进行后续操作时的时间，即使在计时检查后将数组写入文件也可能无效，因为优化的最后一级实际上可能会跳过部分排序过程，将其重新排序到检查点之后。如果数组未被使用，则整个排序可能会被完全跳过。不确定C语言是否会这样做，但是C++和Swift\C#编译器往往会这样做...这就是为什么C++中的别名违规效应通常只出现在优化程序中的原因。 - Swift - Friday Pie

Answer 2

TL;DR: 是的，目前唯一的Swift语言实现很慢。如果你需要快速、数字（和其他类型的代码），那就选择另一个吧。在未来，你应该重新评估你的选择。对于大多数以较高水平编写的应用程序代码而言，它可能已经足够好了。

根据我在SIL和LLVM IR中看到的情况，它们似乎需要进行一些优化，以消除保留和释放操作，这可能已经在Clang（用于Objective-C）中实现了，但他们尚未移植。这是我暂时采用的理论（我仍然需要确认Clang是否有所作为），因为对这个问题的最后一个测试用例运行分析器会产生这样一个“漂亮”的结果：

正如其他人所说，-Ofast 是完全不安全的，并且会改变语言语义。对于我来说，它处于“如果你要使用它，只需使用另一种语言”的阶段。如果有变化，我稍后会重新评估这个选择。 -O3 为我们提供了一堆 swift_retain 和 swift_release 调用，老实说，对于这个示例，它们看起来不应该存在。据我所知，优化器应该已经省略了（大部分）它们，因为它知道关于数组的大部分信息，并且知道它至少具有一个强引用。

当它甚至没有调用可能释放对象的函数时，就不应该发出更多的保留。我认为数组构造器不能返回比所请求的更小的数组，这意味着发出的许多检查是无用的。它还知道整数永远不会超过10k，因此溢出检查可以进行优化（不是因为-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")

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

- filcab

---

编译器可能无法解包数组或数组元素，因为它们被传递给sort()，这是一个外部函数，必须获得它所期望的参数。对于相对较好的编译器来说，这应该不是问题。通过在指针中传递有关实际数据的元数据（64位提供了很多杠杆作用），并在被调用的函数中进行分支处理。 - bestsss

“-Ofast” 究竟为何“完全不安全”？假设您知道如何测试代码并排除溢出。 - Joseph Mark

@sjeohp：这实际上假设了很多 :-) 检查代码并排除溢出是很难做到的。从我的经验（我做编译器工作并检查过一些大型代码库）以及我听到的来自大公司编译器工作人员的意见来看，正确处理溢出和其他未定义行为是非常困难的。即使是苹果公司的建议（只是一个例子）在修复 UB 上也有时是错误的（http://randomascii.wordpress.com/2014/04/17/buggy-security-guidance-from-apple/）。`-Ofast` 也会改变语言语义，但我找不到任何文档。你怎么能确信你知道它在做什么？ - filcab

@bestsss：这是可能的，但可能没有用处。它会在访问Int[]时添加检查。这取决于是否经常使用Int和其他几种原始类型的数组（你最多有3位），特别是当你需要降低到C时。它还使用了一些位，如果他们最终想要添加非ARC GC，他们可能想要使用这些位。它也不能扩展到具有多个参数的泛型。由于他们拥有所有类型，将所有涉及Int[]（但不是Int?[]）的代码专门化为使用内联Int会更容易。但是，这样就需要担心Obj-C互操作性的问题。 - filcab

@filcab，非ARC（即真正的）GC实际上会很有用，但如果他们想要一个真正并发的、非STW GC，他们需要一些不兼容C的东西。我不会担心“对Int[]的每次访问”，因为这取决于编译器可以内联的级别，并且在一些指导后它应该能够内联紧密的循环。 - bestsss

Answer 3

我觉得这挺有趣的，所以决定研究一下，以下是我得到的时间统计：

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

Swift

// 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;
}

结果：

Apple Clang 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

Apple Clang 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

Apple Clang 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

苹果Clang 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

苹果Clang 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的排序速度很快，但尚未像使用-O编译的C++排序那样快。在Swift 4.0.2和Apple LLVM 9.0.0中使用-Ounchecked，它似乎与C++的速度相当。

- Learn OpenGL ES

---

实际上，在插入一千万个元素之前，你永远不应该不调用vector::reserve()。 - BJovke

也许！目前只计时排序。 - Learn OpenGL ES

Answer 4

从The Swift Programming Language：

排序函数Swift的标准库提供了一个名为sort的函数，该函数根据您提供的排序闭包的输出，对已知类型的值数组进行排序。完成排序过程后，sort函数将返回与旧数组相同类型和大小的新数组，其元素按正确的排序顺序排列。 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时，闭包被调用了大约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 }

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

编辑：

我查看了Quicksort维基百科页面，并为其编写了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 + 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次比较

看起来内置的排序方法是快速排序（或类似），但非常慢...

- David Skrundz

---

也许我完全错了，但根据http://en.wikipedia.org/wiki/Quicksort，快速排序中的平均比较次数为“2*n*log(n)”。这意味着对于n = 1000个元素进行排序需要13815次比较，因此如果比较函数被调用约11000次，这并不算太糟糕。 - Martin R

此外，苹果声称在Swift中，“复杂对象排序”（不管那是什么）比Python快3.9倍。因此，寻找“更好的排序函数”可能是不必要的。- 但Swift仍在开发中... - Martin R

确实指的是自然对数。 - Martin R

算法复杂度中的log(n)通常指以2为底的对数。不说明底数的原因是对数的换底公式只会引入一个常数乘子，而在O记号中这个常数会被舍弃。 - minuteman3

关于自然对数和以2为底的对数的讨论：维基百科页面中的准确陈述是，n个元素需要的平均比较次数为 C(n) = 2n ln n ≈ 1.39n log₂ n。当n = 1000时，C(n) = 13815，并且它 不是 “大O符号”。 - Martin R

Answer 5

自 Xcode 7 起，您可以打开 快速、整体模块优化。这将立即提高您的性能。

- Antoine

Answer 6

Swift数组性能重新评估：

我编写了自己的基准测试，比较了Swift与C / Objective-C。我的基准测试计算质数。它使用先前质数的数组在每个新候选项中查找质因数，因此速度非常快。但是，它会大量读取数组，而少量写入数组。

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

该项目允许您选择使用普通Swift数组或使用具有数组语义的Swift不安全内存缓冲区。

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

测试结果似乎相当类似，使用最快，最小的代码优化（[-0s]）或最快，最激进的（[-0fast]）优化。

关闭代码优化后，Swift 2.0性能仍然很差，而C / Objective-C性能仅略慢。

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

当使用最快，最小的代码优化时，带有不安全缓冲区的Swift需要大约1.19倍-1.20倍的时间才比C malloc的数组长。快速，激进的优化（Swift需要比C长1.18倍至1.16倍）时差异似乎略小。

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

普通Swift数组比Swift 1.2 / Xcode 6中要快得多。它们的性能非常接近于基于不安全缓冲区的Swift数组，因此再也没有必要使用不安全内存缓冲区了，这很重要。

顺便说一句，Objective-C NSArray的性能很差。如果在两种语言中都使用本地容器对象，则Swift的速度明显更快。

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

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

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

- Duncan C

Answer 7

其他人提到但没有足够强调的主要问题是，在Swift中-O3根本不起作用（从来没有），因此使用该选项编译时，实际上是非优化的（-Onone）。

随着时间的推移，选项名称已经发生了变化，因此其他答案中的某些选项已经过时。正确的当前选项（Swift 2.2）是：

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

整个模块优化编译时间较慢，但可以在模块内跨文件进行优化，即在每个框架和实际应用程序代码内部进行优化，但不能在它们之间进行优化。对于任何性能关键的内容，您应该使用此选项。

您还可以禁用安全检查以获得更高的速度，但所有断言和前置条件都会被禁用并优化为正确。如果您碰到一个断言错误，这意味着您进入了未定义的行为。请非常谨慎地使用，仅在测试后确定加速效果明显时使用。如果您发现某些代码确实有价值，请将该代码分离为单独的框架，并仅针对该模块禁用安全检查。

- Joseph Lord

---

这个答案现在已经过时了。从Swift 4.1开始，整个模块优化选项是一个单独的布尔值，可以与其他设置结合使用，并且现在有一个-Os选项来优化大小。我可能会在有时间检查确切的选项标志后进行更新。 - Joseph Lord

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) 

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

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

- Atef

Answer 9

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

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

Swift编译器配备了强大的优化功能。使用-O编译时，编译器尝试转换代码，以使其具有最大的性能。但是，这种运行时性能的提高有时会带来增加代码大小的代价。使用新的-Osize优化模式，用户可以选择编译出最小的代码大小，而不是最快的速度。

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

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

- casillas