Gabe Black has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/38896 )
Change subject: base: Re-implement CircleBuf without using CircularQueue.
......................................................................
base: Re-implement CircleBuf without using CircularQueue.
CircularQueue provides iterators which make it easier for users to
interact with it and helps abstract its internal state, but at the same
time it prevents standard algorithms like std::copy from recognizing
opportunities to use bulk copies to speed up execution. It also hides
the seams when wrapping around the buffer happens which std::copy
wouldn't know how to handle.
CircleBuf seems to be intended as a simpler type which doesn't hold
complex entries like the CircularQueue does, and instead just acts as a
wrap around buffer, like the name suggests. This change reimplements it
to not use CircularQueue, and to instead use an underlying vector.
The way internal indexing is handled CircularQueue was simplified
recently, and using the same scheme here means that this code is
actually not much more verbose than it was before. It also intrinsically
handles indexing and bulk accesses, and uses std::copy_n in a way that
lets it recognize and take advantage of contiguous storage and bulk
copies.
Change-Id: I78e7cfe174c52f60c95c81e5cd3d71c6052d4d41
---
M src/base/circlebuf.hh
1 file changed, 90 insertions(+), 20 deletions(-)
diff --git a/src/base/circlebuf.hh b/src/base/circlebuf.hh
index 8d7297a..924ada0 100644
--- a/src/base/circlebuf.hh
+++ b/src/base/circlebuf.hh
@@ -40,6 +40,7 @@
#include <algorithm>
#include <cassert>
+#include <iterator>
#include <vector>
#include "base/circular_queue.hh"
@@ -54,18 +55,43 @@
*
*/
template<typename T>
-class CircleBuf : public CircularQueue<T>
+class CircleBuf
{
+ private:
+ std::vector<T> buffer;
+ size_t start = 0;
+ size_t used = 0;
+ size_t maxSize;
+
public:
- explicit CircleBuf(size_t size)
- : CircularQueue<T>(size) {}
- using CircularQueue<T>::empty;
- using CircularQueue<T>::size;
- using CircularQueue<T>::capacity;
- using CircularQueue<T>::begin;
- using CircularQueue<T>::end;
- using CircularQueue<T>::pop_front;
- using CircularQueue<T>::advance_tail;
+ using value_type = T;
+ using iterator = typename std::vector<T>::iterator;
+ using const_iterator = typename std::vector<T>::const_iterator;
+
+ explicit CircleBuf(size_t size) : buffer(size), maxSize(size) {}
+
+ bool empty() const { return used == 0; }
+ size_t size() const { return used; }
+ size_t capacity() const { return maxSize; }
+
+ iterator begin() { return buffer.begin() + start % maxSize; }
+ const_iterator begin() const { return buffer.begin() + start %
maxSize; }
+ iterator end() { return buffer.begin() + (start + used) % maxSize; }
+ const_iterator
+ end() const
+ {
+ return buffer.begin() + (start + used) % maxSize;
+ }
+
+ /**
+ * Throw away any data in the buffer.
+ */
+ void
+ flush()
+ {
+ start = 0;
+ used = 0;
+ }
/**
* Copy buffer contents without advancing the read pointer
@@ -91,10 +117,27 @@
void
peek(OutputIterator out, off_t offset, size_t len) const
{
- panic_if(offset + len > size(),
+ panic_if(offset + len > used,
"Trying to read past end of circular buffer.");
- std::copy(begin() + offset, begin() + offset + len, out);
+ if (!len)
+ return;
+
+ // The iterator for the next byte to copy out.
+ auto next_it = buffer.begin() + (start + offset) % maxSize;
+ // How much there is to copy from until the end of the buffer.
+ const size_t to_end = buffer.end() - next_it;
+
+ // If the data to be copied wraps, take care of the first part.
+ if (to_end < len) {
+ // Copy it.
+ out = std::copy_n(next_it, to_end, out);
+ // Start copying again at the start of buffer.
+ next_it = buffer.begin();
+ len -= to_end;
+ }
+ // Copy the remaining (or only) chunk of data.
+ std::copy_n(next_it, len, out);
}
/**
@@ -108,7 +151,8 @@
read(OutputIterator out, size_t len)
{
peek(out, len);
- pop_front(len);
+ used -= len;
+ start += len;
}
/**
@@ -121,15 +165,41 @@
void
write(InputIterator in, size_t len)
{
- // Writes that are larger than the backing store are allowed,
- // but only the last part of the buffer will be written.
- if (len > capacity()) {
- in += len - capacity();
- len = capacity();
+ if (!len)
+ return;
+
+ // Writes that are larger than the buffer size are allowed, but
only
+ // the last part of the date will be written.
+ if (len > maxSize) {
+ in += len - maxSize;
+ start += len - maxSize;
+ len = maxSize;
}
- std::copy(in, in + len, end());
- advance_tail(len);
+ // How much existing data will be overwritten?
+ const size_t overflow = std::max<size_t>(0, used + len - maxSize);
+ // The iterator of the next byte to add.
+ auto next_it = buffer.begin() + (start + used) % maxSize;
+ // How much there is to copy to the end of the buffer.
+ const size_t to_end = buffer.end() - next_it;
+
+ // If this addition wraps, take care of the first part here.
+ if (to_end < len) {
+ // Copy it.
+ std::copy_n(in, to_end, next_it);
+ // Update state to reflect what's left.
+ next_it = buffer.begin();
+ std::advance(in, to_end);
+ len -= to_end;
+ used += to_end;
+ }
+ // Copy the remaining (or only) chunk of data.
+ std::copy_n(in, len, next_it);
+ used += len;
+
+ // Don't count data that was overwritten.
+ used -= overflow;
+ start += overflow;
}
};
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/38896
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: develop
Gerrit-Change-Id: I78e7cfe174c52f60c95c81e5cd3d71c6052d4d41
Gerrit-Change-Number: 38896
Gerrit-PatchSet: 1
Gerrit-Owner: Gabe Black <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
%(web_page_url)slistinfo%(cgiext)s/%(_internal_name)s
