swift - स्विफ्ट प्रदर्शन:सरणी सरणी




algorithm performance sorting (8)

टीएल; डीआर : हां, अभी एकमात्र स्विफ्ट भाषा कार्यान्वयन धीमा है, अभी । यदि आपको तेज़, संख्यात्मक (और अन्य प्रकार के कोड, संभवतः) कोड की आवश्यकता है, तो बस एक और के साथ जाएं। भविष्य में, आपको अपनी पसंद का फिर से मूल्यांकन करना चाहिए। हालांकि, उच्च स्तर पर लिखे गए अधिकांश एप्लिकेशन कोड के लिए यह काफी अच्छा हो सकता है।

एसआईएल और एलएलवीएम आईआर में जो कुछ मैं देख रहा हूं, उससे ऐसा लगता है कि उन्हें बनाए रखने और रिलीज को हटाने के लिए ऑप्टिमाइज़ेशन की एक गुच्छा की आवश्यकता है, जिसे Clang (उद्देश्य-सी के लिए) में लागू किया जा सकता है, लेकिन उन्होंने अभी तक उन्हें पोर्ट नहीं किया है। यही वह सिद्धांत है जिसके साथ मैं जा रहा हूं (अभी के लिए ... मुझे अभी भी यह पुष्टि करने की आवश्यकता है कि क्लैंग इसके बारे में कुछ करता है), चूंकि इस प्रश्न के आखिरी टेस्ट-केस पर चलने वाले प्रोफाइलर ने "सुंदर" परिणाम प्राप्त किया है:

जैसा कि कई अन्य लोगों ने कहा था, -Ofast पूरी तरह से असुरक्षित है और भाषा अर्थशास्त्र बदलता है। मेरे लिए, यह "यदि आप इसका उपयोग करने जा रहे हैं, तो बस एक और भाषा का प्रयोग करें" मंच पर है। यदि यह बदलता है, तो मैं बाद में उस विकल्प का पुनर्मूल्यांकन करूंगा।

swift_retain हमें swift_retain का एक गुच्छा प्राप्त swift_retain और swift_release कहते हैं, ईमानदारी से, ऐसा नहीं लगता कि वे इस उदाहरण के लिए वहां होना चाहिए। ऑप्टिमाइज़र को एएफएआईसीटी (उनमें से अधिकतर) को elided होना चाहिए, क्योंकि यह सरणी के बारे में अधिकतर जानकारी जानता है, और जानता है कि इसमें (कम से कम) इसका एक मजबूत संदर्भ है।

