Повышаю. MultiIndex помогает программисту избежать ручной сборки громоздких композиций контейнеров при необходимости многоиндексации. Кроме того, он делает это эффективно, как с точки зрения пространства, так и с точки зрения потребления времени. Экономия пространства обусловлена компактным представлением базовых структур данных, требующих единого узла на элемент. Что касается эффективности времени, то рост. MultiIndex интенсивно использует методы метапрограммирования, которые производят очень жесткие реализации функций-членов, которые заботятся об элементарных операциях для каждого индекса: для<multi_index_container>s с двумя или более индексами время работы может быть уменьшено до половины, как с ручным моделированием с участием нескольких контейнеров STL.
В разделеэмуляции стандартных контейнеров с<multi_index_container>показана эквивалентность между одноиндексными<multi_index_container>и некоторыми контейнерами STL. Теперь остановимся на проблеме моделирования<multi_index_container>с двумя или более индексами с подходящей комбинацией стандартных контейнеров.
<indexed_t>поддерживает два внутренних индекса на элементах типа<int>. Чтобы смоделировать эту структуру данных, прибегая только к стандартным контейнерам STL, можно использовать при первом подходе следующие типы:
// dereferencing compare predicatetemplate<typenameIterator,typenameCompare>structit_compare{booloperator()(constIterator&x,constIterator&y)const{returncomp(*x,*y);}private:Comparecomp;};typedefstd::set<int>manual_t1;// equivalent to indexed_t's index #0typedefstd::multiset<constint*,it_compare<constint*,std::greater<int>>>manual_t2;// equivalent to indexed_t's index #1
где<manual_t1>— «базовый» контейнер, который содержит фактические элементы, и<manual_t2>хранит указатели на элементы<manual_t1>. Эта схема оказывается довольно неэффективной, правда: при этом вставка в структуру данных достаточно проста:
manual_t1c1;manual_t2c2;// insert the element 5manual_t1::iteratorit1=c1.insert(5).first;c2.insert(&*it1);
deletion, on the other hand, necessitates a logarithmic search, whereas
indexed_t deletes in constant time:
// remove the element pointed to by it2manual_t2::iteratorit2=...;c1.erase(**it2);// watch out! performs in logarithmic timec2.erase(it2);
Правильный подход заключается в подаче второго контейнера не сырыми указателями, а элементами типа<manual_t1::iterator>:
typedefstd::set<int>manual_t1;// equivalent to indexed_t's index #0typedefstd::multiset<manual_t1::iterator,it_compare<manual_t1::iterator,std::greater<int>>>manual_t2;// equivalent to indexed_t's index #1
Теперь вставка и удаление могут быть выполнены с ограничениями сложности, эквивалентными<indexed_t>:
manual_t1c1;manual_t2c2;// insert the element 5manual_t1::iteratorit1=c1.insert(5).first;c2.insert(it1);// remove the element pointed to by it2manual_t2::iteratorit2=...;c1.erase(*it2);// OK: constant timec2.erase(it2);
Конструкция может быть расширена простым способом для обработки более двух индексов. Далее мы сравним инстанциации<multi_index_container>с подобными ручными симуляциями.
Прирост в потреблении пространства<multi_index_container>по отношению к его ручному моделированию поддается очень простому теоретическому анализу. Для простоты мы будем игнорировать вопросы выравнивания (которые в целом играют в пользу<multi_index_container>).
Узлы<multi_index_container>с индексамиNсодержат значение элемента плюс заголовкиN, содержащие информацию о ссылках для каждого индекса. Таким образом, размер узла
SI = e + h0 + ··· +
hN-1, where e = size of the element, hi = size of the i-th header.
С другой стороны, ручное моделирование выделяетNузлов на элемент, первый из которых удерживает сами элементы, а остальные хранят итераторы в «базовом» контейнере. На практике итератор просто удерживает необработанный указатель на узле, с которым он связан, поэтому его размер не зависит от типа элементов. Подводя итог всем вкладам, пространство, выделенное на элемент в ручном моделировании, является
SM = (e + h0) +
(p + h1) + ··· +
(p + hN-1) =
SI + (N-1)p, where p = size of a pointer.
Относительный объем памяти, занимаемый<multi_index_container>в отношении его ручного моделирования, составляет всегоSI / SM, который может быть выражен следующим образом:
SI / SM =
SI / (SI + (N-1)p).
Формула показывает, что<multi_index_container>более эффективно в отношении потребления памяти по мере роста числа индексов. Было сделано неявное предположение, что заголовки<multi_index_container>индексных узлов имеют тот же размер, что и их аналоги в STL-контейнерах; но есть конкретный случай, в котором это часто не так: упорядоченные индексы используют методпространственной оптимизации, который не присутствует во многих реализациях<std::set>, давая дополнительное преимущество<multi_index_container>s одного системного слова на упорядоченный индекс. С учетом этого факта прежнюю формулу можно скорректировать следующим образом:
SI / SM =
SI / (SI + (N-1)p + Ow),
гдеO— число упорядоченных индексов контейнера, аw— размер системного слова (обычно 4 байта на 32-битных архитектурах).
Эти соображения упустили из виду аспект наибольшей практической важности: тот факт, что<multi_index_container>выделяет один узел на элемент, по сравнению со многими узлами разных размеров, построенными с помощью ручного моделирования, уменьшает фрагментацию памяти, которая может отображаться в более удобной доступной памяти и лучшей производительности.
С точки зрения вычислительной сложности (т.е. характеристики большого О)<multi_index_container>и соответствующие ей ручные симуляции эквивалентны: вставка элемента в<multi_index_container>сводится к простой комбинации элементарных операций вставки на каждом из индексов и аналогично для удаления. Следовательно, самое большее, что мы можем ожидать, это сокращение (или увеличение) времени исполнения примерно постоянным фактором. Как мы увидим позже, сокращение может быть очень значительным для<multi_index_container>с двумя или более индексами.
В особом случае<multi_index_container>с только одним индексом результирующая производительность будет примерно соответствовать производительности эквивалентных контейнеров STL: тесты показывают, что по отношению к STL наблюдается незначительная деградация, и даже в некоторых случаях небольшое улучшение.
Измеряется для различных инстанциаций<multi_index_container>при значенияхn1000, 10 000 и 100 000, и время его выполнения по сравнению с эквивалентным алгоритмом для соответствующего ручного моделирования структуры данных на основе контейнеров STL. В приведенной ниже таблице описаны используемые среды испытаний.
Tests environments.
Compiler
Settings
OS and CPU
GCC 3.4.5 (mingw special)
<-O3>
Windows 2000 Pro на P4 1,5 ГГц, 256 МБ ОЗУ
Intel C++ 7.1
Параметры выпуска по умолчанию
Windows 2000 Pro на P4 1,5 ГГц, 256 МБ ОЗУ
Microsoft Visual C++ 8.0
По умолчанию,<_SECURE_SCL=0>
Windows XP на P4 Xeon 3,2 ГГц, 1 ГБ ОЗУ
Относительное потребление памяти (т.е. количество памяти, выделенное<multi_index_container>в отношении его ручного моделирования) определяется путем деления размера узла<multi_index_container>на сумму размеров узлов всех контейнеров, интегрирующих имитирующую структуру данных.
Fig. 1: Performance of multi_index_container with 1 ordered index.
Что удивительно,<multi_index_container>работает немного лучше, чем<std::set>. Очень вероятное объяснение такого поведения заключается в том, что более низкое потребление памяти<multi_index_container>приводит к более высокой скорости попадания кэша процессора. Улучшение является наименьшим для GCC, по-видимому, потому, что худшее качество оптимизатора этого компилятора маскирует преимущества, связанные с кэшем.
Fig. 2: Performance of multi_index_container with 1 sequenced index.
<multi_index_container>не достигает производительности своего аналога STL, хотя цифры близки. Опять же, худшие результаты - это GCC с деградацией до 7%, в то время как ICC и MSVC не превышают всего 5%.
Fig. 3: Performance of multi_index_container with 2 ordered indices.
Экспериментальные результаты подтверждают нашу гипотезу о том, что<multi_index_container>обеспечивает улучшение времени выполнения примерно постоянным фактором, который в этом случае составляет около 60%. Нет очевидного объяснения повышенного преимущества<multi_index_container>в MSVC дляn=105.
Fig. 4: Performance of multi_index_container with 1 ordered index
+ 1 sequenced index.
Дляn=103иn=104результаты согласуются с нашим теоретическим анализом, показывая постоянное улучшение коэффициента 50-65% по отношению к ручному моделированию на основе STL. Любопытно, что это ускорение становится еще выше, когдаn=105для двух компиляторов, а именно GCC и ICC. Чтобы исключить ложные результаты, тесты проводились много раз, приводя к аналогичным результатам. Обе тестовые среды развернуты на одной машине, что указывает на некоторую причину этого явления.
Мы показали, что<multi_index_container>превосходит по эффективности как в пространстве, так и во времени эквивалентные структуры данных, полученные из ручной комбинации контейнеров STL. Это улучшение усиливается при увеличении числа индексов.
В особом случае замены стандартных контейнеров одноиндексными<multi_index_container>с производительностью Boost. MultiIndex сопоставим с тестируемыми реализациями STL и может даже привести к некоторым улучшениям как в пространстве, так и во времени выполнения.
