Reddit 观察｜以排序为案例，对 C/CPP/Rust 安全与性能的相关性研究

张汉东

发布于 2023-10-06 12:42:36

3070

发布于 2023-10-06 12:42:36

“原文在此：https://github.com/Voultapher/sort-research-rs/blob/main/writeup/sort_safety/text.md#safety-vs-performance-a-case-study-of-c-c-and-rust-sort-implementations，本文不是翻译，而是对原文的摘要与进一步扩展，让该内容更容易更系统地让人理解，属于二次创作。

先上简单结论：

在用户定义的比较函数中，复杂的通用实现与追求性能的组合，使得通用高性能排序实现在避免每种使用场景下的未定义行为（UB）方面特别困难。即使只使用内存安全的抽象来实现排序，也不能保证相邻逻辑是无未定义行为的。

总体而言，性能和安全之间没有明显的相关性，无论是使用安全还是不安全的内部抽象。然而，实现给 C 或 C++ 用户使用的排序算法与缺乏安全性之间存在明显的相关性。

主题

从 20 世纪 50 年代初开始就有排序操作了，它需要使用一个实现严格弱排序（strict weak ordering）的比较函数（comparison function）来交换元素，直到排序完成。

“对排序算法中的比较函数有以下几点说明:

比较函数必须实现严格弱排序(strict weak ordering),这意味着函数需要满足自反性、反对称性和传递性。
严格弱排序要求,对于任意两个元素 x 和 y,如果 x < y 为真,则 y < x 必须为假,反之亦然。也就是说,不能同时存在 x < y 和 y < x。
使用严格弱排序的比较函数,可以确保排序算法能正确交换元素的顺序,最终达到排序的效果。
不是所有的排序算法都必须使用严格弱排序的比较函数,一些排序算法可以使用部分排序(partial ordering)的比较函数,这时不需要满足严格的自反性、反对称性等。
但大多数经典排序算法(如快速排序、归并排序等)都是基于严格弱排序设计的,使用这种比较函数可以保证算法的正确性和可靠性。
总体来说,为了使排序算法更通用和可靠,使用严格弱排序的比较函数是一个良好的选择。但也不是绝对必要的,可以根据实际需求选择合适的比较函数。

过去的这 70 年，只不过是持续不断发现实现这一比较操作的新方法，而且更加高效。这是科学研究的一个活跃领域，包括BlockQuicksort 2016、ips4o 2017、pdqsort 2021、Multiway Powersort 2022等等。科学界正在探索各种方向。在现代超标量、乱序和推测性CPU上运行单线程的高效排序实现；在多个线程上运行的高效实现；在大规模并行顺序GPU上运行的实现；探索更好的最佳情况、平均情况和最坏情况运行时间；利用输入数据中的现有模式；探索不同特性，如稳定/不稳定、原地/分配等等。

原文关注的是一个很少被讨论的情况：实现如何处理一个用户定义的比较函数，该函数实现任意逻辑，可能不实现严格的弱序关系，可能在比较过程中不返回值并且可以修改被比较的值。

Cpp 实现

如果用户定义的类型或比较函数没有实现严格的弱序关系，会发生什么情况？

C++标准库的排序接口使得触发这种情况非常容易：

sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
    return a <= b; // 正确的写法应该是：a < b.
});

这段代码中的问题在于比较函数使用了 <= 运算符,而并非严格小于 < 运算符。

在排序算法中，比较函数需要实现严格弱排序，也就是说需要满足:

自反性：a <= a 应该为真
反对称性：如果 a <= b 为真，则 b <= a 应该为假
传递性：如果 a <= b 并且 b <= c 为真,则 a <= c 也应该为真

但是使用 <= 运算符并不能满足反对称性,因为存在 a <= b 和 b <= a同时为真的情况。这违反了反对称性的要求。

所以比较函数中必须使用严格小于 < 运算符,才能满足严格弱排序的要求。

Rust 实现

Rust标准库的排序接口在许多情况下避免了这个问题，它要求用户定义的比较函数返回 Ordering 类型而不是bool。

在 Rust 标准库中提供了Eq/PartialEq/Ord/PartialOrd 这四个 trait 来保证排序的正确性。

Ord trait 在 Rust 中实现的是全序(total order)，而 PartialOrd 实现的是偏序(partial order)。

