在 Rust 中预取和屈服于 "hide" 缓存未命中

Question

当 C++20 获得无堆栈协程时 some papers 成功地使用它们通过预取和切换到另一个协程来“隐藏”缓存未命中。据我所知，Rust 的异步也类似于无堆栈协程，因为它是“零成本抽象”。是否有类似于我提到的在 Rust 中实现此类技术的工作？如果不是，是否有什么从根本上阻止人们用 async/await?

做类似的事情

编辑：我想对我理解的论文提出的内容给出一个非常高层次和简化的总结：

我们想要运行一堆独立的进程，如下所示

P1 = load1;proc1; load1';proc1'; load1'';proc1''; ... 
P2 = load2;proc2; load2';proc2'; load2'';proc2''; ... 
...
PN = loadN;procN; loadN';procN'; loadN'';procN''; ...

其中所有 loadI 项都可能导致缓存未命中。作者利用协同程序（动态地）交错进程，以便执行的代码如下所示：

P = 

prefetch1;prefetch2;...;prefetchN;
load1;proc1;prefetch1'; # yield to the scheduler
load2;proc2;prefetch2'; # yield to the scheduler
...
loadN;procN;prefetchN'; # yield to the scheduler
load1';proc1';prefetch1''; # yield to the scheduler
load2';proc2';prefetch2''; # yield to the scheduler

...
loadN';procN';prefetchN''; # yield to the scheduler
...

Answer 1

可以找到此 post 的完整代码 here.

我看起来并不难，但据我所知，目前还没有关于该主题的研究，所以我决定自己做一点。与上述论文不同，我采用了一种简单的方法来测试是否可行，方法是创建几个简单的链表并将它们相加：

pub enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}
impl<T> List<T> {
    pub fn new(iter: impl IntoIterator<Item = T>) -> Self {
        let mut tail = List::Nil;
        for item in iter {
            tail = List::Cons(item, Box::new(tail));
        }
        tail
    }
}
const END: i32 = 1024 * 1024 * 1024 / 16;
fn gen_lists() -> (List<i32>, List<i32>) {
    let range = 1..=END;
    (List::new(range.clone()), List::new(range))
}

好的，几个大的简单链表。我运行在两个不同的基准测试中使用九种不同的算法来查看预取如何影响事物。基准测试以自有方式对列表求和，其中列表在迭代期间被销毁，导致释放时间占测量时间的大部分，并以借用方式对它们求和，其中释放时间未被测量。测试的各种算法实际上只是用三种不同技术实现的三种不同算法，迭代器，Generators, and async Streams。

这三种算法是 zip，它以锁步方式迭代两个列表，链，一个接一个地迭代列表，以及 zip prefetch，其中在压缩两个列表时使用 prefetch 和 switch 方法一起。基本迭代器如下所示：

pub struct ListIter<T>(List<T>);
impl<T> Iterator for ListIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        let mut temp = List::Nil;
        std::mem::swap(&mut temp, &mut self.0);
        match temp {
            List::Cons(t, next) => {
                self.0 = *next;
                Some(t)
            }
            List::Nil => None,
        }
    }
}

预取版本如下所示：

pub struct ListIterPrefetch<T>(List<T>);
impl<T> Iterator for ListIterPrefetch<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        let mut temp = List::Nil;
        std::mem::swap(&mut temp, &mut self.0);
        match temp {
            List::Cons(t, next) => {
                self.0 = *next;
                if let List::Cons(_, next) = &self.0 {
                    unsafe { prefetch_read_data::<List<T>>(&**next, 3) }
                }
                Some(t)
            }
            List::Nil => None,
        }
    }
}

Generators 和 Streams 也有不同的实现，还有一个对引用进行操作的版本，但它们看起来都差不多，所以为了简洁起见，我省略了它们。测试工具非常简单——它只接受一对 name-function 并计算它的时间：

type BenchFn<T> = fn(List<T>, List<T>) -> T;
fn bench(funcs: &[(&str, BenchFn<i32>)]) {
    for (s, f) in funcs {
        let (l, r) = gen_lists();
        let now = Instant::now();
        println!("bench: {s} result: {} time: {:?}", f(l, r), now.elapsed());
    }
}

例如，基本迭代器测试的用法：

bench(&[
    ("iter::zip", |l, r| {
        l.into_iter().zip(r).fold(0, |a, (l, r)| a + l + r)
    }),
    ("iter::zip prefetch", |l, r| {
        l.into_iter_prefetch()
            .zip(r.into_iter_prefetch())
            .fold(0, |a, (l, r)| a + l + r)
    }),
    ("iter::chain", |l, r| l.into_iter().chain(r).sum()),
]);

在我的电脑上测试的结果，这是一台 Intel(R) Core(TM) i5-8365U CPU，内存为 24 Gb：

Bench owned
bench: iter::zip result: 67108864 time: 11.1873901s
bench: iter::zip prefetch result: 67108864 time: 19.3889487s
bench: iter::chain result: 67108864 time: 8.4363853s
bench: generator zip result: 67108864 time: 16.7242197s
bench: generator chain result: 67108864 time: 8.9897788s
bench: generator prefetch result: 67108864 time: 11.7599589s
bench: stream::zip result: 67108864 time: 14.339864s
bench: stream::chain result: 67108864 time: 7.7592133s
bench: stream::zip prefetch result: 67108864 time: 11.1455706s
Bench ref
bench: iter::zip result: 67108864 time: 1.1343996s
bench: iter::zip prefetch result: 67108864 time: 864.4865ms
bench: iter::chain result: 67108864 time: 1.4036277s
bench: generator zip result: 67108864 time: 1.1360857s
bench: generator chain result: 67108864 time: 1.740029s
bench: generator prefetch result: 67108864 time: 904.1086ms
bench: stream::zip result: 67108864 time: 1.0902568s
bench: stream::chain result: 67108864 time: 1.5683112s
bench: stream::zip prefetch result: 67108864 time: 1.2031745s

结果为计算总和，时间为记录时间。在查看破坏性求和基准时，有几件事很突出：

链算法效果最好。我的猜测是，这是因为此方法改进了分配器的缓存局部性，这是花费绝大部分时间的地方。
预取大大改善了 Stream 和生成器版本的时间，使它们的时间与标准迭代器相当。
预取完全破坏了迭代器策略。这就是为什么您在做这些事情时总是进行基准测试。如果这是编译器未能正确优化，而不是预取直接损害性能，我也不会感到惊讶。

在查看借款总和时，有几件事很突出：

在不测量重新分配时间的情况下，记录的时间要短得多。这就是我知道解除分配是上述大部分基准的方式。
链式方法失败了 - 显然运行步调一致是可行的方法。
预取是迭代器和生成器的方法。与之前的基准相比，预取导致迭代器成为最快的策略，而不是最慢的。
预取会导致使用流时速度变慢，尽管流的整体表现不佳。

出于各种原因，此测试不是最科学的，也不是针对特别现实的工作负载，但鉴于结果，我可以自信地说预取和切换策略肯定可以带来可靠的性能改进如果做得对。为了简洁起见，我还省略了一些测试代码，可以找到完整的代码 here.

在 Rust 中预取和屈服于 "hide" 缓存未命中

Prefetching and yielding to "hide" cache misses in rust

rust

async-await

coroutine