boost::circular_buffer как более быстрый контейнер для входных данных
У любой торговой платформы существует потребность в специальных структурах, позволяющих хранить оперативно поступающие данные в определенной последовательности. По сути, это очереди FIFO (first in, first out) с заранее определенным размером и доступом по индексу. По мере поступления новых данных они записываются в конец очереди, а если очередь уже заполнена, старые данные удаляются. Такие очереди, например, используются для хранения временных баров, данных для индикаторов, графиков и т.д.
В настоящее время в нашей торговой платформе QuantPro Platform для этих целей используется std::deque, имеющий всю необходимую функциональность — запись в начало или в конец, доступ по индексу, последовательная итерация. Для возможности контроля наполнения очереди до заданного предела мы реализовали свой класс-обертку, который в общем виде выглядит примерно так (большинство методов опущены для краткости):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include template class FixedQueue { public: FixedQueue() = default; FixedQueue(size_t max_size) : max_size_(max_size) { } size_t max_size() const { return max_size_; } void push_back(T const& v) { if(values_.size() == max_size()) values_.pop_front(); values_.push_back(v); } private: std::deque values_; size_t max_size_ = 0; }; |
В методе push_back() происходит проверка на предмет того, достиг ли размер очереди максимального предела, и при необходимости самый старый элемент выталкивается из головы очереди, после чего в конец добавляется новый.
Однако, поскольку платформа очень интенсивно используется при тестировании стратегий по тиковым данным, скорость ее работы выходит на передний план, и мы постоянно ищем возможности как эту скорость повысить. Например, если в такой очереди будут храниться последние цены бумаги, то заполнение новыми данными будет происходить очень часто, и такая очередь будет оказывать сильное влияние на производительность всей системы.
Обычно std::deque реализован таким образом, что при добавлении одного элемента в памяти выделяется блок определенного размера, размещающий в себе некоторое количество элементов. При добавлении следующего элемента память выделяться не будет до тех пор, пока блок не будет заполнен полностью, после чего будет выделена память под новый блок. По мере удаления элементов эти блоки уничтожаются. Хотя выделение и уничтожение памяти происходит не на каждом элементе, тем не менее, поскольку в нашей реализации очереди происходит интенсивное последовательное добавление и удаление элементов, эти операции с памятью происходят очень часто, значительно снижая скорость работы системы.
Недавно я наткнулся на контейнер boost::circular_buffer, который имеет очень интересную реализацию. При инициализации этому контейнеру задается максимальный размер, и при добавлении элементов происходит его наполнение до этого размера. А дальше происходит самое интересное. Когда контейнер наполняется до максимума, при попытке добавить новый элемент он на самом деле просто перезаписывает элемент, находящийся на другом конце очереди, а его внутреннее состояние меняется таким образом, что конец очереди теперь смотрит на этот новый элемент, а начало — на элемент, который до этого был вторым. Получается своего рода кольцо, по которому происходит запись, откуда и название этого контейнера. При этом не происходит никакого дополнительного выделения и освобождения памяти, как в std::deque. Дополнительным бонусом к этому идет тот факт, что данные в этом контейнере хранятся в памяти последовательно, по тому же принципу, что и в std::vector. При обработке данных процессором этот факт дает дополнительный шанс на то, что соседние данные будут находиться в кеше процессора, и так называемый cache miss будет происходить реже.
Я задался целью протестировать производительность boost::circular_buffer и сравнить ее со скоростью нашей реализации очереди. Код теста представлен ниже.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include "FixedQueue.h" #include <boost/circular_buffer.hpp> #include #include class TimingUtil { public: TimingUtil(std::string const& message) : start_(std::chrono::steady_clock::now()), message_(message) { } ~TimingUtil() { std::chrono::steady_clock::time_point finish = std::chrono::steady_clock::now(); std::cout << message_ << " took " << std::chrono::duration_cast(finish - start_).count() << " ms." << std::endl; } private: std::chrono::steady_clock::time_point start_; std::string message_; }; template void test(int iterations) { C container(100); for(int i = 0; i < iterations; i++) { container.push_back(i); } } int main(int argc, char *argv[]) { { TimingUtil t("deque test"); test<FixedQueue>(1000000000); } { TimingUtil t("circular_buffer test"); test<boost::circular_buffer>(1000000000); } return 0; } |
Класс TimingUtil сделан для удобства, чтобы можно было легко измерять время работы участков кода, которые нас интересуют. Результат теста не разочаровал. При запуске на Ubuntu 16.04, gcc-5.4.0, процессор Intel Core i7 получаем ощутимый выигрыш в 3.6 раза:
|
1 2 |
deque test took 3431087 ms. circular_buffer test took 953880 ms. |
Очевидно, в планах на один из ближайших релизов нас ждут некоторые изменения 
[…] Теперь давайте посмотрим, что мы выиграли от усовершенствованного способа расчета среднего. Для этого немного переделаем код и воспользуемся классом TimingUtil, который был описан в статье о контейнере boost::circular_buffer. […]