Ord 要求实现严格弱排序，即上文提到的满足自反性、反对称性和传递性。这样就构成了一个全序关系，可以对任意两个元素进行排序比较。
PartialOrd 只要求实现部分排序,不强制满足反对称性。所以两个元素之间可以既不相等，也不可排序,构成一个偏序关系。

在 Rust 中实现 Ord trait 需要满足严格弱排序的要求，具体来说:

对于任意的 x ，需要实现 partialOrd 下的x.partial_cmp(&x) == Some(Ordering::Equal)来满足自反性。
对于任意的 x 和 y,需要实现 partialOrd 下的以下要求来满足反对称性:
- 如果x.partial_cmp(&y) == Some(Ordering::Less)则必须有y.partial_cmp(&x) != Some(Ordering::Less)
- 如果x.partial_cmp(&y) == Some(Ordering::Greater)则必须有y.partial_cmp(&x) != Some(Ordering::Greater)
对于任意的 x、y 和 z,需要实现传递性:
- 如果x.partial_cmp(&y) == Some(Ordering::Less) && y.partial_cmp(&z) == Some(Ordering::Less)则必须有x.partial_cmp(&z) == Some(Ordering::Less)
- 如果x.partial_cmp(&y) == Some(Ordering::Greater) && y.partial_cmp(&z) == Some(Ordering::Greater)则必须有x.partial_cmp(&z) == Some(Ordering::Greater)

通过这些要求，Rust 保证了 Ord trait 下的类型必须满足严格弱排序,这样基于这种排序的算法(如排序函数)可以正常工作。

另外，Eq/PartialEq/Ord/PartialOrd 之间的关系如下:

Eq 要求实现相等性判断。
PartialEq 继承了 Eq，加上了不等的判断。
Ord 继承了 PartialEq,加上了严格弱排序的比较函数。
PartialOrd 继承了 PartialEq,加上了部分排序的比较函数。

所以完整的关系是: Eq ⊆ PartialEq ⊆ PartialOrd ⊆ Ord

PartialEq 提供相等性判断
PartialOrd 在此基础上提供部分排序
Ord 提供完整的排序功能

所以，Ord 是全序，PartialOrd 是偏序，两者都建立在 PartialEq 的相等性判断之上，最终构成了 Eq/PartialEq/PartialOrd/Ord 之间的包含关系。这套 trait 系统为 Rust 提供了完善的排序与比较功能。

然而，Rust 代码也能写出问题：

data.sort_by(|a, b| {
    if a == b {
        return Ordering::Less; // bug
    }

    a.cmp(b)
});

这段Rust代码中的排序比较函数有问题,不符合严格弱排序的要求。主要问题在于当 a == b 时，直接返回 Ordering::Less。

根据严格弱排序的要求：如果 a == b，比较函数应该返回 Equal。这里返回 Less 违反了自反性。

更正的代码应该是:

data.sort_by(|a, b| {
  if a == b {
    return Ordering::Equal;
  }
  a.cmp(b)
});

当 a == b 时,返回 Equal。其他情况下,调用 a.cmp(b) 进行默认排序比较。

这满足了严格弱排序的要求:

自反性：a == a 时返回 Equal
反对称性：不会同时存在 a < b && b < a
传递性：排序结果遵循传递性

不遵循严格弱排序会产生什么问题

假设用户想要对这些整数进行排序：[6, 3, 3, 2, 9, 1]。错误地提供了一个比较函数，该函数没有实现所需的严格弱排序。

可能的结果是什么？这里有一些选项。

A: [2, 3, 9, 3, 1, 6] 
B: [3, 2, 1, 3, 9, 6] + exception/panic
C: [1, 3, 3, 9, 9, 6]
D: [3, 3, 0, 0, 7, 9]
E: Runs forever
F: UB

