Rethink data organization

[michalsustr]

Currently you need to pass PlotPoints resp. Vec<PlotPoint { x, y }> as inputs for plotting. This is called AoS (array-of-structures). AoS is in my humble opinion not as good as SoA.

Reasoning

AoS is inefficient:

1. A common use-case for plotting is time-series plots, with shared x-axis. The AoS forces you to make a copy of xs for each line plot, ~doubling memory requirements.
2. It does not allow to slice data efficiently, i.e. to manage ranges of data given current plot bounds.
3. Poorer cache locality for typical access patterns (e.g. compute min/max for plot bounds)
4. It is hard to extend. Some plot items may require more data (i.e. recently colormap) which forces every user of PlotPoint to pass even more data, which may not be used at all, and breaks public API every time.

Better alternative in terms of performance is generally SoA (structure-of-arrays):

5. SoA better aligns with SIMD / most graphics APIs and shaders prefer SoA-like layouts.
6. Addresses weakness points of AoS.

Disadvantages of SoA:

7. xs and ys must have the same length, but this is no longer enforced by the type system - requires runtime checks or truncation.
8. Passing two slices is more verbose than a single Vec.

Proposal

Proposal is to get rid of Vec<PlotPoint { x, y }> and instead pass xs: &[f32] and ys: &[f32]).
This would be a major breaking change.

Related PRs/issues

#76

[michalsustr]

@bircni @kitizz I'm curious about your opinion. WDYT?

[bircni]

hmm how about delaying this to after the release of 0.35 and then making the majro change?

[kitizz]

I think it's worth highlighting that when comparing AoS vs. SoA on the interface, one will be more convenient for some, and the other more convenient for others. Depending on how their source data is organized.

5. SoA better aligns with SIMD / most graphics APIs and shaders prefer SoA-like layouts.
6. Poorer cache locality ...

Please correct me if I'm wrong, but I believe most APIs that use SoA still keep the vertex positions together. Like there'll be an array of point positions, and another for velocities, etc. This is because when you're drawing the point, you need both its X and Y, but maybe not all the other data.

Further, I think when you see the most performance benefits for SoA is when the AoS structure gets quite wide/large. Before making such a change for performance reasons, it would be good to plan/predict the maximum expected size of PlotPoint*. And put together some benchmarks that make a compelling performance case.

4. It is hard to extend.

* I'm struggling to think of extra attributes you might want to add to PlotPoint. But I haven't thought deeply about it, so there may well be. And in #76, the data doesn't need to live inside the PlotPoint, that seems fine as it is.

1. A common use-case for plotting is time-series plots, with shared x-axis ... ~doubling memory requirements.

Have there been reports of this being an issue? I wonder if the PlotPoints enum could be extended to address such a use-case. Even if it's not a performance issue, but could be helpful ergonomically.

2. It does not allow to slice data efficiently...

I'm not sure if I follow this one. I might need an example to understand the problem better.

---

My instinct is that, while this might enhance usability for some, this kind of change will be an overall downgrade in the ergonomics of the egui_plot API for users. But this statement should be given very little weight since I don't really know the user base for the library. A survey is the only objective way to know and that seems like overkill.

(I have a bias, in that I'm usually dealing with geometric point data, and parametric curves. Which works well with the current API)

I'm also skeptical that separating X and Y will provide any performance gains (benchmark required).

In lieu of benchmarks/profiling showing significant bottlenecks for AoS in PlotPoints, I think the most compelling reason for the switch is reason (1.) from an ergonomics perspective.

[michalsustr]

Thank you, I think those are compelling arguments and without benchmarks showing otherwise it indeed does not make sense, so I will not put energy into this now.

Another line of thinking/exploration I'd like to write down.

I was researching existing plotting libs. In the dev-line of "grammar-of-graphics" libs I like the formalization of Vega-Lite. I think at least adopting their nomenclature would be useful, I find it well though out.

Why it's relevant here: What they do is they specify data/transform layer. I was thinking off-loading this to a library like polars (with its lazy syntax) would enable egui_plot to not have to reimplement all kinds of aggregations.
Polars uses column-like representations. But they are internally chunked :-/ So those would have to be either make contiguous (with df.rechunk_mut) or egui_plot support even more complicated API with multiple slices.

I made a polars example, little bit in the direction of pivot tables and plotting. Basically sliced API would allow getting rid of the highlighted lines. I am not too happy with how the code looks, that's mainly due to polars verbosity of return/option types. So again not even sure if we want to support a beast like that. The library seems better on the python side than on the rust side.

[kitizz]

Oh yeah, I've come across Vega-Lite, but haven't looked at it deeply. Sounds like a well-loved library. I'll read up on that, I do enjoy a well thought-out nomenclature 😅

Ooof, yeah, that example looks tedious. A polars wrapper could make sense if it's becoming a defacto standard for data science/analysis in the rust community. Though if possible it seems best to keep it in a separate crate, or at the very least its own separate module with a very clear delineation from the core of egui_plot

[michalsustr]

I am thinking about it in similar ways.