Pixel to Struct of Arrays (and back again?)

[okaneco]

Sometimes when working with colors I want something more like the following, where each component is in its own container.

pub struct RgbSoa<S: RgbStandard = Srgb, T: Component = f32> {
    pub red: Vec<T>,
    pub green: Vec<T>,
    pub blue: Vec<T>,
    pub standard: PhantomData<S>,
}

You might want to operate on only one component at a time and this layout can give a performance benefit by operating on more values at once. Or, you might not care about the order of each container since you're treating it more as data for calculation rather than as individual colors.

I'm usually not concerned about converting from one Soa type to another, just that I can get it back to the base color type. Converting back to an Array of Structs (Vec<Rgb>) is not as hard to do for the user as setting up SoA is. It might be nice if some of the base struct's color operations could be derived for their Soa counterparts.

One drawback to this layout is that a lot of general color operations access all 3 or 4 color struct fields at once. Thus, there's no performance benefit to being in RgbSoa over Vec<Rgb> unless you specifically know you need it. This idea might be too niche/large to make sense to maintain.

Curious to hear what you think or if you've had any thoughts on this before.

[Ogeon]

I have been moving in that direction with things like SIMD support, but that's more for working with all components. I think it depends a lot on the type of operations. Do you have any examples of when SoA tend to be preferred?

Going to and from SoA tend to be a zip and unzip routine, which may be better handled by something like itertools. Unless it's trivial enough. I suppose what could be helpful is to maintain the color type so it's not mistakenly changed. Maybe also iteration without manually chaining zip calls. 🤔 Is this something you think would be helpful?

[okaneco]

I don't have a definitive answer for when to prefer one over the other, it really depends. I often start with AoS unless there's an immediately compelling reason to use SoA, and after implementing it, I'll check if SoA has better performance (if it makes sense to rewrite that way).

The use cases I have are less specific, and indeed, it would be more around the ergonomics of going to and from the different formats. Maintaining the color type information was one of the motivating factors, and handling iteration/zipping in a more convenient way was another.

Sometimes when using color spaces where luminance is separated from chroma like in Lab, some filters were slightly faster only operating on the Vec<f32> for L than Vec<Lab<f32>>. One example of this is if you're smoothing out/repairing luminance in an image. Having the components in more SIMD-convenient or chunks_exact-accessible formats is where I've seen the most speed out of this format, usually in the form of reductions that you can parallelize with some inner accumulators.

I wrote up a test program with two ordinary tasks. After opening an image and converting it to Lab from Rgb, the first task is to find the max L, a, and b components. The second task is to find the average color of the image buffer. After that, it prints the results and time taken. The three main ways I'd solve this problem are by writing the obvious for-loop or fold, using chunks with the Vec<Lab>, or using chunks with the component vectors.

Sample output for a 750x1000 pixel image on my computer.

100 Runs

--Max components--
AoS: 278.079107ms - Lab {
    l: 100.0,
    a: 30.209967,
    b: 73.09378,
    white_point: PhantomData<palette::white_point::D65>,
}
AoS Chunks: 135.04127ms - Lab {
    l: 100.0,
    a: 30.209967,
    b: 73.09378,
    white_point: PhantomData<palette::white_point::D65>,
}
SoA: 82.25373ms - Lab {
    l: 100.0,
    a: 30.209967,
    b: 73.09378,
    white_point: PhantomData<palette::white_point::D65>,
}
--Average color--
AoS: 82.286697ms - Lab {
    l: 80.66697,
    a: 5.7431374,
    b: -11.138302,
    white_point: PhantomData<palette::white_point::D65>,
}
AoS Chunks: 71.112901ms - Lab {
    l: 80.75986,
    a: 5.7401066,
    b: -11.125566,
    white_point: PhantomData<palette::white_point::D65>,
}
SoA: 59.409152ms - Lab {
    l: 80.75986,
    a: 5.7401066,
    b: -11.125566,
    white_point: PhantomData<palette::white_point::D65>,
}

1 Run, the average task is noisy but chunks are faster in both cases

