Hiệu suất Swift Beta: sắp xếp mảng

941
Jukka Suomela 2014-06-08 13:53.

Tôi đang triển khai một thuật toán trong Swift Beta và nhận thấy rằng hiệu suất rất kém. Sau khi tìm hiểu sâu hơn, tôi nhận ra rằng một trong những nút thắt cổ chai là một thứ đơn giản như việc sắp xếp các mảng. Phần có liên quan ở đây:

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

Trong C ++, một thao tác tương tự mất 0,06 giây trên máy tính của tôi.

Trong Python, mất 0,6 giây (không cần thủ thuật, chỉ cần y = sorted (x) cho danh sách các số nguyên).

Trong Swift, mất 6s nếu tôi biên dịch nó bằng lệnh sau:

xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`

Và mất đến 88 giây nếu tôi biên dịch nó bằng lệnh sau:

xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`

Thời gian trong Xcode với các bản dựng "Phát hành" và "Gỡ lỗi" là tương tự nhau.

Có gì sai ở đây? Tôi có thể hiểu một số mất hiệu suất so với C ++, nhưng không phải là sự chậm lại 10 lần so với Python thuần túy.


Chỉnh sửa: thời tiết nhận thấy rằng việc thay đổi -O3để -Ofastlàm cho mã này chạy nhanh như phiên bản C ++! Tuy nhiên, -Ofastthay đổi ngữ nghĩa của ngôn ngữ rất nhiều - trong thử nghiệm của tôi, nó đã vô hiệu hóa việc kiểm tra lỗi tràn số nguyên và tràn chỉ mục mảng . Ví dụ: với -Ofastmã Swift sau đây chạy im lặng mà không bị lỗi (và in ra một số rác):

let n = 10000000
print(n*n*n*n*n)
let x =  [Int](repeating: 10, count: n)
print(x[n])

Vì vậy, -Ofastkhông phải là những gì chúng ta muốn; toàn bộ điểm của Swift là chúng tôi có mạng lưới an toàn tại chỗ. Tất nhiên, lưới an toàn có một số tác động đến hiệu suất, nhưng chúng không nên làm cho các chương trình chậm hơn 100 lần. Hãy nhớ rằng Java đã kiểm tra các giới hạn của mảng, và trong các trường hợp điển hình, tốc độ chậm là một hệ số nhỏ hơn nhiều. Và trong Clang và GCC, chúng tôi đã -ftrapvkiểm tra các lỗi tràn số nguyên (có dấu) và nó cũng không chậm như vậy.

Do đó, câu hỏi đặt ra: làm thế nào chúng ta có thể có được hiệu suất hợp lý trong Swift mà không bị mất mạng lưới an toàn?


Chỉnh sửa 2: Tôi đã thực hiện thêm một số phép đo điểm chuẩn, với các vòng lặp rất đơn giản dọc theo dòng

for i in 0..<n {
    x[i] = x[i] ^ 12345678
}

(Đây là phép toán xor chỉ để tôi có thể dễ dàng tìm thấy vòng lặp có liên quan trong mã lắp ráp. Tôi đã cố gắng chọn một phép toán dễ phát hiện nhưng cũng "vô hại" theo nghĩa là nó sẽ không yêu cầu bất kỳ kiểm tra nào liên quan đến tràn số nguyên.)

Một lần nữa, có sự khác biệt rất lớn về hiệu suất giữa -O3-Ofast. Vì vậy, tôi đã xem xét mã lắp ráp:

  • Với -Ofasttôi nhận được khá nhiều những gì tôi mong đợi. Phần liên quan là một vòng lặp với 5 lệnh ngôn ngữ máy.

  • Với -O3tôi, tôi nhận được một cái gì đó ngoài sức tưởng tượng điên cuồng nhất của tôi. Vòng lặp bên trong kéo dài 88 dòng mã lắp ráp. Tôi đã không cố gắng hiểu tất cả, nhưng phần đáng ngờ nhất là 13 lệnh gọi "callq _swift_retain" và 13 lệnh gọi khác "callq _swift_release". Đó là, 26 lệnh gọi chương trình con trong vòng lặp bên trong !


