Библиотека Boost

Программирование на C++

boost::circular_buffer как более быстрый контейнер для входных данных

У любой торговой платформы существует потребность в специальных структурах, позволяющих хранить оперативно поступающие данные в определенной последовательности. По сути, это очереди FIFO (first in, first out) с заранее определенным размером и доступом по индексу. По мере поступления новых данных они записываются в конец очереди, а если очередь уже заполнена, старые данные удаляются. Такие очереди, например, используются для хранения временных баров, данных для индикаторов, графиков и т.д.

В настоящее время в нашей торговой платформе QuantPro Platform для этих целей используется std::deque, имеющий всю необходимую функциональность — запись в начало или в конец, доступ по индексу, последовательная итерация. Для возможности контроля наполнения очереди до заданного предела мы реализовали свой класс-обертку, который в общем виде выглядит примерно так (большинство методов опущены для краткости):

В методе push_back() происходит проверка на предмет того, достиг ли размер очереди максимального предела, и при необходимости самый старый элемент выталкивается из головы очереди, после чего в конец добавляется новый.

Однако, поскольку платформа очень интенсивно используется при тестировании стратегий по тиковым данным, скорость ее работы выходит на передний план, и мы постоянно ищем возможности как эту скорость повысить. Например, если в такой очереди будут храниться последние цены бумаги, то заполнение новыми данными будет происходить очень часто, и такая очередь будет оказывать сильное влияние на производительность всей системы.

Обычно std::deque реализован таким образом, что при добавлении одного элемента в памяти выделяется блок определенного размера, размещающий в себе некоторое количество элементов. При добавлении следующего элемента память выделяться не будет до тех пор, пока блок не будет заполнен полностью, после чего будет выделена память под новый блок. По мере удаления элементов эти блоки уничтожаются. Хотя выделение и уничтожение памяти происходит не на каждом элементе, тем не менее, поскольку в нашей реализации очереди происходит интенсивное последовательное добавление и удаление элементов, эти операции с памятью происходят очень часто, значительно снижая скорость работы системы.

Недавно я наткнулся на контейнер boost::circular_buffer, который имеет очень интересную реализацию. При инициализации этому контейнеру задается максимальный размер, и при добавлении элементов происходит его наполнение до этого размера. А дальше происходит самое интересное. Когда контейнер наполняется до максимума, при попытке добавить новый элемент он на самом деле просто перезаписывает элемент, находящийся на другом конце очереди, а его внутреннее состояние меняется таким образом, что конец очереди теперь смотрит на этот новый элемент, а начало — на элемент, который до этого был вторым. Получается своего рода кольцо, по которому происходит запись, откуда и название этого контейнера. При этом не происходит никакого дополнительного выделения и освобождения памяти, как в std::deque. Дополнительным бонусом к этому идет тот факт, что данные в этом контейнере хранятся в памяти последовательно, по тому же принципу, что и в std::vector. При обработке данных процессором этот факт дает дополнительный шанс на то, что соседние данные будут находиться в кеше процессора, и так называемый cache miss будет происходить реже.

Я задался целью протестировать производительность boost::circular_buffer и сравнить ее со скоростью нашей реализации очереди. Код теста представлен ниже.

Класс TimingUtil сделан для удобства, чтобы можно было легко измерять время работы участков кода, которые нас интересуют. Результат теста не разочаровал. При запуске на Ubuntu 16.04, gcc-5.4.0, процессор Intel Core i7 получаем ощутимый выигрыш в 3.6 раза:

Очевидно, в планах на один из ближайших релизов нас ждут некоторые изменения :)

3 Мая 2017

Один комментарий на «“boost::circular_buffer как более быстрый контейнер для входных данных”»

  1. […] Теперь давайте посмотрим, что мы выиграли от усовершенствованного способа расчета среднего. Для этого немного переделаем код и воспользуемся классом TimingUtil, который был описан в статье о контейнере boost::circular_buffer. […]

Добавить комментарий

Для отправки комментария вы должны авторизоваться.

Инвестирование с QuantPro Platform

Оптимальное соотношение между доходностью и риском