--Max components--
AoS: 2.785985ms - Lab {
    l: 100.0,
    a: 30.209988,
    b: 73.093834,
    white_point: PhantomData<palette::white_point::D65>,
}
AoS Chunks: 1.337945ms - Lab {
    l: 100.0,
    a: 30.209988,
    b: 73.093834,
    white_point: PhantomData<palette::white_point::D65>,
}
SoA: 822.609µs - Lab {
    l: 100.0,
    a: 30.209988,
    b: 73.093834,
    white_point: PhantomData<palette::white_point::D65>,
}
--Average color--
AoS: 854.953µs - Lab {
    l: 80.666916,
    a: 5.7431355,
    b: -11.138291,
    white_point: PhantomData<palette::white_point::D65>,
}
AoS Chunks: 784.977µs - Lab {
    l: 80.759895,
    a: 5.740104,
    b: -11.125566,
    white_point: PhantomData<palette::white_point::D65>,
}
SoA: 726.819µs - Lab {
    l: 80.759895,
    a: 5.740104,
    b: -11.125566,
    white_point: PhantomData<palette::white_point::D65>,
}

Anything using chunks and not caring about serial floating point operation order will probably end up being a noticeable amount faster with the accumulator method. You still have to write out all the parts by hand like updating the accumulators and reducing at the end, but I think the extra code is worth the performance difference because the transformation is rather mechanical. Chunk size can take some tuning on the user's end for getting the fastest code gen out. This is more a demonstration of the alternate format having potential for better performance than being some general problem I'm looking to solve. I can treat the SoA struct as if it were in AoS format with zipping the components but I've never been able to get the performance benefits of SoA with strided access from AoS, which is where I think something like this feature could be helpful.

[Ogeon]

Thanks a lot for elaborating! That performance difference alone is a good motivation, especially if there's more than one step in the pipeline.

I think it would be a good addition to the library and I bet there are some nice utilities that can be built around it. A good starting point could be to make it possible to construct and iterate over types like Rgb<Vec<T>>.

Things like the fine tuning and when to use which algoritm is very application specific, as you said, so that's the kind of thing I prefer to just provide tools for and not try to be smart about. So something like an interface for chunk iteration and making it fast and easy to change the correct values across the arrays.

I added implementations of some of the traits like Lighten for arrays before, as an extra convenience for when a naive loop is good enough. The same could be done for SoA types if it doesn't clash with SIMD implementations.

Is there anything else that would be good to add?

[okaneco]

That's what I was thinking, supply the baseline tools to build around and make it a more convenient place to experiment. I think giving construction and iterating tools should offer most functionality anyone would want out of the gate through what you've mentioned and things like the iterator traits in the Rust prelude for basic needs (also Index and IndexMut).
https://doc.rust-lang.org/stable/std/prelude/index.html

My experience with writing my own SoA wrappers for myself is that it's easy to explode interface surface area by reimplementing the Vec/array/slice interfaces for things you commonly use or think you'll use. That should be mostly avoidable in this instance because I find when dealing with color data that the container length doesn't change after construction. I mostly think the user should write their own convenience functions because we can't make everyone happy, but there are some operations like clear that feel to me like they should be part of the basic implementation (push and pop might be here too). This is one of those things you'll probably decide on a case by case basis that evolves decision-making policy over time.

The only other thing I've thought about is how chunks could be used internally to make it potentially faster to do an operation, such as an apply/for_each or apply_chunks/for_each_chunks, that can do better than a naive loop. But I'm not sure there's a one-size-fits-all solution so users can write their own fairly easily. The documentation can include an example chunks_exact formula to show how to get the most out of the SoA format.

---

Have you tried to apply SIMD to colorspace conversion? I'm not sure how much benefit there'd be and I know some parts are probably as fast as they can be like the matrix multiplication, but I've noticed in some programs I've written that Srgb<->Lab can be a dominating time factor in calculation. This might be unavoidable but just figured I should ask. 🙂

Edit: Ahh, I'm just seeing #278 now

[Ogeon]

Great! I agree that the basics (construction, indexing and iteration) should be the first step. It should cover most cases and the rest would be extensions of that. It also helps that we can delegate much of the actual work to Vec and slice.

Have you tried to apply SIMD to colorspace conversion?

Yes and I see you found it. The results were varied and seem to depend a lot on the amount of branching if I remember correctly. It's not covering everything yet and is still a bit of a proof of concept. I also didn't really make an effort of optimizing further than preserving the current performance, so there's probably still some untapped potential.

I would like to take it further, though. I think there's value in not having to convert back and forth between SIMD and scalar form if the performance is still at least as good.

Edit: you probably saw it but here's a small surface level analysis of the benchmarks #278 (comment)

[Ogeon]

I opened #305 for keeping track of this. 🙂 I hope I summarized it well.