CODEWITHSUNDEEP
crusttranslate
Markus
Markus

Reputation: 2574

Translate performance critical loop from C to Rust

I'm experimenting with rewriting some old C code into Rust - which I'm new to. One recurring issue I have is that the C code has a lot of loops like this:

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;  
    }
}

How would you translate that into Rust in a performant way? My issue is that while I could probably get the functionality I want I'm not sure how to do it obtain (roughly) the same speed.

This part of the code is the main bottleneck in our code (this part of the code at least) and when translating it would like to keep the following properties.

  1. The loop should break ASAP since asize can be very large.
  2. Both firstEdge and firstEdgeRight are found roughly at the same time. Therefore it has been a good thing to only have one loop instead of two - in order to avoid search from the beginning again (even though I think this solution kills the prefetcher (but I'm not sure, maybe the old machine running the code doesn't even have a prefetcher)).

While performance is important, readability is of course even more important :)

EDIT Ok, here is a possible Rust implementation by me (cond_right() and cond_left() are left out). The things I think about is:

  1. Is this how other people would write it if they had to implement it from scratch?
  2. Do I really need to make first_edge and first_edge_right mutable? They are in my implementation, but it feels wrong to me since they are only assigned once.
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;
    }
}

Upvotes: 1

Views: 459

Answers (3)

Shepmaster
Shepmaster

Reputation: 432139

You need to be prepared to make a choice:

  1. How would you translate that into Rust in a performant way?

  2. while performance is important, readability is of course even more important

Which is actually more important to you? Here's how I would write the code, assuming that I've understood what you are asking for:

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);
}

We iterate once from left-to-right and once from right-to-left. My gut tells me that this will provide code with simple branch prediction that accesses memory in a linear manner, both of which should be optimizable.

However, the variable name asize gives me pause. It certainly sounds like an abbreviation of "array size". If that's the case, then I would 100% recommend using slices instead of array indices. Why? Because array access (foo[0]) usually has overhead of bounds checking. I'd write something with slices:

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));

However, there's only one possible true answer to your question:

Use a profiler

Use a profiler

Use a profiler

Use a profiler

Only knowing your actual data, your actual implementations of the conditions, the rest of the code you are running, etc., can you actually know how fast something will be.

Therefore it has been a good thing to only have one loop instead of two - in order to avoid search from the beginning again

This is nonintuitive to me, so I'd want to see profiling results that back up the claim.

Upvotes: 5

ArtemGr
ArtemGr

Reputation: 12567

cond_left and cond_right are important to answer the performance question. For example, will replacing an index with an iterator help? Not going to tell without knowing what cond_left does.

The other concern you have is that first_edge and first_edge_right are mutable. The proposed RFC allowing loops to return a value could be an elegant way to solve this problem. Right now you could emulate the loop return with a closure:

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());
})();

(In Playground).

Replacing -1 with None will likely make the variable larger. See Can I use the "null pointer optimization" for my own non-pointer types?.

Splitting this loop into two loops, one getting the first_edge and another examining the remaining range to get the first_edge_right seems like the right thing to do, but the CPU branch prediction will likely minimize the impact.

Upvotes: 2

kirelagin
kirelagin

Reputation: 13626

Since it is critical to keep looking from both sides simultaneously, I don’t think there is an easy way to avoid having mutable variables.

One thing that can improve readability is to use option instead of negative numbers. Otherwise the code is fine.

(Another thing you probably could do is to break the loop when the indices meet in the middle, if this means that there is no solution for your problem, but that’s not Rust specific.)

Upvotes: 0

Related Questions