Chỉnh sửa 3: Trong nhận xét, Ferruccio yêu cầu các điểm chuẩn công bằng theo nghĩa là chúng không dựa trên các chức năng cài sẵn (ví dụ: sắp xếp). Tôi nghĩ chương trình sau đây là một ví dụ khá tốt:

let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

Không có số học, vì vậy chúng ta không cần phải lo lắng về lỗi tràn số nguyên. Điều duy nhất chúng tôi làm chỉ là nhiều tham chiếu mảng. Và kết quả là đây - Swift -O3 thua gần 500 điểm so với -Ofast:

  • C ++ -O3: 0,05 giây
  • C ++ -O0: 0,4 giây
  • Java: 0,2 giây
  • Python với PyPy: 0,5 giây
  • Python: 12 giây
  • Nhanh chóng - Nhanh: 0,05 giây
  • Swift -O3: 23 giây
  • Swift -O0: 443 giây

(Nếu bạn lo ngại rằng trình biên dịch có thể tối ưu hóa hoàn toàn các vòng lặp vô nghĩa, bạn có thể thay đổi nó thành ví dụ x[i] ^= x[j], và thêm một câu lệnh in ra kết quả x[0]. Điều này không thay đổi bất cứ điều gì; thời gian sẽ rất giống nhau.)

Và vâng, ở đây việc triển khai Python là một triển khai Python thuần túy ngu ngốc với danh sách các int và các vòng lặp for lồng nhau. Nó sẽ được nhiều chậm hơn so với unoptimized Swift. Có vẻ như có gì đó bị hỏng nghiêm trọng với Swift và lập chỉ mục mảng.


Chỉnh sửa 4: Những vấn đề này (cũng như một số vấn đề về hiệu suất khác) dường như đã được khắc phục trong Xcode 6 beta 5.

Để sắp xếp, bây giờ tôi có các thời gian sau:

  • clang ++ -O3: 0,06 giây
  • nhanh chóng: 0,1 giây
  • swiftc -O: 0,1 giây
  • swiftc: 4 giây

Đối với các vòng lồng nhau:

  • clang ++ -O3: 0,06 giây
  • nhanh chóng: 0,3 giây
  • swiftc -O: 0,4 giây
  • swiftc: 540 giây

Có vẻ như không có lý do gì nữa để sử dụng -Ofast(aka -Ounchecked) không an toàn ; đồng bằng -Otạo ra mã tốt như nhau.

9 answers

464
Joseph Mark 2014-06-08 15:36.

tl; dr Swift 1.0 hiện nhanh bằng C theo điểm chuẩn này sử dụng mức tối ưu hóa bản phát hành mặc định [-O].


Đây là một nhanh tại chỗ trong 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)
}

Và tương tự trong 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);
}

Cả hai đều hoạt động:

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]

Cả hai đều được gọi trong cùng một chương trình như đã viết.

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();

Điều này chuyển đổi thời gian tuyệt đối thành giây:

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

Dưới đây là tóm tắt về các mức tối ưu hóa của trình biên dịch:

