swift - sort - 신속한 베타 성능:배열 정렬




swift4 array sort (6)

스위프트 베타 (Swift Beta) 알고리즘을 구현하면서 성능이 매우 열악하다는 것을 알았습니다. 파고가 깊어지면서 병목 현상 중 하나가 배열을 정렬하는 것처럼 간단하다는 것을 깨달았습니다. 관련 부분은 다음과 같습니다.

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 초가 걸립니다.

파이썬에서는 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`

"Release"대 "Debug"빌드가있는 Xcode의 타이밍은 비슷합니다.

여기서 뭐가 잘못 됐니? 나는 C ++과 비교하여 약간의 성능 손실을 이해할 수 있었지만 순수한 파이썬과 비교할 때 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])

따라서 우리는 우리가 원하는 것이 아닙니다. 스위프트의 핵심은 안전망을 갖추고 있다는 것입니다. 물론 안전망은 성능에 약간의 영향을 미치지 만 프로그램을 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 줄의 어셈블리 코드에 걸쳐 있습니다. 나는이 모든 것을 이해하려고 시도하지는 않았지만, 가장 의심스러운 부분은 "callq _swift_retain"의 13 번의 호출과 "callq _swift_release"의 13 번의 호출입니다. 즉 , 내부 루프에서 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]
    }
}

산술 연산이 없기 때문에 정수 오버 플로우에 대해 걱정할 필요가 없습니다. 우리가하는 유일한 일은 많은 배열 참조입니다. 그리고 결과는 여기에 있습니다 - 신속 -O3는 Ofast와 비교하여 거의 500 배 정도의 요인으로 손실됩니다.

  • C ++ -O3 : 0.05 초
  • C ++ -O0 : 0.4 초
  • Java : 0.2 초
  • Python으로 파이썬 : 0.5 초
  • 파이썬 : 12 초
  • 빠름 - 빠름 : 0.05 초
  • 스위프트 -O3 : 23 초
  • 스위프트 -O0 : 443 초

(컴파일러가 무의미한 루프를 완전히 최적화하는 것이 염려되는 경우 x[i] ^= x[j] 변경할 수 있고 x[0] 을 출력하는 print 문을 추가 할 수 있습니다. 타이밍은 매우 유사합니다.)

그리고 네, 여기 파이썬 구현은 int리스트와 중첩 된 for 루프를 가진 어리석은 순수 파이썬 구현입니다. 그것은 최적화되지 않은 스위프트보다 훨씬 느려야합니다. 스위프트 및 배열 인덱싱을 사용하여 무언가가 심각하게 손상된 것으로 보입니다.

편집 4 : 이 문제 (다른 성능 문제는 물론)는 Xcode 6 베타 5에서 수정 된 것으로 보입니다.

정렬을 위해 이제 다음과 같은 타이밍이 있습니다.

  • clang ++ -O3 : 0.06 초
  • swiftc - 고속 : 0.1 초
  • swiftc -O : 0.1 초
  • swiftc : 4 초

중첩 루프의 경우 :

  • clang ++ -O3 : 0.06 초
  • swiftc -Ofast : 0.3 초
  • swiftc -O : 0.4 초
  • swiftc : 540 초

안전하지 않은 이유를 더 이상 사용하지 않는 것으로 보인다. -Ofast ( -Ounchecked ); plain -O 는 똑같이 좋은 코드를 생성합니다.


Xcode 7부터 Fast, Whole Module Optimization 을 사용할 수 있습니다. 이렇게하면 즉시 실적이 향상됩니다.


drl Swift 1.0은 이제 기본 릴리스 최적화 수준 [-O]을 사용하여이 벤치 마크에서 C만큼 빠릅니다.

스위프트 베타 (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)
}

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

n = 10_000에 대한 Swift의 내장 sort ()가 있습니다 :

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

따라서 최적화가없는 스위프트는 개발 단계의이 벤치 마크에서 C보다 거의 1000 배 느립니다. 반면에 [-Ofast]로 설정된 두 컴파일러 모두에서 Swift는 실제로 C보다 약간 나은 경우에도 실제로 수행했습니다.

[-Ofast]는 언어의 의미를 변경하여 잠재적으로 안전하지 못하다고 지적했습니다. 이것이 Apple이 Xcode 5.0 릴리스 노트에서 말한 내용입니다.

LLVM에서 제공되는 새로운 최적화 수준 -Ofast는 공격적인 최적화를 가능하게합니다. -Ofast는 대부분 부동 소수점 연산에 대한 일부 보수적 인 제한을 완화합니다. 대부분의 코드에서 안전합니다. 컴파일러에서 상당한 성능 향상을 얻을 수 있습니다.

그들은 모두 그것을 옹호하지만. 그것이 현명한 것이 든 아니든 말할 수는 없지만, 고정밀 부동 소수점 연산을 수행하지 않고 정수가 없다고 확신 할 경우 릴리즈에서 [-Ofast]를 사용하는 것이 합리적으로 보일 수도 있습니다. 프로그램에서 배열 오버플로가 가능합니다. 고성능 오버 플로우 검사 / 정밀 산술이 필요한 경우 지금은 다른 언어를 선택하십시오.

베타 3 업데이트 :

[-O]로 n = 10_000 :

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

Swift는 일반적으로 조금 빠르며 Swift의 내장형 정렬이 상당히 변경되었습니다.

최종 업데이트 :

[- 없음] :

Swift:   0.678056695
C:       0.000973914

[-O] :

Swift:   0.001158492
C:       0.001192406

[확인 됨] :

Swift:   0.000827764
C:       0.001078914

다른 사람들에 의해 언급되었지만 충분히 부르지 않은 주된 문제는 -O3 가 Swift에서 아무 것도하지 않는다는 것입니다. 그래서 컴파일 할 때 효과적으로 최적화되지 -Onone ( -Onone ).

옵션 이름은 시간이 지남에 따라 변경되었으므로 일부 다른 응답에는 빌드 옵션에 대해 쓸모없는 플래그가 있습니다. 올바른 현재 옵션 (Swift 2.2)은 다음과 같습니다.

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

전체 모듈 최적화는 컴파일 속도가 느리지 만 모듈 내의 파일 즉, 각 프레임 워크 내 및 실제 응용 프로그램 코드 내에서 파일간에 최적화 할 수 있지만 그 사이에는 최적화 할 수 없습니다. 중요한 성능에 대해서는이 기능을 사용해야합니다.

안전 체크를 더 이상 속도를 낼 수 없도록 할 수는 있지만 모든 어설 션 및 전제 조건은 사용 중지되지 않았지만 올바른 기준에 따라 최적화됩니다. 단언 할 때 당신이 정의되지 않은 행동을한다는 ​​것을 의미합니다. 극도의주의를 기울이면서 테스트를 통해 속도 향상이 가치 있다고 판단한 경우에만 사용하십시오. 일부 코드에서 유용하다고 생각하면 해당 코드를 별도의 프레임 워크로 분리하고 해당 모듈의 안전성 검사 만 비활성화하는 것이 좋습니다.


스위프트 어레이 성능 재검토 :

Swift와 C / Objective-C를 비교하는 자체 벤치 마크를 작성했습니다. 내 벤치 마크는 소수를 계산합니다. 이전 후보 소수점 배열을 사용하여 각 후보자의 소수 요소를 찾습니다. 따라서 매우 빠릅니다. 그러나, 그것은 배열 읽기의 TONS를 수행하고, 배열에 쓰기를 줄입니다.

원래 Swift 1.2에 대한 벤치 마크를 수행했습니다. 나는 프로젝트를 업데이트하고 Swift 2.0에 대해 실행하기로 결정했다.

이 프로젝트를 사용하면 보통의 신속한 배열을 사용하거나 배열 의미 체계를 사용하여 안전하지 않은 신속한 메모리 버퍼를 사용할 수 있습니다.

C / Objective-C의 경우 NSArrays 또는 C malloc의 배열을 사용할 수 있습니다.

테스트 결과는 가장 빠르고 가장 작은 코드 최적화 ([-0s]) 또는 가장 빠르고 적극적인 ([-fast]) 최적화와 매우 유사합니다.

C / Objective-C 성능이 약간 느린 반면 Swift 2.0 성능은 코드 최적화가 해제 되어도 여전히 끔찍합니다.

결론은 Cmalloc의 배열 기반 계산이 가장 빠르며,

안전하지 않은 버퍼가있는 스위프트는 가장 빠르고 작은 코드 최적화를 사용할 때 C malloc의 배열보다 약 1.19X ~ 1.20X 길어집니다. 그 차이는 빠르고 적극적인 최적화 (스위프트는 1.18x보다 1.16x 길다.

일반 Swift 배열을 사용하면 C와의 차이가 약간 커집니다. (스위프트는 ~ 1.22 ~ 1.23 길어집니다.)

일반 Swift 어레이는 Swift 1.2 / Xcode 6보다 훨씬 빠릅니다. 안정성이 떨어지는 안전하지 않은 버퍼 기반 어레이와 성능이 너무 비슷하기 때문에 안전하지 않은 메모리 버퍼를 사용하면 더 이상 큰 문제가되지 않습니다.

BTW, Objective-C NSArray 성능이 악취. 두 언어 모두 네이티브 컨테이너 객체를 사용하려는 경우 Swift는 놀랍도록 빨라졌습니다.

SwiftPerformanceBenchmark 에서 github에서 내 프로젝트를 체크 아웃 할 수 있습니다.

통계를 매우 쉽게 수집 할 수있는 간단한 UI가 있습니다.

C에서보다 Swift에서 정렬이 약간 더 빨라지지만이 소수 알고리즘은 Swift에서 여전히 빠릅니다.


TL : 그렇습니다 . Swift 언어 구현은 느리지 만 지금 은 느립니다. 빠른 숫자 (및 다른 유형의 코드, 아마도) 코드가 필요한 경우 다른 코드와 함께 사용하십시오. 앞으로는 선택 사항을 다시 평가해야합니다. 그것은 더 높은 수준에서 작성된 대부분의 응용 프로그램 코드에 대해 충분할 수도 있습니다.

SIL과 LLVM IR에서 볼 수 Clang (Objective-C의 경우)에서 구현 될 수있는 유지 및 릴리스를 제거하기위한 최적화가 필요하지만 아직 포팅하지 않았습니다. 그것이 내가 할 이론입니다. (지금은 ... Clang이 그것에 대해 뭔가를한다는 것을 확인해야합니다.)이 질문의 마지막 테스트 케이스에서 프로파일 러를 실행하면 "꽤"결과가 나옵니다.

다른 많은 사람들에 의해 -Ofast 이, -Ofast 는 완전히 안전하지 않으며 언어 의미를 변경합니다. 나를 위해, 그것은 "당신이 그것을 사용하려고한다면, 단지 다른 언어를 사용하십시오"단계에 있습니다. 그 선택이 나중에 변경되면 다시 평가할 것입니다.

-O3 는 우리에게 swift_retainswift_release 콜을 swift_release . 솔직히이 예제에서는 거기에 있어야하는 것처럼 보이지 않습니다. 옵티마이 저는 어레이에 대한 대부분의 정보를 알고 있으며, 적어도 그것에 대한 강력한 참조를 가지고 있으므로 AFAICT를 생략해야합니다 (대부분).

객체를 해제 할 수있는 함수를 호출하지 않는 경우에도 더 이상 보유하지 않아야합니다. 배열 생성자가 요청한 것보다 작은 배열을 반환 할 수 없다고 생각합니다. 즉, 배출 된 많은 검사가 쓸모 없다는 것을 의미합니다. 또한 정수가 10k를 넘지 않을 것이라는 것을 알기 때문에 오버 플로우 검사가 최적화 될 있습니다 ( -Ofast 이상한 언어 때문에가 아니라 언어의 의미 때문에 (var를 변경하거나 액세스 할 수 없으므로) ~ 10k는 Int 유형에서 안전합니다.

그러나 컴파일러는 배열이나 배열 요소를 unbox 할 수 없을 수도 있습니다. 외부 함수 인 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")

추신 : 나는 Objective-C에 대한 전문가가 아니며 Cocoa , Objective-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의 분할 알고리즘을 살펴볼 수 있습니다. 스위프트에 쓴





compiler-optimization