разборнизкоуровневоеалгоритмыпроизводительностьeva

Как ускорить кольцевой буфер в 20 раз, просто запомнив чужой индекс

· 2 мин · BadRabbit

Днём я писал про кольцевой буфер в Еве и нашёл в нём проблему. Вот статья, которая объясняет, как сделать такой буфер по-настоящему быстрым.

Базовая очередь

Очередь «один пишет, один читает» (SPSC) на кольцевом буфере выглядит так:

  • писатель кладёт элемент в buffer[write_idx] и публикует новый write_idx;
  • читатель читает buffer[read_idx] и публикует новый read_idx;
  • чтобы понять, есть ли место, писатель читает read_idx; чтобы понять, есть ли данные, читатель читает write_idx.

Публикация идёт через атомарную запись с семантикой release, чтение — с acquire. Блокировок нет. Индексы, как положено, разнесены по разным кеш-линиям, чтобы не было false sharing.

Где всё равно медленно

Проблема в пункте 3: на каждой операции каждая сторона читает индекс другой стороны. Писатель только что изменил write_idx, кеш-линия у него в эксклюзивном состоянии. Читатель хочет её прочитать, и линия переходит в разделяемое состояние. Писатель снова пишет, и линию снова надо забирать. В среднем около трёх промахов кеша на операцию.

Решение: кешировать чужой индекс

Каждая сторона хранит у себя локальную копию индекса другой стороны и обновляет её, только когда это действительно нужно:

  • писатель смотрит на свою копию read_idx. Пока по ней есть место, он пишет, не трогая настоящий read_idx. Только если копия говорит «полно», он перечитывает настоящий индекс;
  • читатель точно так же держит копию write_idx.

Если читатель увидел, что доступно N элементов, следующие N−1 чтений ему вообще не нужно трогать индекс писателя.

Результаты

На тесте Ригторпа:

  • до: около 5,5 млн операций в секунду и ~350 млн промахов кеша;
  • после: около 112 млн операций в секунду и ~15 млн промахов.

Примерно в 20 раз быстрее, и это быстрее, чем очереди из Boost и Folly. Дальше можно выиграть ещё на пакетных операциях и huge pages, но это уже тонкая настройка под конкретное приложение.

Мой комментарий

Для Евы план исправления теперь в двух шагах:

  1. Развести head и tail по разным кеш-линиям. Сейчас они соседи, и это прямой false sharing.
  2. Добавить кешированные копии чужих индексов. Сделать это просто: копия живёт в локальной памяти процесса, а не в общем сегменте, потому что она нужна только своей стороне.

Красота этого трюка в том, что он не меняет протокол. Раскладка общей памяти остаётся той же, меняется только то, как часто каждая сторона в неё заглядывает.