#string #byte-string #memory #heap-memory #compact #stack-allocated #heap-allocated

无 std compact_str

一种内存高效字符串类型,当可能时,透明地在栈上存储字符串

15 个不稳定版本

0.8.0 2024 年 7 月 9 日
0.8.0-测试版2023 年 10 月 8 日
0.7.1 2023 年 6 月 22 日
0.7.0 2023 年 2 月 22 日
0.2.0 2021 年 11 月 14 日

编码 中排名 11

Download history 150831/week @ 2024-05-04 182316/week @ 2024-05-11 174617/week @ 2024-05-18 179688/week @ 2024-05-25 256528/week @ 2024-06-01 249314/week @ 2024-06-08 245138/week @ 2024-06-15 270505/week @ 2024-06-22 248589/week @ 2024-06-29 240677/week @ 2024-07-06 249421/week @ 2024-07-13 255650/week @ 2024-07-20 256490/week @ 2024-07-27 242286/week @ 2024-08-03 251585/week @ 2024-08-10 228052/week @ 2024-08-17

每月下载量 1,027,881
721 包(116 个直接使用)中使用

MIT 许可证

330KB
6.5K SLoC

compact_str

一种内存高效的字符串类型,可以在栈上存储多达 24* 字节。

version on crates.io Minimum supported Rust Version: 1.60 mit license
Continuous Integration Status Cross Platform Status Minimum Supported Rust Version Status Clippy Status

* 32 位架构为 12 字节


关于

CompactString 是一种更节省内存的字符串类型,可以将较小的字符串存储在栈上,并将较长的字符串透明地存储在堆上(即小型字符串优化)。它基本上可以用作 String 的直接替换,特别适用于解析、反序列化或任何可能需要较小字符串的应用。

属性

CompactString 特有的以下属性

  • size_of::<CompactString>() == size_of::<String>()
  • 在栈上存储多达 24 字节
    • 在 32 位架构上为 12 字节
  • 超过 24 字节的字符串存储在堆上
  • CloneO(n)
  • From<String>From<Box<str>> 重新使用底层缓冲区
    • 积极内联小型字符串
  • O(1)&'static str 使用 CompactString::const_new
  • 基于堆的字符串增长速度为1.5倍
    • 标准库 String 的增长速度为2倍
  • Option<_> 优化空间
    • size_of::<CompactString>() == size_of::<Option<CompactString>>()
  • 使用 无分支指令 进行字符串访问
  • 支持 no_std 环境

特性

此包公开了两个特性,ToCompactStringCompactStringExt

ToCompactString

提供了将类型转换为 CompactStringto_compact_string(&self) 方法。对于所有 std::fmt::Display 的类型,此特性会自动实现,并对以下类型提供了专门的高性能实现:

  • u8u16u32u64usizeu128
  • i8i16i32i64isizei128
  • f32f64
  • boolchar
  • NonZeroU*NonZeroI*
  • StringCompactString

CompactStringExt

提供了两个方法 join_compact(seperator: impl AsRef<str>)concat_compact()。对于所有可以被转换为迭代器并产生可 impl AsRef<str> 的类型的特性,会自动实现。这允许您将 Vec 的、切片以及其他任何集合连接起来,形成 CompactString

此包公开了一个宏 format_compact!,可以用于从参数创建 CompactString,就像使用 Stringstd::format! 宏创建字符串一样。

特性

compact_str 有以下可选特性

  • serde实现了来自流行的serde crate 的DeserializeSerialize trait,用于CompactString
  • bytes提供了两种方法from_utf8_buf<B: Buf>(buf: &mut B)from_utf8_buf_unchecked<B: Buf>(buf: &mut B),允许从bytes::Buf创建一个CompactString
  • markup实现了Render trait,因此CompactString可以作为HTML转义字符串在模板中使用
  • diesel允许在diesel文本列中使用CompactStrings
  • sqlx-mysql / sqlx-postgres / sqlx-sqlite允许在sqlx文本列中使用CompactStrings
  • arbitrary实现了用于模糊测试的arbitrary::Arbitrary trait
  • proptest实现了用于模糊测试的proptest::arbitrary::Arbitrary trait
  • quickcheck实现了用于模糊测试的quickcheck::Arbitrary trait
  • rkyv实现了rkyv::Archiverkyv::Serializerkyv::Deserialize,用于快速零拷贝序列化,可以与序列化的字符串互换
  • smallvec提供了into_bytes()方法,它允许您使用smallvec::SmallVecCompactString转换为字节向量

工作原理

注意:本说明假设为64位架构,对于32位架构,通常将任何数字除以2。

通常字符串存储在堆上,因为它们是动态大小的。在Rust中,一个String由三个字段组成,每个字段的长度都是一个usize。例如,其布局类似于以下内容

String: [ ptr<8> | len<8> | cap<8> ]

  1. ptr 是一个指向堆上存储字符串位置的指针
  2. len 是字符串的长度
  3. cap 是被指向的缓冲区的总容量

这导致在栈上存储了24个字节,每个字段8个字节。然后实际的字符串存储在堆上,通常还会额外分配内存以防止字符串更改时重新分配。