यह अधिक बरकरार नहीं रहना चाहिए जब यह उन कार्यों को भी कॉल नहीं कर रहा है जो वस्तुओं को छोड़ सकते हैं। मुझे नहीं लगता कि एक सरणी कन्स्ट्रक्टर एक सरणी वापस कर सकता है जो कि पूछा गया था उससे छोटा है, जिसका मतलब है कि उत्सर्जित किए गए बहुत सारे चेक बेकार हैं। यह भी जानता है कि पूर्णांक 10k से ऊपर कभी नहीं होगा, इसलिए ओवरफ्लो चेक को अनुकूलित किया जा सकता है ( -Ofast अजीबता के कारण नहीं, बल्कि भाषा के अर्थशास्त्र के कारण (कुछ और नहीं बदल रहा है और न ही इसे एक्सेस कर सकता है, और जोड़ रहा है प्रकार Int लिए 10k सुरक्षित है)।

कंपाइलर सरणी या सरणी तत्वों को अनबॉक्स करने में सक्षम नहीं हो सकता है, हालांकि, क्योंकि वे sort() को पारित कर रहे हैं, जो बाहरी कार्य है और इसे तर्कों को प्राप्त करना है। यह हमें अप्रत्यक्ष रूप से Int मानों का उपयोग करना होगा, जो इसे थोड़ा धीमा कर देगा। यह बदल सकता है अगर sort() बहु-कार्य (मल्टी-विधि तरीके से नहीं) संकलक के लिए उपलब्ध था और इनलाइन हो गया था।

यह एक बहुत ही नई (सार्वजनिक रूप से) भाषा है, और यह मुझे लगता है कि बहुत सारे बदलाव हैं, क्योंकि स्विफ्ट भाषा के साथ लोगों (भारी) शामिल हैं जो प्रतिक्रिया के लिए पूछ रहे हैं और वे सभी कहते हैं कि भाषा समाप्त नहीं हुई है और परिवर्तन।

कोड का इस्तेमाल किया गया:

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

पीएस: मैं उद्देश्य-सी पर विशेषज्ञ नहीं हूं और न ही Cocoa , उद्देश्य-सी, या स्विफ्ट रनटाइम्स की सभी सुविधाएं। मैं कुछ चीजें भी मान सकता हूं जिन्हें मैंने नहीं लिखा था।

मैं स्विफ्ट में एक एल्गोरिदम लागू कर रहा था और देखा कि प्रदर्शन बहुत खराब था। गहराई से खोदने के बाद मुझे एहसास हुआ कि बाधाओं में से एक सरणी को सॉर्ट करने जैसा सरल था। प्रासंगिक हिस्सा यहां है:

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

सी ++ में, एक समान ऑपरेशन मेरे कंप्यूटर पर 0.06 एस लेता है।

पायथन में यह पूर्णांक की सूची के लिए 0.6 एस (कोई चाल नहीं, बस y = क्रमबद्ध (x) लेता है)।

स्विफ्ट में अगर मैं इसे निम्न आदेश से संकलित करता हूं तो इसमें 6 एस लगते हैं:

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

और अगर मैं इसे निम्न आदेश से संकलित करता हूं तो इसमें 88 एस लगते हैं:

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

"रिलीज" बनाम "डीबग" बिल्ड के साथ एक्सकोड में समय समान है।

यहाँ क्या गलत है? मैं सी ++ की तुलना में कुछ प्रदर्शन हानि को समझ सकता हूं, लेकिन शुद्ध पायथन की तुलना में 10 गुना मंदी नहीं।

संपादित करें: mweathers ने देखा कि बदलते -Ofast से -Ofast इस कोड को लगभग C ++ संस्करण के रूप में तेज़ी से चलाता है! हालांकि, -Ofast भाषा के अर्थशास्त्र को बहुत बदलता है - मेरे परीक्षण में, यह पूर्णांक अतिप्रवाह और सरणी अनुक्रमण ओवरफ्लो के लिए चेक अक्षम कर देता है । उदाहरण के लिए, निम्नलिखित स्विफ्ट कोड के साथ चुपचाप बिना चुपचाप चलाता है (और कुछ कचरे को प्रिंट करता है):

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

तो -Ofast वह नहीं है जो हम चाहते हैं; स्विफ्ट का पूरा बिंदु यह है कि हमारे पास सुरक्षा जाल है। बेशक सुरक्षा नेट पर प्रदर्शन पर कुछ प्रभाव पड़ता है, लेकिन उन्हें प्रोग्राम को 100 गुना धीमा नहीं करना चाहिए। याद रखें कि जावा पहले से ही सरणी सीमाओं के लिए जांच करता है, और सामान्य मामलों में मंदी 2 से कम कारक द्वारा होती है। और -ftrapv और जीसीसी में हमें जांच (हस्ताक्षरित) पूर्णांक ओवरफ़्लो के लिए -ftrapv मिला है, और यह धीमा नहीं है, या तो ।

इसलिए सवाल: हम सुरक्षा जाल खोए बिना स्विफ्ट में उचित प्रदर्शन कैसे प्राप्त कर सकते हैं?

संपादित करें 2: मैंने कुछ और बेंचमार्किंग की, लाइनों के साथ बहुत ही सरल लूप के साथ

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

(यहां एक्सर ऑपरेशन बस इतना है कि मैं असेंबली कोड में प्रासंगिक लूप को आसानी से ढूंढ सकता हूं। मैंने एक ऑपरेशन चुनने की कोशिश की जो स्पॉट करने में आसान है लेकिन इस अर्थ में "हानिरहित" भी है कि इसे किसी भी चेक से संबंधित नहीं होना चाहिए पूर्णांक अतिप्रवाह करने के लिए।)

फिर, -Ofast और -Ofast बीच प्रदर्शन में एक बड़ा अंतर था। तो मैंने असेंबली कोड पर एक नज़र डाली:

  • साथ-साथ मुझे बहुत कुछ मिलता है जो मैं उम्मीद करता हूं। प्रासंगिक भाग 5 मशीन भाषा निर्देशों के साथ एक लूप है।

  • -O3 साथ मुझे कुछ ऐसी चीज मिलती है जो मेरी जंगली कल्पना से परे थी। आंतरिक पाश असेंबली कोड की 88 लाइनों को फैलाता है। मैंने इसे सब कुछ समझने की कोशिश नहीं की, लेकिन सबसे संदिग्ध भाग "callq _swift_retain" के 13 आमंत्रण और "callq _swift_release" के 13 अन्य आमंत्रण हैं। यही है, आंतरिक लूप में 26 subroutine कॉल !

संपादित करें 3: टिप्पणियों में, फेरुसियो ने उन मानकों के लिए कहा जो इस अर्थ में निष्पक्ष हैं कि वे अंतर्निहित कार्यों (जैसे क्रमबद्ध) पर भरोसा नहीं करते हैं। मुझे लगता है कि निम्नलिखित कार्यक्रम एक काफी अच्छा उदाहरण है:

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

कोई अंकगणित नहीं है, इसलिए हमें पूर्णांक अतिप्रवाह के बारे में चिंता करने की आवश्यकता नहीं है। एकमात्र चीज जो हम करते हैं वह बहुत सारे सरणी संदर्भ हैं। और परिणाम यहां हैं- स्विफ्ट-ओ 3 कारक द्वारा लगभग 500 की तुलना में खो देता है - ओफ़फा:

  • सी ++-ओ 3: 0.05 एस
  • सी ++-ओ 0: 0.4 एस
  • जावा: 0.2 एस
  • पायपी के साथ पायथन: 0.5 एस
  • पायथन: 12 एस
  • स्विफ्ट-ओफ़ास्ट: 0.05 एस
  • स्विफ्ट-ओ 3: 23 एस
  • स्विफ्ट -00: 443 एस

(यदि आप चिंतित हैं कि कंपाइलर पूरी तरह से व्यर्थ लूप को अनुकूलित कर सकता है, तो आप इसे x[i] ^= x[j] बदल सकते हैं, और एक प्रिंट स्टेटमेंट जोड़ सकते हैं जो x[0] आउटपुट करता है। यह कुछ भी नहीं बदलेगा समय बहुत समान होगा।)

और हां, यहां पाइथन कार्यान्वयन एक बेवकूफ शुद्ध पायथन कार्यान्वयन था जिसमें चींटियों की सूची और लूप के लिए घोंसला था। यह unoptimised स्विफ्ट से बहुत धीमी होनी चाहिए। स्विफ्ट और सरणी अनुक्रमण के साथ कुछ गंभीर रूप से टूटा हुआ प्रतीत होता है।

4 संपादित करें: ये समस्याएं (साथ ही साथ कुछ अन्य प्रदर्शन समस्याएं) एक्सकोड 6 बीटा 5 में तय की गई हैं।

सॉर्ट करने के लिए, अब मेरे पास निम्नलिखित समय हैं:

  • क्लैंग ++-ओ 3: 0.06 एस
  • swiftc -Ofast: 0.1 एस
  • स्विफ्टक-ओ: 0.1 एस
  • स्विफ्टसी: 4 एस

नेस्टेड लूप के लिए:

  • क्लैंग ++-ओ 3: 0.06 एस
  • swiftc -Ofast: 0.3 एस
  • स्विफ्टक-ओ: 0.4 एस
  • स्विफ्टसी: 540 एस

ऐसा लगता है कि असुरक्षित-उर्फ (उर्फ- -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()

परिणाम:

स्विफ्ट 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

स्विफ्ट 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

स्विफ्ट 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 साथ संकलित करता हूं तो यह वही प्रदर्शन -Ounchecked

स्विफ्ट 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

ऐसा लगता है कि स्विफ्ट 2.0 से स्विफ्ट 3.0 तक एक प्रदर्शन प्रतिगमन रहा है, और मुझे पहली बार -O और -Ounchecked बीच एक अंतर भी दिखाई दे रहा है।

स्विफ्ट 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

स्विफ्ट 4 -O और -Ounchecked बीच एक अंतर बनाए रखते हुए प्रदर्शन को फिर से -Ounchecked-O -whole-module-optimization एक फर्क नहीं पड़ता था।

सी ++

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

परिणाम:

ऐप्पल क्लैंग 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

ऐप्पल क्लैंग 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

ऐप्पल क्लैंग 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

ऐप्पल क्लैंग 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

निर्णय

इस लेखन के समय के रूप में, स्विफ्ट का प्रकार तेज़ है, लेकिन उपरोक्त कंपाइलर्स और पुस्तकालयों के साथ -O साथ संकलित होने पर सी ++ के प्रकार के जितना तेज़ नहीं है। -Ounchecked साथ, यह स्विफ्ट 4.0.2 और ऐप्पल एलएलवीएम 9.0.0 में सी ++ जितना तेज़ प्रतीत होता है।


The Swift Programming Language :

सॉर्ट फ़ंक्शन स्विफ्ट की मानक लाइब्रेरी सॉर्ट नामक एक फ़ंक्शन प्रदान करती है, जो आपके द्वारा प्रदान किए गए सॉर्टिंग क्लोजर के आउटपुट के आधार पर ज्ञात प्रकार के मानों की एक सरणी प्रदान करती है। एक बार यह सॉर्टिंग प्रक्रिया को पूरा करने के बाद, सॉर्ट फ़ंक्शन एक ही प्रकार और आकार की एक नई सरणी को पुराने क्रम के रूप में देता है, जिसमें इसके तत्व सही क्रमबद्ध क्रम में होते हैं।

sort फ़ंक्शन में दो घोषणाएं हैं।

डिफ़ॉल्ट घोषणा जो आपको तुलना बंद करने की अनुमति देती है:

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

और एक दूसरी घोषणा जो केवल एक पैरामीटर (सरणी) लेती है और "तुलनित्र से कम उपयोग करने के लिए हार्डकोडेड" है।

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

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

मैंने अपने कोड के एक संशोधित संस्करण को एक खेल के मैदान में बंद करने के साथ परीक्षण किया है, इसलिए मैं फ़ंक्शन को थोड़ा अधिक बारीकी से देख सकता हूं, और मैंने पाया कि एन सेट 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 }

यह एक कुशल कार्य नहीं है, मैं एक बेहतर सॉर्टिंग फ़ंक्शन कार्यान्वयन का उपयोग करने की अनुशंसा करता हूं।

संपादित करें:

मैंने क्विक्सोर्ट विकिपीडिया पेज पर एक नज़र डाली और इसके लिए एक स्विफ्ट कार्यान्वयन लिखा। यहां मेरा पूरा कार्यक्रम है (एक खेल के मैदान में)

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
}

