Create a new variable in Index

help
1

I am trying to use data-oriented design in some code of mine, and the preliminary results are pretty good.

this part is only for context, skip it if you are in hurry

So I have an array of structs (Part) containing both hot (x, y) and cold (name) parts of data. I have heard that this is bad for cache performances, so I would like to transform it to a struct of arrays. But I still want the nice interface given by a struct, with impl and all that. So here is an attempt to benchmarck the differents solutions.

#![feature(test)]
extern crate test;

// Array of structs
mod aos {
    #[derive(Clone, Debug)]
    pub struct Part {
        pub x: f64,
        pub y: f64,
        pub name: String
    }

    impl Part {
        pub fn new() -> Part {
            Part{x: 0.0, y: 0.0, name: String::from("He")}
        }

        pub fn move_by(&mut self, dx: f64, dy: f64) {
            self.x += dx;
            self.y += dy;
        }
    }
}

// Manual struct of array
mod soa_manual {
    #[derive(Clone, Debug)]
    pub struct PartVec {
        pub x: Vec<f64>,
        pub y: Vec<f64>,
        pub name: Vec<String>
    }

    impl PartVec {
        pub fn new(size: usize) -> PartVec {
            PartVec{x: vec![0.0; size], y: vec![0.0; size], name: vec![String::from("He"); size]}
        }

        pub fn move_by(&mut self, dx: &Vec<f64>, dy: &Vec<f64>) {
            for (i, x) in self.x.iter_mut().enumerate() {
                *x += dx[i];
            }
            for (i, y) in self.x.iter_mut().enumerate() {
                *y += dy[i];
            }
        }
    }
}

// Automatic struct of array
mod soa {
    #[derive(Clone, Debug)]
    pub struct PartVec {
        x: Vec<f64>,
        y: Vec<f64>,
        name: Vec<String>,
    }

    impl PartVec {
        pub fn new(size: usize) -> PartVec {
            PartVec{
                x: vec![0.0; size],
                y: vec![0.0; size],
                name: vec![String::from("He"); size],
            }
        }

        pub fn get_mut(&mut self, i: usize) -> PartMut {
            PartMut{x: &mut self.x[i], y: &mut self.y[i]}
        }

        pub fn len(&self) -> usize {
            self.x.len()
        }
    }

    pub struct PartMut {
        x: *mut f64,
        y: *mut f64,
    }

    impl PartMut {
        pub fn move_by(&mut self, x:f64, y:f64) {
            unsafe {
                *self.x += x;
                *self.y += y;
            }
        }
    }
}

#[cfg(test)]
mod tests {
    const N: usize = 10000;
    use test::Bencher;

    #[bench]
    fn aos(b: &mut Bencher) {
        use aos::*;

        let mut parts = vec![Part::new(); N];
        b.iter(|| {
            for part in parts.iter_mut() {
                part.move_by(3.0, 2.0);
            }
        });
    }

    #[bench]
    fn soa_manual(b: &mut Bencher) {
        use soa_manual::*;

        let mut parts = PartVec::new(N);
        let dx = vec![3.0; N];
        let dy = vec![2.0; N];
        b.iter(|| parts.move_by(&dx, &dy));
    }

    #[bench]
    fn soa(b: &mut Bencher) {
        use soa::*;

        let mut parts = PartVec::new(N);
        b.iter(|| {
            for i in 0..parts.len() {
                let mut part = parts.get_mut(i);
                part.move_by(3.0, 2.0);
            }
        });
    }
}

With the last nightly build, cargo bench gives me

running 3 tests
test tests::aos        ... bench:      14,730 ns/iter (+/- 2,039)
test tests::soa        ... bench:       9,906 ns/iter (+/- 1,358)
test tests::soa_manual ... bench:      12,950 ns/iter (+/- 2,145)

test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured

So the structure of arrays (soa) give me very good results, even better that the (unoptimized) manual implementation.

My real problem here

Now I want to add nice syntactic sugar to this code, and in particular indexing. So I isolated my problem in

use std::ops::Index;

struct MyVec {
    x: Vec<f64>,
    y: Vec<f64>,
}

struct MyVecView {
    x: *const f64,
    y: *const f64,
}

impl Index<usize> for MyVec {
    type Output = MyVecView;
    fn index<'a>(&'a self, i: usize) -> &'a MyVecView {
        &MyVecView{x: &self.x[i], y: &self.y[i]}
    }
}

And here the compiler complains that borrowed value does not live long enough, which is true. But If I try to return a variable directly:

impl Index<usize> for MyVec {
    type Output = MyVecView;
    fn index(&self, i: usize) -> MyVecView {
        MyVecView{x: &self.x[i], y: &self.y[i]}
    }
}

Then I get method index has an incompatible type for trait.

How can I make index to return a new variable, and not a reference ?

The other solution I can think of (using a static variable in the function) feels like a bad idea. What happen if more than one thread try to index MyVec at different indexes ?

2

This may be sidestepping the issue, but it looks like you're always accessing x and y at the same index, why not put them together into one vector? That way you can return a reference that is actually valid.

struct MyVec {
    coords: Vec<MyVecView>,
}

struct MyVecView {
    x: f64,
    y: f64,
}

impl Index<usize> for MyVec {
    type Output = MyVecView;
    fn index<'a>(&'a self, i: usize) -> &'a MyVecView {
        &self[i]
    }
}
3

Mainly because this case is a simpler than the real code, where I got positions and velocities which are already [f64; 3], and that I will not access all of them every time.

4

Boiling down the problem is great and all, but a detail that might lead to an easy solution could have gotten lost in the process.