performance - Swift Beta 성능 : 배열 정렬

swift / sorting / xcode6 / compiler-optimization

Swift Beta에서 알고리즘을 구현하고 있는데 성능이 매우 나쁘다는 것을 알았습니다. 더 깊이 파고 들자 병목 현상 중 하나가 배열 정렬과 같은 간단한 것임을 깨달았습니다. 관련 부분은 다음과 같습니다.

let n = 1000000
var x =  [Int](repeating: 0, count: n)
for i in 0..<n {
    x[i] = random()
}
// 여기에서 시계 시작
let y = sort(x)
// 여기서 시계 중지

Swift에서는 다음 명령으로 컴파일하면 6 초가 걸립니다 .

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

그리고 다음 명령으로 컴파일하면 88 초가 걸립니다 .

xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`
let n = 10000000
print(n*n*n*n*n)
let x =  [Int](repeating: 10, count: n)
print(x[n])

편집 2 : 몇 가지 벤치마킹을 수행했습니다.

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

편집 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]
    }
}

Nilesh R Patel



Answer #1

나는 이것을 재미로 살펴보기로 결정했고 여기에 내가 얻는 타이밍이 있습니다.

Swift 4.0.2           :   0.83s (0.74s with `-Ounchecked`)
C++ (Apple LLVM 8.0.0):   0.74s
// Swift 4.0 코드
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

스위프트 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

스위프트 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
#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

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

이 글을 쓰는 시점에서 Swift의 정렬은 빠르지 만 위의 컴파일러 및 라이브러리를 사용하여 -O 로 컴파일 할 때 C ++의 정렬만큼 빠르지는 않습니다 . -Ounchecked 를 사용하면 Swift 4.0.2 및 Apple LLVM 9.0.0에서 C ++만큼 빠릅니다.