I have a string of functions that generate arrays and return them up a call stack. Roughly the function signatures are:

fn solutions(...) -> [[u64; M]; N] {                         /* run iterator on lots of problem sets */ }
fn generate_solutions(...) -> impl Iterator<Item=[u64; M]> { /* call find_solution on different problem sets */ }
fn find_solution(...) -> [u64; M] {                          /* call validate_candidate with different candidates to find solution */ }
fn validate_candidate(...) -> Option<[u64; M]> { 
    let mut table = [0; M];
    // do compute intensive work
    if works { Some(table) } else { None }
 }

My understanding was that Rust will not actually copy the arrays up the call stack but optimize the copy away.

But this isn't what I see. When I switch to Vec, I see 20x speed improvement with the only change being [u64;M] to Vec<u64>. So, it is totally copying the arrays over and over.

So why array and not Vec, everyone always asks. Embedded environment. no_std.

How to encourage Rust to optimize these array copies away?

CodePudding user response：

Unfortunately, guaranteed lack of copies is currently an unsolved problem in Rust. To get the characteristics you want, you will need to explicitly pass in storage it should be written into (the “out parameter” pattern):

fn solutions(..., out: &mut [[u64; M]; N]) {...}
fn find_solution(..., out: &mut [u64; M]) {...}
fn validate_candidate(table: &mut [u64; M]) -> bool { 
    // write into table
    works
}

Thus you will also have to find some alternative to Iterator for generate_solutions (since using Iterator implies that all the results can exist at once without overwriting each other).