[解決済み] Swift Betaのパフォーマンス：配列のソート

質問

私はSwift Betaでアルゴリズムを実装していたのですが、パフォーマンスが非常に悪いことに気づきました。深く掘り下げた後、私はボトルネックの1つが配列の並べ替えのような単純なものであることに気づきました。関連する部分はここにあります。

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.06s を私のコンピュータで実行します。

Pythonでは、以下のようになります。 0.6s (トリックはなく、整数のリストに対して y = sorted(x) とするだけです)。

Swift では、次のようになります。 6s というコマンドでコンパイルすると。

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

と同じくらいかかります。 88s というコマンドでコンパイルすると。

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

Xcode で "Release" と "Debug" をビルドした場合のタイミングは似ています。

何が問題なのでしょうか？C++と比較して多少のパフォーマンス低下は理解できますが、純粋なPythonと比較して10倍も遅くなることはないでしょう。

---

編集する を変更することで、天候が変化することに気づきました。 -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])

だから -Ofast Swiftの要点は、セーフティネットがあることです。もちろん、セーフティネットはパフォーマンスに何らかの影響を与えますが、プログラムを100倍も遅くするべきではありません。Javaはすでに配列の境界をチェックしており、典型的なケースでは2倍よりもはるかに小さい速度低下であることを思い出してください。そして、ClangとGCCでは、わたしたちは -ftrapv 符号付き）整数のオーバーフローをチェックするためのもので、これもそれほど遅くありません。

そこで、「どうすれば、セーフティネットを失うことなく、Swiftで妥当なパフォーマンスを得ることができるのか？

---

2を編集します。 さらに、以下のような非常に単純なループでベンチマークを行いました。

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

(ここでxor演算があるのは、アセンブリコードの中で関連するループを見つけやすくするためです。整数オーバーフローに関連するチェックを必要としないという意味で、発見しやすくかつquot;無害な演算を選ぼうとしました)。

今回も -O3 と -Ofast . そこで、アセンブリコードを見てみた。

• と -Ofast ほぼ期待通りの結果が得られました。該当箇所は5つの機械語命令によるループです。

• と -O3 私の想像を超えたものが出てきました。内側のループは88行のアセンブリコードにまたがっている。そのすべてを理解しようとしたわけではありませんが、最も疑わしい部分は "callq _swift_retain" を13回呼び出し、さらに "callq _swift_release" を13回呼び出しているところです。ということです。 インナーループで26回のサブルーチン呼び出し !

---

3を編集します。 Ferruccio氏はコメントで、組み込み関数（例えばsort）に頼らないという意味で公平なベンチマークが欲しいという要望を述べています。以下のプログラムはかなり良い例だと思います。

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

演算を行わないので、整数のオーバーフローを心配する必要はありません。唯一やっていることは、たくさんの配列の参照だけです。その結果、Swift -O3は-Ofastと比較して500倍近くも損失を出しています。

• C++ -O3。 0.05 s
• C++ -O0: 0.4秒
• Java 0.2 s
• PyPyを使用したPython。0.5 s
• Python 12 s
• スイフト -Ofast: 0.05秒
• スウィフト -O3。 23 s
• スイフト -O0: 443秒

(もし、コンパイラが無意味なループを完全に最適化することを懸念するのであれば、例えば、次のように変更することができます。 x[i] ^= x[j] を出力するprintステートメントを追加してください。 x[0] . これは何も変わらないので、タイミングは非常に似ています)。

そうそう、ここでPythonの実装は、intのリストとネストされたforループを持つ愚かな純粋なPythonの実装でした。それは、次のようになるはずです。 大いに 最適化されていないSwiftより遅い。Swiftと配列のインデックス付けは、何かが深刻に壊れているようです。

---

4を編集します。 これらの問題（および他のいくつかのパフォーマンスの問題）は、Xcode 6 beta 5で修正されたようです。

ソートについては、現在、以下のようなタイミングになっています。

• clang++ -O3: 0.06秒
• swiftc -Ofast: 0.1秒
• swiftc -O: 0.1秒
• swiftc: 4 s

ネストされたループの場合。

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

もう、安全でないものを使う理由はないようです。 -Ofast (通称 -Ounchecked ); プレーン -O も同様に良いコードを生成します。

どのように解決するのですか？

tl;dr 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.

との時間（秒 (-Onone) に対して n=10_000 :

Swift:            0.895296452
C:                0.001223848

以下は、Swiftの組み込みのsort()で n=10_000 :

Swift_builtin:    0.77865783

以下は [-O] に対して n=10_000 :

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

比較のため、これは [-Onone］ に対して n=1_000_000 :

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] を使うことは十分に合理的だと思われます。もし、高いパフォーマンスが必要なら と オーバーフローチェックや正確な演算を行うには、今のところ他の言語を選択する必要があります。

BETA 3 UPDATE。

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