A Long Journey of Changing std::sort Implementation at Scale

• 语言: 英语
• 格式: .pdf
• 来源: github.com/CppCon

摘要

本文探讨了改变标准库中排序算法std::sort实现的历程，分析了在大规模应用中遇到的问题，特别是与严格弱序相关的bug。作者详细介绍了新实现的改进措施，包括在调试模式下添加的检查机制，以提高排序算法的稳定性和安全性。文档还讨论了在实际应用中使用稳定排序的重要性，以及如何通过新标准（如C++20的std::weak_ordering）减少潜在错误。

AI总结

Danila Kutenin，作为一名高级软件工程师，分享了关于改变`std::sort`实现的历程。以下是文档的核心内容总结：

1. **演讲背景**
- 作者介绍了自己在Google的工作背景，并提到其主要关注点是与`std::sort`实现相关的效率和改进。

2. **演讲主题**
- 本次演讲围绕以下内容展开：
- 排序算法的历史
- 为什么需要改变`std::sort`的实现
- 遇到的Bug问题
- 新的实现方案
- 用户可以采取的行动

3. **标准库的演变**
- `std::sort`是C++标准库中的核心排序函数，定义在``头文件中。
- 其功能包括：
- 支持随机迭代器（RandomIt）
- 提供 constexpr 版本（C++20引入）
- 支持自定义比较函数（Compare）
- 支持执行策略（ExecutionPolicy，C++17引入）

4. **复杂度分析**
- `std::sort`的时间复杂度为$O(N \cdot \log(N))$，其中$N$是待排序元素的数量。

5. **严格弱排序问题**
- 演讲重点提到，比较基于排序算法的严格弱排序（strict weak ordering）是确保排序正确性的关键。
- 如果比较器不符合严格弱排序，可能导致排序结果不一致或安全漏洞。
- 作者提出在调试模式（`_LIBCPP_ENABLE_DEBUG_MODE`）中添加检查，以帮助开发者发现不符合严格弱排序的比较器。

6. **修改`std::sort`的背景**
- 作者团队曾尝试改进`std::sort`的实现，但由于某些断言失败的问题，该改进在16.0.1版本中被回滚。
- 新的实现虽然暴露了更多问题，但为后续改进提供了重要经验。

7. **确定性问题**
- 修改后的排序算法可能导致相同输入的排序结果不同，从而影响程序的确定性行为（如缓存命中率）。
- 为解决此问题，建议使用`std::stable_sort`来确保相同输入的排序结果一致。

8. **用户注意事项**
- 用户应确保自定义比较器符合严格弱排序要求。
- 通过调试模式中的断言检查，可以提前发现并修复不符合条件的比较器。

9. **C++20的改进**
- C++20引入了`std::weak_ordering`，允许开发者更灵活地定义排序关系，从而减少因比较器问题引发的Bug。

总结：
本次演讲强调了`std::sort`实现改进的重要性和挑战性。通过修复严格弱排序问题、添加调试检查，并结合新标准（如C++20的`std::weak_ordering`），可以显著提升排序算法的可靠性和安全性。用户在使用排序算法时，也应特别注意比较器的正确性，以避免潜在的Bug和安全风险。