Swift性能:對數組進行排序




algorithm performance (7)

我決定看看這個有趣的,這裡是我得到的時間:

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 ++一樣快。

我在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 = sorted(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產生同樣好的代碼。


從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'ed數組。

測試結果似乎與最快,最小的代碼優化([-0s])或最快,最積極(最快(最快)]優化非常相似。

在關閉代碼優化的情況下,Swift 2.0的性能仍然很糟糕,而C / Objective-C的性能只是稍微慢一些。

底線是C malloc'd基於數組的計算速度最快,幅度不大

使用最快,最小的代碼優化時,帶有不安全緩衝區的Swift比C malloc'd數組長1.19X - 1.20X。 與快速,積極的優化相比,差異似乎稍微小一些(Swift比C更長1.18倍到1.16倍。

如果你使用普通的Swift數組,與C的差別稍大 。 (Swift花費大約1.22到1.23。)

普通的Swift數組比DRAMATICALLY速度上要快於在Swift 1.2 / Xcode 6中的速度。它們的性能非常接近Swift不安全的基於緩衝區的數組,使用不安全的內存緩衝區看起來並不值得麻煩,這很大。

順便說一句,Objective-C的NSArray性能很糟糕。 如果你打算在兩種語言中使用本地容器對象,Swift的運行速度會更快。

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

它有一個簡單的用戶界面,使收集統計很容易。

有趣的是,Swift中的排序似乎比C中的稍快,但這個素數算法在Swift中仍然更快。


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的分區算法。 寫在Swift中


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

其他人提到的主要問題是, -O3在Swift中完全沒有做任何事情(所以從來沒有),所以在編譯時它實際上是非優化的( -Onone )。

選項名稱隨時間而改變,所以其他一些答案對於構建選項具有過時的標誌。 正確的當前選項(Swift 2.2)是:

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

整個模塊優化的編譯速度較慢,但可以跨模塊內的文件進行優化,即在每個框架內和實際應用程序代碼內但不在它們之間。 你應該使用它來表現任何關鍵性能)

您還可以停用安全檢查,以獲得更快的速度,但所有斷言和前提條件不僅僅是禁用,而是基於它們是正確的進行了優化。 如果你打了一個斷言,這意味著你陷入了未定義的行為。 只有在確定速度提升對您有價值時(通過測試),才能非常謹慎地使用。 如果您確實發現它對於某些代碼很有價值,我建議將該代碼分離到單獨的框架中,並且僅對該模塊禁用安全檢查。


TL; DR :是的,現在唯一的Swift語言實施速度很慢。 如果你需要快速,數字(和其他類型的代碼,大概是)代碼,那麼就去另一個代碼吧。 將來,你應該重新評估你的選擇。 不過,對於大多數應用程序代碼而言,它可能已經足夠好了。

從我在SIL和LLVM IR中看到的情況看來,他們似乎需要一系列優化來移除保留和釋放,這可能會在Clang (Objective-C)中實現,但他們尚未移植它們。 這就是我正在使用的理論(現在...我仍然需要確認Clang是否做了些什麼),因為在這個問題的最後一個測試案例上運行的分析器產生了這個“相當”的結果:

正如許多人所說的, -Ofast是完全不安全的,並改變了語言語義。 對我而言,它是在“如果你要使用它,只是使用另一種語言”階段。 如果它發生變化,我會在稍後重新評估這一選擇。

-O3給我們帶來了一堆swift_retainswift_release調用,說實話,看起來他們不應該在這個例子中。 優化器應該已經消除了AFAICT(大部分),因為它知道大部分關於數組的信息,並且知道它至少有一個很強的參考。

當它甚至不調用可能釋放對象的函數時,它不應該釋放更多的保留。 我不認為一個數組構造函數可以返回一個比要求的數組小的數組,這意味著很多發出的檢查都是無用的。 它也知道整數永遠不會超過10k,因此可以優化溢出檢查(不是因為-Ofast怪異,而是因為語言的語義(沒有其他任何改變該-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")

PS:我不是Objective-C的專家,也不是來自Cocoa ,Objective-C或Swift運行時的所有設施。 我可能也會假設一些我沒有寫的東西。





sorting