Swift ベータ版のパフォーマンス: 配列のソート質問する

Question

tl;dr デフォルトのリリース最適化レベル [-O] を使用したこのベンチマークでは、Swift 1.0 は 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

ご覧のとおり、Swift のパフォーマンスは 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

そのため、このベンチマークでは、開発のこの段階では、最適化なしの Swift は C よりもほぼ 1000 倍遅くなりました。一方、両方のコンパイラを [-Ofast] に設定すると、Swift は実際には C と同等か、それよりわずかに優れたパフォーマンスを発揮しました。

[-Ofast] は言語のセマンティクスを変更し、潜在的に安全でなくなる可能性があると指摘されています。これは Apple が Xcode 5.0 のリリースノートで述べていることです。

LLVM で利用可能な新しい最適化レベル -Ofast では、積極的な最適化が可能になります。-Ofast は、主に浮動小数点演算に関する一部の保守的な制限を緩和しますが、これはほとんどのコードにとって安全です。これにより、コンパイラから大幅な高性能が得られます。

彼らはそれを推奨しています。それが賢明かどうかは私には分かりませんが、私が言えることは、高精度の浮動小数点演算を行わず、プログラムで整数または配列のオーバーフローが発生しないことを確信している場合は、リリースで [-Ofast] を使用するのが合理的であるように思われます。高性能とオーバーフローチェック/正確な演算が必要な場合は、今のところ別の言語を選択してください。

ベータ 3 アップデート:

n=10_000 [-O]の場合:

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

Answer 1