A选项代表排序结果错误。比如说输入 [6, 3, 3, 2, 9, 1],结果可能是 [2, 3, 9, 3, 1, 6] 这样明显错误的顺序。
B 选项代表排序过程抛出异常（Cpp 中）或者 Panic（Rust 中）。算法可能会在比较或交换元素时检测到不一致，并主动抛出错误。
C 选项结果含有重复元素。意味着比较过程复制了一些元素并"丢失"了一些元素。严格弱排序会确保相等元素的相对顺序保持不变，否则相等元素位置可能会混乱。
D 选项结果含有明显不可能的值。如果比较函数逻辑错误，可能会产生一些随机数字。
E 选项排序永远运行不停，算法无法终止。
F 选项产生未定义行为(UB)。由于违反排序算法的前提，编译器优化可能会造成意想不到的后果。比如导致CPU MMU异常的越界读取、非法CPU指令、堆栈溢出、改变无关程序状态等等。

可能你会有疑问，排序只不过是这些数字的比较和位置交换，怎么可能会产生 UB 呢？

对于 C 选项来说，通常情况下，复制通常发生在位级别，忽略类型语义。如果元素类型是例如 unique_ptr<int32_t> / Box<i32> ，这些类型假设对分配具有唯一所有权。它们的析构函数将传递一个指向分配器的指针以进行释放。位拷贝会导致使用后释放的未定义行为，很可能以双重释放的形式出现。与 C 选项相同，D 选项但还增加了由于将未初始化的内存解释为类型的有效占用而导致的任意 UB。对于 E 选项情况来说，或许会 UB，LLVM 将这种没有副作用的无限循环定义为 UB，C++ 也是如此。

Panic Safety

C++ 和 Rust 都是具有基于作用域的析构函数（RAII）和栈展开（Unwind）的语言。它们共同为手动内存管理提供了强大的抽象。与此同时，它们也可能使得实现通用代码更加复杂。

在排序实现中，每个调用用户提供的比较函数的地方都必须假设该调用可能通过异常返回（C++中）:

sort(data.begin(), data.end(), [](const auto& a, const auto& b) {
    if (some_condition(a, b)) {
        throw std::runtime_error{"unwind"};
    }

    return a < b;
});

或通过 Panic 返回（Rust中）:

data.sort_by(|a, b| {
    if some_condition(a, b) {
        panic!("unwind");
    }

    a.cmp(b)
});

这里就需要考虑 Panic Safety （Cpp 中叫异常安全），否则就会造成 UB。

你可以尝试来通过回答下面这道多选题来检测一下自己是否理解 Panic Safety :

下面关于 Panic Safety 和 Unwind Safety 的描述正确的有：

A) Panic Safety  通常指的是在发生 Panic 时，代码依然可以保持内存安全性和逻辑一致性。Panic safety 主要关心的是在面对 panic 时，代码仍然能保持其内存安全的特性，这意味着即使出现了 panic，也不会导致未定义的行为。
B)  Unwind safety 关注的是在一个 panic 的栈展开（unwinding）过程中，对象的状态是否保持正确。
C) 在栈展开过程中，不会发生不可预知的副作用或状态不一致的类型，可以自动实现 UnwindSafe trait。
D) panic safety 保证内存安全性，而 unwind safety 则更关心逻辑状态的一致性和正确性。
E) 使用 `catch_unwind` 捕获 panic 可能会意外地保存一个处于不正确状态的对象，除非该对象是自动实现 UnwindSafe trait。
F) 使用 `AssertUnwindSafe` 手工包装的类型完全可以保证 Unwind Safety 。

正确答案（ABCDE）

Observation Safety

C++ 和 Rust 都提供了通过 const/shared引用来改变值的方法。C语言没有任何机制可以通过const/shared指针进行安全修改，因此被测试的基于C的排序实现理所当然地无法满足这个要求。

在 Rust 中，这被称为内部可变性。C++ 通过 mutable 类型说明符来实现这一点，而 Rust 在语言内置的 UnsafeCell 上构建了安全可用的抽象。

由于这个原因，可以将每次对用户提供的比较函数的调用视为栈值的修改。一旦使用辅助内存（auxiliary memory，HDD/SSD之类），无论是栈还是堆，都会执行不安全的位复制操作。

“外部排序算法中,会在主存和磁盘之间进行数据交换，这些操作在涉及主存和二级存储器之间的数据拷贝时，会进行位复制,存在一定的不安全性。

如果将这样一个复制的元素用作用户提供的比较函数的输入，它可能会以一种必须在排序完成时观察到的方式被修改，无论是通过正常返回还是通过引发异常/Panic。