[-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.

Thời gian tính bằng giây với [-Onone] cho n = 10_000 :

Swift:            0.895296452
C:                0.001223848

Đây là sắp xếp nội trang của Swift () cho n = 10_000 :

Swift_builtin:    0.77865783

Đây là [-O] cho n = 10_000 :

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Như bạn có thể thấy, hiệu suất của Swift đã được cải thiện thêm 20.

Theo Hiệu suất Swift Beta: sắp xếp mảng , cài đặt [-Ofast] tạo ra sự khác biệt thực sự, dẫn đến những khoảng thời gian này cho n = 10_000 :

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

Và đối với n = 1_000_000 :

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

Để so sánh, đây là với [-Onone] cho n = 1_000_000 :

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Vì vậy, Swift không có tối ưu hóa đã chậm hơn gần 1000 lần so với C trong điểm chuẩn này, ở giai đoạn phát triển này. Mặt khác, với cả hai trình biên dịch được đặt thành [-Ofast] Swift thực sự cũng hoạt động ít nhất nếu không muốn nói là tốt hơn C.

Người ta đã chỉ ra rằng [-Ofast] thay đổi ngữ nghĩa của ngôn ngữ, khiến nó có khả năng không an toàn. Đây là những gì Apple tuyên bố trong ghi chú phát hành Xcode 5.0:

Mức tối ưu hóa mới -Ofast, có sẵn trong LLVM, cho phép tối ưu hóa tích cực. -Ofast nới lỏng một số hạn chế bảo thủ, chủ yếu đối với các hoạt động dấu phẩy động, an toàn cho hầu hết các mã. Nó có thể mang lại chiến thắng hiệu suất cao đáng kể từ trình biên dịch.

Tất cả họ đều ủng hộ nó. Dù điều đó có khôn ngoan hay không thì tôi không thể nói, nhưng từ những gì tôi có thể nói thì có vẻ như đủ hợp lý để sử dụng [-Ofast] trong một bản phát hành nếu bạn không thực hiện số học dấu phẩy động có độ chính xác cao và bạn tin rằng không có số nguyên hoặc tràn mảng có thể xảy ra trong chương trình của bạn. Nếu bạn cần hiệu suất cao kiểm tra tràn / số học chính xác thì hãy chọn ngôn ngữ khác ngay bây giờ.

CẬP NHẬT BETA 3:

n = 10_000 với [-O] :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Swift nói chung nhanh hơn một chút và có vẻ như kiểu cài sẵn của Swift đã thay đổi khá nhiều.

CẬP NHẬT CUỐI CÙNG:

[-Onone] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[-Đã kiểm tra] :

Swift:   0.000827764
C:       0.001078914
111
filcab 2014-06-09 20:30.

TL; DR : Vâng, việc thực hiện ngôn ngữ duy nhất Swift là chậm, ngay bây giờ . Nếu bạn cần mã nhanh, dạng số (và các loại mã khác, có lẽ là), chỉ cần sử dụng một mã khác. Trong thời gian tới, bạn nên đánh giá lại sự lựa chọn của mình. Tuy nhiên, nó có thể đủ tốt cho hầu hết các mã ứng dụng được viết ở cấp độ cao hơn.

Từ những gì tôi thấy trong SIL và LLVM IR, có vẻ như họ cần một loạt các tối ưu hóa để loại bỏ các bản lưu giữ và bản phát hành, có thể được triển khai trong Clang (cho Objective-C), nhưng họ chưa chuyển chúng. Đó là lý thuyết mà tôi đang theo đuổi (hiện tại… tôi vẫn cần xác nhận rằng Clang làm điều gì đó về nó), vì một hồ sơ chạy trên trường hợp thử nghiệm cuối cùng của câu hỏi này cho kết quả “khá” này:

Như đã nói bởi nhiều người khác, -Ofastlà hoàn toàn không an toàn và thay đổi ngữ nghĩa ngôn ngữ. Đối với tôi, đó là giai đoạn "Nếu bạn định sử dụng ngôn ngữ đó, chỉ cần sử dụng ngôn ngữ khác". Tôi sẽ đánh giá lại lựa chọn đó sau, nếu nó thay đổi.

-O3khiến chúng tôi nhận được một loạt các cuộc gọi swift_retainswift_releasethành thật mà nói, có vẻ như chúng không nên ở đó cho ví dụ này. Trình tối ưu hóa lẽ ra đã làm sáng tỏ (hầu hết) chúng AFAICT, vì nó biết hầu hết thông tin về mảng và biết rằng nó có (ít nhất) một tham chiếu mạnh đến nó.

Nó không nên phát ra nhiều lưu giữ hơn khi nó thậm chí không gọi các hàm có thể giải phóng các đối tượng. Tôi không nghĩ rằng một phương thức khởi tạo mảng có thể trả về một mảng nhỏ hơn những gì được yêu cầu, có nghĩa là rất nhiều kiểm tra đã được phát ra là vô ích. Nó cũng biết rằng số nguyên sẽ không bao giờ vượt quá 10k, vì vậy kiểm tra tràn có thể được tối ưu hóa (không phải vì -Ofastsự kỳ lạ, mà vì ngữ nghĩa của ngôn ngữ (không có gì khác đang thay đổi var mà cũng không thể truy cập nó và cộng tới 10k là an toàn cho loại Int).

Tuy nhiên, trình biên dịch có thể không thể mở hộp mảng hoặc các phần tử của mảng, vì chúng được chuyển đến sort(), đây là một hàm bên ngoài và phải nhận các đối số mà nó mong đợi. Điều này sẽ khiến chúng ta phải sử dụng các Intgiá trị một cách gián tiếp, điều này sẽ làm cho nó chậm hơn một chút. Điều này có thể thay đổi nếu sort()hàm chung (không theo cách đa phương thức) có sẵn cho trình biên dịch và được nội tuyến.

Đây là một ngôn ngữ rất mới (công khai) và nó đang trải qua những gì tôi cho là có rất nhiều thay đổi, vì có những người (rất nhiều) liên quan đến ngôn ngữ Swift yêu cầu phản hồi và tất cả họ đều nói rằng ngôn ngữ này chưa hoàn thiện và sẽ thay đổi.

Mã đã được sử dụng:

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")

Tái bút: Tôi không phải là chuyên gia về Objective-C cũng như tất cả các thiết bị từ Cocoa , Objective-C hay Swift runtimes. Tôi cũng có thể giả định một số điều mà tôi đã không viết.

55
Learn OpenGL ES 2014-10-27 11:47.

Tôi quyết định xem xét điều này cho vui và đây là thời gian mà tôi nhận được:

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

Nhanh

// 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()

Các kết quả:

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

Nó có vẻ là cùng một hiệu suất nếu tôi biên dịch với -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

Có vẻ như đã có sự hồi quy hiệu suất từ ​​Swift 2.0 sang Swift 3.0 và tôi cũng thấy sự khác biệt giữa -O-Ouncheckedlần đầu tiên.

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 cải thiện hiệu suất một lần nữa, đồng thời duy trì khoảng cách giữa -O-Ounchecked. -O -whole-module-optimizationdường như không tạo ra sự khác biệt.

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

Các kết quả:

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

Nhận định

Tính đến thời điểm viết bài này, cách sắp xếp của Swift nhanh, nhưng chưa nhanh bằng cách sắp xếp của C ++ khi được biên dịch -O, với các trình biên dịch & thư viện ở trên. Với -Ounchecked, nó có vẻ nhanh như C ++ trong Swift 4.0.2 và Apple LLVM 9.0.0.

34
David Skrundz 2014-06-08 14:29.

Từ The Swift Programming Language:

Hàm sắp xếp Thư viện chuẩn của Swift cung cấp một hàm được gọi là sắp xếp, sắp xếp một mảng giá trị của một kiểu đã biết, dựa trên kết quả của một bao đóng sắp xếp mà bạn cung cấp. Sau khi hoàn tất quá trình sắp xếp, hàm sắp xếp trả về một mảng mới có cùng kiểu và kích thước với mảng cũ, với các phần tử của nó theo đúng thứ tự được sắp xếp.

Các sortchức năng có hai tờ khai.

Khai báo mặc định cho phép bạn chỉ định một đóng so sánh:

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

Và một khai báo thứ hai chỉ nhận một tham số duy nhất (mảng) và được "mã hóa cứng để sử dụng bộ so sánh nhỏ hơn."

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

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

Tôi đã thử nghiệm một phiên bản đã sửa đổi của mã của bạn trong một sân chơi với phần đóng được thêm vào để tôi có thể theo dõi hàm chặt chẽ hơn một chút và tôi thấy rằng với n được đặt thành 1000, lần đóng được gọi khoảng 11.000 lần.

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

Nó không phải là một chức năng hiệu quả, tôi khuyên bạn nên sử dụng một triển khai chức năng sắp xếp tốt hơn.

BIÊN TẬP:

Tôi đã xem qua trang wikipedia Quicksort và viết một bản triển khai Swift cho nó. Đây là toàn bộ chương trình tôi đã sử dụng (trong một sân chơi)

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
}

Sử dụng điều này với n = 1000, tôi thấy rằng

  1. quickSort () đã được gọi khoảng 650 lần,
  2. khoảng 6000 giao dịch hoán đổi đã được thực hiện,
  3. và có khoảng 10.000 so sánh

Có vẻ như phương pháp sắp xếp tích hợp là (hoặc gần với) sắp xếp nhanh và thực sự chậm ...

18
Antoine 2015-06-12 06:56.

Kể từ Xcode 7, bạn có thể bật Fast, Whole Module Optimization. Điều này sẽ làm tăng hiệu suất của bạn ngay lập tức.

12
Duncan C 2016-02-26 15:31.

Hiệu suất Swift Array đã được xem lại:

Tôi đã viết điểm chuẩn của riêng mình để so sánh Swift với C / Objective-C. Điểm chuẩn của tôi tính toán các số nguyên tố. Nó sử dụng mảng các số nguyên tố trước đó để tìm thừa số nguyên tố trong từng ứng viên mới nên khá nhanh. Tuy nhiên, nó thực hiện HÀNG TẤN đọc mảng và ghi ít hơn vào mảng.

Ban đầu tôi đã làm điểm chuẩn này so với Swift 1.2. Tôi quyết định cập nhật dự án và chạy nó trên Swift 2.0.

Dự án cho phép bạn lựa chọn giữa việc sử dụng mảng nhanh bình thường và sử dụng bộ đệm bộ nhớ không an toàn của Swift bằng ngữ nghĩa mảng.

Đối với C / Objective-C, bạn có thể chọn sử dụng NSArrays hoặc C malloc'ed mảng.

Kết quả thử nghiệm dường như khá giống nhau với tối ưu hóa mã nhanh nhất, nhỏ nhất ([-0s]) hoặc tối ưu hóa nhanh nhất, tích cực ([-0fast]).

Hiệu suất Swift 2.0 vẫn còn tồi tệ với việc tắt tối ưu hóa mã, trong khi hiệu suất C / Objective-C chỉ chậm hơn vừa phải.

Điểm mấu chốt là các phép tính dựa trên mảng C malloc'd là nhanh nhất, với một biên độ khiêm tốn

Swift với bộ đệm không an toàn mất khoảng 1,19X - 1,20X so với mảng C malloc'd khi sử dụng tối ưu hóa mã nhanh nhất, nhỏ nhất. sự khác biệt dường như ít hơn một chút với tính năng tối ưu hóa nhanh và tích cực (Swift dài hơn từ 1,18x đến 1,16x so với C.

Nếu bạn sử dụng mảng Swift thông thường, sự khác biệt với C lớn hơn một chút . (Swift mất ~ 1,22 đến 1,23 lâu hơn.)

Các mảng Swift thông thường DRAMATICALLYnhanh hơn chúng trong Swift 1.2 / Xcode 6. Hiệu suất của chúng gần với các mảng dựa trên bộ đệm không an toàn của Swift nên việc sử dụng bộ đệm bộ nhớ không an toàn dường như không thực sự đáng để gặp rắc rối nữa, điều này rất lớn.

BTW, Objective-C NSArray hiệu suất bốc mùi. Nếu bạn định sử dụng các đối tượng vùng chứa gốc trong cả hai ngôn ngữ, Swift nhanh hơn DRAMATICALLY .

Bạn có thể xem dự án của tôi trên github tại SwiftPerformanceBenchmark

Nó có một giao diện người dùng đơn giản giúp thu thập số liệu thống kê khá dễ dàng.

Thật thú vị khi việc sắp xếp trong Swift có vẻ nhanh hơn một chút so với C, nhưng thuật toán số nguyên tố này vẫn nhanh hơn trong Swift.

8
Joseph Lord 2016-04-14 00:58.

Vấn đề chính được đề cập bởi những người khác nhưng không được gọi đủ là nó -O3không làm gì cả trong Swift (và không bao giờ có) nên khi biên dịch với nó, nó không được tối ưu hóa một cách hiệu quả ( -Onone).

Tên tùy chọn đã thay đổi theo thời gian vì vậy một số câu trả lời khác có cờ lỗi thời cho các tùy chọn xây dựng. Các tùy chọn hiện tại đúng (Swift 2.2) là:

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

Tối ưu hóa toàn bộ mô-đun có một biên dịch chậm hơn nhưng có thể tối ưu hóa trên các tệp trong mô-đun tức là trong mỗi khuôn khổ và trong mã ứng dụng thực tế nhưng không phải giữa chúng. Bạn nên sử dụng điều này cho bất kỳ điều gì quan trọng về hiệu suất)

Bạn cũng có thể tắt kiểm tra an toàn để có tốc độ cao hơn nhưng với tất cả các xác nhận và điều kiện tiên quyết không chỉ bị vô hiệu hóa mà còn được tối ưu hóa trên cơ sở chúng đúng. Nếu bạn từng khẳng định điều này có nghĩa là bạn đang có hành vi không xác định. Hãy sử dụng hết sức thận trọng và chỉ khi bạn xác định rằng việc tăng tốc độ là đáng giá cho bạn (bằng cách thử nghiệm). Nếu bạn thấy nó có giá trị đối với một số mã, tôi khuyên bạn nên tách mã đó thành một khuôn khổ riêng và chỉ tắt các kiểm tra an toàn cho mô-đun đó.

7
Abo3atef 2016-12-07 01:12.
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) 

Đây là Blog của tôi về Sắp xếp nhanh- Mẫu Github Sắp xếp nhanh

Bạn có thể xem qua thuật toán phân vùng của Lomuto trong Phân vùng danh sách. Được viết bằng Swift.

4
casillas 2018-12-15 17:25.

Swift 4.1 giới thiệu -Osizechế độ tối ưu hóa mới .

Trong Swift 4.1, trình biên dịch hiện hỗ trợ chế độ tối ưu hóa mới cho phép tối ưu hóa chuyên dụng để giảm kích thước mã.

Trình biên dịch Swift đi kèm với các tính năng tối ưu hóa mạnh mẽ. Khi biên dịch với -O, trình biên dịch cố gắng biến đổi mã để nó thực thi với hiệu suất tối đa. Tuy nhiên, sự cải thiện này trong hiệu suất thời gian chạy đôi khi có thể đi kèm với sự đánh đổi của kích thước mã tăng lên. Với chế độ tối ưu hóa -Osize mới, người dùng có lựa chọn biên dịch cho kích thước mã tối thiểu hơn là tốc độ tối đa.

Để bật chế độ tối ưu hóa kích thước trên dòng lệnh, hãy sử dụng -Osize thay vì -O.

Đọc thêm: https://swift.org/blog/osize/

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

BoJack Horseman vẫn gan ruột và gan dạ hơn bao giờ hết trong phần 3

BoJack Horseman vẫn gan ruột và gan dạ hơn bao giờ hết trong phần 3

BoJack Horseman (Ảnh: Netflix) BoJack Horseman bắt đầu mùa thứ ba với sự xuất hiện của nhân vật tiêu biểu, người vẫn đang theo đuổi những lời khen ngợi từ giới phê bình trong một nỗ lực tuyệt vọng để tìm ra ý nghĩa trong cuộc sống của mình. Mùa thứ hai về số phận bi kịch của Raphael Bob-Waksberg dày đặc những trò đùa cũng như tuyệt vọng.

Xem cách tính năng lái tự động cập nhật của Tesla bùng phát như thế nào khi bạn bỏ qua các cảnh báo của nó

Xem cách tính năng lái tự động cập nhật của Tesla bùng phát như thế nào khi bạn bỏ qua các cảnh báo của nó

Bản nâng cấp Phiên bản 8.0 gần đây của Tesla đối với hệ thống Lái xe tự động được thiết kế để cải thiện hệ thống và mối quan hệ của nó với người lái.

UnREAL, Chương trình Truyền hình Về Truyền hình Thực tế Chúng tôi Không biết Chúng tôi Cần

UnREAL, Chương trình Truyền hình Về Truyền hình Thực tế Chúng tôi Không biết Chúng tôi Cần

Chắc chắn khi con cái chúng ta xem lại các chương trình chúng ta đã xem vào khoảng năm 2015, chúng sẽ thấy UnREAL, một chương trình truyền hình mới chiếu vào tối Thứ Hai của Lifetime — bạn sẽ thấy đúng lúc, sẽ phát sóng ngay sau khi The Bachelor kết thúc — như một chương trình không thể được thực hiện vào bất kỳ thời điểm nào khác trong lịch sử truyền hình, nhưng một chương trình cảm thấy cần thiết để xem bây giờ. UnREAL có sự tham gia của Shiri Appleby trong vai Rachel, một nhà sản xuất truyền hình cho một chương trình về cơ bản là The Bachelor, mặc dù trong thế giới này, nó được gọi là Vĩnh viễn.

