#byte-string #list #compact #memory #allocation #immutability

compact_strings

字符串或字节数组的更紧凑但功能有限的表示

6个稳定版本

4.1.2 2024年4月17日
4.0.2 2024年1月23日
3.0.0 2024年1月7日
2.0.0 2023年9月9日
0.1.0 2023年5月15日

#592 in 数据结构

Download history 316/week @ 2024-04-14 155/week @ 2024-04-21 66/week @ 2024-04-28 41/week @ 2024-05-05 24/week @ 2024-05-12 44/week @ 2024-05-19 28/week @ 2024-05-26 43/week @ 2024-06-02 37/week @ 2024-06-09 27/week @ 2024-06-16 29/week @ 2024-06-23 16/week @ 2024-06-30 22/week @ 2024-07-07 36/week @ 2024-07-14 34/week @ 2024-07-21 64/week @ 2024-07-28

每月 156 次下载
用于 2 crates

MIT 许可证

90KB
1.5K SLoC

compact_strings

字符串或字节数组的更紧凑但功能有限的表示。

此crate与compact_str无关,且不执行相同的优化。

关于

Vec<u8>,它也支持String,每个都是3个指针宽度。
它们包括指向数据开始位置的指针、表示当前在Vec中元素数量的长度以及表示分配所指元素可以容纳的元素数量的容量。

当存储在列表结构中时,容量可能不需要,尤其是当字符串(字节)不可变时。此外,由于每个(字节)字符串都使用自己的分配,大列表将创建许多分配,这可能会非常慢。

因此,此crate将(字节)字符串的列表存储为两个向量

  1. 元数据 - 保存(字节)字符串的起始索引
  2. 数据 - 保存(字节)字符串的实际字节

这意味着与只有3个指针宽度的3相比,我们支付了6个指针宽度的前期成本,但与3个指针宽度的3n + 3相比,我们有更慢增长的辅助内存消耗2n + 6,同时能够将所有字符串存储在一个快速增长的分配中。

遗憾的是,这种结构使得在不移动其他数据的情况下修改数据向量中存储的(字节)字符串变得极其困难。
可以通过有限的修改API来解决这个问题,但移动其余字节的成本将远高于使用Vec<String>

有关更多详细信息,请参阅基准测试

4.1.0 新增

通过去除上述结构体中 Metadata 的 (字节) 字符串长度,这个crate现在拥有了上述数据结构的更紧凑版本。

这意味着我们仍然需要支付 6 个指针宽度的预支成本,而不是 3 个,但辅助内存消耗增长得更慢,仅为 n + 6 个指针宽度。

这些版本与旧版本的性能差异不大,因此没有进行基准测试。

基准测试

一些预期性能与它们的 Vec 相当物差异很大的操作已经进行了基准测试,您可以在这里查看。

依赖项

约 170KB