对于反向迭代、for 或 while 循环,哪个更快?

Which is faster for reverse iteration, for or while loops?

我正在尝试在 Rust 中实现标准 memmove 函数,我想知道哪种方法对于向下迭代更快(其中 src < dest):

for i in (0..n).rev() {
    //Do copying
}

let mut i = n;
while i != 0 {
    i -= 1;
    // Do copying
}

for 循环版本中的 rev() 会显着降低速度吗?

对于小N来说,这真的不应该重要。

Rust 在迭代器上是惰性的;在您实际 询问 一个元素之前,0..n 不会导致任何评估。 rev() 首先请求最后一个元素。据我所知,Rust 计数器迭代器很聪明,不需要生成前 N-1 个元素来获得第 N 个元素。在这种特定情况下,rev 方法可能更快。

一般情况下,取决于你的迭代器有什么样的访问范式和访问时间;确保访问结尾需要恒定的时间,并且没有什么不同。

与所有基准测试问题一样,它取决于。亲自测试您的 N 值!

过早的优化也是邪恶的,所以如果您的 N 很小,并且您的循环不经常执行...别担心。

TL;DR: 使用 for 循环。


两者应该同样快。我们可以非常简单地检查编译器剥离 for 循环中涉及的抽象层的能力:

#[inline(never)]
fn blackhole() {}

#[inline(never)]
fn with_for(n: usize) {
    for i in (0..n).rev() { blackhole(); }
}

#[inline(never)]
fn with_while(n: usize) {
    let mut i = n;
    while i > 0 {
        blackhole();
        i -= 1;
    }
}

这会生成这个 LLVM IR:

; Function Attrs: noinline nounwind readnone uwtable
define internal void @_ZN8with_for20h645c385965fcce1fhaaE(i64) unnamed_addr #0 {
entry-block:
  ret void
}

; Function Attrs: noinline nounwind readnone uwtable
define internal void @_ZN10with_while20hc09c3331764a9434yaaE(i64) unnamed_addr #0 {
entry-block:
  ret void
}

即使您不精通 LLVM,也很明显两个函数都编译成相同的 IR(因此显然是相同的程序集)。

由于它们的性能相同,因此应该更喜欢更明确的 for 循环并将 while 循环保留给迭代不规则的情况。


编辑:解决 starblue 对不健康的担忧。

#[link(name = "snappy")]
extern {
    fn blackhole(i: libc::c_int) -> libc::c_int;
}

#[inline(never)]
fn with_for(n: i32) {
    for i in (0..n).rev() { unsafe { blackhole(i as libc::c_int); } }
}

#[inline(never)]
fn with_while(n: i32) {
    let mut i = n;
    while i > 0 {
        unsafe { blackhole(i as libc::c_int); }
        i -= 1;
    }
}

编译为:

; Function Attrs: noinline nounwind uwtable
define internal void @_ZN8with_for20h7cf06f33e247fa35maaE(i32) unnamed_addr #1 {
entry-block:
  %1 = icmp sgt i32 %0, 0
  br i1 %1, label %match_case.preheader, label %clean_ast_95_

match_case.preheader:                             ; preds = %entry-block
  br label %match_case

match_case:                                       ; preds = %match_case.preheader, %match_case
  %.in = phi i32 [ %2, %match_case ], [ %0, %match_case.preheader ]
  %2 = add i32 %.in, -1
  %3 = tail call i32 @blackhole(i32 %2)
  %4 = icmp sgt i32 %2, 0
  br i1 %4, label %match_case, label %clean_ast_95_.loopexit

clean_ast_95_.loopexit:                           ; preds = %match_case
  br label %clean_ast_95_

clean_ast_95_:                                    ; preds = %clean_ast_95_.loopexit, %entry-block
  ret void
}

; Function Attrs: noinline nounwind uwtable
define internal void @_ZN10with_while20hee8edd624cfe9293IaaE(i32) unnamed_addr #1 {
entry-block:
  %1 = icmp sgt i32 %0, 0
  br i1 %1, label %while_body.preheader, label %while_exit

while_body.preheader:                             ; preds = %entry-block
  br label %while_body

while_exit.loopexit:                              ; preds = %while_body
  br label %while_exit

while_exit:                                       ; preds = %while_exit.loopexit, %entry-block
  ret void

