链式原子随机插入向量

Lariv 是一个线程安全的、自我管理的向量，不保证顺序插入。它内部使用链式环形缓冲区，与传统的环形缓冲区不同，它是可扩展的，并且更重要的是，它不会在整个过程中重新分配整个缓冲区。它诞生于 TPR 项目 之中，旨在存储 TPR 服务器上的客户端连接，这些服务器通常存储的是生命周期短暂的数据，需要通过 128 位整数访问。这基本上是向量的 DashMap。

Lariv 与传统向量非常相似，只是能够在不复制后续元素的情况下移除任何索引处的元素（而不仅仅是最后一个元素）。Lariv 是无锁的，具有最坏情况下的 O(n) 智能插入算法，该算法试图以快速常数的速度保持插入。重新分配是无等待的，查找（用于获取和删除）是 O(n/capacity)。尽管 Lariv 是为短生命周期数据设计的，但它适用于大多数多线程场景，在这些场景中，向量类数据结构是可行的。Lariv 已经针对更好的缓存局部性进行了优化；这些优化为小型元素（例如几个单词）提供了等效的性能，但对于大型元素（例如 4KB）则实现了大约 20% 的性能提升。

建议预留的容量要远远超过实际预期占用的平均大小，至少 50%，理想情况下是 100% 或 200%。这是为了降低数据竞争，避免线程争夺可用空间。只有在算法假定缓冲区“有点满”时才会进行重新分配，这要么是缓冲区已满，要么是元素实际上并未被删除（自上次检查以来小于 30%），这可能会影响性能。这实际上是一个错误，但我将其作为一个特性添加并添加了复杂的百分比。

代码示例

use std::thread::scope;
use lariv::{Lariv, LarivIndex};

fn example() {
    // The Lariv is backed by a collection of buffers
    // distributed across nodes, and you need to specify
    // the amount of elements each one holds at most.
    let capacity = 50;
    let lariv = Lariv::new(capacity);
    let ptr = &lariv;
    scope(|s| {
        for i in 1..=330 {
            // Some processing that is pushed to the Lariv.
            // The insertion order is completely random,
            // if you need it to be sorted append the correct index
            // with the data, `i` on this case, and sort it later.
            // The alternative is having threads starve waiting on
            // a lock, which often is not ideal at best.
            s.spawn(move || ptr.push(i.to_string()));
        }
    });
    // Iterate the Lariv and do something with the data.
    for e in lariv {
        println!("{e}");
    }
}

安全性

Miri 使用树借用时不会有抱怨。如果您遇到错误，请提交问题。

性能

根据我所知，性能非常好。如果您有改进性能的建议，请为我祈祷，并请提交一个PR。它比DashMap（见下文）快得多，但作为附带说明，Lariv是一个向量，而DashMap是一个哈希表，所以这并不是一个苹果对苹果的比较。在这里，DashMap只是要打败的分数，因为它是一个可以用于与Lariv相同位置的数据结构，它也是Rust中的事实上的多线程哈希表。

基准测试，每个样本30000个操作，元素大小为4KB

结论

Lariv比DashMap快得多，并且具有更一致的延迟。因此，需要一致延迟的应用程序，例如游戏、视频会议等，可能会更愿意使用它。我认为Lariv已准备好投入生产使用，并且表现良好，但我不会对生产中的崩溃、核战争，或者你即将成为的妻子因为你必须在婚礼期间调试生产而与你分手负责；DashMap的维护者也是如此。向Joel Wejdenstål（dashmap开发者）致敬，他太棒了。