Pertanyaan Kinerja cepat: menyortir array


Saya menerapkan algoritma di Swift dan memperhatikan bahwa kinerjanya sangat buruk. Setelah menggali lebih dalam, saya menyadari bahwa salah satu kemacetan adalah sesuatu yang sederhana seperti menyortir array. Bagian yang relevan ada di sini:

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

Di C ++, operasi yang sama membutuhkan 0,06 dtk di komputer saya.

Dengan Python yang dibutuhkan 0,6 detik (tidak ada trik, cukup y = diurutkan (x) untuk daftar bilangan bulat).

Dalam Swift dibutuhkan 6s jika saya mengkompilasinya dengan perintah berikut:

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

Dan dibutuhkan sebanyak itu 88 detik jika saya mengkompilasinya dengan perintah berikut:

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

Timing di Xcode dengan build "Rilis" vs. "Debug" serupa.

Apa yang salah disini? Saya dapat memahami beberapa kerugian kinerja dibandingkan dengan C ++, tetapi bukan perlambatan 10 kali lipat dibandingkan dengan Python murni.


Edit: mweathers memperhatikan perubahan itu -O3 untuk -Ofast membuat kode ini berjalan hampir secepat versi C ++! Namun, -Ofast mengubah semantik bahasa banyak - dalam pengujian saya, itu menonaktifkan pemeriksaan untuk overflow bilangan bulat dan luapan indeks pengindeksan. Misalnya, dengan -Ofast kode Swift berikut berjalan tanpa suara tanpa menabrak (dan mencetak beberapa sampah):

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

Begitu -Ofast bukan yang kita inginkan; seluruh titik Swift adalah bahwa kita memiliki jaring pengaman di tempat. Tentu saja jaring pengaman berdampak pada kinerja, tetapi mereka seharusnya tidak membuat program 100 kali lebih lambat. Ingat bahwa Java sudah memeriksa batas-batas larik, dan dalam kasus-kasus biasa, pelambatannya adalah dengan faktor yang jauh lebih kecil daripada 2. Dan dalam Clang dan GCC kita sudah mendapat -ftrapv untuk memeriksa (bertanda) integer overflows, dan itu tidak terlalu lambat.

Oleh karena itu pertanyaannya: bagaimana kita bisa mendapatkan kinerja yang wajar di Swift tanpa kehilangan jaring pengaman?


Edit 2: Saya melakukan beberapa pembandingan, dengan loop yang sangat sederhana sepanjang garis

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

(Di sini operasi xor hanya ada agar saya dapat lebih mudah menemukan loop yang relevan dalam kode assembly. Saya mencoba memilih operasi yang mudah dikenali tetapi juga "tidak berbahaya" dalam arti bahwa itu tidak memerlukan pemeriksaan terkait ke overflows integer.)

Sekali lagi, ada perbedaan besar dalam kinerja antara -O3 dan -Ofast. Jadi saya melihat kode assembly:

  • Dengan -Ofast Saya mendapatkan cukup banyak apa yang saya harapkan. Bagian yang relevan adalah loop dengan 5 instruksi bahasa mesin.

  • Dengan -O3 Saya mendapatkan sesuatu yang berada di luar imajinasi saya yang paling liar. Lingkaran dalam mencakup 88 baris kode assembly. Saya tidak mencoba untuk memahami semuanya, tetapi bagian yang paling mencurigakan adalah 13 panggilan "callq _swift_retain" dan 13 panggilan "callq _swift_release". Itu adalah, 26 panggilan subrutin dalam lingkaran dalam!


Sunting 3: Dalam komentar, Ferruccio meminta tolok ukur yang adil dalam arti bahwa mereka tidak bergantung pada fungsi-fungsi bawaan (misalnya sortir). Saya pikir program berikut adalah contoh yang cukup bagus:

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

