Boost.MultiIndex PerformanceContents
Introduction
Boost.MultiIndex helps the programmer to avoid the manual construction of cumbersome
compositions of containers when multi-indexing 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 Manual simulation of a
|
Compiler | Settings | OS and CPU |
---|---|---|
GCC 3.4.5 (mingw special) | -O3 |
Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM |
Intel C++ 7.1 | default release settings | Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM |
Microsoft Visual C++ 8.0 | default release settings, _SECURE_SCL=0 |
Windows XP on P4 Xeon 3.2 GHz, 1 GB RAM |
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.
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>
.
GCC 3.4.5 | ICC 7.1 | MSVC 8.0 |
---|---|---|
80% | 80% | 80% |
multi_index_container
with 1
ordered index.
The reduction in memory usage is accounted for by the optimization technique implemented in Boost.MultiIndex ordered indices, as explained above.
Fig. 1: Performance of multi_index_container
with 1 ordered index.
Somewhat surprisingly, multi_index_container
performs slightly
better than std::set
. A very likely explanation for this behavior
is that the lower memory consumption of multi_index_container
results in a higher processor cache hit rate.
The improvement is smallest for GCC, presumably because the worse quality of
this compiler's optimizer masks the cache-related benefits.
The following instantiation of multi_index_container
was tested:
multi_index_container< int, indexed_by< sequenced<> > >
which is functionally equivalent to std::list<int>
.
GCC 3.4.5 | ICC 7.1 | MSVC 8.0 |
---|---|---|
100% | 100% | 100% |
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.
Fig. 2: Performance of multi_index_container
with 1 sequenced index.
multi_index_container
does not attain the performance
of its STL counterpart, although the figures are close. Again, the worst results
are those of GCC, with a degradation of up to 7%, while ICC and MSVC do not
exceed a mere 5%.
The following instantiation of multi_index_container
was tested:
multi_index_container< int, indexed_by< ordered_unique<identity<int> >, ordered_non_unique<identity<int> > > >
GCC 3.4.5 | ICC 7.1 | MSVC 8.0 |
---|---|---|
70% | 70% | 70% |
multi_index_container
with 2
ordered indices.
These results concinde with the theoretical formula for SI = 28, N = O = 2 and p = w = 4.
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 lies around 60%. There is no obvious explanation for the
increased advantage of multi_index_container
in MSVC for
n=105.
The following instantiation of multi_index_container
was tested:
multi_index_container< int, indexed_by< ordered_unique<identity<int> >, sequenced<> > >
GCC 3.4.5 | ICC 7.1 | MSVC 8.0 |
---|---|---|
75% | 75% | 75% |
multi_index_container
with 1
ordered index + 1 sequenced index.
These results concinde with the theoretical formula for SI = 24, N = 2, O = 1 and p = w = 4.
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 50-65% with respect to the STL-based manual simulation. Curiously enough, this speedup gets even higher when n=105 for two of the compilers, namely GCC and ICC. In order to rule out spurious results, the tests have been run many times, yielding similar outcoumes. Both test environments are deployed on the same machine, which points to some OS-related reason for this phenomenon.
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> > > >
GCC 3.4.5 | ICC 7.1 | MSVC 8.0 |
---|---|---|
66.7% | 66.7% | 66.7% |
multi_index_container
with 3
ordered indices.
These results concinde with the theoretical formula for SI = 40, N = O = 3 and p = w = 4.
Fig. 5: Performance of multi_index_container
with 3 ordered indices.
Execution time for this case is between 45% and 55% lower than achieved with an STL-based manual simulation of the same data structure.
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<> > >
GCC 3.4.5 | ICC 7.1 | MSVC 8.0 |
---|---|---|
69.2% | 69.2% | 69.2% |
multi_index_container
with 2
ordered indices + 1 sequenced index.
These results concinde with the theoretical formula for SI = 36, N = 3, O = 2 and p = w = 4.
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%.
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_container
s, the performance of Boost.MultiIndex
is comparable with that of the tested STL implementations, and can even yield
some improvements both in space consumption and execution time.
Revised May 9th 2006
© Copyright 2003-2006 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)