Std::vector -подобный класс, оптимизированный для хранения небольшого количества элементов

В одной критичной для времени части программы есть член класса, который выглядит так: std::vector m_vLinks; Во время профилирования я заметил, что около 99,98% исполнений этот вектор содержит только 0 или 1 элемент. Однако в очень редких случаях это может быть больше. Этот вектор определенно является узким местом по профилировщику, поэтому я думаю о следующей оптимизации:

  • Создайте ручной класс с векторным интерфейсом
  • Этот класс будет содержать истинный размер, один элемент и необязательный указатель на вектор
  • В этом случае, когда вектор содержит 1 элемент, не будет никаких распределений динамической памяти, а также доступ к этому элементу будет (бит) быстрее из-за удаления одной косвенности.
  • Когда нам нужно удерживать больше данных, вектор динамически выделяется
  • Конечно, этот вектор не будет содержать один блок памяти, содержащий все элементы (не нужны здесь), а также некоторые операции будут более сложными

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

Я уже думал о boost:: array, но не хочу, чтобы ограничение по размеру накладывало

Ответы

Ответ 1

LLVM имеет класс для SmallVector.

Ответ 2

В неотчуждаемой части вашего кода выполните: m_vLinks.reserve(1);. Таким образом, в критически важной части обычно не будет динамического выделения.

Ответ 3

Моя первая попытка - оптимизировать распределитель памяти. Наивные malloc реализации не слишком эффективны, вы можете попробовать tcmalloc или jemalloc.

Моя вторая попытка - изменить распределитель. Ховард Хиннант продемонстрировал, как использовать генератор состояний, который имеет некоторую память, предварительно распределенную в стеке. Это только стандарт совместим с С++ 11, но может уже поддерживаться.

Моя третья попытка состояла в том, чтобы изменить код и предварительно выделить память, если это возможно. Вместо того, чтобы создавать vector заново каждый раз, вы можете сохранить его: его емкость не будет уменьшаться, и поэтому последующее использование не будет выделять память.

Существует мало шансов, что реализация homebrew будет соответствовать скорости классов std::vector<T>, так как многие из его методов настроены для максимальной производительности.

Ответ 4

Я обычно использую std::list для этих случаев. Операции O (N) в std::list не повреждают меня, когда N == 1.