strong performance issue when using struct instead of multiple variables

[ZuseZ4]

I ran into an issue when working on a prime sieve.
I grouped three related variables (two arrays and an integer) into a struct to have less variables being passed around.
While profiling I noticed that the execution time went up from 2.8s to 7s when using the struct.
Based on some Discord hint´s I guess that shouldn´t be the case: https://discord.com/channels/273534239310479360/273541522815713281/843272480852672513

Here is my actual struct:

pub struct Aux {
    pub sieve: [u64;_AUX_SIEVE_WORDS_ as usize], 
    pub primes: [u32;_NUMBER_OF_AUX_PRIMES_],
    pub base: u32,
}

I created a gh repo, showing the different versions: https://github.com/ZuseZ4/perf_comp

Branch with_struct: I´m passing the struct by ref => 7s
Branch no_struct: I´m passing both arrays by ref, integer by value => 2.8s
Branch no_struct_ref: I´m passing both arrays and the integer by ref => 2.8s

Setup:
I use release mode, lto=true and target=native. (The last two seem to have no effect.)
rustc 1.52.1 (9bc8c42 2021-05-09)
(1.54.0-nightly (fe72845 2021-05-16) gives the same performance)
Ubuntu 20.04 (5.4.0-73-generic)
AMD® Athlon 200ge with 2x16 GB DDR4-3200

I could understand that an extra layer of indirection and therefore (if not removed by optimizations) pointer deref. could cause some performance cost, but I´m surprised about the large difference.

Did I miss something?

[leonardo-m]

It could be a good idea to minimize the code that shows the problem (and copy it here, if you want).

[ZuseZ4]

The gh version is already quite minimized @leonardo-m, but I now also removed all assertions and a little bit of initialization.
Removing more code led to execution times being too short or long to measure.

Site note, the compiler doesn´t notice that I´m not using the results anymore, so the entire calculation could be removed.
This doesn´t change when removing all time measurements / println calls.
However, that´s probably less interesting than the struct issue.

On my pc I now have execution times of ~4s with the struct vs 1.3s without the struct:

Edit: found some more things to remove, now the relevant update_aux_sieve function ended up being only 6 loc.
I hope that´s small enough to be valuable.

use std::time::Instant;

pub struct Aux {
    pub sieve: [u64;1 << 12],
    pub primes: [u32;6536],
}

pub const MARK_MASK: [u64;64] = {
    let mut res = [0; 64];
    let mut i = 0;
    while i < 64 {
        res[i] = 1 << i;
        i += 1;
    }
    res
};

#[inline(always)]
fn mark_2(arr: &mut [u64], index: usize) { arr[index >> 6] |= MARK_MASK[index & 63usize]; }
#[inline]
const fn test_2(arr: &[u64], index: usize) -> bool { arr[index >> 6] & MARK_MASK[index & 63usize] == 0 }

#[inline]
pub fn update_aux_sieve(aux_sieve: &mut [u64], aux_primes: &[u32]) {
    for i in 0..6536 {
        let mut j = aux_primes[i] * aux_primes[i];
        while j < (1 << 18) { 
            mark_2(aux_sieve, j as usize);
            j += aux_primes[i];
        }
    }
}

#[inline]
pub fn update_aux_struct_sieve(aux: &mut Aux) {
    for i in 0..6536 {
        let mut j = aux.primes[i] * aux.primes[i];
        while j < (1 << 18) { 
            mark_2(&mut aux.sieve, j as usize);
            j += aux.primes[i];
        }
    }
}


pub fn init_aux_primes() -> ([u64;1 << 12], [u32;6536]) {
    let mut aux_sieve:  [u64;1 << 12] = [0;1 << 12];
    let mut aux_primes: [u32;6536] = [1;6536];
    let start = Instant::now();
    println!("Initializing aux primes");
    for i in (3..256).step_by(2) {
        if test_2(&mut aux_sieve, i >> 1usize) {
            for j in (((i*i) >> 1)..32768).step_by(i) {
                mark_2(&mut aux_sieve, j as usize);
            }
        }
    }
    let mut j = 0;
    for i in 8..32768 {
        if test_2(&mut aux_sieve, i) {
            aux_primes[j] = 2 * (i as u32) + 1;
            j += 1;
        }
    }

    let end = Instant::now();
    let duration = end.duration_since(start);
    eprintln!("init_aux_primes took, {:?}\n", duration);
    (aux_sieve, aux_primes)
}

pub fn main() {

    let (sieve, primes)  = init_aux_primes();
    let mut aux = Aux { sieve, primes };

    let start = Instant::now();
    for _ in 0..8192 {
        //update_aux_struct_sieve(&mut aux); // slow
        update_aux_sieve(&mut aux.sieve, &aux.primes); // fast
    }
    let end = Instant::now();
    let duration = end.duration_since(start);
    eprintln!("duration {:?}\n", duration);
}

