How to parallelize the sum of a custom struct into a different struct

Hi everyone,

I am struggling with making some code faster and I think it would gain from parallelization. I have a vector that holds a struct with many fields that I want to aggregate (sum) the fields and produce a resulting structure that is similar but not identical to the one being aggregated.

If the struct was identical I would probably go about it by implementing the Sum Trait and doing a simple map followed by sum. However, in this scenario I'm afraid I don't see the clear path forward. How would you do it?

Here is a minimal working example: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4059af4206dc3ac6e62690c2c8709543

Some things to note are that the struct to be aggregate has data types that consume less memory like u16 while the aggregated one may use something like u64 to store the sum of all the u16s. Also, at least one field may not need to be aggregated.

Please feel free to suggest different ways of doing things as well. I wonder for example if the type casting there (i.e. as u32) is the most idiomatic way of doing such a thing.

Thank you for your guidance!

For parallelizing, rayon is the go to library. Here's an example of a bit more idiomatic version of your code along with a parallel implementation


fn sum_points1(points: &[Point]) -> AggregatedPoint {
    points.iter()
    .fold(AggregatedPoint::default(),|mut agg, point| {
        agg.x += point.x;
        agg.y += point.y;
        agg.n += point.n as u32;
        agg
    })
}

fn par_sum_points1(points: &[Point]) -> AggregatedPoint {
    use rayon::prelude::*;
    points.par_iter()
    .fold(|| AggregatedPoint::default(),|mut agg, point| {
        agg.x += point.x;
        agg.y += point.y;
        agg.n += point.n as u32;
        agg
    })
    .reduce(|| AggregatedPoint::default(),|mut sum, agg| {
        sum.x += agg.x;
        sum.y += agg.y;
        sum.n += agg.n as u32;
        sum
    })
}

Playground Link

As far as the type cast is concerned, that's totally fine for going from u8 to u32.

I did change the argument to be a slice instead of a reference to a Vec. This just avoids one level of indirection, since a Vec holds its own pointer to the data. You really never need &Vec in practical use (a similar argument holds for the use of &str instead of &String).

3 Likes

I have used rayon in the past and love it but I did not know how to move forward. I would not have thought of adding the reduce. Thank you for showing me the way and thank you for the additional tips. I really appreciate it! You made my day.

One other note. While as is commonly used, you need to be careful because it can truncate value going from a larger type to a smaller one (such as casting 1000 to a u8). The safer approach is .into() and .try_into(). .into() is only defined for types that losslessly convert between types. And try_into() is defined for conversions that might truncate data. The annoyance with them though is that rust can't always infer the type you want when using them, so you'd need to do one of the following in this case if you wanted to use them instead

let n: u32 = point.n.into();
agg.n += n;

or

agg.n += Into::<u32>::into(point.n);

That should be fine, just impl Sum<Point> for AggregatePoint, and/or Sum<&Point>. Rayon's sum will use that too, but it also needs the self-Sum, because it ultimately amounts to about the same as the fold-reduce mentioned above.

1 Like

Alternatively, u32::from can be used.

1 Like

True! I even use that in my code, but got distracted getting into to work.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.