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中,它需要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我得到了我所期待的.相关部分是一个包含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],并添加一个输出的print语句x[0].这不会改变任何内容;时间将非常相似.)

是的,这里的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秒

似乎没有理由再使用不安全-Ofast(又名-Ounchecked); 普通-O产生同样好的代码.

Answer 1

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

Answer 2

TL; DR:是的,只有雨燕语言的实现是缓慢的,现在.如果您需要快速,数字(以及其他类型的代码,可能是代码)代码,请使用另一个代码.将来,您应该重新评估您的选择.但是,对于大多数应用程序代码而言,它可能已经足够好了.

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

正如许多其他人所说,-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 = 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;
}

结果:

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++的排序速度快.有了-Ounchecked它,它似乎与Swift 4.0.2和Apple LLVM 9.0.0中的C++一样快.

Answer 4

来自The Swift Programming Language:

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

该sort函数有两个声明.

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

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

第二个声明只接受一个参数(数组),并且"硬编码使用less-than比较器".

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

我在操场上测试了你的代码的修改版本,并添加了闭包,这样我可以更接近地监视函数,并且我发现当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个比较

似乎内置的排序方法是(或接近)快速排序,而且非常慢......

Answer 5

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

Answer 6

重新审视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的基于数组的计算是最快的,适度的利润率

使用最快,最小的代码优化时,使用不安全缓冲区的Swift比C malloc阵列长约1.19倍 - 1.20倍.通过快速,积极的优化,差异似乎略微减少(Swift比C长1.18倍到1.16倍更长)

如果使用常规的Swift数组,与C的差异会略大一些.(斯威夫特需要大约1.22到1.23.)

常规的Swift数组DRAMATICALLY比它们在Swift 1.2/Xcode 6 中更快.它们的性能非常接近Swift不安全的基于缓冲区的数组,使用不安全的内存缓冲区似乎不值得再麻烦了,这很大.

BTW,Objective-C NSArray表现很糟糕.如果你要使用本机的容器对象在两种语言中,斯威夫特是DRAMATICALLY更快.

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

它有一个简单的用户界面,可以很容易地收集统计数据.

有趣的是,Swift中的排序似乎比现在的C稍快,但是这个素数算法在Swift中仍然更快.

Answer 7

其他人提到的主要问题却没有被充分说明-O3,在Swift中什么都没做(而且从来没有),因此在编译时它实际上是非优化的(-Onone).

选项名称随着时间的推移而发生了变化,因此其他一些答案的构建选项都有过时的标志.正确的当前选项(Swift 2.2)是:

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

整个模块优化具有较慢的编译,但可以跨模块内的文件进行优化,即在每个框架内和实际应用程序代码内,但不在它们之间.您应该将此用于任何性能关键)

您还可以禁用安全检查以获得更高的速度,但所有断言和前提条件不仅被禁用,而且在它们正确的基础上进行了优化.如果您遇到过断言,则意味着您处于未定义的行为.请谨慎使用,并且只有在您确定速度提升对您有用时(通过测试).如果您确实发现它对某些代码很有价值,我建议将该代码分离到一个单独的框架中,并且只禁用该模块的安全检查.

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) 

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

您可以在分区列表中查看Lomuto的分区算法.用Swift写的

Answer 9

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

在 Swift 4.1 中，编译器现在支持新的优化模式，可以进行专门的优化来减少代码大小。

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

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

进一步阅读： https: //swift.org/blog/osize/