while_body:                                       ; preds = %while_body.preheader, %while_body
  %i.05 = phi i32 [ %3, %while_body ], [ %0, %while_body.preheader ]
  %2 = tail call i32 @blackhole(i32 %i.05)
  %3 = add nsw i32 %i.05, -1
  %4 = icmp sgt i32 %i.05, 1
  br i1 %4, label %while_body, label %while_exit.loopexit
}

核心循环是:

; -- for loop
match_case:                                       ; preds = %match_case.preheader, %match_case
  %.in = phi i32 [ %2, %match_case ], [ %0, %match_case.preheader ]
  %2 = add i32 %.in, -1
  %3 = tail call i32 @blackhole(i32 %2)
  %4 = icmp sgt i32 %2, 0
  br i1 %4, label %match_case, label %clean_ast_95_.loopexit

; -- while loop
while_body:                                       ; preds = %while_body.preheader, %while_body
  %i.05 = phi i32 [ %3, %while_body ], [ %0, %while_body.preheader ]
  %2 = tail call i32 @blackhole(i32 %i.05)
  %3 = add nsw i32 %i.05, -1
  %4 = icmp sgt i32 %i.05, 1
  br i1 %4, label %while_body, label %while_exit.loopexit

唯一的区别是:

  • 在调用 blackhole 之前递减,而在
  • 之后递减
  • for 与 0 比较,while 与 1 比较

否则就是同一个核心循环

简而言之:它们(几乎)一样快——使用for循环!


更长的版本:

首先:rev()只适用于实现DoubleEndedIterator, which provides a next_back() method. This method is expected to run in o(n) (sublinear time), usually even O(1) (constant time). And indeed, by looking at the implementation of next_back() for Range的迭代器,我们可以看到它运行在常数时间。

现在我们知道两个版本都具有渐近相同的运行时间。如果是这种情况,您通常应该停止考虑并使用更惯用的解决方案(在本例中为 for)。过早考虑优化通常会降低编程效率,因为在您编写的所有代码中,性能只占很小的一部分。

但由于您正在实施 memmove,性能可能对您来说真的很重要。因此,让我们尝试查看生成的 ASM。我使用了这段代码:

#![feature(start)]
#![feature(test)]

extern crate test;

#[inline(never)]
#[no_mangle]
fn with_for(n: usize) {
    for i in (0..n).rev() { 
        test::black_box(i); 
    }
}

#[inline(never)]
#[no_mangle]
fn with_while(n: usize) {
    let mut i = n;
    while i > 0 {
        test::black_box(i);
        i -= 1;
    }
}

#[start]
fn main(_: isize, vargs: *const *const u8) -> isize {
    let random_enough_value = unsafe {
        **vargs as usize
    };

    with_for(random_enough_value);
    with_while(random_enough_value);
    0
}

(Playground Link)

#[no_mangle] 是为了提高生成的 ASM 的可读性。 #inline(never)random_enough_value 以及 black_box 用于防止 LLVM 优化我们不想优化的东西。生成的 ASM(在发布模式下!)经过一些清理后如下所示:

with_for:                       |   with_while:
    testq   %rdi, %rdi          |       testq   %rdi, %rdi
    je  .LBB0_3                 |       je  .LBB1_3
    decq    %rdi                |   
    leaq    -8(%rsp), %rax      |       leaq    -8(%rsp), %rax
.LBB0_2:                        |   .LBB1_2:
    movq    %rdi, -8(%rsp)      |       movq    %rdi, -8(%rsp)
    decq    %rdi                |       decq    %rdi
    cmpq    $-1, %rdi           |       
    jne .LBB0_2                 |       jne .LBB1_2
.LBB0_3:                        |   .LBB1_3:
    retq                        |       retq

唯一的区别是 with_while 少了两条指令,因为它倒数到 0 而不是 -1,就像 with_for 那样。

结论:如果你知道渐近运行时是最优的,你可能根本不应该考虑优化。现代优化器足够聪明,可以将高级构造编译成非常完美的 ASM。通常,无论如何,数据布局和由此产生的高速缓存效率比最少的指令数量重要得多。

如果您确实需要考虑优化,请查看 ASM(或 LLVM IR)。在这种情况下,for 循环实际上有点慢(更多指令,与 -1 而不是 0 进行比较)。但是 Rust 程序员应该关心这个的情况可能很少。