Lib.rs

› 数据结构
#bucket #vec #box #pin #vector

no-std bucket_vec

一种类似向量的数据结构，保证其包含的元素从不移动

作者：Robin Freyler

11个版本 (7个破坏性更新)

0.8.0 2020年2月24日
0.7.1 2020年2月24日
0.6.0 2020年2月23日
0.5.0 2020年2月22日
0.1.1 2020年2月20日

#1631 in 数据结构

每月34次下载

MIT/Apache

48KB
914 行

桶向量

文档 Crates.io
docs crates

⚠️ 警告

谨慎使用

目前，这个crate还没有经过充分的实战测试或基准测试，作者不会推荐将其用于通用生产环境。请向此存储库的问题跟踪器提交错误、建议或改进。

描述

一种类似向量的数据结构，将元素组织成固定容量的桶集合，以保证对桶向量的修改永远不会移动元素，从而不破坏对其的引用。

这与Vec<Box<T>>类似，但效率更高。

配置

BucketVecConfig trait 允许自定义 BucketVec 的内部结构。这允许用户针对特定用例对他们的 BucketVec 进行微调。

该trait主要控制第一个桶的容量以及新桶容量增长速度。

默认的 DefaultConfig 尝试平衡起始容量和增长速度之间的不同利益。

内部机制

BucketVec 实际上是一个 Bucket 实例的向量。每当向 BucketVec 添加元素时，如果最后一个 Bucket 没有满，该元素就会被推送到最后一个 Bucket。如果最后一个 Bucket 已满，就会根据所使用的桶向量配置确定新容量，并将一个新 Bucket 推送到 BucketVec。

这种方式，当在插入新元素时，BucketVec 永远不会移动元素，以保留引用。当修改一个普通的 Vec 时，由于内部缓冲区的重新分配可能会使引用失效，这可能会在外部存储 Vec 内部元素时引发严重错误。请注意，Rust 通常会防止此类情况，因此 BucketVec 主要用于 unsafe Rust 区域，开发者主动决定他们想要或需要将引用固定到另一个数据结构中。

与上述原因相同，BucketVec 不允许删除或交换元素。

示例

考虑一个具有以下配置的 BucketVec<i32> 示例

  • start_capacity:= 1
  • growth_rate:= 2

我们已经将元素 A、...、K 推送到它上面。

[ [A], [B, C], [D, E, F, G], [H, I, J, K, _, _, _, _] ]

其中 _ 指的是空桶条目。

将另一个 L、...、O 推送到同一个 BucketVec 上将导致

[ [A], [B, C], [D, E, F, G], [H, I, J, K, L, M, N, O] ]

所以所有桶都满了。下次我们将另一个元素推送到 BucketVec 时，它将创建一个容量为 16 的新 Bucket，因为 growth_rate == 2，而我们的当前最新桶的容量已经是 8。

[ [A], [B, C], [D, E, F, G], [H, I, J, K, L, M, N, O], [P, 15 x _] ]

其中 15 x _ 表示 15 个连续的空条目。

基准测试

BucketVec 在替换那些使用 Vec<Box<T>> 作为直观解决方案的情况时发挥了其作用。基准测试套件仍然很小，并不特别具有表达力，但已经提供了一些关于 BucketVec 已经表现得相当出色以及它可以在哪些方面进行改进的见解。

在 Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz 上运行了基准测试。请注意，对于每个基准测试组（push、get 和 iter），已选择了 BucketVec 最有效的配置。一些基准测试（get）显示了配置之间的显著差异。

以下是一个基准测试的输出

bucket_vec::push/10000       time:   [43.647 us 43.861 us 44.108 us]
bucket_vec::push_get/10000   time:   [48.872 us 49.396 us 49.834 us]
vec_box::push/10000          time:   [405.37 us 410.91 us 417.20 us]
vec_value::push/10000        time:   [25.826 us 25.915 us 26.020 us]

bucket_vec::get/10000        time:   [17.369 us 17.416 us 17.470 us]
vec_box::get/10000           time:   [14.446 us 14.485 us 14.537 us]
vec_value::get/10000         time:   [8.7939 us 8.8105 us 8.8300 us]

bucket_vec::iter/10000       time:   [4.4195 us 4.4316 us 4.4454 us]
vec_box::iter/10000          time:   [9.5925 us 9.6246 us 9.6610 us]
vec_value::iter/10000        time:   [3.5955 us 3.6043 us 3.6142 us]

bucket_vec::iter.rev()/10000 time:   [3.9804 us 3.9957 us 4.0144 us]
vec_box::iter.rev()/10000    time:   [9.9677 us 9.9980 us 10.033 us]
vec_value::iter.rev()/10000  time:   [3.5827 us 3.5944 us 3.6080 us]

bucket_vec::iter_mut/10000   time:   [5.0533 us 5.0710 us 5.0909 us]
vec_box::iter_mut/10000      time:   [13.425 us 13.845 us 14.203 us]
vec_value::iter_mut/10000    time:   [4.0172 us 4.0473 us 4.0820 us]

可以看出，在 push、iter 和 iter().rev() 基准测试中，BucketVec 明显优于 Vec<_>。此外，BucketVec 大约比 Vec<_> 慢 50%，这是理论上最佳的选择，但它不幸地无法解决根本问题。

作者 & 致谢

作者：Robin Freyler (github.com/Robbepop)

特别感谢 Niklas Tittjung (github.com/lugino-emeritus)，他在一些内部公式上给了我很多帮助。

许可

在以下任一许可下授权

由您选择。

双重许可：badge badge

依赖项

~385–730KB
~16K SLoC