एन = 1000 के साथ इसका उपयोग करके, मैंने पाया

  1. quickSort () को लगभग 650 बार बुलाया गया,
  2. लगभग 6000 स्वैप किए गए थे,
  3. और लगभग 10,000 तुलना हैं

ऐसा लगता है कि अंतर्निहित सॉर्ट विधि त्वरित प्रकार है (या करीब है), और वास्तव में धीमी है ...


एक्सकोड 7 के रूप में आप Fast, Whole Module Optimization चालू कर सकते हैं। यह तुरंत आपके प्रदर्शन में वृद्धि करनी चाहिए।


स्विफ्ट ऐरे प्रदर्शन पुनरीक्षित:

मैंने सी / ऑब्जेक्टिव-सी के साथ स्विफ्ट की तुलना में अपना खुद का बेंचमार्क लिखा। मेरा बेंचमार्क प्राइम नंबर की गणना करता है। यह प्रत्येक नए उम्मीदवार में प्रमुख कारकों की तलाश करने के लिए पिछले प्राइम नंबरों की सरणी का उपयोग करता है, इसलिए यह काफी तेज़ है। हालांकि, यह सरणी पढ़ने के टन, और सरणी के लिए कम लेखन करता है।

मैंने मूल रूप से स्विफ्ट 1.2 के खिलाफ यह बेंचमार्क किया था। मैंने प्रोजेक्ट को अपडेट करने और इसे स्विफ्ट 2.0 के खिलाफ चलाने का फैसला किया।

