Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.

Boost.MultiIndex Performance



Contents

Introduction

Boost.MultiIndex helps the programmer to avoid the manual construction of cumbersome compositions of containers when multiindexing capabilities are needed. Furthermore, it does so in an efficient manner, both in terms of space and time consumption. The space savings stem from the compact representation of the underlying data structures, requiring a single node per element. As for time efficiency, Boost.MultiIndex intensively uses metaprogramming techniques producing very tight implementations of member functions which take care of the elementary operations for each index: for multi_index_containers with two or more indices, the running time can be reduced to half as long as with manual simulations involving several STL containers.

Manual simulation of a multi_index_container

The section of simulation of standard containers with multi_index_container shows the equivalence between single-index multi_index_containers and some STL containers. Let us now concentrate on the problem of simulating a multi_index_container with two or more indices with a suitable combination of standard containers.

Consider the following instantiation of multi_index_container:

typedef multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int>, std::greater >,
  >
> indexed_t;

indexed_t maintains two internal indices on elements of type int. In order to simulate this data structure resorting only to standard STL containers, one can use on a first approach the following types:

// dereferencing compare predicate
template<typename Iterator,typename Compare>
struct it_compare
{
  bool operator()(const Iterator& x,const Iterator& y)const
  {
    return comp(*x,*y);
  }

private:
  Compare comp;
};

typedef std::set<int>  manual_t1; // equivalent to indexed_t's index #0
typedef std::multiset<
  const int*,
  it_compare<
    const int*,
    std::greater<int>
  >
>                      manual_t2; // equivalent to indexed_t's index #1

where manual_t1 is the "base" container that holds the actual elements, and manual_t2 stores pointers to elements of manual_t1. This scheme turns out to be quite inefficient, though: while insertion into the data structure is simple enough:

manual_t1 c1;
manual_t2 c2;

// insert the element 5
manual_t1::iterator=c1.insert(5).first;
c2.insert(&*t1);
deletion, on the other hand, necessitates a logarithmic search, whereas indexed_t deletes in constant time:
// remove the element pointed to by it2
manual_t2::iterator it2=...;
c1.erase(*it2); // watch out! performs in logarithmic time
c2.erase(it1); 

The right approach consists of feeding the second container not with raw pointers, but with elements of type manual_t1::iterator:

typedef std::set<int>  manual_t1; // equivalent to indexed_t's index #0
typedef std::multiset<
  manual_t1::iterator,
  it_compare<
    manual_t1::iterator,
    std::greater<int>
  >
>                      manual_t2; // equivalent to indexed_t's index #1

Now, insertion and deletion can be performed with complexity bounds equivalent to those of indexed_t:

manual_t1 c1;
manual_t2 c2;

// insert the element 5
manual_t1::iterator=c1.insert(5).first;
c2.insert(t1);

// remove the element pointed to by it2
manual_t2::iterator it2=...;
c1.erase(*it2); // OK: constant time
c2.erase(it1); 

The construction can be extended in a straightworward manner to handle more than two indices. In what follows, we will compare instantiations of multi_index_container against this sort of manual simulations.

Spatial efficiency

The gain in space consumption of multi_index_container with respect to its manual simulations is amenable to a very simple theoretical analysis. For simplicity, we will ignore alignment issues (which in general play in favor of multi_index_container.)

Nodes of a multi_index_container with N indices hold the value of the element plus N headers containing linking information for each index. Thus the node size is

SI = e + h0 + иии + hN-1, where
e = size of the element,
hi = size of the i-th header.

On the other hand, the manual simulation allocates N nodes per element, the first holding the elements themselves and the rest storing iterators to the "base" container. In practice, an iterator merely holds a raw pointer to the node it is associated to, so its size is independent of the type of the elements. Suming all contributions, the space allocated per element in a manual simulation is

SM = (e + h0) + (p + h1) + иии + (p + hN-1) = SI + (N-1)p, where
p = size of a pointer.

The relative amount of memory taken up by multi_index_container with respect to its manual simulation is just SI / SM, which can be expressed then as:

SI / SM = SI / (SI + (N-1)p).

The formula shows that multi_index_container is more efficient with regard to memory consumption as the number of indices grow.

These considerations have overlooked an aspect of the greatest practical importance: the fact that multi_index_container allocates a single node per element, compared to the many nodes of different sizes built by manual simulations, diminishes memory fragmentation, which can show up in more usable memory available and better performance.

Time efficiency

From the point of view of computational complexity (i.e. big-O characterization), multi_index_container and its corresponding manual simulations are equivalent: inserting an element into a multi_index_container reduces to a simple combination of elementary insertion operations on each of the indices, and similarly for deletion. Hence, the most we can expect is a reduction (or increase) of execution time by a roughly constant factor. As we will see later, the reduction can be very significative for multi_index_containers with two or more indices.

In the special case of multi_index_containers with only one index, the best we can hope for is equal performance: the tests show that the performance degradation in this particular situation ranges from negligible to small, depending on the compiler used.

Performance tests

See source code used for measurements.

In order to assess the efficiency of multi_index_container, the following basic algorithm

multi_index_container<...> c;
for(int i=0;i<n;++i)c.insert(i);
for(iterator it=c.begin();it!=c.end();)c.erase(it++);

has been measured for different instantiations of multi_index_container at values of n 1,000, 10,000 and 100,000, and its execution time compared with that of the equivalent algorithm for the corresponding manual simulation of the data structure based on STL containers. The following compilers have been used:

with their default release settings. All tests were performed on a Wintel box equipped with a P4 1.5GHz processor and 256 MB RAM, running Microsoft Windows 2000 Professional SP2.