[hellow554]

For me the runtime does not differ... neither with your original example, nor with your second one.

945.0161ms vs 954.0564ms

What compiler version do you use (rustc --version --verbose)?

[ZuseZ4]

I´m on the latest stable version:

rustc 1.52.1 (9bc8c42 2021-05-09)
binary: rustc
commit-hash: 9bc8c42
commit-date: 2021-05-09
host: x86_64-unknown-linux-gnu
release: 1.52.1
LLVM version: 12.0.0

[hellow554]

Ok. To reproduce the issue, you do exactly what?
Please make a step by step instruction from cloning the repo to see the actual behavoir. Please use a clean directory for that (at best use cd $(mktemp -d)).

[ZuseZ4]

Sure, I created a new branch for that. I haven´t used mktemp before, but I created a new directory for that. Inside of it I ran:

git clone https://github.com/ZuseZ4/perf_comp
cd perf_comp
git checkout simple_example
cargo run --release 
vim src/main.rs // now call the fast path on line 82 instead of the slow on line 81.
cargo run --release // the exec time changed from 4s to 1.3s  

[hellow554]

(simple_example)> cargo run --release
   Compiling perf_comp v0.1.0 (/tmp/tmp.tNq5F6nEPZ/perf_comp)
    Finished release [optimized] target(s) in 0.51s
     Running `target/release/perf_comp`
Initializing aux primes
init_aux_primes took, 112.9µs

duration 950.4344ms

(simple_example)> vim src/main.rs
(simple_example)> cargo run --release
   Compiling perf_comp v0.1.0 (/tmp/tmp.tNq5F6nEPZ/perf_comp)
    Finished release [optimized] target(s) in 0.27s
     Running `target/release/perf_comp`
Initializing aux primes
init_aux_primes took, 111.4µs

duration 913.6341ms

I'm sorry.... I can't reproduce your issue... :(

[ZuseZ4]

Sure, updated it.
I also just checked with mktemp, still getting the same numbers.
Unfortunately I couldn´t test it on a server due to an outdated rust version.

 /t/t/perf_comp> cargo run --release                                                                                                                                   simple_example
   Compiling perf_comp v0.1.0 (/tmp/tmp.el9PvYMGpW/perf_comp)
    Finished release [optimized] target(s) in 0.89s
     Running `target/release/perf_comp`
Initializing aux primes
init_aux_primes took, 310.209µs

duration 4.192843814s

 /t/t/perf_comp> vim src/main.rs                                                                                                                                      simple_example?
 /t/t/perf_comp> cargo run --release                                                                                                                                 simple_example!?
   Compiling perf_comp v0.1.0 (/tmp/tmp.el9PvYMGpW/perf_comp)
    Finished release [optimized] target(s) in 0.43s
     Running `target/release/perf_comp`
Initializing aux primes
init_aux_primes took, 240.856µs

duration 1.472958919s

Nightly gives me the same performance.

That´s awkward, but thanks for testing!
Guess I will need to wait for someone else to see if it´s just a local issue.

[ZuseZ4]

https://play.rust-lang.org/?version=stable&mode=release&edition=2018&gist=19862feadf5a335ae4765e31d0a9c1fd

We probably don´t want to use the playground for serious benchmarking, at least for me the execution time varies greatly.
However, slow and fast are +- equal.
On my own PC I get:

/t/t/perf_comp> cargo +nightly run --release  
   Compiling perf_comp v0.1.0 (/tmp/tmp.el9PvYMGpW/perf_comp)
    Finished release [optimized] target(s) in 0.94s
     Running `target/release/perf_comp`
Initializing aux primes
init_aux_primes took, 159.632µs

slow 2.137172522s

fast 739.105792ms

[hellow554]

I'm calling @jonas-schievink for further actions. Could you add the correct tags and do you think it's worth to call the ICEBreaker-Cleanup-Crew?

[jonas-schievink]

Hmm, the slow version is consistently slower for me (on 1.52.0, as well as rustc 1.54.0-nightly (881c1ac40 2021-05-08)). Here's timings on 1.52.0, with -O:

Slow:

~> ./sieve
Initializing aux primes
init_aux_primes took, 105.982µs

duration 2.959215981s

~> ./sieve
Initializing aux primes
init_aux_primes took, 212.863µs

duration 2.948748385s

Fast:

~> ./sieve
Initializing aux primes
init_aux_primes took, 108.476µs

duration 695.428093ms

~> ./sieve
Initializing aux primes
init_aux_primes took, 214.827µs

duration 706.368691ms

[jonas-schievink]

(this is with the code in #85354 (comment), compiled directly with rustc)