Circular Buffers & Min-Max Trees for Dynamic Data

From Infinite Growth to a Rolling Window

The core idea is to move from a data store that keeps all historical data to one that only keeps a "rolling window" of the most recent data points. This is a classic use case for a circular buffer, also known as a ring buffer. You've already implemented a sophisticated lock-free version for your SPSC queues; now, we'll apply the same fundamental concept for data storage in the UI thread.

Let's start by refreshing our understanding of the ring buffer data structure.

The key takeaway is that a circular buffer uses a fixed block of memory and a set of indices that wrap around from the end of the block to the beginning. When the buffer is full, adding a new element overwrites the oldest one.

Implementing a Circular Buffer in C++

For our plotter, we don't need the complexity of atomic indices since the buffer will be accessed exclusively by the UI thread. A simple class encapsulating a std::vector and a head pointer will work perfectly.

Here is a C++ implementation for a CircularBuffer.

#include <vector>
#include <numeric> // For std::iota

template <typename T>
class CircularBuffer {
public:
    explicit CircularBuffer(size_t capacity) : m_capacity(capacity) {
        m_data.reserve(m_capacity);
    }

    // Add a new element, overwriting the oldest if full.
    void add(T value) {
        if (m_data.size() < m_capacity) {
            m_data.push_back(std::move(value));
        } else {
            m_data[m_head] = std::move(value);
            m_head = (m_head + 1) % m_capacity;
        }
    }

    // Return all elements in their logical order (oldest to newest).
    std::vector<T> get_all_elements() const {
        if (m_data.size() < m_capacity) {
            // Buffer is not full yet, data is already in order.
            return m_data;
        }

        // Buffer has wrapped, we need to "unroll" it.
        std::vector<T> ordered_data;
        ordered_data.reserve(m_capacity);

        // Add elements from head to the end of the vector
        ordered_data.insert(ordered_data.end(), m_data.begin() + m_head, m_data.end());
        
        // Add elements from the beginning of the vector up to head
        ordered_data.insert(ordered_data.end(), m_data.begin(), m_data.begin() + m_head);

        return ordered_data;
    }
    
    size_t size() const {
        return m_data.size();
    }

    size_t capacity() const {
        return m_capacity;
    }

private:
    std::vector<T> m_data;
    size_t m_capacity;
    size_t m_head = 0; // Points to the oldest element (next to be overwritten)
};

Key parts of this implementation:

• add(T value): This method handles adding new data. Initially, it behaves like a regular vector. Once the capacity is reached, it starts overwriting the oldest elements, advancing the m_head pointer with a modulo (%) operation to ensure it wraps around.
• get_all_elements(): This is the crucial helper function. Our min-max tree expects a flat, ordered array of data. Since the data in our circular buffer might be "broken" across the wrap-around point (e.g., oldest elements at index 500-999, newest at 0-499), this function "unrolls" it into a new, temporary vector that is logically ordered from oldest to newest.

Rebuilding the Min-Max Tree from the Circular Buffer

Now we can integrate this into our LODPlotter. The change is straightforward:

1. Replace the std::vector<float> m_all_data member with CircularBuffer<float> m_buffer.
2. Modify the addData method to use the new buffer and its get_all_elements helper.

// In your LODPlotter class
class LODPlotter {
public:
    LODPlotter() : m_buffer(100000) {} // Example: Store 100k points

    // ...

    void addData(const std::vector<float>& new_points) {
        // 1. Add all new points to our circular buffer.
        for (const auto& point : new_points) {
            m_buffer.add(point);
        }

        // 2. The data has changed, so the MinMaxTree is invalid.
        //    Get the unrolled data and rebuild the tree.
        m_minMaxTree.build(m_buffer.get_all_elements());
    }

private:
    CircularBuffer<float> m_buffer;
    MinMaxTree m_minMaxTree;
    // ...
};

With this change, your plotter now operates with a fixed memory budget. It continuously displays the most recent 100,000 data points (or whatever capacity you choose), discarding the oldest ones as new data arrives. This is exactly the behavior required for a robust, long-running profiler.

The "Rebuild" Strategy vs. More Complex Alternatives

Our "rebuild on change" strategy is simple and robust. However, it's worth understanding the performance trade-offs. Each time we add even one new data point, we re-process the entire buffer capacity to build the tree. This is an O(N) operation, where N is the buffer capacity.

For a problem like this—finding the min/max in a sliding window—more complex and efficient algorithms exist.

The approach described in the link is significantly faster in terms of algorithm complexity, but it adds considerable implementation complexity (heaps, hash maps). For our application, where the plotter updates at UI framerates (e.g., 60Hz) and the buffer rebuild is already very fast, the simplicity and correctness of the "rebuild on change" strategy is a winning trade-off. It's a perfect example of choosing the right tool for the job and not over-engineering.

Conclusion

You have now made a critical improvement to your plotter. By replacing the infinite std::vector with a CircularBuffer, you have achieved a constant memory footprint, making your telemetry tool stable for long-running analysis.

Key Takeaways:

• A circular buffer is the ideal data structure for storing a fixed-size "rolling window" of data.
• It can be implemented with a fixed-size array/vector and a head pointer that wraps around using the modulo operator.
• When data in a circular buffer is overwritten, any aggregate data structure built on it (like our min-max tree) must be updated.
• The "rebuild on change" strategy is a simple and robust way to keep the min-max tree synchronized with the circular buffer's state.

What's Next?

Your plotter is now robust and displays live data. The next step is to make it interactive. In the following lesson, we will dive back into ImGui and user input to implement interactive zooming and panning with the mouse. The solid data foundation you've built today will make this surprisingly straightforward.