Use ringbuffer instead of using memcpy to shift element at EVERY PUSH

[hbina]

This introduces a data structure that replaces Vec<(f64, f64)> so that it does not perform a shift left at every push when its at full capacity. This should introduce performance benefits when the buffer is large enough. Additionally, this data structure performs better the larger the buffer size.

Signed-off-by: Hanif Bin Ariffin hanif.ariffin.4326@gmail.com

[orf]

I've just fixed the CI steps so this MR should now run the test suite. Can you rebase?

[hbina]

@orf I have rebased and added couple more commits to actually test.

Thanks!

[SOF3]

Why not just use VecDeque from std?

[orf]

I originally used VecDequeue but the memory layout is not contiguous so it cannot be fed into tui in the same way a Vec can.

Thanks for the MR @hbina, I'll have a look at this later <3

[SOF3]

In that case, why not allocate a Vec of size capacity * 2 and memcpy everything back to 0 when ptr == capacity? This would avoid allocations entirely.

[hbina]

This is basically what this PR does @SOF3 . We just hide this behind a data structure. We only do allocation once when we create the vector and every push beyond that is within our capacity.

[SOF3]

This is basically what this PR does @SOF3 . We just hide this behind a data structure. We only do allocation once when we create the vector and every push beyond that is within our capacity.

Isn't this PR dynamically extending and shrinking the allocate memory? That'd depend on the memory allocator.

[hbina]

AFAIK these 2

self.buf.copy_within(self.head + 1..len, 0);
self.buf.resize(self.cap - 1, Default::default());

basically memmoves the buffer to the beginning pointer and resizes (no need to allocate because we are resizing to less than capacity) to the appropriate length. If unsafe is allowed, we can remove the Default constraint.

[SOF3]

oops, I meant you are performing an O(capacity) memmove every push (except the first cycle).

[hbina]

Nope, resize will change the underlying len to something smaller than capacity so that if branch will fail.
However, this can still be improved by using truncate so we can remove Default entirely. This is also the correct method AFAIK, because we will be calling Drop on the rest.