对于反向迭代、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
}
#[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 程序员应该关心这个的情况可能很少。
我正在尝试在 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
}
#[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 程序员应该关心这个的情况可能很少。