प्रोजेक्ट आपको सामान्य स्विफ्ट सरणी का उपयोग करने और सरणी असंतुलन स्मृति का उपयोग कर स्विफ्ट असुरक्षित मेमोरी बफर का उपयोग करने के बीच चुनने देता है।

सी / उद्देश्य-सी के लिए, आप या तो NSArrays, या सी malloc'ed arrays का उपयोग करने का विकल्प चुन सकते हैं।

परीक्षण परिणाम सबसे तेज़, सबसे छोटे कोड अनुकूलन ([-0s]) या सबसे तेज़, आक्रामक ([-0fast]) अनुकूलन के साथ बहुत समान प्रतीत होते हैं।

स्विफ्ट 2.0 प्रदर्शन कोड अनुकूलन बंद होने के साथ अभी भी भयानक है, जबकि सी / उद्देश्य-सी प्रदर्शन केवल मामूली धीमी है।

निचली पंक्ति यह है कि सी malloc'd सरणी आधारित गणना एक मामूली मार्जिन द्वारा सबसे तेज़ हैं

असुरक्षित बफर के साथ स्विफ्ट सबसे तेज़, सबसे छोटा कोड अनुकूलन का उपयोग करते समय लगभग 1.1 9एक्स - सी 0 malloc'd सरणी से 1.20X लंबा लगता है। अंतर तेजी से, आक्रामक अनुकूलन के साथ थोड़ा कम लगता है (स्विफ्ट 1.18x से 1.16x से अधिक लंबा लेता है।

