4次发布

0.2.1	2023年7月12日
0.2.0	2023年7月12日
0.1.1	2023年7月4日
0.1.0	2023年7月4日

#172 in 内存管理

每月21次下载

MIT/Apache

1.5MB
3K SLoC

btree-plus-store: 基于slab/arena的B树，以减少分配并提高局部性 + 可复制、不可变的B树，必须手动丢弃

由 btree-slab 分支而来。

你为什么要使用这个库呢？

你有很多B树，其中一些非常小，并且希望将它们都存储在同一内存区域中，以减少分配并提高局部性。

或者，你想要不可变且可复制的B树，可以共享相同的内存，但代价是必须通过手动触发的跟踪垃圾收集来手动丢弃和释放它们的内存。

它是什么？

BTreeMap 和 BTreeSet，具有与标准库几乎相同的接口（具有一些额外功能），但通过 new_in(&'a BTreeStore) 构建。

BTreeStore 内部是一个区域分配器，因为它在大型固定大小的区域中分配节点；但也是一个 slab分配器，因为它维护一个已分配和已丢弃节点的链表。这意味着我们获得了区域分配的局部性优势，但也可以通过在新的B树中重用丢弃的B树的存储来重用存储，尽管内存将不会在区域被销毁之前回收（在B树外可用）。

在 copyable 功能下：copyable::BTreeMap 和 copyable::BTreeSet 是可 Copy 的，由它们的可变对应物创建的不可变 b 树。一旦创建，与可变 b 树关联的内存将不再自动回收（因为这些可以自由复制，我们永远不知道我们是否正在释放最后一个）。相反，有一个不安全的 tracing_gc 方法，它允许您手动指定仍然活跃的 b 树，其他任何节点都将被回收。

use btree_plus_store::{BTreeSet, BTreeStore};
#[cfg(feature = "copyable")]
use btree_plus_store::copyable;

fn main() {
  let store = BTreeStore::new();
  let mut foo_bars: BTreeSet<'_, &'static str> = BTreeSet::new_in(&store);
  let mut alphabeticals: BTreeSet<'_, &'static str> = BTreeSet::new_in(&store);
  
  foo_bars.insert("foo");
  alphabeticals.insert("abc");
  foo_bars.insert("bar");
  alphabeticals.insert("def");
  foo_bars.insert("baz");
  foo_bars.insert("qux");
  alphabeticals.insert("xyz");
  foo_bars.remove(&"baz");
  alphabeticals.remove(&"def");
  for elem in &foo_bars {
      println!("Iterate {}", elem);
  }
  // TODO: retain, drain_filter, intersect, union, difference, and symmetric_difference
  // for elem in alphabeticals.drain_filter(|a| a.starts_with('a')) {
  //     println!("Drain {}", elem);
  // }
  for elem in alphabeticals {
      println!("Consume {}", elem)
  }
    
  #[cfg(feature = "copyable")]
  {
      let foo_bars = copyable::BTreeSet::from(foo_bars);
      let foo_bars2 = foo_bars;
      let foo_bars3 = foo_bars2;
      for elem in &foo_bars {
          assert!(foo_bars2.contains(elem) && foo_bars3.contains(elem));
      }
  }
}

安全性

此库大量使用 unsafe，尽管非 copyable 测试可以通过 MIRI 通过。大多数操作和边缘情况都有测试，但仍在早期阶段。并且由于 std::collections::BTreeMap 和 std::collections::BTreeSet 可用且在大多数情况下表现更好，因此不应用于生产。

基准测试

基准测试包括插入、检索、迭代和删除等操作序列。我们改变映射和集合的数量和大小。

此库在非常小的映射和集合上比 std 表现略快，但其他情况下较慢。

完整报告

1_map_3000_operations 10_maps_300_operations 100_maps_30_operations 1000_maps_3_operations 1_set_3000_operations 10_sets_300_operations 100_sets_30_operations 1000_sets_3_operations