为什么选择 pui-arena 而不是其他替代方案

pui-arena 允许你在可能的情况下最小化开销，并完全自定义区域。这允许你根据如何使用 api 来使用类似 slab 或 slotmap 的 api。 (还有由 slab 和 slotmap 特性控制的特性门控的新类型，实现了这两个包的类似接口)。

如果你使用 pui/scoped 特性，那么你也可以完全消除边界检查，这可以在性能敏感的区域中节省大量性能。

pui-arena 还提供了比竞争对手更多的功能，例如为版本化区域提供空缺条目 api，以及所有区域的 drain_filter。

选择 sparse、hop 或 dense

• 如果你需要快速插入/删除/访问，而不在乎迭代速度，请使用 sparse。

• 如果你需要所有东西中最重要的是迭代速度，请使用 dense。

• 如果你需要合理的迭代速度，同时也需要快速的访问/删除，或者如果 dense 对内存太重，请使用 hop。

您可以在相应的模块文档中了解每个模块的工作细节。

性能特性

速度

pui-arena中的所有集合允许您

• 以摊销时间复杂度O(1)插入元素
• 以O(1)删除/访问元素
• 确保除非调用remove，否则键值永远不会被失效

内存

对于每个Arena<T, _, V>，其中V: Version，内存开销如下

• sparse Arena - 每个槽位size_of(V) + max(size_of(T), size_of(usize))
• hop Arena - 每个槽位size_of(V) + max(size_of(T), 3 * size_of(usize))
• dense Arena - 每个槽位size_of(V) + size_of(usize)，以及每个值size_of(usize) + size_of(T)

实现细节

此crate的核心是Version特质、ArenaKey特质和BuildArenaKey特质。

Version指定了集合的行为。pui-arena提供了三个实现，更多详情请见Version

• DefaultVersion
  • 确保所有由insert生成的键都是唯一的
  • 由一个u32支持，因此对于小值可能会浪费空间
    • 技术上来说，如果项目被插入/删除多次，槽位将被“泄漏”，迭代性能可能会降低，但这种情况不太可能发生，除非相同的槽位被重复使用超过20亿次
• TinyVersion -
  • 确保所有由insert生成的键都是唯一的
  • 由一个u8支持，如果项目被插入/删除多次，槽位将被“泄漏”，迭代性能可能会降低
• Unversioned -
  • insert生成的键不必保证是唯一的
  • 槽位永远不会被“泄漏”

ArenaKey 用于指定键在区域中的行为。 pui-arena 提供了多种实现。请参见 ArenaKey 以获取详细信息。

• usize - 允许直接访问给定的槽位，不考虑其版本
  • 注意：当我说“不考虑其版本”时，它仍然会检查槽位是否已被占用，但没有方法来检查一个值是否被重新插入到同一个槽位
• Key<K, _> - 允许通过 K 访问指定的槽位，并在提供值之前检查槽位的生成
  • K 可以是这里列出的其他键之一（除了 ScopedKey）
• TrustedIndex - 允许直接访问给定的槽位，不考虑其版本
  • 省略了边界检查，但构造时是不安全的
  • 应该小心使用这个功能，如果确实需要使用，最好使用 pui 功能并使用 pui_vec::Id。它是安全的，并且也保证了边界检查的省略
• ScopedKey<'_, _> - 只允许访问范围区域（否则与 Key 相同）

通过 pui 功能启用

• pui_vec::Id - 允许直接访问给定的槽位，不考虑其版本
  • 省略了边界检查

BuildArenaKey 指定了区域应该如何创建键，除了 TrustedIndex 之外，该包提供的所有 ArenaKey 实现也实现了 BuildArenaKey

自定义区域

您可以使用 newtype 宏或功能： slab、slotmap 或 scoped 来创建区域的新类型。

• slab - 提供了与 slab 包 相似的 API
  • 使用 usize 键和 Unversioned 槽位
• slotmap - 提供了与 slab 包 相似的 API
  • 使用 Key<usize> 键和 DefaultVersion 插槽
• scoped - 提供使用 pui_core::scoped 以省略边界检查的新类型竞技场
  • 使用 scoped::ScopedKey<'_, _> 键，并对版本进行泛型化
• newtype - 创建具有 base 模块结构的系列新类型竞技场
  • 这些竞技场省略了边界检查，转而进行 ID 检查，这更便宜，并且根据你的底层 ID，甚至可以完全不检查！（见 pui_core::scalar_allocator 详细信息）

// Because the backing id type is `()`, there are no bounds checks when using
// this arena!
pui_arena::newtype! {
    struct MyCustomArena;
}

let my_sparse_arena = sparse::Arena::new();
let my_dense_arena = dense::Arena::new();
let my_hop_arena = hop::Arena::new();

变成了类似下面的东西

pui_core::scalar_allocator! {
    struct MyCustomArena;
}

mod sparse {
    pub(super) Arena(pub(super) pui_arena::base::sparse::Arena<...>);

    /// more type aliases here
}

mod dense {
    pub(super) Arena(pub(super) pui_arena::base::dense::Arena<...>);

    /// more type aliases here
}

mod hop {
    pub(super) Arena(pub(super) pui_arena::base::hop::Arena<...>);

    /// more type aliases here
}

let my_sparse_arena = sparse::Arena::new();
let my_dense_arena = dense::Arena::new();
let my_hop_arena = hop::Arena::new();

其中每个 Arena 新类型都有一个简化的 API 和更好的错误信息。