CompactString 的想法是,而不是在栈上存储元数据,只存储字符串本身。这样对于较短的字符串,我们可以节省一些内存,并且我们不需要在堆上进行分配,因此性能更高。一个 CompactString 限制为24字节(即 size_of::<String>()),所以它不会比 String 使用更多的内存。

CompactString 的内存布局看起来像这样

CompactString: [ 缓冲区<23> | len<1> ]

内存布局

内部,一个 CompactString 有两个变体

  1. 内联,字符串长度 <= 24字节
  2. 分配,字符串长度 > 24字节

我们定义一个判别符(即跟踪我们使用哪个变体) 最后一个字节中,具体来说

  1. 0b11111110 - 所有1后跟0,表示 分配
  2. 0b11XXXXXX - 两个前导1,表示 内联,其中后跟的6位用于存储长度

并且一个 CompactString 的总体内存布局是

  1. : {ptr: 非空<u8>,len: usize,cap:容量}
  2. 内联: {缓冲区: [u8; 24] }

两种变体都是24字节长

对于 分配的字符串,我们使用自定义的 HeapBuffer,它通常在栈上存储字符串的容量,但也可以选择在堆上存储。由于我们使用最后一个字节来跟踪判别符,所以我们只有7个字节来存储容量,或者在32位架构上只有3个字节。7个字节允许我们存储高达 2^56 的值,即64拍字节,而3个字节只允许我们存储高达 2^24 的值,即16兆字节。

对于64位架构,我们总是内联容量,因为我们可以安全地假设我们的字符串永远不会超过64拍字节,但在32位架构上,当创建或扩展一个 CompactString 时,如果文本长度超过16MB,则将容量移动到堆上。

我们以这种方式处理容量的原因有两个

  1. 用户不应为不使用的部分付费。这意味着,在 大多数 情况下,缓冲区的容量可以轻松地适应7或3个字节,因此用户不需要为存储容量在堆上的内存成本付费,如果他们不需要的话。
  2. 允许我们在O(1)时间内将From<String>转换为String,通过取String的部分(例如ptrlencap)并使用这些部分来创建一个CompactString,而不需要进行任何堆分配。这在在大型代码库中使用CompactString时非常重要,在这些代码库中,您可能会在CompactStringString之间进行工作。

对于内联字符串,我们只在堆栈上有一个24字节的缓冲区。这可能会让您想知道我们如何存储24字节的字符串,内联?我们不是也需要在某处存储长度吗?

为了做到这一点,我们利用了这样一个事实,即字符串的最后一个字节只能具有以下范围内的值[0, 192)。我们知道这一点,因为所有Rust字符串都是有效的UTF-8,而UTF-8字符的最后一个字节的唯一有效字节模式(以及字符串可能的最后一个字节)是0b0XXXXXXX,即[0, 128)0b10XXXXXX,即[128, 192)。这使所有值在[192, 255]范围内都未被使用在我们的最后一个字节中。因此,我们可以使用范围在[192, 215]内的值来表示范围在[0, 23]内的长度,如果我们的最后一个字节的值为< 192,我们知道它是一个UTF-8字符,并将字符串的长度解释为24

具体来说,CompactString在堆栈上的最后一个字节有以下用途

  • [0, 191] - 是UTF-8字符的最后一个字节,CompactString存储在堆栈上,并且隐式具有长度为24
  • [192, 215] - 表示长度范围在[0, 23]内的长度,此CompactString存储在堆栈上。
  • 216 - 表示此CompactString存储在堆上
  • 217 - 表示此CompactString存储了一个&'static str
  • [218, 255] - 未使用,例如表示 None 变体用于 Option<CompactString>

测试

字符串和 Unicode 可能相当混乱,更进一步的,我们在位级别上工作。 compact_str 有一个 广泛的 测试套件,包括单元测试、属性测试和模糊测试,以确保我们的不变性得到维护。我们在所有主要操作系统(Windows、macOS 和 Linux)、架构(64 位和 32 位)和字节序(大端和小端)上进行测试。

模糊测试使用 libFuzzerAFL++以及 honggfuzz 进行,其中 AFL++x86_64ARMv7 架构上运行。我们使用 miri 来捕获未定义行为的情况,并在从 v1.60 开始的所有 Rust 编译器上运行所有测试,以确保对最小支持的 Rust 版本(MSRV)的支持。

unsafe 代码

CompactString 使用一些不安全的代码,因为我们手动定义了我们是什么变体,所以与枚举不同,编译器不能保证实际存储的值。我们还实现了一些手动实现的堆数据结构,即 HeapBuffer,并在位级别上处理字节,以充分利用我们的资源。尽管如此,此库中不安全代码的使用仅限于绝对必要的地方,并且总是使用 // SAFETY: <reason> 进行文档说明。

类似的 Crates

在栈上存储字符串不是一个新想法,实际上,Rust 生态系统中还有几个其他 crate 做类似的事情,以下是不完整的列表

  1. smol_str - 可以内联 22 个字节,CloneO(1),不调整 32 位架构
  2. smartstring - 可以内联 23 个字节,CloneO(n),是可变的
  3. kstring - 可以内联 15 或 22 个字节,取决于 crate 功能,CloneO(1),也可以存储 &'static str
  4. flexstr - 可以内联 22 个字节,CloneO(1),也可以存储 &'static str

感谢阅读!

依赖关系

~0.1–15MB
~210K SLoC