一个具有意想不到后果的良性场景是通过在每次对用户提供的比较函数的调用中增加一个计数器来计算执行的比较次数。如果不满足可观察比较的属性，结果可能在描述用户提供的比较函数被调用的次数时非常不准确。一个更为棘手的情况是，用户定义的类型持有一个指针，该指针在用户提供的比较函数中有条件地被释放并设置为null。如果在排序完成后没有观察到这种修改，依赖于空指针检查来判断是否已经释放的代码将遇到使用已释放内存的未定义行为。

C++ 代码：

struct ValWithPtr {
    int32_t val;
    mutable uint8_t* buffer;
    size_t buffer_len;

    ~ValWithPtr() {
        if (buffer) {
            free(buffer);
        }
    }
};

std::sort(data, data + len,  [&some_condition](const auto& a, const auto& b) {
    if (some_condition(a, b)) {
        free(a.buffer);
        a.buffer = nullptr;
        free(b.buffer);
        b.buffer = nullptr;
    }

    return a.val < b.val;    
});

Rust 代码：

pub struct ValWithPtr {
    val: i32,
    buffer: Cell<Option<Box<[u8]>>>,
}

data.sort_by(|a, b| {
    if some_condition(a, b) {
        a.buffer.set(None);
        b.buffer.set(None);
    }

    a.val.cmp(&b.val)
});

基准测试结果分析

可以在 https://github.com/Voultapher/sort-research-rs 查看测试代码以及测试结果。

表头属性说明：

Functional，实现是否成功通过了不同输入模式和支持的类型的测试套件？
Generic，实现是否支持任意用户定义的类型？
Ord safety，如果用户定义的类型或比较函数没有实现严格的弱序关系，会发生什么情况？
Exception safety，如果用户提供的比较函数抛出异常/Panic，会发生什么情况？✅表示它以未指定的顺序保留原始输入集，🚫表示它可能在输入中有重复的元素。
Observable comp，如果类型具有内部可变性，在调用用户定义的比较函数时使用 const/shared 引用引起的每个修改是否在排序函数返回1后对输入可见; 通常为2：Panic。
Miri，如果在Miri下运行测试套件，是否通过？S：使用堆栈借用别名模型。T：使用树借用别名模型。

稳定排序测试结果：

不稳定排序测试结果：

原文作者的结论和观点

正如基准测试所显示的那样，当前的 Rust 标准库不稳定排序实现优于C++标准库的对应实现。

尽管如此，Rust 提供的实现在使用上更加安全。glidesort 和 ipnsort 证明了即使在最先进的高性能实现中，这些特性仍然可以得到保持。

C++标准库中的排序实现通常相当古老，这可以解释它们的性能较差。然而，即使是相对较新的 C++ 实现（如ips4o），也完全忽视了使用安全性，甚至在观察安全性方面与测试的标准库实现相比出现了退步。

新的、迄今为止未经测试的 libc++ 实现在某些分析过的安全特性上表现出了一定的意识，主要是 Ord 安全性，但未能找到一种保证无未定义行为（UB）的使用方式。它只能执行可选的越界检查。忽视了重复元素和异常安全性的问题。这有点令人惊讶，因为它的发布日期是2022年，而 Rust 中基于 pdqsort 的不稳定排序在 2017 年合并。

我不明白为什么不能直接从 Rust 转换到 C++，同时满足他们的要求。作者Danila Kutenin在他们的博客文章中甚至提到了 Rust 的实现，所以我认为他们是知道的。

对我来说，所有测试实现的结果表明了 C 和 C++ 世界中普遍存在的一种思维方式，即认为用户有责任小心谨慎，即使这在规模上已被证明是不可能的。就我个人而言，我在工作中花了几天时间调试一些以非常奇怪的方式出错的代码，原因是在比较函数中意外地写成了 <= 而不是 < ，影响了完全不同的地方的逻辑。

安全性和性能经常被描述为一组零和权衡，然而往往可以找到更好的权衡，其整体特性改进了以前看到的“要么这样要么那样”的情况。考虑到基础库作者与库用户之间的一对多关系，安全可用的抽象的影响应该变得明显起来。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-10-06 09:00，如有侵权请联系 cloudcommunity@tencent.com 删除

安全

rust

排序

性能

本文分享自觉学社微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度