切片迭代器可以在恒定时间内推进多个元素吗？

Question

一些示例代码:(游戏围栏)

let data = [0, 1, 2, 3, 4];
let mut iter = data.iter();
println!("{}", iter.next().unwrap());
println!("{}", iter.skip(3).next().unwrap());

按预期打印0和4.

我很好奇切skip片迭代器的操作是否是恒定时间？在源代码中我只找到了这个实现skip,这导致了Skip struct的Iterator实现.

这似乎是一个通用的O(n)跳过,我看不到任何可以做指针算术的基于指针的迭代器的专门化.

我错过了一些关于实施的内容skip吗？或者还有其他方法可以做到这一点吗？

Answer 1

还没有快进的内置功能std.

正如Chris演示的那样,它可以实现,skip有时优化为O(1).不幸的是,优化并不总是发生,我的实验发现了一个类似的功能

pub fn foo(xs: &[u32], x: usize) -> u32 {
    *xs.iter().skip(x).next().unwrap()
}

优化(选择级别3)到

.LBB6_2:
    pushq   %rax
.Ltmp10:
    .cfi_def_cfa_offset 16
    movq    (%rdi), %rdx
    movq    8(%rdi), %rdi
    xorl    %eax, %eax
    testq   %rdi, %rdi
    movq    %rdx, %rcx
    je  .LBB6_4
    leaq    4(%rdx), %rcx
    movq    %rdx, %rax
.LBB6_4:
    testq   %rsi, %rsi
    je  .LBB6_9
    leaq    (%rdx,%rdi,4), %rdx
    .align  16, 0x90
.LBB6_6:
    testq   %rax, %rax
    je  .LBB6_12
    decq    %rsi
    cmpq    %rdx, %rcx
    movq    %rdx, %rdi
    movl    $0, %eax
    je  .LBB6_8
    leaq    4(%rcx), %rdi
    movq    %rcx, %rax
.LBB6_8:
    testq   %rsi, %rsi
    movq    %rdi, %rcx
    jne .LBB6_6
.LBB6_9:
    testq   %rax, %rax
    je  .LBB6_12
    movl    (%rax), %eax
    popq    %rdx
    retq
.LBB6_12:
    movq    _ZN6option15Option$LT$T$GT$6unwrap14_MSG_FILE_LINE20ha41302a4e895de223qFE@GOTPCREL(%rip), %rdi
    callq   _ZN9panicking5panic20h90c2ad20c9dac62bKRCE@PLT

特别值得注意的是.LBB6_6:...... jne .LBB6_6序列:它是一个循环.

幸运的是,至少有一种方法,它有一个额外的有用属性:它不需要更改类型,因此可以直接使用.

切片迭代器可以转换回它所代表的切片as_slice:Iter<T>并且&[T]实际上是同构的,它们的不同主要是因为出于优化原因.一旦我们得到切片,我们就可以对它进行切片和切块以获得更短的内存区域,然后仅在这些元素上创建一个迭代器.生命周期全部结束,我们只剩下几个元素而完全相同的类型.

use std::slice::Iter;
use std::cmp;

pub fn skip(iter: &mut Iter<u32>, x: usize) {
    let s = iter.as_slice();
    *iter = s[cmp::min(x, s.len())..].iter();
}

用过像skip(&mut some_iter, 10).

该min电话是复制的行为Iterator::skip,避免恐慌(跳过更多的元素比迭代器包含只会导致"回归"值为空).

要在实践中看到它,请考虑foo转换为使用新的skip:

pub fn foo(xs: &[u32], x: usize) -> u32 {
    let mut iter = xs.iter();
    skip(&mut iter, x);
    *iter.next().unwrap()
}

它优化为:

.LBB7_2:
    pushq   %rax
.Ltmp12:
    .cfi_def_cfa_offset 16
    movq    8(%rdi), %rax
    cmpq    %rsi, %rax
    cmovbq  %rax, %rsi
    cmpq    %rax, %rsi
    je  .LBB7_4
    movq    (%rdi), %rax
    movl    (%rax,%rsi,4), %eax
    popq    %rdx
    retq
.LBB7_4:
    movq    _ZN6option15Option$LT$T$GT$6unwrap14_MSG_FILE_LINE20ha41302a4e895de223qFE@GOTPCREL(%rip), %rdi
    callq   _ZN9panicking5panic20h90c2ad20c9dac62bKRCE@PLT

值得注意的是,没有循环.这不是很短的xs[x]实现(ASM下面,仅供参考),但它是非常接近(2个额外的指令).

.LBB5_2:
    pushq   %rax
.Ltmp8:
    .cfi_def_cfa_offset 16
    movq    8(%rdi), %rdx
    cmpq    %rsi, %rdx
    jbe .LBB5_4
    movq    (%rdi), %rax
    movl    (%rax,%rsi,4), %eax
    popq    %rdx
    retq
.LBB5_4:
    leaq    panic_bounds_check_loc1464(%rip), %rdi
    callq   _ZN9panicking18panic_bounds_check20h5ef74c98f9f69401jSCE@PLT

(事实上​​,我几乎认为这是一个LLVM错误的区别:看起来它可以用两个cmps和a 做得更好cmovbq.)

它很好地优化,但是,正如该Iterator::skip方法的问题所示,这不能依赖.但是,as_slice无论优化级别如何,该方法都是O(1).

我怀疑slice::Iter可以覆盖skip方法来执行快进,然后返回Skip { iter: self, n: 0 },从而保证skipon Iter实际上是高效的.但是这(如上所述)感觉有点像黑客,并且仍然导致类型改变,因此无法就地使用.