在 .NET 中手動實現高性能算法
作為學習經驗，我最近嘗試在 C# 中使用 3 路分區實現快速排序。
除了需要在遞歸呼叫之前對左/右變數添加額外的範圍檢查之外，它似乎工作得很好。
我事先知道該框架在 List<>.Sort（通過 Array.Sort）中提供了一個內置的快速排序實現。所以我嘗試了一些基本的分析來比較性能。結果：內置的 List<>.Sort 方法，在相同的列表上執行，比我自己手動實現的速度快大約 10 倍。
使用反射器，我發現 List<>.Sort 中的實際排序是在外部程式碼中實現的，而不是 IL（在名為 tryszsort() 的函式中）。
看看我自己的 Quicksort 實現，我希望用迭代替換遞歸呼叫可能會帶來一些改進。此外，禁用數組邊界檢查（如果可能）也可以帶來一些好處。也許這會更接近內置實現，但我不自信。
所以我的問題是：期望優化算法（用 .NET IL 編寫，編譯為本機程式碼）的性能可以與外部實現的算法的性能競爭是否現實？
再一次，我意識到 Quicksort 是作為框架的一部分提供的，這對我來說只是一次學習經歷。然而，還有許多算法（想到 CRC32）沒有提供，但對許多應用程序仍然具有很大的價值。這是關於在 .NET 中實現 CRC32和性能問題的相關問題。
因此，如果您需要在 .NET 中實現這樣的算法，需要了解哪些主要的性能注意事項，以便您的算法至少可以接近外部程式碼的性能？
$$ Update $$ 通過更改算法以對簡單的 Int 數組而不是 List 進行操作，我將執行速度提高到內置 Array.Sort 的 10% 以內。在 Reflector 中，我可以看到這避免了對列表中的每個 get 或 set 執行 Callvirt() 操作。我認為這可能會改善事情，但我對多少感到驚訝。
通過使用非遞歸程式碼，特別是通過使用“不安全”塊和指針算法（如果適用），您實際上可以看到使用 C# 編寫的算法獲得 x5 或 x10 的性能提升。與性能一樣（在處理託管環境時更是如此），除非您嘗試它並對其進行基準測試，否則您永遠不會完全知道。
現在，一般來說，您應該主要用 C# 編寫東西，然後對其進行優化，再優化一些，如果仍然不夠好，請確定確切的關鍵程式碼段並將其移植到 C++（同時注意限制數量託管/本地呼叫邊界）。