Circular Queue(Buffer)를 c++로 구현해 보았다. Ring Buffer로 오래 전부터 네트워크 프로그램에서 많이 사용하던 놈이다. 컨테이너 Class 들은 c++을 배우고, 또 적응하는데 매우 도움이 된다. 단지 공부하려고 만든 것은 아니고 실시간 차트 데이터를 저장하는데 적용해 보려고 만든 것이다.
그 간에는 std::deque을 사용했었는데 뒤에서 채우고 앞에서 지우는 식으로 고정크기를 유지했는데, 메모리 관리를 내 맘대로 못하는게 문제였고 성능 문제가 생길 수 밖에 없었다. 아예 첨부터 고정크기 메모리를 할당해서 사용하는게 효율적이고, 실시간 데이터는 시간 단위로 저장하면 되기 때문에 필요한 메모리 크기를 사전에 예측할 수 있다. 결론은 피부로 느낄만큼 성능향상 효과가 있더라.
성능을 높이는 김에 메모리 할당 외에 fast modulo 함수를 사용했다. Circular Buffer의 특성상 메모리 상에서 현재 데이터의 위치를 빠르게 알아내야 하는데 나머지(%) 연산을 해야만 한다. 다행히도 나누는 수가 양수이고 2의 거듭제곱(power of 2)이라면 bit 연산으로 나머지를 빠르게 계산할 수 있다. 여기서 나누는 수는 고정크기 용량 또는 최대 저장 크기이다. 그리고, 사용자가 용량을 적당히 지정하더라도 무조건 가까운 크기의 2의 거듭제곱으로 용량을 설정하도록 하였다. 이렇게 하지 않으면 나머지 연산 결과가 엉뚱하게 나오기 때문이다.
Circular Queue
// Circular Queue(Buffer) and Circular Iterator C++ Implementation
//
// This program is copyright (c) 2019 by Umundu @ https://zapary.blogspot.com .
// It is distributed under the terms of the GNU LGPL version 3, as detailed in
// https://opensource.org/licenses/lgpl-3.0.html .
#include <memory>
template<typename TC>
class CircularIterator;
template<typename TD>
class CircularQueue
{
public:
using value_type = TD;
using reference = TD&;
using const_reference = TD const&;
using pointer = TD*;
using const_pointer = TD const*;
using difference_type = std::ptrdiff_t;
using size_type = std::size_t;
using iterator = CircularIterator<CircularQueue>;
using const_iterator = CircularIterator<const CircularQueue>;
using riterator = std::reverse_iterator<iterator>;
using const_riterator = std::reverse_iterator<const_iterator>;
public:
CircularQueue() = default;
CircularQueue(size_type capacity)
: m_capacity(toPow2(capacity)), m_data(new TD[m_capacity]{}) {}
template<typename TI>
CircularQueue(TI b, TI e)
: m_capacity(toPow2(std::distance(b, e))), m_data(new TD[m_capacity]{})
{ for(auto it = b; it != e; ++it) push_back(*it); }
CircularQueue(std::initializer_list<TD> const& il)
: CircularQueue(std::begin(il), std::end(il)) {}
~CircularQueue() { destroy(); }
CircularQueue(const CircularQueue& cq)
: m_capacity(cq.m_capacity), m_nDequeue(cq.m_nDequeue), m_nOverflow(cq.m_nOverflow),
m_nUnderflow(cq.m_nUnderflow), m_nRemoved(cq.m_nRemoved), m_data(new TD[m_capacity]{})
{
try {
for(size_type i = 0; i < cq.m_size; ++i) push_back(cq[i]);
// Note: m_capacity and m_size are already set.
// m_head and m_tail should be reset automatically in updateSize().
m_nEnqueue = cq.m_nEnqueue;
}
catch(...) { destroy(); throw; }
}
CircularQueue& operator=(const CircularQueue& cq)
{
if(this != &cq) { CircularQueue<TD> tmp(cq); tmp.swap(*this); }
return *this;
}
CircularQueue(CircularQueue&& cq) noexcept { cq.swap(*this); }
CircularQueue& operator=(CircularQueue&& cq) noexcept { cq.swap(*this); return *this; }
bool empty() const { return !m_size; }
bool full() const { return m_size == m_capacity - 1; }
size_type size() const { return m_size; }
size_type capacity() const { return m_capacity - 1; } // for iterators
size_type removed() const { return m_nRemoved; }
reference at(size_type idx)
{ validate(idx); return *(m_data + modCapacity(m_head + idx)); }
const_reference at(size_type idx) const
{ validate(idx); return *(m_data + modCapacity(m_head + idx)); }
reference operator[](size_type idx) { return *(m_data + modCapacity(m_head + idx)); }
const_reference operator[](size_type idx) const
{ return *(m_data + modCapacity(m_head + idx)); }
reference front() { return *(m_data + m_head); }
const_reference front() const { return *(m_data + m_head); }
reference back() { return *(m_data + (m_tail ? m_tail - 1 : m_capacity - 1)); }
const_reference back() const { return *(m_data + (m_tail ? m_tail - 1 : m_capacity - 1)); }
iterator begin() { return iterator(this, m_data + m_head); }
riterator rbegin() { return riterator(end()); }
const_iterator begin() const { return const_iterator(this, m_data + m_head); }
const_riterator rbegin() const { return const_riterator(end()); }
iterator end() { return iterator(this, m_data + m_tail); }
riterator rend() { return riterator(begin()); }
const_iterator end() const { return const_iterator(this, m_data + m_tail); }
const_riterator rend() const { return const_riterator(begin()); }
const_iterator cbegin() const { return begin(); }
const_riterator crbegin() const { return rbegin(); }
const_iterator cend() const { return end(); }
const_riterator crend() const { return rend(); }
void enqueue(const value_type& item) { push_back(item); }
void enqueue(value_type&& item) noexcept { move_back(std::move(item)); }
template<typename... TAs>
void enqueue(TAs&&... args) noexcept { emplace_back(std::move(args)...); }
TD dequeue() noexcept
{
if(!m_size) {
++m_nUnderflow;
return TD{};
}
TD item = std::move(*(m_data + m_head));
m_head = modCapacity(++m_head);
--m_size;
++m_nDequeue;
++m_nRemoved;
return item; // Respect RVO for local objects.
}
void reserve(size_type capacity)
{
if(m_capacity >= capacity) return;
capacity = toPow2(capacity);
reserveData(capacity);
}
private:
// Return a number with a power of 2 that is larger but the most adjacent to a given value.
size_type toPow2(size_type value) const
{
int hbit = 0;
for(; value != 1; ++hbit) value >>= 1;
return (size_type(1 << hbit) == value) ? value : 1 << (hbit + 1);
}
// Return a fast modulo. m_capacity is assumed a power of 2 and positive number.
size_type modCapacity(size_type num) const { return num & (m_capacity - 1); }
void validate(size_type idx) const
{ if(idx >= m_size || !m_capacity) throw std::out_of_range("Error: index out of range."); }
void updateSize()
{
++m_nEnqueue;
m_tail = modCapacity(++m_tail);
// If Queue is full(or empty) head and tail are same. This makes iterators useless.
if(m_size == m_capacity - 1) {
++m_nRemoved;
++m_nOverflow;
m_head = modCapacity(m_tail + 1); // Make head != tail for iterators.
}
else ++m_size;
}
void push_back(const TD& item) { *(m_data + m_tail) = item; updateSize(); }
void move_back(TD&& item) noexcept { *(m_data + m_tail) = std::move(item); updateSize(); }
template<typename... TAs>
void emplace_back(TAs&&... args) noexcept
{ *(m_data + m_tail) = TD(std::move(args)...); updateSize(); }
void reserveData(size_type capacity)
{
CircularQueue<TD> tmp(capacity);
restoreData(tmp);
tmp.swap(*this);
}
void restoreData(CircularQueue<TD>& cq)
{
if(!m_size) return;
for(size_type i = 0; i < m_size; ++i) cq.move_back(std::move((*this)[i]));
// Note: m_capacity and m_size are already set.
// m_head and m_tail should be reset automatically in updateSize().
cq.m_nEnqueue = m_nEnqueue;
cq.m_nDequeue = m_nDequeue;
cq.m_nOverflow = m_nOverflow;
cq.m_nUnderflow = m_nUnderflow;
cq.m_nRemoved = m_nRemoved;
}
void swap(CircularQueue& cq) noexcept
{
std::swap(m_capacity, cq.m_capacity);
std::swap(m_size, cq.m_size);
std::swap(m_head, cq.m_head);
std::swap(m_tail, cq.m_tail);
std::swap(m_nEnqueue, cq.m_nEnqueue);
std::swap(m_nDequeue, cq.m_nDequeue);
std::swap(m_nOverflow, cq.m_nOverflow);
std::swap(m_nUnderflow, cq.m_nUnderflow);
std::swap(m_nRemoved, cq.m_nRemoved);
std::swap(m_data, cq.m_data);
}
void destroy() { std::unique_ptr<TD, Deleter> deleter(m_data, Deleter()); }
private:
struct Deleter { void operator()(TD* data) const { delete[] data; } };
size_type m_capacity{0}; // queue capacity
size_type m_size{0}; // current data size
size_type m_head{0}; // head index
size_type m_tail{0}; // tail index
size_type m_nEnqueue{0}; // enqueued data size(m_size + m_nRemoved)
size_type m_nDequeue{0}; // dequeued data size
size_type m_nOverflow{0}; // overflowed data size
size_type m_nUnderflow{0}; // underflowed data size
size_type m_nRemoved{0}; // removed(m_nOverflow + m_nDequeue) data size
TD* m_data{nullptr}; // data storage
friend iterator;
friend const_iterator;
};
Circular Iterator
만드는 김에 iterator까지 만들어 보았다. 로직이 간단하지는 않아서 애를 좀 먹었다. STL 표준 iterator들은 컨테이너의 begin()과 end() 함수만으로 동작하는데, Circular Queue의 경우 두 함수가 동일한 메모리 주소를 갖는 경우가 생기기 때문에 구현하기 어렵다. 즉, Queue가 비어 있거나 꽉찼을 때 head와 tail 위치가 같아진다. loop를 아예 돌릴 수 없거나 무한 loop를 돌게 되는 상황에 빠진다.
나의 해결 방법은 head와 tail이 같아지지 않도록 하여 정확히 1 cycle의 loop이 돌게 하였다. 대신 최대 데이터 크기는 고정 용량 크기 보다 1개 줄어든다.
// Circular Queue(Buffer) and Circular Iterator C++ Implementation
//
// This program is copyright (c) 2019 by Umundu @ https://zapary.blogspot.com .
// It is distributed under the terms of the GNU LGPL version 3, as detailed in
// https://opensource.org/licenses/lgpl-3.0.html .
#include "CircularQueue.h"
template<typename TC>
class CircularIterator
{
public: // Should be public!
using iterator_category = std::random_access_iterator_tag;
using value_type = typename TC::value_type;
using pointer = typename TC::pointer;
using difference_type = typename TC::difference_type;
using size_type = typename TC::size_type;
using reference = typename TC::reference;
public:
CircularIterator() = default;
CircularIterator(const CircularIterator& it) : m_cque{it.m_cque}, m_it{it.m_it} {}
CircularIterator(TC* co, const pointer po) : m_cque{co}, m_it{po} {}
CircularIterator& operator=(const CircularIterator& it)
{
if(this == &it) return *this;
m_cque = it.m_cque;
m_it = it.m_it;
return *this;
}
reference operator*() const { return *m_it; }
pointer operator->() const { return &(operator*()); }
CircularIterator& operator++() {
if(++m_it == m_cque->m_data + m_cque->m_capacity) m_it = m_cque->m_data;
return *this;
}
CircularIterator operator++(int) {
CircularIterator tmp = *this;
++*this;
return tmp;
}
CircularIterator& operator--() {
if(m_it == m_cque->m_data) m_it = m_cque->m_data + m_cque->m_capacity;
--m_it; // note!
return *this;
}
CircularIterator operator--(int) {
CircularIterator tmp = *this;
--*this;
return tmp;
}
CircularIterator& operator+=(difference_type n) {
if(n > 0) m_it = m_cque->m_data + m_cque->modCapacity(m_it - m_cque->m_data + n);
else if(n < 0) *this -= -n;
return *this;
}
CircularIterator& operator-=(difference_type n) {
if(n > 0) {
difference_type idx = m_it - m_cque->m_data;
m_it = m_cque->m_data +
(n > idx ? m_cque->m_capacity - m_cque->modCapacity(n - idx) : idx - n);
}
else if(n < 0) *this += -n;
return *this;
}
CircularIterator operator+(difference_type n) const { return CircularIterator(*this) += n; }
CircularIterator operator-(difference_type n) const { return CircularIterator(*this) -= n; }
difference_type operator+(CircularIterator& it) const
{ return m_cque->modCapacity(index(m_it) + index(it.m_it)); }
difference_type operator-(CircularIterator& it) const
{ return index(m_it) - index(it.m_it); }
reference operator[](difference_type n) const { return *(*this + n); }
bool operator!() const { return !m_it; }
bool operator==(const CircularIterator& it) const { return m_it == it.m_it; }
bool operator!=(const CircularIterator& it) const { return !operator==(it); }
bool operator<(const CircularIterator<TC>& it) const
{ return (index(m_it) < index(it.m_it)); }
bool operator>(const CircularIterator<TC>& it) const
{ return (index(m_it) > index(it.m_it)); }
bool operator<=(const CircularIterator& it) const { return !(operator>(it)); }
bool operator>=(const CircularIterator& it) const { return !(operator<(it)); }
private:
difference_type index(const pointer& it) const
{
difference_type idx = it - m_cque->m_data - m_cque->m_head;
return idx < 0 ? m_cque->m_capacity + idx : idx;
}
const TC* m_cque{nullptr}; // CircularQueue
pointer m_it{nullptr}; // iterator
};
Test 결과
테스트 결과만 아래에 보였다. 잘 돌아간다~!!!
===============[[ Queue: 0x7ffcd5d379a0 Status ]]===============
=== Queue capacity(the maximum data size) : 15
=== Current(queue keeping) data size : 15
=== Enqueued(= Current + Removed) size : 46
=== Dequeued size : 15
*** Overflowed(starving capacity) size : 16
*** Underflowed(starving enque data) size : 5
*** Removed(= Dequeued + Overflowed) size : 31
=== Head/Front(next dequeue point) index (value) : 3 (8)
=== Back(the last data point) index (value) : 1 (-48)
=== Tail(next enqueue point) index : 2
-------------< Storage Data in memory address order >-------------
-49, -48, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50,
-------------< Current Data in enqueued order >-------------
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48,
==================================================================
*** for-loop test on a Circular Queue
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, index loop
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, auto iterator
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, iterator
8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, -50, -49, -48, const iterator
-48, -49, -50, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, reverse iterator
-48, -49, -50, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, c-r iterator
-50, -49, -48, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, std::sort()
Tip: 함수 성능 측정을 위한 Simple Timer
가끔 함수 성능 측정을 해야 하는데 아래와 같은 Simple Timer 하나 장만해 두면 편하다.
#include <chrono>
#include <thread>
using namespace std::chrono_literals;
// Simple Timer
class Timer {
using TClock = std::chrono::high_resolution_clock;
using TTime = decltype(TClock::now());
public:
Timer() : m_start(TClock::now()) {}
operator long()
{
auto interval = std::chrono::duration_cast<std::chrono::microseconds>
(TClock::now() - m_start).count();
reset();
return interval;
}
void reset() { m_start = TClock::now(); }
private:
TTime m_start;
};
아래와 같이 간단하게 사용할 수 있다.
void main()
{
Timer now;
for(size_t i = 0; i < 1000; ++i) [] { std::this_thread::sleep_for(2ms); };
std::cout << "f1: " << now << '\n';
for(size_t i = 0; i < 1000; ++i) [] { std::this_thread::sleep_for(3ms);};
std::cout << "f2: " << now << '\n';
}