Sau tất cả, Josh Trank sẽ không đạo diễn bộ phim tuyển tập Star Wars thứ hai

Sau tất cả, Josh Trank sẽ không đạo diễn bộ phim tuyển tập Star Wars thứ hai

Thông báo chính thức đến trực tiếp từ trang web của Star Wars: Fantastic Four, đạo diễn Josh Trank, một người bí ẩn không xuất hiện tại đại hội Star Wars Celebration gần đây, sẽ không chỉ đạo phần hai Star Wars Anthology. Đây là tuyên bố được đăng ngày hôm qua: Tất cả thực sự là ngôn ngữ rất lịch sự, nhưng một bài báo của Hollywood Reporter cho thấy tất cả đều không tốt ở hậu trường, gọi sự ra đi là "một vụ sa thải" một phần dựa trên "hành vi bất thường" của Trank trong khi quay Fantastic Four: The Bài báo trích dẫn các nguồn gọi là Trank “đôi khi thiếu quyết đoán và thiếu sáng tạo,” và lưu ý rằng Fantastic Four, khởi chiếu vào ngày 7 tháng 8, đã được khởi động lại vào cuối tháng 4.

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

McCain, người đang làm việc cho một album mới, lần đầu tiên bước vào vòng kết nối vào tối thứ Sáu ở Nashville

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Tôi viết như thế nào

Tôi viết như thế nào

Đối với tôi, mọi thứ là về dòng đầu tiên đó và nó sẽ đưa bạn đến đâu. Một số nhà văn bị điều khiển bởi cốt truyện, sự sắp xếp tinh tế của các quân cờ, trong khi những người khác bị lôi cuốn bởi một nhân vật và khả năng thực hiện một cuộc hành trình với một người bạn hư cấu mới.

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Language