Optimizing Stroke Data: From AoS to SoA

From vector<struct> to struct<vector>

Let's begin by contrasting the "before" and "after" states of our data structures. In the last lesson, we defined a StrokePoint and an AoS-style Stroke:

// "Before": The intuitive AoS layout
struct StrokePoint {
    float x;
    float y;
    float pressure;
};

struct StrokeAoS {
    // ... other stroke properties: color, etc.
    std::vector<StrokePoint> points;
};

This is the object-oriented approach. To refactor this to a data-oriented SoA layout, we invert the relationship between the struct and the vector. Instead of an array of structs, we create a struct of arrays.

// "After": The data-oriented SoA layout
struct StrokeSoA {
    // ... other stroke properties: color, etc.
    std::vector<float> x_coords;
    std::vector<float> y_coords;
    std::vector<float> pressures;
    
    // We also need a way to get the number of points
    size_t size() const {
        return x_coords.size();
    }
};

The fundamental unit of a Stroke is no longer a StrokePoint object. A Stroke is now a collection of parallel arrays, where the data for a single conceptual point is spread across these arrays at the same index.

This image provides a clear side-by-side comparison of the code for both defining and iterating over these two layouts.

This change is more than just syntax; it's a paradigm shift. We are no longer thinking about a "list of points" but rather about "columns of data" (positions, pressures, etc.).

Refactoring Data Operations

Changing the data layout necessitates changing the code that operates on that data. Let's examine the three most common operations.

1. Appending a New Point

This operation occurs continuously as the user draws a stroke.

• AoS: stroke.points.push_back({new_x, new_y, new_pressure});
  This is a single, atomic operation.

• SoA:

  stroke.x_coords.push_back(new_x);
  stroke.y_coords.push_back(new_y);
  stroke.pressures.push_back(new_pressure);
  

  This is more verbose, requiring three separate push_back calls. It's crucial that these arrays are always kept in sync and have the same size.

2. Iterating Over All Points (Rendering)

This is our performance-critical hot path.

• AoS:

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

  This is clean and idiomatic C++, but as we know, it fetches interleaved data (x,y,p,x,y,p,...), leading to poor cache utilization.

• SoA:

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

  This index-based loop might seem less elegant, but it is the source of our performance win. When processing x_coords, the CPU loads cache lines packed only with x coordinates. Every byte loaded is useful, enabling perfect spatial locality for the hardware prefetcher.

3. Removing a Point

Removing an element from the middle of a std::vector is an expensive operation in either layout, as it requires shifting all subsequent elements. A common, more efficient pattern is the "swap-and-pop" idiom, which swaps the element to be removed with the last element, and then pops the back. This is an O(1) operation but does not preserve the order of elements. For a user stroke, order is critical, so we must use vector::erase.

• AoS: stroke.points.erase(stroke.points.begin() + i);
  A single, albeit slow, operation.

• SoA:

  stroke.x_coords.erase(stroke.x_coords.begin() + i);
  stroke.y_coords.erase(stroke.y_coords.begin() + i);
  stroke.pressures.erase(stroke.pressures.begin() + i);
  

  Again, this is more verbose and requires careful synchronization across all three vectors.

The Intel article on memory layout transformations provides more C-style examples of these conversions. While it uses some non-standard array notation, the core logic is the same.

Hiding the Complexity: The Abstraction Layer

We've made a deliberate trade-off: sacrificing API elegance for performance. The raw SoA implementation is more verbose and error-prone. In high-performance systems development, the next step is to build an abstraction layer to reclaim that elegance without sacrificing the performance.

The goal is to provide an API that feels like AoS but is implemented with SoA underneath.

Let's enhance our StrokeSoA struct:

struct StrokeSoA {
    // Public interface
    void add_point(float x, float y, float pressure) {
        x_coords.push_back(x);
        y_coords.push_back(y);
        pressures.push_back(pressure);
    }
    
    void clear() {
        x_coords.clear();
        y_coords.clear();
        pressures.clear();
    }

    size_t size() const {
        return x_coords.size();
    }
    
    // ... more methods soon ...

// private: // Making these private enforces use of the clean API
    std::vector<float> x_coords;
    std::vector<float> y_coords;
    std::vector<float> pressures;
};

By adding methods like add_point and clear, we ensure the parallel arrays remain synchronized and hide the implementation detail from the user of the StrokeSoA class.

What about accessing an element? We can't return a StrokePoint struct because we'd have to construct it on the fly, defeating the purpose. This is where the proxy object pattern comes in. We can create a lightweight object that refers to the data for a single point.

// A non-owning proxy object that provides an AoS-like interface
// to a point within a StrokeSoA container.
class StrokePointProxy {
public:
    StrokePointProxy(StrokeSoA& stroke, size_t index)
        : m_stroke(stroke), m_index(index) {}

    float& x() { return m_stroke.x_coords[m_index]; }
    float& y() { return m_stroke.y_coords[m_index]; }
    float& pressure() { return m_stroke.pressures[m_index]; }
    
    // Constant versions for read-only access
    const float& x() const { return m_stroke.x_coords[m_index]; }
    // ... etc.

private:
    StrokeSoA& m_stroke;
    size_t m_index;
};

With this proxy, you could add a get_point(size_t i) method to StrokeSoA that returns a StrokePointProxy. This approach combines the performance of SoA with the ergonomic feel of AoS for random access, encapsulating the complexity perfectly.

Vittorio Romeo's work on data-oriented design provides excellent, practical examples of these abstractions in modern C++.

In his blog post accompanying the talk, Romeo demonstrates a complete, templated SoAFor wrapper that automates this entire process, providing a powerful and reusable abstraction.

While you don't need to implement a fully generic template like SoAFor for your project right now, understanding the principle is key: use C++ features to build a clean, safe interface over your raw, performant data layout.

Conclusion

In this lesson, we executed our decision to prioritize performance by refactoring our core data structure from an Array-of-Structs to a Struct-of-Arrays layout. This is a foundational change for building a high-performance graphics application.

Key Takeaways:

• Refactoring to SoA: The process involves changing from a std::vector<struct> to a struct containing multiple std::vectors. All code that accesses this data must be updated accordingly, typically from range-based loops to index-based loops.
• API vs. Implementation: The raw SoA layout leads to a more verbose and error-prone API. This is a common trade-off in systems programming.
• Abstraction is Key: We can mitigate the ergonomic downsides of SoA by creating an abstraction layer. Using methods on the container class and creating proxy objects allows you to provide a safe, intuitive API that feels like AoS while retaining the underlying performance of SoA.

You now have a high-throughput data structure at the heart of your application, ready to handle thousands of stroke points efficiently.

In our next lesson, we will shift our focus from single-threaded, data-layout optimization to multi-threaded performance. You will learn how to use std::thread to spawn and manage background threads, which will be essential for offloading heavy tasks like PDF parsing without freezing your application's UI.