AoS vs. SoA: Stroke Data Iteration Performance

The Anatomy of a Stroke: Defining the Contenders

First, let's define the fundamental unit of data for a single point in a stroke. For a pressure-sensitive input, each point needs at least a position and a pressure value.

// A single point in a user's stroke
struct StrokePoint {
    float x;
    float y;
    float pressure;
};

A complete stroke is an ordered collection of these points. The core of our analysis is deciding how to store this collection. We have two primary contenders, which should now be familiar.

Contender 1: Array of Structures (AoS)

This is the intuitive, object-oriented approach. A Stroke object contains a vector of StrokePoint objects.

// AoS representation of a stroke
struct StrokeAoS {
    // ... other stroke properties like color, thickness ...
    std::vector<StrokePoint> points;
};

In memory, this would consist of a contiguous block of StrokePoint structs: [p0, p1, p2, ...], where each p is (x, y, pressure).

Contender 2: Struct of Arrays (SoA)

This is the data-oriented approach. A Stroke object contains separate vectors for each component of the points.

// SoA representation of a stroke
struct StrokeSoA {
    // ... other stroke properties like color, thickness ...
    std::vector<float> x_coords;
    std::vector<float> y_coords;
    std::vector<float> pressures;
};

In memory, this results in three separate contiguous blocks: one for all x coordinates, one for all y coordinates, and one for all pressures.

Now, let's analyze how these two layouts perform under the common operations of your whiteboard application.

Trade-off Analysis: Operation by Operation

The optimal data layout is not universal; it is dictated by the access patterns of your code. We must analyze the key operations your application will perform.

1. Rendering (The Hot Path)

This is the most critical operation for a responsive feel. Every frame, the application must iterate through all points of all visible strokes to generate the geometry for Skia to draw. This loop can run on millions of points, 60 or more times per second.

• Access Pattern: Sequential iteration over a large number of points, reading the x, y, and pressure of each point.

With an AoS layout, the render loop looks like this:

for (const auto& point : stroke.points) {
    // Process point.x, point.y, point.pressure
}

For each point, the CPU fetches a 64-byte cache line. A StrokePoint is 12 bytes (3 * sizeof(float)). This means a single cache line can hold about five StrokePoint objects. While all the data for one point is together, the cache line is a mix of x, y, and pressure values.

With an SoA layout, the loop is different:

for (size_t i = 0; i < stroke.x_coords.size(); ++i) {
    // Process stroke.x_coords[i], stroke.y_coords[i], stroke.pressures[i]
}

When this loop processes the x_coords array, each cache line it loads is packed exclusively with 16 floating-point x coordinates. Every single byte loaded into the cache is useful data for the current task. This perfect spatial locality is ideal for the hardware prefetcher and enables the compiler to generate efficient SIMD instructions.

The article from CedarDB you reviewed in the last lesson provides benchmarks that directly mirror this scenario.

Verdict for Rendering: SoA is the decisive winner. The performance gain on this hot path is the most significant factor in our decision.

2. Random Access (Hit-Testing, Point Editing)

Less frequent, but still important, are operations that need all the data for a single, specific point. Examples include checking if a user's click is near a stroke (hit-testing) or allowing a user to edit a single point.

• Access Pattern: Random access to a point at an arbitrary index i, needing all of its fields (x, y, pressure) at once.

With AoS, this is simple and efficient:

StrokePoint p = stroke.points[i];
// use p.x, p.y, p.pressure

Since all the data for p is already contiguous in the StrokePoint struct, accessing it is typically a single cache miss, bringing all necessary data into the cache at once.

With SoA, the operation is more fragmented:

float x = stroke.x_coords[i];
float y = stroke.y_coords[i];
float pressure = stroke.pressures[i];

This requires three separate array indexing operations. Since x_coords, y_coords, and pressures are in different memory regions, this could potentially lead to three separate cache misses, making it significantly slower than the AoS approach for this specific task.

The "Update Performance" benchmark in the CedarDB article illustrates this principle. Updating two fields of a single record was faster with AoS because the data was already in the same cache line.

Verdict for Random Access: AoS is the clear winner for its simplicity and superior cache performance when accessing a whole object.

3. Adding and Removing Data

Finally, let's consider how we modify the stroke data.

• Appending new points (while drawing): This happens continuously as the user draws.

  • AoS: stroke.points.push_back({new_x, new_y, new_p});. A single, clean operation.
  • SoA: stroke.x_coords.push_back(new_x); stroke.y_coords.push_back(new_y); stroke.pressures.push_back(new_p);. This is more verbose and requires three separate push_back calls. The performance is likely comparable, but the code is less elegant.

• Adding/Removing entire strokes (Undo/Redo): This involves managing a collection of Stroke objects, e.g., std::vector<StrokeAoS> or std::vector<StrokeSoA>.

  • The operation itself (push_back or pop_back on the vector of strokes) is largely the same.
  • The main difference is the complexity of the Stroke object itself. A StrokeAoS is a simpler object to manage (one vector) than a StrokeSoA (three vectors).

Verdict for Data Modification: AoS offers a simpler, more intuitive API, making the code easier to write and maintain.

Making the Decision: Prioritizing the Hot Path

Let's summarize our analysis in a table:

As a systems programmer building for performance, your guiding principle must be: optimize for the hot path. Rendering is, without a doubt, the hottest path in your application. The work done here happens millions of times more often than any other operation.

The massive performance gain that SoA provides for rendering outweighs the increased complexity and slight performance penalty it introduces in colder paths like random access or data entry. We are making a deliberate trade-off: sacrificing some elegance in less critical code paths for a huge win where it matters most.

Vittorio Romeo's talk provides an excellent, dense summary of these exact trade-offs.

The complexity of SoA can be managed. For example, the awkwardness of random access can be hidden behind an abstraction, like a proxy StrokePointRef object that provides an AoS-like interface while still using an SoA layout under the hood. We accept this complexity as the cost of performance.

Conclusion

Today we moved from theory to practice. By analyzing the specific access patterns of your whiteboard application, we've navigated the performance trade-offs between Array-of-Structs and Struct-of-Arrays for stroke data.

Key Takeaways:

• Analyze by Operation: The choice between AoS and SoA depends entirely on the access patterns of your most frequent and performance-critical operations.
• Identify the Hot Path: For a graphics application, the rendering loop is almost always the hot path that demands the most optimization.
• SoA for Rendering: The SoA layout is vastly superior for rendering because it maximizes cache line utilization, enables hardware prefetching, and is ideal for SIMD vectorization.
• Trade-Offs are Necessary: We accept that SoA makes random access and data modification more complex, but this is a worthwhile trade-off for the massive performance gain in the rendering hot path.

Based on this analysis, we have made a crucial design decision: we will use a Struct-of-Arrays layout for our stroke data.

In the next lesson, we will put this decision into action. You will refactor the stroke data storage from a conceptual AoS layout to a concrete SoA implementation, laying the high-performance foundation for your application's drawing canvas.