Tidak ada aritmatika, jadi kita tidak perlu khawatir tentang overflows integer. Satu-satunya hal yang kami lakukan hanyalah banyak referensi array. Dan hasilnya ada di sini — Swift -O3 kalah oleh faktor hampir 500 dibandingkan dengan -Luas:

  • C ++ -O3: 0,05 dtk
  • C ++ -O0: 0,4 dtk
  • Jawa: 0,2 s
  • Python dengan PyPy: 0,5 s
  • Python: 12 dtk
  • Swift -Ofast: 0,05 s
  • Swift -O3: 23 dtk
  • Swift -O0: 443 dtk

(Jika Anda khawatir bahwa kompiler mungkin mengoptimalkan seluruh loop tanpa titik sepenuhnya, Anda dapat mengubahnya ke misalnya. x[i] ^= x[j], dan tambahkan pernyataan cetak yang dihasilkan x[0]. Ini tidak mengubah apa pun; timingnya akan sangat mirip.)

Dan ya, di sini implementasi Python adalah implementasi Python murni bodoh dengan daftar int dan bersarang untuk loop. Harus banyak lebih lambat dari Swift yang tidak dioptimalkan. Sepertinya ada sesuatu yang rusak serius dengan Swift dan pengindeksan array.


Edit 4: Masalah-masalah ini (serta beberapa masalah kinerja lainnya) tampaknya telah diperbaiki di Xcode 6 beta 5.

Untuk penyortiran, sekarang saya memiliki timing berikut:

  • berdentang ++ -O3: 0,06 dtk
  • swiftc - Cepat: 0,1 s
  • swiftc -O: 0,1 s
  • swiftc: 4 s

Untuk loop bersarang:

  • berdentang ++ -O3: 0,06 dtk
  • swiftc - Cepat: 0,3 dtk
  • swiftc -O: 0.4 s
  • swiftc: 540 s

Tampaknya tidak ada alasan lagi untuk menggunakan yang tidak aman -Ofast (a.k.a. -Ounchecked); polos -O menghasilkan kode yang sama bagusnya.


829
2018-06-07 23:53


asal


Jawaban:


tl; dr Swift sekarang secepat C oleh patokan ini menggunakan tingkat pengoptimalan rilis default [-O].

Berikut ini adalah quicksort di tempat di 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)
}

Dan hal yang sama di 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);
}

Keduanya bekerja:

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]

Keduanya dipanggil dalam program yang sama seperti yang tertulis.

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

Ini mengubah waktu absolut menjadi detik:

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

Berikut ini adalah ringkasan tingkat optimazation kompilator:

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

Waktu dalam hitungan detik [-Onone] untuk n = 10_000:

Swift:            0.895296452
C:                0.001223848

Di sini ada jenis bawaan Swift () untuk n = 10_000:

Swift_builtin:    0.77865783

Disini adalah [-HAI] untuk n = 10_000:

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

Seperti yang Anda lihat, kinerja Swift meningkat dengan faktor 20.

Sesuai jawaban mweathers ', pengaturan [- Cepat] membuat perbedaan nyata, menghasilkan waktu untuk ini n = 10_000:

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

Dan untuk n = 1_000_000:

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

Sebagai perbandingan, ini dengan [-Onone] untuk n = 1_000_000:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

Jadi Swift tanpa optimasi hampir 1000x lebih lambat daripada C dalam benchmark ini, pada tahap ini dalam perkembangannya. Di sisi lain dengan kedua compiler yang diatur ke [-Opsi] Swift sebenarnya dilakukan setidaknya juga jika tidak sedikit lebih baik daripada C.

Telah ditunjukkan bahwa [--Otomatis] mengubah semantik bahasa, sehingga berpotensi tidak aman. Inilah yang Apple nyatakan dalam catatan rilis Xcode 5.0:

Tingkat pengoptimalan baru - Cepat, tersedia di LLVM, memungkinkan pengoptimalan agresif. -Lambat rileks beberapa pembatasan konservatif, sebagian besar untuk operasi floating-point, yang aman untuk sebagian besar kode. Ini dapat menghasilkan kemenangan kinerja tinggi yang signifikan dari kompilator.

