需要帮助将一个从C到Rust的免等待trie移植

Question

对于某些HPC计算，我需要从C到Rust移植一个没有等待的trie (但您可以把它看作树)。trie是99%的读、1%写，同时用于并行并发场景和并发只读场景(具有多个协同线程的单线程)。树的大小通常在100 mb到8 mb之间。

基本上这棵树就像：

pub struct WFTrie {
    nodes: Vec<Node>,
    leaves: Vec<Leaf>,
    updates: Vec<Update>,
    update_pos: AtomicUsize,
    update_cap: usize,
}

//.... 
let mut wftrie = WFTrie::new(); 
let wftrie_ptr = AtomicPtr::new(&mut wftrie);

//....

如您所见，trie已经使用了与许多人建议的竞技场方法非常类似的方法，通过使用vec和存储。

• 当我想更新时，我在update_pos上做一个fetch_and_add。如果它大于update_cap，我返回一个错误(大小耗尽)，否则我确信我的coroutine/线程具有对updates[update_pos % update_cap]的独占访问权，我可以在其中放置更新

wftrie_ptr将克隆树，应用所有挂起的更新，然后对compare_and_swap进行compare_and_swap

当我想阅读

• 时，我在wtftrie_ptr上做了一个原子负载，我可以访问树，同时也考虑挂起的更新.

。

我的问题是：

• ，如果我有多个coroutine有一个不变的引用，我如何才能让一个coroutine进行更新？最惯用的翻译方法是什么呢？

• ，如果在更新过程中，协同线仍然保持对旧树的引用，那么会发生什么？我应该用圆弧代替AtomicPtr吗？

• 这个设计是否与锈蚀检查器很匹配，还是我必须使用不安全？

• 在只并发的情况下，我可以在不使用不安全的情况下丢弃原子吗？

Answer 1

我并不是特别了解HPC，但我希望我能为您提供一些关于在Rust中使用并发性进行编程的有用提示。

…我确信我的coroutine/线程可以独占地访问updatesupdate_pos，在那里我可以把我的更新

这是必要的，但还不够:如果要写入&引用后面的数据(无论是否来自多个线程)，那么您就实现了内部可更改性，并且必须始终使用某种单元格类型向编译器发出信号。做到这一点的最低风险方法是使用UnsafeCell，它不提供同步，并且是操作的unsafe：

    updates: Vec<UnsafeCell<Update>>,

但是，您也可以使用更安全的类型，如锁(您知道，因为您安排了没有其他线程使用它，所以不会发生任何争用)。在Rust中，所有锁和其他内部可变原语(包括atomics )都是在UnsafeCell之上构建的；这是如何告诉编译器“这个内存不受N读取器xor 1编写器的常规规则的限制”。

每一个X更新…协线将克隆树…

您必须进行安排，这样克隆人就不会试图读取正在被修改的数据。也就是说，不要克隆WFTrie，而是只克隆nodes和leaves向量，因为这是您实际需要的数据。

如果像我前面提到的那样使用UnsafeCell或锁，那么您将发现不能仅仅克隆updates矢量，这正是因为如果不显式锁定就无法这样做。如果有必要，您可以一步一步地阅读，以符合您的并发要求。

如果我有多个coroutine有一个不变的引用，我如何才能让一个coroutine进行更新？把这个翻译成生锈的最习惯的方法是什么？

我不知道有什么特别的方法。听起来你只需要一个AtomicBool就行了，但你可能比我知道得更多。

如果在更新过程中协同线仍然持有对旧树的引用，会发生什么情况？我应该用弧形代替AtomicPtr吗？

是的，这是个问题。请注意，AtomicPtr是要读取的unsafe，因为它不能保证指向对象是活动的。您需要一种使用类似Arc和原子交换的方法，其中特定的Arc位于wftrie_ptr位置；arc-swap库提供了这样的功能。

这个设计与锈蚀借阅器很相配吗，还是我不得不使用不安全的？

从使用数据结构的角度来看，- it似乎不会比Arc后面的任何其他数据结构更不方便地读写。

对于实现，您将不会有太多的“与借入检查器的斗争”，因为您不会使用非常多的借用- since(您的数据结构拥有它的内容)来编写函数。但是，在使用unsafe编写自己的并发原语时，无论如何都需要小心地遵守所有内存规则。请记住，unsafe不是无视规则的许可；它告诉编译器“我将遵守规则，但在某种程度上您无法检查”。

在只并发的情况下，

可以在不使用不安全的情况下删除atomics吗？

是的；在无线程场景中，您可以将Cell用于atomics所提供的所有用途。