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

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, which leads down to the Skip struct's Iterator implementation.

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

我是否遗漏了有关 skip 实施的内容？或者有其他方法可以做到这一点吗？

Answer 1

库中没有任何东西可以做到这一点，但有时不稳定的 RandomAccessIterator.idx 特征方法可能会做你想做的事。

检查生成的汇编代码表明编译器至少可以优化一些从 O(n) 到 O(1) 的跳跃。作为一个简单的例子，给定 x: &[u32]、*x.iter().skip(5).next().unwrap() 和 x[5] 生成相同的汇编代码。我不确定它在优化skips方面会有多彻底，但绝对不会寒酸。这是优化编译器的好主意之一：您寻求的这种专业化可以在编译器而不是代码中实现，这通常会帮助您避免错过可以完成的优化，但是（因为它们不是perfect) 偶尔会导致您期望发生的优化失败。

Answer 2

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    [=11=], %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$GTunwrap14_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 的行为并避免恐慌（跳过比迭代器包含更多的元素只会导致 'return' 值为空）。

要在实践中看到它，请考虑将 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$GTunwrap14_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 方法来快进，然后 return Skip { iter: self, n: 0 }，从而保证 skip Iter 实际上是高效的。但是这个（和上面一样）感觉有点像 hack，and，仍然导致类型改变所以不能就地使用。

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

Can a slice iterator be advanced more than one element in constant time?

iterator

rust