Mereka semua mendukungnya. Apakah itu bijaksana atau tidak, saya tidak bisa mengatakannya, tetapi dari apa yang saya dapat katakan itu tampaknya cukup masuk akal untuk menggunakan [-Opsi] dalam rilis jika Anda tidak melakukan aritmatika floating point presisi tinggi dan Anda yakin tidak ada bilangan bulat atau luapan array dimungkinkan dalam program Anda. Jika Anda memang membutuhkan kinerja tinggi dan cek overflow / aritmatik yang tepat lalu pilih bahasa lain untuk saat ini.

BETA 3 UPDATE:

n = 10_000 dengan [-HAI]:

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Swift secara umum sedikit lebih cepat dan sepertinya Swift's built-in sort telah berubah cukup signifikan.

UPDATE AKHIR:

[-Onone]:

Swift:   0.678056695
C:       0.000973914

[-HAI]:

Swift:   0.001158492
C:       0.001192406

[-Kotak-kotak]:

Swift:   0.000827764
C:       0.001078914

404
2018-06-08 01:36



TL; DR: Ya, satu-satunya penerapan bahasa Swift lambat, sekarang juga. Jika Anda membutuhkan kode cepat, numerik (dan kode jenis lainnya, mungkin), cukup gunakan kode yang lain. Di masa depan, Anda harus mengevaluasi kembali pilihan Anda. Mungkin cukup bagus untuk sebagian besar kode aplikasi yang ditulis pada level yang lebih tinggi.

Dari apa yang saya lihat di SIL dan LLVM IR, sepertinya mereka membutuhkan banyak pengoptimalan untuk menghapus retensi dan rilis, yang mungkin diimplementasikan di Dentang (untuk Objective-C), tetapi mereka belum memportnya. Itulah teori yang akan saya dengarkan (untuk saat ini ... Saya masih perlu mengkonfirmasi bahwa Clang melakukan sesuatu tentang hal itu), karena seorang profiler yang menjalankan test-case terakhir dari pertanyaan ini menghasilkan hasil yang "cantik" ini:

Time profiling on -O3 Time profiling on -Ofast

Seperti yang dikatakan oleh banyak orang lain, -Ofast benar-benar tidak aman dan mengubah semantik bahasa. Bagi saya, ini adalah pada tahap “Jika Anda akan menggunakannya, gunakan saja bahasa lain”. Saya akan mengevaluasi kembali pilihan itu nanti, jika itu berubah.

-O3 memberi kita banyak swift_retain dan swift_release panggilan itu, jujur, tidak terlihat seperti mereka harus ada di sana untuk contoh ini. Pengoptimal seharusnya telah memulainya (sebagian besar) mereka AFAICT, karena ia tahu sebagian besar informasi tentang larik, dan tahu bahwa ia memiliki (setidaknya) referensi yang kuat untuk itu.

