iterator - 切片迭代器能否在恒定时间内前进多个元素？

Question

一些示例代码:( playpen )

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 操作对于切片迭代器来说是否是恒定时间的？在源代码中搜索我只找到了 this implementation for skip ，这导致 Skip 结构的 Iterator implementation .

这似乎是一个通用的 O(n) 跳过，而且我看不到任何可以只进行指针运算的基于指针的迭代器的专门化。

我是否遗漏了有关skip 的实现的某些内容？还是有其他方法可以做到这一点？

Answer 1

std 没有内置快进功能还没有。

正如 Chris 所演示的，它可以用 skip 来实现这有时会优化到 O(1)。不幸的是，优化并不总是发生，我的实验发现像

这样的函数

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

优化(opt-level 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]实际上是同构的，它们的不同主要是因为优化的原因。一旦我们有了切片，我们就可以对其进行切片和切 block 以获得更短的内存区域，然后只在这些元素上创建一个迭代器。生命周期全部解决，剩下的是完全相同的类型，只是少了一些元素。

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 的行为并避免 panic (跳过比迭代器包含的元素更多的元素只会导致“返回”值为空)。

要在实践中看到它，请考虑 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 错误:使用两个 cmp 和一个 cmovbq 似乎可以做得更好。)

很高兴它优化得很好，但是，由于 Iterator::skip 的问题方法论证，这个不能靠。然而，as_slice无论优化级别如何，方法都是 O(1)。

---

我怀疑slice::Iter可以覆盖 skip方法进行快进，然后返回 Skip { iter: self, n: 0 } ，从而保证 skip在 Iter实际上是有效的。但是这(和上面的一样)感觉有点像 hack，并且，仍然会导致类型发生变化，因此不能就地使用。