将性能关键循环从 C 翻译成 Rust
Translate performance critical loop from C to Rust
我正在尝试将一些旧的 C 代码重写为 Rust——我是新手。我遇到的一个反复出现的问题是 C 代码有很多这样的循环:
for (i = startIndex; i < asize; i++)
{
if (firstEdge < 0 && condLeft(i))
{
firstEdge = i;
}
RightIndex = asize-1-i;
if (firstEdgeRight < 0 && condRight(RightIndex))
{
firstEdgeRight = RightIndex;
}
// Found both edges
if (firstEdge >= 0 && firstEdgeRight >= 0) {
break;
}
}
您将如何以高效的方式将其转化为 Rust?我的问题是,虽然我可能可以获得我想要的功能,但我不确定如何才能获得(大致)相同的速度。
这部分代码是我们代码中的主要瓶颈(至少这部分代码),在翻译时希望保留以下属性。
- 循环应该尽快中断,因为
asize
可能非常大。
firstEdge
和firstEdgeRight
大致同时被发现。因此,只有一个循环而不是两个循环是一件好事——为了避免再次从头开始搜索(尽管我认为这个解决方案会杀死预取器(但我不确定,也许旧机器 运行 代码甚至没有预取器))。
虽然性能很重要,但可读性当然更重要:)
EDIT 好的,这是我可能的 Rust 实现(cond_right()
和 cond_left()
被遗漏了)。
我考虑的事情是:
- 如果其他人必须从头开始实施,他们会这样写吗?
- 我真的需要让
first_edge
和 first_edge_right
可变吗?它们在我的实现中,但我觉得不对,因为它们只分配了一次。
let mut first_edge = -1;
let mut first_edge_right = -1;
// Find first edge
let start_index = 300; // or something
let asize = 10000000;
for i in start_index..asize {
if first_edge < 0 && cond_left(i) {
first_edge = i;
}
let right_index = asize - i -1;
if first_edge_right < 0 && cond_right(right_index) {
first_edge_right = right_index;
}
if (first_edge >= 0 && first_edge_right >= 0) {
break;
}
}
由于同时从两方面进行观察很重要,我认为没有避免可变变量的简单方法。
可以提高可读性的一件事是使用 option
而不是负数。否则代码没问题。
(你可能做的另一件事是当索引在中间相遇时打破循环,如果这意味着你的问题没有解决方案,但这不是 Rust 特定的。)
cond_left
和 cond_right
对于回答性能问题很重要。例如,用迭代器替换索引会有帮助吗?不知道 cond_left
做什么就不会说。
您担心的另一个问题是 first_edge
和 first_edge_right
是可变的。提议的 RFC allowing loops to return a value 可能是解决此问题的一种优雅方法。现在你可以用闭包模拟循环 return:
let (_first_edge, _first_edge_right): (i32, i32) = (||{
let (mut first_edge, mut first_edge_right) = (None, None);
// ...
return (first_edge.unwrap(), first_edge_right.unwrap());
})();
将-1
替换为None
可能会使变量变大。参见 。
将这个循环分成两个循环,一个获取 first_edge
,另一个检查剩余范围以获得 first_edge_right
似乎是正确的做法,但是 CPU 分支预测可能会将影响降至最低。
你需要做好选择的准备:
How would you translate that into Rust in a performant way?
while performance is important, readability is of course even more important
哪个对你来说更重要?以下是我将如何编写代码,假设我已经理解您的要求:
fn left_condition(i: usize) -> bool {
i > 1000
}
fn right_condition(i: usize) -> bool {
i % 73 == 0
}
fn main() {
let start_index = 300;
let asize = 10000000;
let left = (start_index..asize).position(left_condition);
let right = (start_index..asize).rev().position(right_condition);
println!("{:?}, {:?}", left, right);
}
我们从 left-to-right 迭代一次,从 right-to-left 迭代一次。我的 直觉 告诉我,这将提供具有简单分支预测的代码,以线性方式访问内存,两者都应该是可优化的。
然而,变量名asize
让我停顿了一下。它确实听起来像"array size"的缩写。如果是这样的话,那么我会 100% 推荐使用切片而不是数组索引。为什么?因为数组访问(foo[0]
)通常有边界检查的开销。我会用切片写点东西:
let data = vec![0; 10_000_000];
let start_index = 300;
let slice = &data[start_index..];
let left = slice.iter().position(|&i| left_condition(i));
let right = slice.iter().rev().position(|&i| right_condition(i));
但是,您的问题只有一个可能的正确答案:
使用分析器
使用分析器
使用分析器
使用分析器
只有知道你的实际数据,你对条件的实际实现,你剩下的代码运行,等等,你才能真正知道有多快会有的。
Therefore it has been a good thing to only have one loop instead of two - in order to avoid search from the beginning again
这对我来说不直观,所以我希望看到支持声明的分析结果。
我正在尝试将一些旧的 C 代码重写为 Rust——我是新手。我遇到的一个反复出现的问题是 C 代码有很多这样的循环:
for (i = startIndex; i < asize; i++)
{
if (firstEdge < 0 && condLeft(i))
{
firstEdge = i;
}
RightIndex = asize-1-i;
if (firstEdgeRight < 0 && condRight(RightIndex))
{
firstEdgeRight = RightIndex;
}
// Found both edges
if (firstEdge >= 0 && firstEdgeRight >= 0) {
break;
}
}
您将如何以高效的方式将其转化为 Rust?我的问题是,虽然我可能可以获得我想要的功能,但我不确定如何才能获得(大致)相同的速度。
这部分代码是我们代码中的主要瓶颈(至少这部分代码),在翻译时希望保留以下属性。
- 循环应该尽快中断,因为
asize
可能非常大。 firstEdge
和firstEdgeRight
大致同时被发现。因此,只有一个循环而不是两个循环是一件好事——为了避免再次从头开始搜索(尽管我认为这个解决方案会杀死预取器(但我不确定,也许旧机器 运行 代码甚至没有预取器))。
虽然性能很重要,但可读性当然更重要:)
EDIT 好的,这是我可能的 Rust 实现(cond_right()
和 cond_left()
被遗漏了)。
我考虑的事情是:
- 如果其他人必须从头开始实施,他们会这样写吗?
- 我真的需要让
first_edge
和first_edge_right
可变吗?它们在我的实现中,但我觉得不对,因为它们只分配了一次。
let mut first_edge = -1;
let mut first_edge_right = -1;
// Find first edge
let start_index = 300; // or something
let asize = 10000000;
for i in start_index..asize {
if first_edge < 0 && cond_left(i) {
first_edge = i;
}
let right_index = asize - i -1;
if first_edge_right < 0 && cond_right(right_index) {
first_edge_right = right_index;
}
if (first_edge >= 0 && first_edge_right >= 0) {
break;
}
}
由于同时从两方面进行观察很重要,我认为没有避免可变变量的简单方法。
可以提高可读性的一件事是使用 option
而不是负数。否则代码没问题。
(你可能做的另一件事是当索引在中间相遇时打破循环,如果这意味着你的问题没有解决方案,但这不是 Rust 特定的。)
cond_left
和 cond_right
对于回答性能问题很重要。例如,用迭代器替换索引会有帮助吗?不知道 cond_left
做什么就不会说。
您担心的另一个问题是 first_edge
和 first_edge_right
是可变的。提议的 RFC allowing loops to return a value 可能是解决此问题的一种优雅方法。现在你可以用闭包模拟循环 return:
let (_first_edge, _first_edge_right): (i32, i32) = (||{
let (mut first_edge, mut first_edge_right) = (None, None);
// ...
return (first_edge.unwrap(), first_edge_right.unwrap());
})();
将-1
替换为None
可能会使变量变大。参见
将这个循环分成两个循环,一个获取 first_edge
,另一个检查剩余范围以获得 first_edge_right
似乎是正确的做法,但是 CPU 分支预测可能会将影响降至最低。
你需要做好选择的准备:
How would you translate that into Rust in a performant way?
while performance is important, readability is of course even more important
哪个对你来说更重要?以下是我将如何编写代码,假设我已经理解您的要求:
fn left_condition(i: usize) -> bool {
i > 1000
}
fn right_condition(i: usize) -> bool {
i % 73 == 0
}
fn main() {
let start_index = 300;
let asize = 10000000;
let left = (start_index..asize).position(left_condition);
let right = (start_index..asize).rev().position(right_condition);
println!("{:?}, {:?}", left, right);
}
我们从 left-to-right 迭代一次,从 right-to-left 迭代一次。我的 直觉 告诉我,这将提供具有简单分支预测的代码,以线性方式访问内存,两者都应该是可优化的。
然而,变量名asize
让我停顿了一下。它确实听起来像"array size"的缩写。如果是这样的话,那么我会 100% 推荐使用切片而不是数组索引。为什么?因为数组访问(foo[0]
)通常有边界检查的开销。我会用切片写点东西:
let data = vec![0; 10_000_000];
let start_index = 300;
let slice = &data[start_index..];
let left = slice.iter().position(|&i| left_condition(i));
let right = slice.iter().rev().position(|&i| right_condition(i));
但是,您的问题只有一个可能的正确答案:
使用分析器
使用分析器
使用分析器
使用分析器
只有知道你的实际数据,你对条件的实际实现,你剩下的代码运行,等等,你才能真正知道有多快会有的。
Therefore it has been a good thing to only have one loop instead of two - in order to avoid search from the beginning again
这对我来说不直观,所以我希望看到支持声明的分析结果。