The relative memory consumption (i.e. the amount of memory allocated by a multi_index_container with respect to its manual simulation) is determined by dividing the size of a multi_index_container node by the sum of node sizes of all the containers integrating the simulating data structure.

Results for 1 ordered index

The following instantiation of multi_index_container was tested:

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >
  >
>

which is functionally equivalent to std::set<int>.

Memory consumption

GCC 3.1.1 ICC 7.1 MSVC 6.5
100% 100% 100%
Table 1: Relative memory consumption of multi_index_container with 1 ordered index.

The figures confirm that in this case multi_index_container nodes are the same size than those of its std::set counterpart.

Execution time

performance of multi_index_container with 1 ordered index
Fig. 1: Performance of multi_index_container with 1 ordered index.

As expected, multi_index_container does perform in this case somewhat worse than std::set. The degradation is within 10% for ICC and MSVC compilers, while in GCC peaks to 20%, which can be significative in certain applications. This latter result is presumably accounted for by a lower quality of the optimizing stage carried out by GCC.

Results for 1 sequenced index

The following instantiation of multi_index_container was tested:

multi_index_container<
  int,
  indexed_by<
    sequenced<>
  >
>

which is functionally equivalent to std::list<int>.

Memory consumption

GCC 3.1.1 ICC 7.1 MSVC 6.5
100% 100% 100%
Table 2: Relative memory consumption of multi_index_container with 1 sequenced index.

The figures confirm that in this case multi_index_container nodes are the same size than those of its std::list counterpart.

Execution time

performance of multi_index_container with 1 sequenced index
Fig. 2: Performance of multi_index_container with 1 sequenced index.

As in the former case, multi_index_container does not attain the performance of its STL counterpart. Again, worst results are those of GCC, with a degradation of up to 20% , while ICC and MSVC do not exceed a mere 5%.

Results for 2 ordered indices

The following instantiation of multi_index_container was tested:

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int> >
  >
>

Memory consumption

GCC 3.1.1 ICC 7.1 MSVC 6.5
90% 90% 90%
Table 3: Relative memory consumption of multi_index_container with 2 ordered indices.

These results concinde with the theoretical formula for SI=36 and p=4.

Execution time

performance of multi_index_container with 2 ordered indices
Fig. 3: Performance of multi_index_container with 2 ordered indices.

The experimental results confirm our hypothesis that multi_index_container provides an improvement on execution time by an approximately constant factor, which in this case ranges from 65% to 75% depending on the compiler.

Results for 1 ordered index + 1 sequenced index

The following instantiation of multi_index_container was tested:

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    sequenced<>
  >
>

Memory consumption

GCC 3.1.1 ICC 7.1 MSVC 6.5
87.5% 87.5% 87.5%
Table 4: Relative memory consumption of multi_index_container with 1 ordered index + 1 sequenced index.

These results concinde with the theoretical formula for SI=28 and p=4.

Execution time

performance of multi_index_container with 1 ordered index + 1 sequenced index
Fig. 4: Performance of multi_index_container with 1 ordered index + 1 sequenced index.

For n=103 and n=104, the results are in agreement with our theoretical analysis, showing a constant factor improvement of 60-75% with respect to the STL-based manual simulation. Curiously enough, this speedup gets even higher when n=105 for two of the compilers (35% for ICC, 25% for MSVC.) In order to rule out spurious results, the tests have been run many times, yielding similar outcoumes. A tentative explanation of this unexpected behavior may point to a degradation in the execution time of the manual simulation, attributable to poor performance of the standard STL allocator in ICC and MSVC when dealing with many objects of diverse sizes (the manual simulation is comprised of an std::set and a std::list, which demand differently sized nodes.)

Results for 3 ordered indices

The following instantiation of multi_index_container was tested:

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int> >,
    ordered_non_unique<identity<int> >
  >
>

Memory consumption

GCC 3.1.1 ICC 7.1 MSVC 6.5
86.7% 86.7% 86.7%
Table 5: Relative memory consumption of multi_index_container with 3 ordered indices.

These results concinde with the theoretical formula for SI=52 and p=4.

Execution time

performance of multi_index_container with 3 ordered indices
Fig. 5: Performance of multi_index_container with 3 ordered indices.

Execution time for this case is between 55% and 65% lower than achieved with an STL-based manual simulation of the same data structure.

Results for 2 ordered indices + 1 sequenced index

The following instantiation of multi_index_container was tested:

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int> >,
    sequenced<>
  >
>

Memory consumption

GCC 3.1.1 ICC 7.1 MSVC 6.5
84.6% 84.6% 84.6%
Table 6: Relative memory consumption of multi_index_container with 2 ordered indices + 1 sequenced index.

These results concinde with the theoretical formula for SI=44 and p=4.

Execution time

performance of multi_index_container with 2 ordered indices + 1 sequenced index
Fig. 6: Performance of multi_index_container with 2 ordered indices + 1 sequenced index.

In accordance to the expectations, execution time is improved by a fairly constant factor, which ranges from 45% to 55%.

Conclusions

We have shown that multi_index_container outperforms, both in space and time efficiency, equivalent data structures obtained from the manual combination of STL containers. This improvement gets larger when the number of indices increase.

In the special case of replacing standard containers with single-indexed multi_index_containers, the programmer should balance the benefits brought on by Boost.MultiIndex (subobject searching, in-place updating, etc.) against the resulting degradation in execution time. Depending on the compiler, this degradation can reach up to 20% of the original time.




Revised September 7th 2004

© Copyright 2003-2004 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)