यदि आप नियमित स्विफ्ट सरणी का उपयोग करते हैं, तो सी के साथ अंतर थोड़ा अधिक है। (स्विफ्ट ~ 1.22 से 1.23 लंबा लेता है।)

नियमित स्विफ्ट एरे स्विफ्ट 1.2 / एक्सकोड 6 में DRAMATICALLY से तेज़ होते हैं। उनका प्रदर्शन स्विफ्ट असुरक्षित बफर आधारित सरणी के बहुत करीब है कि असुरक्षित मेमोरी बफर का उपयोग करने से वास्तव में परेशानी के लायक नहीं लगते हैं, जो कि बड़ा है।

बीटीडब्ल्यू, उद्देश्य-सी एनएसएआरएआर प्रदर्शन डूबता है। यदि आप दोनों भाषाओं में देशी कंटेनर ऑब्जेक्ट्स का उपयोग करने जा रहे हैं, तो स्विफ्ट तेजी से तेज़ है।

आप SwiftPerformanceBenchmark पर SwiftPerformanceBenchmark पर अपनी परियोजना देख सकते हैं

इसमें एक साधारण यूआई है जो आंकड़ों को इकट्ठा करना बहुत आसान बनाता है।

यह दिलचस्प है कि अब स्विफ्ट में स्विफ्ट में सॉर्टिंग थोड़ा तेज लगता है, लेकिन स्विफ्ट में यह प्राइम नंबर एल्गोरिदम अभी भी तेज है।


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) 

यह त्वरित सॉर्ट- गीथब नमूना त्वरित-क्रमबद्ध करने के बारे में मेरा ब्लॉग है

आप सूची विभाजन में लोमूटो के विभाजन एल्गोरिदम के बारे में एक नज़र डाल सकते हैं। स्विफ्ट में लिखा है


tl; डॉ स्विफ्ट अब डिफ़ॉल्ट रिलीज अनुकूलन स्तर [-O] का उपयोग करके इस बेंचमार्क द्वारा सी के रूप में तेज़ है।

स्विफ्ट में एक जगह में क्विकॉर्ट है:

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

और सी में वही:

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.

एन = 10_000 के लिए [-ऑनोन] के साथ सेकंड में समय:

Swift:            0.895296452
C:                0.001223848

एन = 10_000 के लिए स्विफ्ट का बिल्टिन सॉर्ट () यहां है:

Swift_builtin:    0.77865783

एन = 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

और एन = 1_000_000 के लिए :

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

तुलना के लिए, यह n = 1_000_000 के लिए [-ऑनोन] के साथ है:

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

तो इस चरण में, इस विकास में, इस बेंचमार्क में सी से ऑप्टिमाइज़ेशन के साथ स्विफ्ट लगभग 1000x धीमी थी। दूसरी तरफ दोनों कंपाइलर्स [-Ofast] स्विफ्ट के साथ सेट वास्तव में कम से कम प्रदर्शन किया जाता है यदि सी से थोड़ा बेहतर नहीं है।

यह इंगित किया गया है कि [-ओफास्ट] भाषा के अर्थशास्त्र को बदलता है, जिससे इसे संभावित रूप से असुरक्षित बना दिया जाता है। एक्सकोड 5.0 रिलीज नोट्स में ऐप्पल ने यही कहा है:

एक नया अनुकूलन स्तर - ओएफएफ, एलएलवीएम में उपलब्ध, आक्रामक अनुकूलन को सक्षम बनाता है। -ऑफस्ट कुछ रूढ़िवादी प्रतिबंधों को आराम देता है, ज्यादातर फ्लोटिंग-पॉइंट ऑपरेशंस के लिए, जो अधिकांश कोड के लिए सुरक्षित हैं। यह संकलक से महत्वपूर्ण उच्च प्रदर्शन जीत पैदा कर सकते हैं।

वे सब इसका समर्थन करते हैं। चाहे वह बुद्धिमान हो या नहीं, मैं कह नहीं सका, लेकिन जो कुछ मैं कह सकता हूं उससे रिलीज में [-ओफास्ट] का उपयोग करने के लिए पर्याप्त उचित लगता है यदि आप उच्च परिशुद्धता फ्लोटिंग पॉइंट अंकगणित नहीं कर रहे हैं और आपको विश्वास है कि कोई पूर्णांक नहीं है या आपके कार्यक्रम में सरणी अतिप्रवाह संभव है। यदि आपको उच्च प्रदर्शन और अतिप्रवाह चेक / सटीक अंकगणित की आवश्यकता है तो अब के लिए एक और भाषा चुनें।

बीटा 3 अद्यतन:

एन = 10_000 [-ओ] के साथ :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

सामान्य रूप से स्विफ्ट थोड़ा तेज़ है और ऐसा लगता है कि स्विफ्ट के अंतर्निहित प्रकार में काफी बदलाव आया है।

अंतिम अद्यतन:

[-ऑनोन] :

Swift:   0.678056695
C:       0.000973914

[-ओ] :

Swift:   0.001158492
C:       0.001192406

[-ऑनचेक्ड] :

Swift:   0.000827764
C:       0.001078914

Denormalized फ्लोटिंग बिंदु की दुनिया में आपका स्वागत है! वे प्रदर्शन पर कहर बरबाद कर सकते हैं !!!

फ्लोरेटिंग पॉइंट प्रस्तुति से शून्य के करीब कुछ अतिरिक्त मूल्य प्राप्त करने के लिए असामान्य (या असामान्य) संख्याएं हैंक की तरह हैं। Denormalized फ्लोटिंग-पॉइंट पर संचालन सामान्यीकृत फ्लोटिंग-पॉइंट की तुलना में सैकड़ों गुना धीमा हो सकता है। ऐसा इसलिए है क्योंकि कई प्रोसेसर उन्हें सीधे संभाल नहीं सकते हैं और उन्हें माइक्रोक्रोड का उपयोग करके जाल और हल करना चाहिए।

यदि आप 10,000 पुनरावृत्तियों के बाद संख्याओं को प्रिंट करते हैं, तो आप देखेंगे कि 0 या 0.1 का उपयोग करने के आधार पर वे अलग-अलग मानों में एकत्र हुए हैं।

X64 पर संकलित परीक्षण कोड यहां दिया गया है:

int main() {

    double start = omp_get_wtime();

    const float x[16]={1.1,1.2,1.3,1.4,1.5,1.6,1.7,1.8,1.9,2.0,2.1,2.2,2.3,2.4,2.5,2.6};
    const float z[16]={1.123,1.234,1.345,156.467,1.578,1.689,1.790,1.812,1.923,2.034,2.145,2.256,2.367,2.478,2.589,2.690};
    float y[16];
    for(int i=0;i<16;i++)
    {
        y[i]=x[i];
    }
    for(int j=0;j<9000000;j++)
    {
        for(int i=0;i<16;i++)
        {
            y[i]*=x[i];
            y[i]/=z[i];
#ifdef FLOATING
            y[i]=y[i]+0.1f;
            y[i]=y[i]-0.1f;
#else
            y[i]=y[i]+0;
            y[i]=y[i]-0;
#endif

            if (j > 10000)
                cout << y[i] << "  ";
        }
        if (j > 10000)
            cout << endl;
    }

    double end = omp_get_wtime();
    cout << end - start << endl;

    system("pause");
    return 0;
}

आउटपुट:

#define FLOATING
1.78814e-007  1.3411e-007  1.04308e-007  0  7.45058e-008  6.70552e-008  6.70552e-008  5.58794e-007  3.05474e-007  2.16067e-007  1.71363e-007  1.49012e-007  1.2666e-007  1.11759e-007  1.04308e-007  1.04308e-007
1.78814e-007  1.3411e-007  1.04308e-007  0  7.45058e-008  6.70552e-008  6.70552e-008  5.58794e-007  3.05474e-007  2.16067e-007  1.71363e-007  1.49012e-007  1.2666e-007  1.11759e-007  1.04308e-007  1.04308e-007

//#define FLOATING
6.30584e-044  3.92364e-044  3.08286e-044  0  1.82169e-044  1.54143e-044  2.10195e-044  2.46842e-029  7.56701e-044  4.06377e-044  3.92364e-044  3.22299e-044  3.08286e-044  2.66247e-044  2.66247e-044  2.24208e-044
6.30584e-044  3.92364e-044  3.08286e-044  0  1.82169e-044  1.54143e-044  2.10195e-044  2.45208e-029  7.56701e-044  4.06377e-044  3.92364e-044  3.22299e-044  3.08286e-044  2.66247e-044  2.66247e-044  2.24208e-044

ध्यान दें कि दूसरी दौड़ में संख्या शून्य के बहुत करीब हैं।

Denormalized संख्या आम तौर पर दुर्लभ हैं और इस प्रकार अधिकांश प्रोसेसर कुशलतापूर्वक उन्हें संभालने की कोशिश नहीं करते हैं।

यह दिखाने के लिए कि इसमें सब कुछ है जो denormalized संख्याओं के साथ करने के लिए है, अगर हम कोड की शुरुआत में इसे जोड़कर शून्य पर denormals फ्लश :

_MM_SET_FLUSH_ZERO_MODE(_MM_FLUSH_ZERO_ON);

फिर 0 साथ संस्करण अब 10x धीमा नहीं है और वास्तव में तेज़ी से हो जाता है। (यह आवश्यक है कि कोड एसएसई सक्षम के साथ संकलित किया जाए।)

इसका मतलब है कि इन अजीब निचले परिशुद्धता लगभग-शून्य मानों का उपयोग करने के बजाय, हम इसके बजाय शून्य पर गोल करते हैं।

समय: कोर i7 920 @ 3.5 गीगाहर्ट्ज:

//  Don't flush denormals to zero.
0.1f: 0.564067
0   : 26.7669

//  Flush denormals to zero.
0.1f: 0.587117
0   : 0.341406

अंत में, इसका वास्तव में कुछ भी नहीं है कि यह एक पूर्णांक या फ़्लोटिंग-पॉइंट है या नहीं। 0 या 0.1f दोनों लूप के बाहर एक रजिस्टर में परिवर्तित / संग्रहीत किया जाता है। तो इसका प्रदर्शन पर कोई प्रभाव नहीं पड़ता है।





swift algorithm performance sorting