производительность boost multi_index_container

Мне интересно узнать производительность multi_index_container для следующего варианта использования:

struct idx_1 {};
struct idx_2 {};

typedef multi_index_container<
    Object,
    indexed_by<
      // Keyed by: idx1
      hashed_unique<
        tag<idx_1>,
        unique_key >,
      // Keyed by: (attribute1, attribute2 and attribute3)
      ordered_non_unique<
        tag<idx_2>,
        composite_key<
          Object,
          attribute1,
          attribute2,
          attribute3 > >
    >
  > ObjectMap;

Мне нужна карта для сохранения объекта, а количество объектов должно быть более 300 000. при этом каждый объект имеет 1 уникальный ключ и 3 атрибута. Детали ключей:

  1. уникальный ключ является "уникальным" как имя
  2. каждый атрибут имеет только несколько возможных значений, скажем, всего 16 комбинаций. Таким образом, с 300 000 объектов каждая комбинация будет иметь список из 300 000/16 объектов.
  3. attribute1 необходимо время от времени изменять с одного значения на другое значение
  4. поиск объектов всегда выполняется с помощью unique_key, в то время как композитный ключ используется для итерации объектов с одним или несколькими атрибутами.

Для такого случая использования multi_index_container очень хорошо подходит, так как мне не нужно поддерживать несколько карт независимо друг от друга. Я считаю, что для части уникального ключа хорошим кандидатом является hashed_unique, а не order_unique.

Но меня крайне не устраивает часть «ordered_non_unique». Я не знаю, как это реализовано в boost. Я предполагаю, что это поможет поддерживать список объектов в одном списке для каждой комбинации, аналогичной unordered_map (простите меня, если это слишком наивно!). Если это так, изменение атрибута существующего объекта будет большой проблемой, поскольку для этого требуется: 1) просмотреть длинный список объектов для конкретной комбинации 2) выполнить равное сравнение 3) и переместить целевую комбинацию.

шаги, которые я подозреваю с высокой задержкой:

ObjectMap objects_;
auto& by_idx1 = objects_.get<idx1>();
auto it = by_idx1.find(some_unique_key);
Object new_value;
by_idx1.modify(it, [&](const Object& object) {
  object = new_value;
});

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


c++ performance boost-multi-index
person xiaodong    schedule 23.10.2014    source источник
comment
изменить атрибут существующего объекта будет большой проблемой, поскольку для этого требуется 1) просмотреть длинный список объектов для конкретной комбинации 2) выполнить сравнение на равных 3) и переместить целевую комбинацию. - вы должны описать это более подробно... когда вы хотите внести изменения, вы говорите, что будете знать значения атрибутов [1-3], но не уникальный ключ, но по мере повторения совпадений вы каким-то образом распознаете одно значение, которое нужно изменить, сравнивая некоторые другие поля? Если вы хотите, чтобы это было более эффективно, очевидно, вам нужен дополнительный индекс для этого/тех полей.   -  person Tony Delroy    schedule 23.10.2014
comment
@TonyD, я использую unique_key, чтобы найти объект, и вызываю функцию модификации multi_index_container для обновления атрибутов. Я считаю, что контейнер автоматически перестроит макет на основе обновленных атрибутов. Меня беспокоит эта операция по реорганизации. Отредактировал вопрос, чтобы было понятнее   -  person xiaodong    schedule 23.10.2014
comment
Я думаю, вы должны просто реализовать это, а затем измерить, чтобы увидеть, есть ли проблема с производительностью... Я был бы очень удивлен.   -  person Tony Delroy    schedule 23.10.2014

Ответы (2)


arrow_upward
0
arrow_downward

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

person Fabio A. Correa    schedule 23.10.2014

arrow_upward
0
arrow_downward

Как комментирует Фабио, лучший вариант — профилировать дело и посмотреть результат. В любом случае, индекс ordered_non_unique реализован точно так же, как std::multimap, а именно через обычное rb-дерево с условием, что элементы с эквивалентными ключами могут сосуществовать в контейнере; никаких списков эквивалентных элементов или чего-то еще. Что касается modify (для вашего конкретного варианта использования лучше подходит replace), выполняется следующая процедура:

  • Проверить, на месте ли элемент: O(1).
  • Если нет, переставьте: O (log n), что для 300 000 элементов составляет максимум 19 сравнений элементов (а не 300 000/16 = 18 750, как вы предлагаете): эти сравнения выполняются лексикографически в тройке (attribute1, attribute2, attribute3) . Это достаточно быстро или нет? Ну, это зависит от ваших требований к производительности, так что только профилирование может сказать.
person Joaquín M López Muñoz    schedule 23.10.2014
comment
Я не понимаю ту часть, которая в среднем составляет 300 000/16 элементов с одним и тем же ключом, как внутренне он сохраняется либо в multimap, либо в order_non_unique, потому что контейнер не может сохранить их в древовидной структуре, поскольку он не знает, является ли элемент должен перейти к левому дочернему дереву или правому дочернему дереву, поскольку они имеют одинаковое значение ключа. - person xiaodong; 24.10.2014
comment
Алгоритмы вставки rb-дерева работают одинаково с уникальными и неуникальными элементами; единственная дополнительная характеристика в случае эквивалентных элементов заключается в том, что они в конечном итоге вставляются таким образом, что линейный обход структуры встречает все эквивалентные элементы вместе. Например, если вы вставите (1,2,4,2,3,5,2,4), результирующий обход будет 1,2,2,2,3,4,4,5. - person Joaquín M López Muñoz; 24.10.2014