Swift Beta 性能：排序数组

我在 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 中，它需要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 中使用 “Release” 与 “Debug” 构建的计时相似。

这有什么不对？与 C ++ 相比，我可以理解一些性能损失，但与纯 Python 相比，速度没有降低 10 倍。

编辑：天气注意到将-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不是我们想要的; 斯威夫特的全部意义在于我们有安全网。当然，安全网对性能有一些影响，但它们不应该使程序慢 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 秒
Java： 0.2 秒
使用 PyPy 的 Python：0.5 秒
Python： 12 秒
Swift -Ofast：0.05 秒
Swift -O3： 23 秒
Swift -O0：443 秒

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

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

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

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

clang ++ -O3：0.06 s
swiftc -Ofast：0.1 秒
swiftc -O：0.1 秒
swiftc：4 秒

对于嵌套循环：

clang ++ -O3：0.06 s
swiftc -Ofast：0.3 秒
swiftc -O：0.4 s
swiftc：540 秒

似乎没有理由再使用 unsafe -Ofast （aka -Ounchecked ）; plain -O产生同样好的代码。

答案

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 = 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 的内置排序（），用于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：是的，只有雨燕语言的实现是缓慢的， 就是现在 。如果您需要快速，数字（以及其他类型的代码，可能是代码）代码，请使用另一个代码。将来，您应该重新评估您的选择。但是，对于大多数应用程序代码而言，它可能已经足够好了。

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

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

正如许多其他人所说的那样， -Ofast完全不安全并且改变了语言语义。对我来说，它是在 “如果你打算使用它，只需使用另一种语言” 阶段。如果它发生变化，我将在稍后重新评估该选择。

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

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

但是，编译器可能无法取消装入数组或数组元素，因为它们已经传递给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 运行时的所有工具。我也可能会假设一些我没写过的东西。

我决定看看这个很有趣，以下是我得到的时间：

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

结果：

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

Apple 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

Apple 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 ++ 排序速度相-O 。使用-Ounchecked ，它似乎与 Swift 4.0.2 和 Apple LLVM 9.0.0 中的 C ++ 一样快。