如何提高自定义迭代器的`extend`性能

Question

我的应用程序包含自定义 RingBuffer 实现，因为我需要 一些

VecDeque<u8>

不提供的功能。

对我来说，性能关键路径是

extend

具有此环形缓冲区的子范围的

Vec<u8>

。因此，我进行了基准测试，发现默认的

VecDeque

range

iter 的性能明显优于我的，尽管数据结构完全相同。

我检查了 godbolt，正如预期的那样，内置的获得了很酷的自动矢量化，而我的则没有。

虽然我可能最终会为我的用例编写手册

extend_from_slice

/

std::ptr::copy

， 我有兴趣了解是否可以采取任何措施来获得与内置迭代器相当的性能。到目前为止，我尝试使用

&u8

作为 iter，但效果更糟。

我可以为我的 Iter 或其他东西实现一些额外的特性吗？

我的代码看起来像这样：

use std::collections::VecDeque;

pub struct RingbufIter<'a> {
    s1: std::slice::Iter<'a, u8>,
    s2: std::slice::Iter<'a, u8>,
}
impl<'a> Iterator for RingbufIter<'a> {
    type Item = u8;
    fn next(&mut self) -> Option<Self::Item> {
        match self.s1.next().copied() {
            Some(b) => Some(b),
            None => {
                // swap to reduce branches on subsequent `next` calls
                std::mem::swap(&mut self.s1, &mut self.s2);
                self.s1.next().copied()
            }
        }
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let (s1_min, s1_max) = self.s1.size_hint();
        let (s2_min, s2_max) = self.s2.size_hint();
        (s1_min + s2_min, Some(s1_max.unwrap() + s2_max.unwrap()))
    }
}

#[no_mangle]
pub fn extend_from_custom_iter(src: RingbufIter, sink: &mut Vec<u8>)  {
    sink.extend(src)
}

#[no_mangle]
pub fn extend_from_vec_deque(src: &mut VecDeque<u8>, sink: &mut Vec<u8>)  {
    sink.extend(src.range(0..src.len()))
}

Answer 1

标准库使用专门化来为它所了解的某些集合提供更快的

Extend

实现。但是您不能使用它，因为它不稳定。如果您想手动实现

Extend

，您可以为新类型执行此操作。否则就写普通方法

RingbufIter::extend_into_vec(&mut self, &mut Vec<u8>)

。例如：

struct VecWrapper<'a>(&'a mut Vec<u8>);

impl Extend<u8> for VecWrapper<'_> { 
    // use optimized algorithm here
}

#[no_mangle]
pub fn extend_from_custom_iter(src: RingbufIter, sink: &mut Vec<u8>)  {
    VecWrapper(sink).extend(src)
}

不幸的是，这阻止了编写通用代码，但如果您的用例只是使用自定义环形缓冲区和

Vec

，这应该没问题。