[Boost-users] Re: compilation time [was: Re: multi_index: performance issue]

From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2004-12-22 07:01:14

Stanislas RENAN <stanislas.renan <at> nsktechnologies.com> writes:

> 
> Joaquin M Lopez Munoz a écrit :
> > I post the code at the end of the message.
> I also post the patch using equal_range().

I haven't tried the equal_range patch. As for your code
without the patch, I have built it unmodified and here are
my figures:

MSVC++ 6.0 SP5, machine P4 1.6 GHz 261 KB
Release mode

Case A: tailleEnsemble=1000

multi = 0
STL   = 0
Recherche
multi = 156
STL   = 140

Sometimes, multi insertion jumps to 15, some other times
it is STL insertion that jumps to 15. This case is too
fast to obtain significant results.

Case B: tailleEnsemble=10000

Insertion
multi = 62
STL   = 78
Recherche
multi = 297
STL   = 281

Some variations on succesive runs, but the tendency
(less insertion time, somewhat slower on search) remains.

Case C: tailleEnsemble=100000

Insertion
multi = 1188
STL   = 1406
Recherche
multi = 437
STL   = 454

In some runs, multi search is the same or slightly larger
than STL search. multi insertion remains always below
the STL case.

Another issue you haven't considered is memory comsumption.
Your EmployeeMapper class takes the following per element:

* one employee object
* 13 B (map node) + 1 int + 1 pointer (ID index)
* 13 B (map node) + 1 std::string + 1 pointer (Name index)
* 13 B (map node) + 1 int + 1 pointer (age index)

that is, sizeof(employee) + sizeof(string) + 59 bytes per element.
Boost.MultiIndex takes:

* one employee object
* 13 B (index node) (ID index)
* 13 B (index node) (Name index)
* 13 B (index node) (age index)

which sums sizeof(employee) + 39 bytes per element.
Of course, EmployeeMapper can do better (having underlying
sets instead of maps so as to not duplicate the keys), but
even so you won't attain the memory efficiency of
Boost.MultiIndex by at least 8 bytes per element.

As for building times, I have roughly

Debug mode: approx. 15 s.
Release mode: approx. 15 s

If I undefine COMPILE_BOOST, your program does not
compile, so I can't compare.

> For now, to refocus on MI, I have roughly the four elements :
> 1-it is complex to write it the first times, but it can be encapsulated, 
> as STL is in my example ;

I'm sorry I couldn't make it simpler. The idea is
to leverage as much STL expertise as possible, so that
the programmer hasn't to learn a new interface.

> 2-it is as efficient as the STL is, but not more in my example ;

See above.

> 3-it stresses the compiler a lot, which adds compilation time yet to be 
> evaluated ;

Yep.

> 4-it avoids writing encapsulating classes if we are familiar with it, 
> which cannot be done with basic containers of the STL.

OK

> 
> If point 2 is changed from "as efficient" to "more efficient", it
> certainly will weight on decisions.
> I admit that my test example is basic, and may not show the capabilities
> of MI, but that's a real life example.

Well, of course it is your job to decide whether
Boost.MultiIndex is any use to you, and it might not be so.
I try not to evangelize (too much), but IMHO
multi_index_container has real advantages that might come
up when you need to turn your EmployeeMapper into an
industrial-strength component:

* It is exception safe.
* Removal is taken care of (you talk about this yourself
later).
* Includes updating functions.
* Has a key extraction model that you either has to
rewrite or else mimic as you have done with maps, thus
incurring some memory overhead.
* Perhaps most importantly, adding a new index is
simple. With a homemade component, adding a new index
involves lots of additional (admittedly boilerplate)
coding. Heck, this is what templates are about, avoiding
code repetition.

On the downside, compilation times increase
significantly :(

In any case, I'd be happy to know what your final decision
regarding Boost.MultiIndex adoption is. If you join
the party, count me in for as much support as you need.

Best,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo