关于整数的思考 (2023)

# 关于整数的思考 · Luna 的博客 原文链接：https://blog.xoria.org/integers/ 在这篇文章中，我将阐述我对整数类型的看法，以及我是如何形成这些看法的。希望一开始你会不同意，但最终会被说服！ ## 现状 咱们先从当前主流编程语言中的现状说起。但首先，有几个说明：本文不会提及脚本语言，原因显而易见。此外，我暂时不把 Java 纳入本节，因为它在整数方面有些古怪（`int` 与 `Integer` 之分，且没有独立的无符号类型）。 我们先从经典的系统编程语言 C 开始。除了传统的 C 整数类型 `int`、`char`、`short`、`long`、`long long` 等，C99 增加了固定大小的类型，例如 `int8_t`、`uint64_t` 等等。在现代 64 位平台上，`int` 始终是有符号的，且宽度为 32 位。此外，C 还拥有一系列令人困惑的机器相关类型，比如 `ptrdiff_t` 和 `size_t`。通常，下标和大小都属于 `size_t` 类型，但由于 C 的隐式转换，你经常会看到 `int` 或其他类型被替代使用。当有符号整数溢出时，C 会触发**未定义行为**，这意味着编译器假设溢出永远不会发生。另一方面，无符号整数的溢出被定义为回绕。 接下来是 C#，我认为它是一种典型的“应用编程”语言，在不需要底层控制时使用。C# 的类型命名与 C 类似：`int`、`short`、`long` 和 `byte`。`int` 是 32 位宽。无符号版本通过在类型前加 `u` 前缀得到。下标和大小使用普通的 `int`，默认情况下整数在溢出时回绕。 Go 是与 C# 同领域的一种现代替代语言。这里我们可以看到一种趋势的开始：Go 没有使用不直观的 C 风格整数类型名，而是简单地给每个类型附加位宽：`int8`、`uint64` 等。另一个有趣的区别出现在 `int` 和 `uint` 的大小上：它们与目标平台上地址的大小相匹配，而不是硬编码为特定宽度。同样，大小和下标都使用 `int`。Go 定义整数溢出为回绕。 Swift 是另一种近期出现在“编译型、静态类型、非底层商业软件”领域中的语言，它的整数类型在多方面与 Go 相似。类型名除了大小写外与 Go 完全相同：`Int8`、`UInt64` 等。`Int` 和 `UInt` 的大小行为与 Go 相同，下标和大小都使用 `Int`。奇怪的是，Swift 在整数溢出时默认触发恐慌（panic），即使在发布构建中也是如此。 ## Rust：一种更好的方法 你注意到我上面列出的所有示例中的共同点了吗？所有这些语言都有某种默认的 `int` 类型。它们需要额外的输入才能使用无符号类型而不是有符号类型，以及使用显式指定大小的类型而不是默认大小的 `int`。我认为这鼓励了使用 `int` 而非其他类型。毕竟：你愿意盯着满屏的 `int` 还是 `uint32_t`？这不仅仅是美学问题。人们很容易偷懒，不假思索地输入 `int`，而不是仔细分析用例以确定最适合工作的类型。 Rust 消除了上述每一个问题：所有整数类型都有显式的大小，并且所有类型都带有前缀 `i` 或 `u`，分别表示有符号和无符号。没有对特定大小或符号性的偏见。你被迫考虑具体情况，并判断哪种类型最适合当前场景。也许当整数变窄时可以节省内存，并且可以通过使得无效值（负数）不可表示来防止错误——这是 Rust 社区经常引用的一个教条。 | 名称 | 有符号？ | 位宽 | |---------|----------|--------------| | `u8` | 否 | 8 | | `u16` | 否 | 16 | | `u32` | 否 | 32 | | `u64` | 否 | 64 | | `usize` | 否 | 地址大小 | | `i8` | 是 | 8 | | `i16` | 是 | 16 | | `i32` | 是 | 32 | | `i64` | 是 | 64 | | `isize` | 是 | 地址大小 | 你可能注意到这张表中出现了 `usize` 和 `isize`。`usize` 用于下标和大小，就像 C 中的 `size_t`。与 C 不同，Rust 没有隐式整数转换，所以你**必须**使用 `usize` 作为数组索引（除非你想淹没在 `as` 类型转换中）。使用 `usize` 而不是 32 位的 `int` 意味着数组可以拥有超过 20 亿个元素，而使用无符号类型意味着永远不会出现负数组索引。Rust 在调试构建中溢出时触发恐慌以捕获错误，但在发布构建中使用回绕以提升性能。注意溢出时没有未定义行为。 关于 Rust 不偏向某种整数类型的说法，有一个例外： ```rust fn demo() { let x = 1; // x: i32 } ``` 当 Rust 没有整数文字的类型信息时，默认使用 `i32`，因此存在（尽管轻微）对 32 位有符号整数的偏见。不过，根据我的 Rust 经验，我发现我很少使用有符号整数，以至于我几乎主张让无符号整数成为默认。如果 Rust 不让无符号和有符号整数处于平等地位，我可能永远不会得出这个结论。对我来说，所有这些改变都是显而易见的改进。 ## Rust 程序员尝试其他语言 当我开始试验 C#、Swift 和 Go 时，我很快就感到沮丧。抱着选择正确整数类型来完成任务的态度，我试图到处使用 `uint` 作为数组索引，而不是这些语言默认使用的有符号 `int`。但由于需要大量的类型转换，这种做法不实际，于是我沮丧地放弃了。这让我更加确信：为什么其他语言不能像 Rust 那样拥有整数类型呢？ ## 为什么 C 让有符号整数溢出成为 UB？ 最初的原因是硬件行为的差异，但今天你最常听到的性能论点。然而，大多数 CPU 在算术运算溢出时难道不都会执行回绕吗？为什么不直接定义溢出为回绕（无需额外成本，因为 CPU“免费”提供），然后就此结束呢？我看了一场 Chandler Carruth 关于 UB 的演讲（YouTube 链接），其中包含一个启发性的例子。（假设我们运行在拥有 64 位地址的架构上。¹） ```c bool mainGtU(int32_t i1, int32_t i2, uint8_t *block) { uint8_t c1, c2; c1 = block[i1]; c2 = block[i2]; if (c1 != c2) return c1 > c2; i1++; i2++; c1 = block[i1]; c2 = block[i2]; if (c1 != c2) return c1 > c2; i1++; i2++; // 重复多次 } ``` 编译器足够聪明，可以消除 `i1` 和 `i2` 的修改。字节直接从 `block + i1` 和 `block + i2` 加载，然后是 `block + i1 + 1` 和 `block + i2 + 1`，然后是 `block + i1 + 2` 和 `block + i2 + 2`，依此类推。这些地址计算作为加载指令本身的一部分完成，因此它们在 64 位整数的空间内发生。假设我们强制编译器在溢出时回绕。`i1++;` 和 `i2++;` 在达到 32 位整数极限时会回绕。为了确保运行时行为忠实于这种回绕，编译器会生成额外的指令，使 `block + i1 + n` 在 `i1 + n` 溢出 32 位时回绕到 `block + 0`。换句话说，“CPU 免费提供溢出回绕”在这种情况下并不成立，结果就是代码膨胀。这些都不是假设；将 `i1` 和 `i2` 改为无符号也会导致这些额外指令被生成。在他的演讲中，Chandler 用这段代码作为例子说明，从无符号切换到有符号整数如何提高性能，因为它让编译器可以利用溢出时的 UB。他甚至说： > 如果你有一个整数，你想将其算术地使用（而不是在某个模空间内，比如 2 的幂），就把它做成有符号的。如果你需要更多位，就去获取更多位。保持有符号。 这让我着迷。难道不应该使用类型系统来防止错误吗？如果一个数永远不可能为负，为什么还要把它做成有符号的呢？Chandler 对这个问题的看法让我感到不安。 ## 深入探索 C 当我沉浸在使用 C 进行系统编程时，我遇到了几个人，他们一直说应该使用有符号整数作为索引，即使它们不可能为负。特别是，我阅读了 Chris Wellons 博客上的三篇不同的文章，这些文章都支持这一观点： > 近年来，我确信无符号类型的大小是一个严重的错误，甚至可能是早期计算中的重大错误之一，大小和下标应该是有符号的。不仅如此，pkg-config 根本不应该处理巨大的对象！我们谈论的是短字符串和小文件。如果它最终处理大对象，那么某处存在缺陷——要么在自身，要么在系统——它应该中止。因此大小和下标自然应该是 `int`！ 看到引用的段落中的链接了吗？它链接到一份由 Bjarne Stroustrup 撰写的简短文档，他也说*大小和下标应该是有符号的*。抱着怀疑的态度和基于 Rust 的先入之见，我觉得他的论点不太有说服力。尽管如此，我心里隐隐有种感觉，所有这些人都一定有道理。 ## 看看一些 C 的替代语言 Odin 是众多新兴 C 替代语言之一，专注于简单和“编程的乐趣”。在尝试了另一种 C 替代语言 Zig 并经历了一些失败后，我决定更仔细地看看 Odin。熟悉的“现代语言”整数系统再次出现，但有一些针对底层编程的调整： - `int` 和 `uint` 是地址大小的 - `i8` 到 `i128` 是有符号的 - `u8` 到 `u128` 是无符号的 - 显式指定大小的类型可以用 `le` 或 `be` 后缀来指定其在内存中的表示是小端序还是大端序 - 大小和下标使用 `int` - 溢出时回绕 这一次，我决定保持开放心态，仔细看看这种设置可能带来的好处。下面的一些论点不是我的原创，但我记不清哪些是从哪里吸收的，哪些是我自己的。 ## 地址大小是完美的默认大小 正如我们之前看到的，如果我们不愿意让溢出成为 UB，那么混合指针和 32 位整数会导致性能问题。如果我们把 `i1` 和 `i2` 做成 `ptrdiff_t` 或类似类型，那么溢出时的回绕就会完美工作。此外，像 A64 这样的 ISA 只有 32 位和 64 位的算术指令，因此在 8 位和 16 位整数上进行操作需要额外的 `and` 指令。在地址大小的整数上执行所有算术通常是最佳选择。 对此的一个反驳是，现代 CPU 通常受内存带宽限制，因此将数据结构尽可能打包得小是一个好主意。将整数默认为地址大小而不是 32 位等，与此目标相悖。尽管如此，我认为能够为数组索引、大小、算术和作为默认整数类型使用简单的 `int` 所带来的简洁性，超过了必须记住在适当场合使用 `int32` 的成本。 ## 在发布构建中，溢出回绕是一个不错的权衡 如果所有被操作的整数都是地址大小的，那么让溢出成为未定义行为并没有好处。我宁愿在函数顶部有一些类型转换，而不是更多即将爆炸的 UB 定时炸弹。考虑到溢出检查大约有 30% 的开销，我认为将它们限制在调试构建中是一个合理的权衡。我也可以看到即使在调试构建中也使用溢出回绕以保持一致性和简洁性的论点。 ## 无符号整数不直观 假设你想从一个数字循环到零。使用有符号整数很简单： ```c void demo(int32_t top) { for (int32_t i = top; i >= 0; i--) { printf("%d\n", i); } } ``` 正如你所期望的，运行 `demo(3)` 会打印： ``` 3 2 1 0 ``` 不过，这里的 `i` 和 `top` 永远不会为负，所以无符号整数在这种情况下肯定更好？ ```c void demo(uint32_t top) { for (uint32_t i = top; i >= 0; i--) { printf("%u\n", i); } } ``` 这是一个无限循环。对于无符号整数 `n`，`n >= 0` 总是为真。由于无符号整数在溢出时回绕，当 `i` 达到零时我们递减它，得到 4,294,967,295。要修复这个问题，我们可以将条件改为 `i <= top`： ```c void demo(uint32_t top) { for (uint32_t i = top; i <= top; i--) { printf("%u\n", i); } } ``` 一旦 `i` 回绕，它将大于 `top`，从而跳出循环。简直糟糕透了。 ## 有符号整数会不会使边界检查变慢？ 使用有符号索引执行边界检查需要同时检查 `0 <= i` 和 `i < count`。这两个检查相互独立，因此现代 CPU 可以并行执行它们。CPU 的所有 ALU 很少同时饱和，因此移除第一个检查很可能不会改变边界检查的执行时间。 ## 无符号整数更容易出错 假设我们有两个数组索引，`i` 和 `j`。再假设在我们的用例中，溢出时触发恐慌的开销不可接受，因此我们采用溢出回绕。我们想要找出 `i` 和 `j` 之间的元素个数，并将它们复制到一个新数组中。很简单，对吧？只需要 `j - i` 就能确定元素个数，然后我们可以创建一个该大小的新数组并执行复制。想象一下，在你测试数据中，`j` 总是大于或等于 `i`，但生产环境中不知何故 `j` 小于 `i`。如果 `i` 和 `j` 是无符号的，`j - i` 会回绕到一个很可能非常大的数字。我们最终创建了一个非常大的数组；如果幸运的话，复制操作有边界检查并导致恐慌。关键是，很难捕捉无符号整数下溢：无法分辨一个很大的数字是由回绕错误造成的，还是故意如此。这里使用有符号整数意味着无效的 `j - i` 减法会立即产生一个“有毒的”（负的）结果。当这个结果被用于创建数组时，可以立即被捕获，而不是通过大数字带来的不可预测的连锁反应在后期才暴露。 ## 有符号整数是否需要更多断言？ 确实，要捕获那个负数组大小，我们的数组分配代码需要有一个 `assert(count > 0)`。然而，如果使用无符号整数，要捕获它就需要远不止一个 `assert`——我们需要为整个程序启用全面的溢出检查。你可以将使用有符号整数时需添加的断言视为一种轻量级的溢出检查形式。与其在*每一次*算术运算后都测试溢出，我们可以在每个函数顶部放置一个等效检查。换句话说，大量的溢出检查被合并到 API 边界的一个检查中。当然，一个 `assert(count > 0)` 并不等同于到处彻底检查溢出。例如，它不会捕获像 `create_array(1000 + j - i)` 这样的东西。性能和安全之间需要权衡，我认为采用有符号整数并结合大量断言以及溢出回绕，是一个令人愉快的中间地带。 ## 有符号整数的最大值更小，所以你需要使用更多位吗？ 我不同意这一点。既然我们在 64 位平台上，数组元素数量被限制在 63 位实际上无关紧要，而如果