Rust 中不可变字符串的优化
对克隆和堆分配的厌恶
Rust、Go 和 C++ 程序员都特别厌恶堆内存分配和数据克隆。他们尽可能地将变量分配到本地（栈上），以避免占用额外的动态内存。换句话说，我们常常竭尽全力确保只在绝对必要时才进行内存分配。
事实上，C++ 利用编译时语言特性进一步优化，允许预先求值并内联指令。这使得程序在运行时不再需要执行某些指令。一个显著的例子是小字符串优化，它通过内联“小字符串”来完全避免动态内存分配。
同样，克隆数据通常是最后的选择。考虑一张可以用任意字节数组表示的图像。如果要克隆这张图像，开销肯定会很大。这促使我们更倾向于使用引用语义而不是值语义。也就是说，如果所有权无法转移，我们通常会通过引用而不是值来传递对象。事实上，复制指针/引用肯定比复制整个字节数组要便宜得多。
因此，Rustaceans 最不愿看到的功能之一就是：
// Suppose we have an image...
let image: Vec<u8> = get_image_bytes_from_somewhere();
// Every Rustacean's kryptonite...
let cloned = image.clone();
仅仅一行代码就足以让人不寒而栗。虽然有些情况下克隆确实是必要的，但它仍然是一件令人不快的景象。
本文将探讨在不可变上下文中优化数据分配和克隆方式的几种方法。本文将以String类型为例进行说明，但请记住，这些概念也普遍适用于其他情况。
多线程环境下的示例
假设我们需要在运行时配置中跨多个线程共享一个不可变字符串。例如，这可能是文件名、用户名或参数标志。
痛苦地实现此目的的简单方法是为每个线程克隆字符串。
use std::thread::{self, JoinHandle};
// Runtime configuration from somewhere...
let username: String = get_username();
// Spawn ten threads
let handles: Vec<_> = (0..10)
.map(|id| {
// NOTE: `username` is captured by reference here.
// That is, `String::clone(&username)`. Observe that
// obtaining a reference is sufficient for cloning
// the **entire** string.
let cloned = username.clone();
// Here, we move the owned clone of the `username`.
thread::spawn(move || {
println!("Hello {} from Thread #{}!", cloned, id);
})
})
.collect();
// Join all the threads
handles.into_iter()
.try_for_each(JoinHandle::join)
.expect("failed to join all threads");
不过，我们肯定可以做得更好。与其克隆 `<object>`String及其内容，为什么不直接使用 `<object>`std::sync::Arc呢？这样，我们只需克隆指向 `<object>` 的智能指针，String而无需克隆其内容本身。事实上， 《Rust Book》的“无畏并发”章节String中就给出了类似的解决方案。
use std::{
sync::Arc,
thread::{self, JoinHandle},
};
// Observe that we now wrap the string in an `Arc`.
let username: Arc<String> = Arc::new(get_username());
// Spawn ten threads again
let handles: Vec<_> = (0..10)
.map(|id| {
// Here, we are explicitly cloning the smart pointer,
// not the `String` itself. Note that it is possible to
// write `username.clone()` instead, but that may be ambiguous
// to readers of this code. It is best to explicitly
// invoke the `Clone` implementation for `Arc`.
let cloned = Arc::clone(&username);
// We now move the cloned smart pointer to the thread.
thread::spawn(move || {
println!("Hello {} from Thread #{}!", cloned, id);
})
})
.collect();
// Join all the threads again
handles.into_iter()
.try_for_each(JoinHandle::join)
.expect("failed to join all threads");
一些不易察觉的低效率
这个改进确实好多了，但似乎有些奇怪Arc<String>。由于`a`Arc是一个智能指针，我们知道它实现了 `int` 接口std::ops::Deref。在这种情况下，`a`Deref::Target是`int` 类型String。但是，我们知道 `a`String也实现了 `int` 接口Deref，其中`int`Deref::Target是原始类型str。因此，为了使用底层的`int`str类型，我们需要经过两层Deref间接寻址！
但需要注意的是，编译器可能会优化双重间接寻址，但内存使用情况却未必如此。请记住，所有用于存储Sized目标的指针类型都与一个指针类型大小相同usize。在 64 位目标系统中，这相当于 8 个字节。
免责声明：从现在开始，我在计算指针大小时将假设目标系统为 64 位。
由于String是一个Sized类型，Arc<String>所以 实际上只是指针的大小。事实上，至少就大小而言，Arc智能指针是对普通指针的“零成本抽象”。但是，我们不要忘记Arc实际上是指向某个堆分配的指针。在这种情况下，它指向一个String。
截至撰写本文时（Rust 1.54），我们知道`a`String本质上是一个 `<T>`Vec<u8>，其中字节恰好是有效的 UTF-8 编码。此外，`a`由两个字段Vec<u8>组成：一个内部字段和一个存储数据的指针。`a`只是对内部字段和指向底层数据缓冲区的指针的一个内部包装。RawVeclengthRawVeccapacity
因此，aString实际上代表三个指针：一个整数length（usize），一个整数capacity（usize），以及一个数据指针（usize）。总共占用 24 字节！
综上所述，`a`Arc<String>是一个 8 字节的智能指针，指向一个 24 字节的堆分配内存String（某些内存capacity）——加上 8 字节的强计数（AtomicUsize）和另外 8 字节的弱计数（AtomicUsize）——它解引用一个堆分配内存str（某些内存length <= capacity）。
换句话说，一个实例Arc<String>实际上占用 8 字节（栈上）加上 40 字节（堆上），再加上底层str分配的字节（堆的另一部分）。如果我们忽略感叹号，总共capacity至少需要48 字节。str
// The total memory used is at least `8 + 24 + 16 + 11 = 59` bytes!
// Note that I have disregarded alignment to keep the example simple.
use std::sync::Arc;
let text = Arc::new(String::from("Hello World"));
// Here, we dereference the variable to verify how much
// memory is used by each level of indirection.
use std::mem::size_of_val;
dbg!(size_of_val::<Arc<String>>(&text)); // 8
dbg!(size_of_val::<String>(&text)); // 24
dbg!(size_of_val::<str>(&text)); // 11
利用不变性
呼！信息量有点大，但我希望我已经证明了Vec对于不可变字符串来说，双重间接寻址和由此带来的开销相当可观。那么……我们该如何解决这个问题呢？
首先，我们必须解决双重间接寻址的问题。正如前面所展示的，指向指针的指针str并不是处理我们用例的最有效方法。
第一个关键洞见源于我们假设对象str必须是不可变的。也就是说，我们实际上并不需要提供的变更方法String。如果我们能够以某种方式与str对象的底层进行交互String，就可以完全消除双重间接寻址。幸运的是，它恰好Arc允许我们做到这一点！回想一下，它Arc<str>实现了From<String>。3这种转换足以满足我们的用例。
use std::sync::Arc;
// Retrieve the string from somwhere...
let text: String = get_string_from_somwhere();
// Here, we "consume" the `String` wrapper
// as a smart pointer to a `str`. Alternatively,
// we may invoke the `Arc::from` syntax.
let owned_reference: Arc<_> = text.into();
todo!("spawn threads here");
差不多就是这样了！现在，当我们在多个线程中克隆智能指针时，我们实际上只是克隆了指向底层对象的直接指针str——不再有双重间接寻址了！
分析内存使用情况，我们发现它Arc<str>占用了 16 个字节。但是等等……它不是Arc<String>只占用了 8 个字节吗？没错！这是因为 ` Stringint`是 `int` 类型的指针。Sized如前所述，所有指向Sized`int` 类型的指针都占用 8 个字节（一个指针）。
同时，请记住，指向动态大小类型（例如 `A` str）的指针实际上是一个宽指针。也就是说，它们包含的信息远比普通指针多得多。在这种情况下，`A` &str、Box<str>`B`、Rc<str>`C`、Arc<str>`D` 或任何其他指向 `A` 的类似指针的包装器都占用 16 个字节，因为它们内部包含指向分配地址（`A` ）及其长度（` L`）str的直接指针。strusizeusize
是的，这意味着后续复制的宽指针的大小是普通指针的两倍，但这确实使我们能够绕过双重间接寻址的问题。因此，我们只需要宽指针即可进行引用str——无需额外的堆分配！另一个巧妙的副作用是，多余的容量也被释放出来，从而提高了内存利用率。
总而言之，Arc<str>栈上只占用 16 字节。而堆上，除了底层分配的字节之外，强计数（ AtomicUsize）占用 8 字节，弱计数（）占用 8 字节。这使得总大小达到 32字节以上。相比之下，（单独占用 48 字节）加上（）以及额外的（如果有的话），这些节省相当可观！AtomicUsizelengthstrlengthArc<String>lengthstr capacity
注意：需要强调的是，
Arc由于原子性，这需要一些额外的开销。特别是，如果没有强计数和弱计数，两种情况下都可以节省 16 字节。也就是说，如果我们使用 `a`Box代替 `b`，无论它是 `a`Arc<str>还是 `b` ，我们都会得到相同的结果，但会少 16 字节Arc<String>。
因此，如果不需要可变性，那么使用拥有的str引用或许是一种值得的优化。这同样适用于[u8]`int`、Path`int`、CStr`int` 和其他类似切片的类型。
哈希映射的应用示例
换个角度，我们来看另一个例子：我们维护一个包含用户名和代币（用整数表示）的表格。该表格本质上是一个映射表，它将一个不可变的用户名与其钱包中的代币数量关联起来。
一个简单的实现方法是利用 `[] std::collections::HashMap`。直觉上，我们首先会想到使用 `[]`HashMap<String, u16>作为初始类型签名。但是，由于用户名是不可变的，因此可以String完全移除抽象。代码如下：
use std::iter::repeat_with;
fn generate_username() -> (String, u16) {
todo!("generate string-coins pairs somehow")
}
// This results in a `HashMap<Box<str>, u16>`.
// Observe the the key-type is a `Box<str>` instead
// of the typical `String` wrapper.
let table: HashMap<_, _> = repeat_with(generate_username)
.map(|(name, coins)| (name.into_boxed_str(), coins))
.collect();
事实上，Rust 编译器曾经利用这种优化来高效地跟踪代码中的不可变符号表。以下代码片段展示了这一优化的应用：
pub struct Interner {
names: HashMap<Box<str>, Symbol>,
strings: Vec<Box<str>>,
}
结论
不可变性真是太棒了！它使我们能够对编写的代码进行许多有价值的优化和假设。首先，正是由于不可变性，才使得String上述示例中的包装器能够被“溶解”。实际上，String包装器存在的唯一目的就是为“可调整大小”的字符串提供一个接口——也就是通过String::push……
否则，当不需要可变性时，String包装器实际上除了带来额外的开销之外，没有任何其他作用。而只需付出相对较低的成本（例如使用一个强制的宽指针），不可变对象Box<str>就能获得以下优化：
- 对原始土地的直接所有权
str。 - 不再使用双重间接引语。
- 不再有过剩产能。
- 不再进行额外的堆内存分配。
- 整体内存占用降低。
Vec<T>对于某种类型，也可以这样说T，它恰好包装了一个切片[T]。事实上，存在大量这样的包装类型：例如，用于包装 `T` Path、CStr`C` 以及许多其他类似切片的类型。
或许这里最有价值的经验就是了解你的类型。诚然，Rust 声称实现了“零成本抽象”，但这并不意味着我们可以放松警惕，忽略进一步优化程序的各种可能性。
如前所述，仔细审视这些抽象概念可能会揭示其不必要的成本。因此，敏锐地识别并正确评估用例的限制至关重要。这样做，我们甚至可能无意中发现一些激进的优化方法，从而最大限度地利用计算机资源。
-
动态内存本质上更难以预测，因为它的行为只能在运行时确定。例如，用户输入就是如此。编译器无法预测并针对用户可能输入字符串的各种方式进行优化。程序所能做的最好办法是动态分配内存（基于输入的潜在大小），并相应地调整大小。这种行为无法在编译时完成和优化。虽然可以为字符串分配一个“固定预算”，这或许可以进行一些优化，但总的来说，这并非最灵活的选择 。
-
为了更加确保万无一失，我使用Compiler Explorer进行了验证
rustc 1.54。编译器标志设置为--edition 2018和-O（用于优化）。为了便于说明，我将 11 字节的字符串硬编码到代码中"Hello World"。实际上，生成的汇编代码为 分配了 11 字节str，为 分配了 24 字节String，为Arc<String>智能指针分配了 8 字节。@jakubdabek还在评论区 提供了一个Godbolt 示例。↩ -
从技术上讲，该
From<String>实现只是对字符串进行解引用，并将底层数据复制str到分配的内存中。因此Arc，真正的魔法发生在From<&str>实现层面。