並行排序算法效能優化實戰：四維向量排序從 534ms 降至 16ms 的極致之路

問題背景

對 32,768（2^15）個四維向量按模長（歐幾里得範數）排序，初始演算法 A 耗時 534ms，如何大幅提升效能？

演算法演進

版本 A：直接排序，比較器內重複計算模長

class VectorComparer : IComparer<Vector> {
    public int Compare(Vector c1, Vector c2) {
        double x = Math.Sqrt(c1.X*c1.X + c1.Y*c1.Y + c1.Z*c1.Z + c1.W*c1.W);
        double y = Math.Sqrt(c2.X*c2.X + c2.Y*c2.Y + c2.Z*c2.Z + c2.W*c2.W);
        return x.CompareTo(y);
    }
}
Array.Sort(vectors, new VectorComparer());
// 耗時：534ms

問題：比較器被呼叫 O(N log N) 次，每次重複計算平方根與冪次，極度浪費 CPU。

版本 B：預計算模長存入欄位，排序時直接比較

for (int i = 0; i < n; i++) {
    vectors[i].T = Math.Sqrt(vectors[i].X*vectors[i].X + ...);  // 預計算
}
Array.Sort(vectors, new VectorComparer2());  // 比較 T 欄位
// 耗時：16ms（快 33 倍！）

關鍵優化：

• 將 O(N log N) 次重複計算降為 O(N)
• 避免 Math.Pow 呼叫開銷，改用直接乘法
• 比較器簡化為單一 double 比較

版本 C：微優化乘法替換 Pow

vectors[i].T = Math.Sqrt(vectors[i].X * vectors[i].X + ...);  // 乘法比 Pow 快
// 耗時：12ms（再提升 ~25%）

效能對比總結

並行化嘗試

使用 PLINQ 平行排序：

vectors.AsParallel().OrderBy(v => v.T).ToArray();
// 或
Array.Sort(vectors, (a,b) => a.T.CompareTo(b.T));  // 單執行緒已極快，並行開銷反而較大

對於已優化至 12ms 的情況，並行化因任務分割、合併開銷反而變慢。並行適合「單元運算昂貴」且「資料量極大」場景。

進一步優化方向

1. 結構體替換類別：struct Vector 避免堆積分配與 GC 壓力
2. SIMD 向量化：System.Numerics.Vector<T> 批次計算 4/8 個元素
3. 避免平方根：比較平方和即可保持順序，省去 Sqrt
4. 基數排序：若分布已知，O(N) 非比較排序更快
5. GPU 運算：CUDA/OpenCL 大規模平行處理

核心心法

演算法複雜度優於並行化；資料局部性與記憶體存取模式決定實際效能。

• 先消除冗餘計算（預計算、查表）
• 再優化單元運算（乘法 vs Pow、避免 Sqrt）
• 再考慮資料結構（struct、陣列 vs List）
• 最後才評估並行化收益

完整測試程式碼

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace Vector4Test {
    public class Vector {
        public double W, X, Y, Z, T;
    }
    class VectorComparer : IComparer<Vector> { ... }  // 版本 A
    class VectorComparer2 : IComparer<Vector> { ... } // 版本 B/C

    class Program {
        static void Main() {
            var vectors = GetVectors();
            Benchmark("A", vectors, v => Array.Sort(v, new VectorComparer()));
            vectors = GetVectors();
            Benchmark("B", vectors, v => { Precompute(v); Array.Sort(v, new VectorComparer2()); });
            vectors = GetVectors();
            Benchmark("C", vectors, v => { PrecomputeFast(v); Array.Sort(v, new VectorComparer2()); });
        }
        static Vector[] GetVectors() { ... }
        static void Precompute(Vector[] v) { ... }
        static void PrecomputeFast(Vector[] v) { ... }
        static void Benchmark(string name, Vector[] v, Action<Vector[]> act) { ... }
    }
}

結語

從 534ms 到 12ms，並非靠並行硬體，而是演算法重構。這是效能優化的鐵律：先做對（正確性），再做快（複雜度），最後才做並行。