swift - Swift性能:对数组进行排序




4 Answers

tl;通过使用默认版本优化级别[-O]的此基准测试,Swift现在与C一样快。

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

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

正如你所看到的,斯威夫特的表现提高了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放宽了一些保守的限制,主要用于浮点运算,这对大多数代码都是安全的。 它可以从编译器中获得显着的高性能优势。

他们都提倡它。 无论这是否明智,我都不能说,但从我可以告诉的是,如果您没有进行高精度浮点运算,并且您确信没有整数或数组溢出可能在你的程序中。 如果您确实需要高性能溢出检查/精确算术,那么现在就选择另一种语言。

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

我在Swift中实现了一个算法,并注意到性能非常差。 在深入挖掘之后,我意识到其中一个瓶颈就像排序数组一样简单。 相关部分在这里:

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的“发布”与“调试”版本的时间类似。

这里有什么问题? 与C ++相比,我可以理解一些性能损失,但与纯Python相比,不会减少10倍。

编辑: mweathers注意到将-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
}

(这里的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 s
  • Java: 0.2秒
  • Python与PyPy:0.5秒
  • Python: 12秒
  • 迅速 - 快速:0.05秒
  • Swift -O3: 23 s
  • Swift -O0:443 s

(如果你担心编译器会完全优化无意义的循环,你可以把它改成例如x[i] ^= x[j] ,并添加一个输出x[0]的打印语句,这并不会改变任何东西;时间将非常相似。)

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

编辑4:这些问题(以及一些其他性能问题)似乎在Xcode 6 beta 5中得到了修复。

为了排序,我现在有以下时间:

  • 铛++ -O3:0.06秒
  • swiftc - 快:0.1秒
  • swiftc -O:0.1秒
  • swiftc:4秒

对于嵌套循环:

  • 铛++ -O3:0.06秒
  • swiftc - 快速:0.3秒
  • swiftc -O:0.4秒
  • swiftc:540秒

看起来没有理由再使用不安全的-Ofast (又名-Ounchecked ); 平原-O产生同样好的代码。




我决定看看这个有趣的,这里是我得到的时间:

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

苹果铿锵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 ++一样快。




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




其他人提到的主要问题是, -O3在Swift中根本就没有做任何事情(所以从来没有),所以编译时它实际上是非优化的( -Onone )。

选项名称随时间而改变,所以其他一些答案对于构建选项具有过时的标志。 正确的当前选项(Swift 2.2)是:

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

整个模块优化的编译速度较慢,但​​可以跨模块内的文件进行优化,即在每个框架内和实际应用程序代码内但不在它们之间。 你应该使用它来表现任何关键性能)

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




Related