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 ?