Seharusnya tidak memancarkan lebih banyak mempertahankan ketika itu bahkan tidak memanggil fungsi yang mungkin melepaskan objek. Saya tidak berpikir sebuah konstruktor array dapat mengembalikan array yang lebih kecil dari yang diminta, yang berarti bahwa banyak pemeriksaan yang dipancarkan tidak berguna. Ia juga tahu bahwa bilangan bulat tidak akan pernah di atas 10k, sehingga pemeriksaan meluap bisa dioptimalkan (bukan karena -Ofast Keanehan, tetapi karena semantik bahasa (tidak ada yang lain yang mengubah var itu juga tidak dapat mengaksesnya, dan menambahkan hingga 10k aman untuk tipe Int).

Compiler mungkin tidak dapat unbox array atau elemen-elemen array, meskipun, karena mereka dilewatkan sort(), yang merupakan fungsi eksternal dan harus mendapatkan argumen yang diharapkannya. Ini akan membuat kita harus menggunakan Int nilai secara tidak langsung, yang akan membuatnya sedikit lebih lambat. Ini bisa berubah jika sort() fungsi generik (tidak dalam cara multi-metode) tersedia untuk compiler dan mendapat inline.

Ini adalah bahasa yang sangat baru (publik), dan melalui apa yang saya anggap banyak perubahan, karena ada orang (berat) yang terlibat dengan bahasa Swift yang meminta umpan balik dan mereka semua mengatakan bahasa belum selesai dan akan perubahan.

Kode yang digunakan:

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

P.S: Saya bukan ahli Objective-C atau semua fasilitas dari Biji cokelat, Objective-C, atau Swift runtimes. Saya mungkin juga mengasumsikan beberapa hal yang tidak saya tulis.


100
2018-06-09 06:30



Saya memutuskan untuk melihat ini untuk bersenang-senang, dan berikut adalah timing yang saya dapatkan:

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

Cepat

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

Hasil:

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

Sepertinya performanya sama jika saya mengkompilasi -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

Tampaknya ada regresi kinerja dari Swift 2.0 ke Swift 3.0, dan saya juga melihat perbedaan antara -O dan -Ounchecked untuk pertama kalinya.

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 meningkatkan kinerja lagi, sambil mempertahankan jarak antara -O dan -Ounchecked. -O -whole-module-optimization tampaknya tidak membuat perbedaan.

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

Hasil:

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

Putusan

Pada saat penulisan ini, semacam Swift cepat, tetapi belum secepat C ++ ketika disusun dengan -O, dengan kompiler & pustaka di atas. Dengan -Ounchecked, tampaknya secepat C ++ di Swift 4.0.2 dan Apple LLVM 9.0.0.


42
2017-10-26 21:47



Dari The Swift Programming Language:

Pustaka standar Sort Function Swift menyediakan fungsi yang disebut   sort, yang mengurutkan array nilai dari tipe yang dikenal, berdasarkan pada   output dari penutupan penyortiran yang Anda berikan. Setelah selesai   proses penyortiran, fungsi urut mengembalikan array baru yang sama   jenis dan ukuran seperti yang lama, dengan elemen-elemennya diurutkan dengan benar   memesan.

Itu sort fungsi memiliki dua deklarasi.

Deklarasi default yang memungkinkan Anda untuk menentukan penutupan perbandingan:

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

Dan deklarasi kedua yang hanya mengambil satu parameter (array) dan "hardcoded untuk menggunakan komparator yang kurang dari".

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

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

Saya menguji versi modifikasi kode Anda di taman bermain dengan penutupan ditambahkan sehingga saya dapat memantau fungsi sedikit lebih dekat, dan saya menemukan bahwa dengan n disetel menjadi 1000, penutupan itu disebut sekitar 11.000 kali.

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

Ini bukan fungsi yang efisien, saya akan merekomendasikan menggunakan implementasi fungsi penyortiran yang lebih baik.

EDIT:

Saya melihat halaman Quicksort wikipedia dan menulis implementasi Swift untuk itu. Berikut adalah program lengkap yang saya gunakan (di taman bermain)

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
}

Menggunakan ini dengan n = 1000, saya menemukan itu

  1. quickSort () dipanggil sekitar 650 kali,
  2. sekitar 6000 swaps dibuat,
  3. dan ada sekitar 10.000 perbandingan

Tampaknya metode sortir bawaan adalah (atau dekat) cepat, dan sangat lambat ...


29
2018-06-08 00:29



Mulai Xcode 7 Anda dapat mengaktifkan Fast, Whole Module Optimization. Ini harus segera meningkatkan kinerja Anda.

enter image description here


15
2018-06-11 16:56



Penampilan Swift Array ditinjau kembali:

Saya menulis tolok ukur saya sendiri membandingkan Swift dengan C / Objective-C. Tolok ukur saya menghitung bilangan prima. Ini menggunakan array dari bilangan prima sebelumnya untuk mencari faktor prima di setiap kandidat baru, sehingga cukup cepat. Namun, itu TONS dari membaca larik, dan kurang menulis ke array.

Saya awalnya melakukan benchmark terhadap Swift 1.2 ini. Saya memutuskan untuk memperbarui proyek dan menjalankannya dengan Swift 2.0.

