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

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

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

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

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

источник

2012-02-21 Alex Zakharenko

Какие операции занимают большую часть времени в вашем сценарии? – sharptooth

является узким местом, потому что вы часто создаете новые? В этом случае я сомневаюсь, что ваша оптимизация поможет ... –

Выделение и освобождение динамического буфера вектора (я использую пул объектов для хранения объектов, которые имеют этот элемент, но в любом случае необходимо периодически очищать их путем замены вектора ссылок с пустым вектором, хотя это не частая операция). –

LLVM имеет класс для этого называется SmallVector.

источник

2012-02-21 14:45:34

Конечно, один вопрос: это быстрее, правда? Существует довольно тяжелая иерархия, и я действительно задаюсь вопросом, может ли она управлять скоростью «вектора» или нет. –

В целом, иерархии не делают код медленным. Компиляторы видят это прямо. В частности, если вы видите такие вещи, как 'is_pod ' в иерархии, вы знаете, что это компиляция времени. – MSalters

@MSalters: Извините, если это звучит не так. Я имел в виду, что для меня слишком много кода для глазного яблока, будет ли он быстрее, чем «вектор». –

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

источник

2012-02-21 14:58:41 MSalters

Я полагаю, что в список добавлено не менее 1 динамического распределения памяти (даже если это первый элемент). Мне нужно решение, которое могло бы содержать 1 элемент без каких-либо динамических распределений. –

Правда, но динамическое распределение всегда одного и того же размера (единственный узел), в отличие от std :: vector, а указатель узла всегда разыменовывается. Это на самом деле не так плохо, как вы думаете, на современном оборудовании и с современными распределителями. – MSalters

Динамическое распределение решается пулом, которым он пользуется. Однако это приводит к плохой локальности. – phkahler

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

источник

2012-02-21 15:00:10

Мне нравится ваше предложение. Просто. Будь проще. (+1) –

http://stackoverflow.com/a/36371057/1599699 – Andrew

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

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

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

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

источник

2012-02-21 15:05:06

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

ответ

Смежные вопросы