Padded ScrollingBuffer support

[ToppDev]

Hello,

this is a feature request, as I don't think the library can handle this yet (tell me if otherwise).

Problem description

When inserting data in a ScrollingBuffer (implementation from the Demo), the following behavior occurs

The plot often connects the start to the end of the circle and therefore causing weird lines to appear. I insert the data in a different thread than the plot thread, and that is why this happens.

Solution

I know that implot does not support multithreading, so one solution would be, to use mutexes, in order to make the data insertion and plotting thread safe. This however causes a lot of overhead, which I think can be avoided.

The solution I came up with is, to insert padding elements in my ScrollingBuffer. A quick example will explain what I mean with padding. (s means the start of the data, e is one after the last and marks the next insert position)

• Normal (unpadded) ScrollingBuffer

  # Size of 5 and 4 elements inserted:
  s           e
  0, 1, 2, 3, _
  
  # Inserting the element 4
  se
  0, 1, 2, 3, 4
  
  # Inserting the element 5
  se
  5, 1, 2, 3, 4

• Padded ScrollingBuffer

  # Size of 5 and 4 elements inserted, padding is 2 elements:
      s           e
  0, 0, 0, 1, 2, 3, _
  |  |
  Padding
  
  # Inserting the element 4
  e     s
  0, 0, 0, 1, 2, 3, 4
  |  |
  Padding
  
  # Inserting the element 5
   e     s
  5, 0, 0, 1, 2, 3, 4
   |  |
   Padding

  The padded buffer has the advantage, that the old value is not directly overridden and therefore the circle would not connect the ends of the circle, but rather just plot a value which is one insertion old.

Improvements for ImPlot needed to make this work

The current behavior of the offset and the buffer is that it starts from the offset reading size - offset elements and the jumping back to the start pointer and then reading till offset

         offset = 3
         |
   e     s
5, 0, 0, 1, 2, 3, 4
|
data*

count = 5

Plots the values: 1, 2, 5, 0, 0

Needed would be an ability to tell the Getter how many elements come after the offset and not automatically calculate it with the formula size - offset. I don't have in-depth knowledge of the ImPlot library so I don't know how this could be done the easiest way.

Additional info / resources

Padded ScrollingBuffer implementation: https://compiler-explorer.com/z/6WPP3WTG6

Code in case compiler-explorer goes down

```C++ #include #include #include /// @brief A buffer which is overwriting itself from the start when full /// @tparam T Type of data stored in the buffer template class ScrollingBuffer { public: explicit ScrollingBuffer(size_t maxSize = 2000, size_t padding = 0) : _maxSize(maxSize + padding), _padding(padding), _dataStart(padding), _dataEnd(padding) { _data.reserve(maxSize + padding); _data.resize(padding); } /// @brief Erases all elements from the container. After this call, size() returns zero. void clear() { _data.clear(); _dataStart = _padding; _dataEnd = _padding; for (size_t i = 0; i < _padding; i++) { _data.push_back(0); } } /// @brief Appends the given element value to the end of the container. /// @param[in] value the value of the element to append void push_back(const T& value) { if (_data.size() < _maxSize) // The real buffer is smaller than the allowed buffer size { _data.push_back(value); _dataEnd = (_dataEnd + 1) % _maxSize; } else // The real buffer as large as or bigger than the allowed buffer size, so we have to scroll the buffer { _data.at(_dataEnd) = value; _dataStart = (_dataStart + 1) % _maxSize; _dataEnd = (_dataEnd + 1) % _maxSize; } } /// @brief Checks if the container has no elements [[nodiscard]] bool empty() const { return size() == 0; } /// @brief Returns the number of elements in the container [[nodiscard]] size_t size() const { if (_dataStart == _padding && _dataEnd == _padding) // Buffer empty or full and not scrolled { return _data.size() - _padding; } if (_dataStart < _dataEnd) // not scrolled buffer { return _dataEnd - _dataStart; } // scrolled buffer return _maxSize - (_dataStart - _dataEnd); } /// @brief Returns the data index of the first element in the buffer [[nodiscard]] int offset() const { return static_cast(_dataStart); } /// @brief Returns a pointer to the raw data array (not in scrolled order) [[nodiscard]] const T* data() { return _data.data(); } /// @brief Prints the buffer to the output stream /// @param[in, out] os The output stream to print to /// @param[in] buffer The buffer to print /// @return The output stream given as parameter friend std::ostream& operator<<(std::ostream& os, const ScrollingBuffer& buffer) { for (int i = 0; static_cast(i) < buffer._maxSize; i++) { if ((i >= static_cast(buffer._dataStart - buffer._padding) && static_cast(i) < buffer._dataStart) || (static_cast(i) >= buffer._dataStart + buffer._maxSize - buffer._padding)) { os << "X(" << std::to_string(buffer._data.at(static_cast(i))) << ")"; // padding } else if (bool scrolled = buffer.isScrolled(); (scrolled && static_cast(i) >= buffer._dataEnd && (static_cast(buffer._dataStart - buffer._padding) < 0 || i < static_cast(buffer._dataStart - buffer._padding))) || (!scrolled && static_cast(i) >= buffer._dataEnd)) { os << "_"; // empty } else { os << std::to_string(buffer._data.at(static_cast(i))); } if (static_cast(i) != buffer._maxSize - 1) { os << ", "; } } return os; } private: /// The maximum amount of objects to store in the buffer before overwriting itself when full /// When _infiniteBuffer == true, then this corresponds to m_data.size() size_t _maxSize; /// The padding are empty values at the start of the buffer to prevent overriding the start value in multithreaded applications size_t _padding{ 0 }; /// The index of the first element in the scrolling buffer (0 if the buffer is empty) size_t _dataStart{ 0 }; /// The index one after the last element (0 if the buffer is empty) size_t _dataEnd{ 0 }; /// The data storage object std::vector _data; /// @brief Checks if the buffer is scrolled [[nodiscard]] bool isScrolled() const { if (_dataEnd == 0 && !empty()) return true; return _dataEnd < _dataStart || (_dataStart != _padding); } }; int main() { auto example = [](size_t padding) { ScrollingBuffer buffer(5, padding); for (int i = 0; i < 4; i++) { buffer.push_back(i); } std::cout << buffer << '\n'; buffer.push_back(4); std::cout << buffer << '\n'; buffer.push_back(5); std::cout << buffer << '\n'; }; std::cout << "Normal ScrollingBuffer without padding:\n"; example(0); std::cout << "\nPadded ScrollingBuffer with padding of 2:\n"; example(2); } ```