Proyek ini memungkinkan Anda memilih antara menggunakan swift array normal dan menggunakan buffer memori tidak aman Swift menggunakan array semantik.

Untuk C / Objective-C, Anda dapat memilih untuk menggunakan NSArrays, atau array C malloc'ed.

Hasil tes tampaknya sangat mirip dengan tercepat, optimasi kode terkecil ([-0s]) atau tercepat, agresif ([-0fast]) optimasi.

Kinerja Swift 2.0 masih mengerikan dengan optimalisasi kode dimatikan, sedangkan kinerja C / Objective-C hanya sedikit lebih lambat.

Intinya adalah bahwa perhitungan berbasis array C malloc'd adalah yang tercepat, dengan margin yang sederhana

Swift dengan buffer yang tidak aman membutuhkan waktu sekitar 1,19X - 1,20X lebih lama dari C malloc'd array ketika menggunakan tercepat, optimasi kode terkecil. perbedaannya tampak sedikit kurang dengan cepat, optimasi agresif (Swift mengambil lebih seperti 1,18x ke 1,16x lebih lama dari C.

Jika Anda menggunakan array Swift biasa, perbedaannya dengan C adalah sedikit lebih besar. (Swift mengambil ~ 1,22-1,23 lebih panjang.)

Array Swift Reguler adalah DRAMATICALLY lebih cepat daripada Swift 1.2 / Xcode 6. Performanya sangat dekat dengan Swift berbasis buffer yang tidak aman yang menggunakan buffer memori yang tidak aman tidak benar-benar tampak sebanding dengan masalah lagi, yang besar.

BTW, kinerja Objective-C NSArray menyebalkan. Jika Anda akan menggunakan objek penampung asli dalam kedua bahasa, Swift adalah DRAMATIK lebih cepat.

Anda dapat melihat proyek saya di github di SwiftPerformanceBenchmark

Ini memiliki UI sederhana yang membuat statistik pengumpulan cukup mudah.

Sangat menarik bahwa pengurutan tampaknya sedikit lebih cepat di Swift daripada di C sekarang, tetapi algoritma bilangan prima ini masih lebih cepat di Swift.


8
2018-02-26 01:31



Masalah utama yang disebutkan oleh orang lain tetapi tidak disebut cukup adalah itu -O3 tidak melakukan apa-apa di Swift (dan tidak pernah ada) sehingga ketika dikompilasi dengan itu secara efektif tidak dioptimalkan (-Onone).

Nama-nama pilihan telah berubah dari waktu ke waktu sehingga beberapa jawaban lain memiliki bendera-bendera usang untuk opsi-opsi pembangunan. Pilihan saat ini yang benar (Swift 2.2) adalah:

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

Seluruh pengoptimalan modul memiliki kompilasi yang lebih lambat tetapi dapat mengoptimalkan seluruh file dalam modul yaitu di dalam setiap kerangka kerja dan dalam kode aplikasi yang sebenarnya tetapi tidak di antara keduanya. Anda harus menggunakan ini untuk kinerja apa pun yang kritis)

Anda juga dapat menonaktifkan pemeriksaan keamanan untuk kecepatan yang lebih tinggi tetapi dengan semua pernyataan dan prakondisi tidak hanya dinonaktifkan tetapi dioptimalkan atas dasar bahwa mereka benar. Jika Anda pernah memukul pernyataan ini berarti Anda menjadi perilaku tidak terdefinisi. Gunakan dengan sangat hati-hati dan hanya jika Anda menentukan bahwa dorongan kecepatan bermanfaat bagi Anda (dengan menguji). Jika Anda merasa berharga untuk beberapa kode, saya sarankan memisahkan kode itu ke dalam kerangka terpisah dan hanya menonaktifkan pemeriksaan keamanan untuk modul itu.


5
2018-04-13 10:58



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) 

Ini Blog saya tentang Quick Sort- Contoh Github Quick-Sort

Anda dapat melihat tentang algoritma partisi Lomuto dalam Mempartisi daftar. Ditulis dalam Swift


4
2017-12-06 11:12