Это сокращённый и адаптированный перевод моей статьи на DEV Community.

Однажды я заменил std::deque на boost::circular_buffer в своем аудиоплеере Kalinka. Буфер является критическим компонентом и используется для передачи данных между узлами аудиографа: от считывания из сети или файла, декодирования и воспроизведения. Кольцевой буфер казалось бы, лучше подходил для задачи, микробенчмарк показывал ускорение в 2–3 раза, а сама замена выглядела почти очевидной.

После неё загрузка процессора на Raspberry Pi при воспроизведении выросла примерно с 2% до 25%.

Через неделю я вернул std::deque.

В Kalinka Player данные проходят через несколько ограниченных FIFO-буферов:

сеть/файл → декодер → аудиовыход

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

Изначально там использовался std::deque<uint8_t>:

data.insert(data.end(), source, source + size);

std::copy_n(data.begin(), size, destination);
data.erase(data.begin(), data.begin() + size);

Но std::deque хранит данные отдельными блоками. А boost::circular_buffer заранее выделяет один массив и просто перемещает позиции начала и конца.

Для ограниченного FIFO это выглядело правильнее:

• одна аллокация;

• фиксированная ёмкость;

• удаление из начала за O(1);

• хорошая локальность данных.

Я написал тест с элеметнами фиксированного размера (32-байта). Результат подтвердил ожидания: circular_buffer был быстрее примерно в 2–3 раза.

Я заменил контейнер, закоммитил изменения и довольный принялся совершенствованием других компонентов.

До изменения плеер потреблял около 1–3% CPU. После — 20–30%. Я не сразу понял почему.

Через некоторое время нашлась очевидная ошибка. Я удалял данные обычным erase():

data.erase(data.begin(), data.begin() + size);

У boost::circular_buffer для этого есть специализированный метод:

data.erase_begin(size);

Замена ускорила само удаление почти в сто раз. Нагрузка снизилась, но всё ещё оставалась намного выше исходной.

Значит, проблема была не только в erase().

Первый тест измерял добавление и удаление небольших отдельных объектов.

Реальная программа делала другое: копировала блоки байтов размером примерно 16 КБ.

Я переписал тест под настоящую нагрузку:

• буфер на 768 КБ;

• блоки по 16 КБ;

• несколько гигабайт данных;

• тот же код insert() и copy_n(), что использовался в плеере.

И получил противоположный результат.

При установившемся потоке скорость записи выглядела примерно так:

В этой операции std::deque оказался почти в девять раз быстрее. Бывает, но я не мог оставить это так и пытался понять.

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

Хотя std::deque не хранит данные одним массивом, используемая мной реализация libstdc++ умеет эффективно копировать его внутренние блоки.

У boost::circular_buffer физическая память непрерывна, но логические данные могут переходить через конец массива:

[ вторая часть ][ свободно ][ первая часть ]

Обычный итератор должен на каждом шаге проверять, не пора ли перейти в начало массива. Для универсального std::copy_n() это уже не один непрерывный диапазон.

В моей версии Boost и libstdc++ код через итераторы не превращался в несколько крупных вызовов memmove. Вместо этого выполнялся значительно более дорогой проход по элементам.

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

Да. У него есть array_one() и array_two(), которые возвращают два физически непрерывных участка.

Копирование можно было бы написать вручную:

auto first = data.array_one();
auto second = data.array_two();

std::memcpy(destination, first.first, first.second);

if (second.second > 0) {
    std::memcpy(
        destination + first.second,
        second.first,
        second.second
    );
}

Но это означало бы больше кода, больше граничных случаев и больше тестов.

std::deque уже обеспечивал нужную производительность, поэтому я просто вернул его.

Микробенчмарк не соврал. Он честно показал, что circular_buffer быстрее в том сценарии, который я придумал.

Проблема была в том, что это был не мой сценарий.

Выбирать структуру данных только потому, что она «правильно» звучит для задачи, опасно. Даже асимптотически подходящий контейнер может проиграть из-за деталей реализации итераторов, алгоритмов стандартной библиотеки и конкретного размера операций.

Так, лишний раз убедился, что никогда не стоит пренебрегать измерением производительности на рабочей системе, так как синтетические тесты не всегда реализуют точно такой же сценарий.

Полный код тестов можно посмотреть в GitHub Gist.