[marcizhu]

IMHO adding padding to ScrollingBuffer does not solve the underlying problem: you have a data race in your code. Adding padding without using mutexes is still undefined behaviour and might still show artifacts. I know mutexes are expensive, but it's the only solution that guarantees that the program won't randomly crash if, for example, one thread is reading the begin() of the buffer while the other thread is updating that exact same pointer.

[ToppDev]

As there is no iterator in this case, which gets invalidated. The program can't crash I think. The memory stays the same because the buffer is scrolling. Therefore it is guaranteed, that memory is valid. The only thing which happens (because of the data race) is, that the buffer gets data added while trying to draw the old data (which then leads to the lines appearing).

The padding I think in this case also ensures, that I never write the same element in my buffer as I try to read/plot.

I agree, that my padded buffer solution is not ideal, but I try to avoid the expensive mutex here. Data is inserted at very high frequencies in my case and the mutex in the draw function would directly affect the framerate too.

[marcizhu]

As there is no iterator in this case, which gets invalidated the program can't crash I think

An iterator is just an abstraction. Even if there is no iterator the container has two pointers, one that points to the begin and one that points to the end of the sequence. A pointer is (usually) 8 bytes. Now imagine one thread is reading these 8 bytes while the other thread is writing them. The first thread will read a (probably) invalid pointer.

The memory stays the same because the buffer is scrolling. Therefore it is guaranteed, that memory is valid

Yeah, the memory is the same, but the pointers do change. On x86 writing an 8-byte integer is usually atomic, but this is never guaranteed nor it is portable behaviour. Thus a crash is possible and in fact very likely on non-x86 machines because you have a data race in the code.

The padding I think in this case also ensures, that I never write the same element in my buffer as I try to read/plot.

The padding does solve the data race between the items, that's true. However it doesn't solve the other data race issue, which is that you have two threads simultaneously reading and writing two pointers at the same time. The data race is not only in the insertion of the data itself, but in the updating of the pointers of the buffer too.

I agree, that my padded buffer solution is not ideal, but I try to avoid the expensive mutex here. Data is inserted at very high frequencies in my case and the mutex in the draw function would directly affect the framerate too.

I get it, and I agree that mutexes are somewhat expensive. But perhaps you could use a spinlock instead, or use std::atomic, or maybe batch the data and update it all at once using a mutex... I 100% agree that mutexes are slow, but for example spdlog uses mutexes and it is able to log over 1.600.000 strings per second. It should be fast enough for 99.9999% of the applications out there.

The padding idea is really good and it solves the data race on insertion/deletion of the items in the ring buffer, but you need something more in order to guarantee that this won't randomly crash because of the begin/end pointers.

[epezent]

I think @marcizhu is giving sound advice in this situation. I would definitely try a mutex before jumping to conclusions. My experience has been that mutexes are sufficient in the vast majority of applications. Another option to consider is a lock-free SPSC queue [1], [2]. There would be some copying involved (i.e. you need to pop elements off the queue and copy them into a local buffer in the ImPlot thread), but you can at leaest avoid having the producer thread wait on the ImPlot plot function to unlock a mutex.

I will carefully review your proposal on the offset/stride, but my initial reaction is that this would be an API altering change that may cause more problems than it potentially fixes.

[epezent]

@ToppDev , I suggest you read up on lock-free queues and false sharing if you aren't familiar with the concept. Your proposal is logical, but this is a far more nuanced propblem than you might initially expect.

[ToppDev]

thank you both for your detailed explanation and suggestions on how to solve this.

I agree, that I did not understand the depth of the problem with the start and end pointer and that I subconsciously relied on the compiler making certain things possible, while he is not forced to do so. I will definitely read up on lock-free queues and false sharing, as it is actually the first time hearing the term for me :smile:

Thank you both again for your time. I see that this change would introduce a breaking change to the API and therefore its better for me to solve it 'the right way' than trying to win the race with cheats.

From my side this issue can be closed then. Feel free to close it or I will close it in a few days just in case someone wants to answer as well.

[epezent]

Feel free to reopen this or come back with questions if you need!

[marcizhu]

I agree with @epezent, feel free to come back with questions if you have them, we're always glad to help 😄