Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2005-10-26 11:14:39

Joaquín Mª López Muñoz <joaquin_at_[hidden]> writes:

> While in the process of replacing iterator helpers from
> <boost/operators.hpp>
> in favor of boost::iterator_facade as my internal iterator generation
> lib in
> Boost.MultiIndex, I've discovered an unpleasant increase in compilation
> times.
> The attached program shows the problem. Compilation times when
> using boost::iterator_facade are *way* higher than with good old
> boost::bidirectional_iterator_helper (to test it yourself, just
> comment/uncomment the line "#define USE_BOOST_ITERATOR"
> in the program):
> MSVC++ 6.0:
> iterator_facade: ~7 sec.
> bidirectional_iterator_helper: less than 1 sec.
> GCC 3.2
> iterator_facade: 4.9 sec.
> bidirectional_iterator_helper: 2.5 sec.

I had to modify the test to eliminate undefined behavior and make sure
dead code elimination didn't kick in (enclosed). Results:

GCC 3.4.4:
  Test 1 discarded

  Test 2
    with operator library: 1.469
    with iterator library: 2.282

  Test 3
    with operator library: 1.438
    with iterator library: 2.297

GCC 4.0.2:
  Test 1 discarded

  Test 2
    with operator library: 1.468
    with iterator library: 1.579

  Test 3
    with operator library: 1.453
    with iterator library: 1.563

MSVC 7.1
  Test 1 discarded

  Test 2
    with operator library: 1.219
    with iterator library: 1.187

  Test 3
    with operator library: 1.203
    with iterator library: 1.188

Unfortunately I couldn't get vc6 or vc7 to compile it :(

Now, here's the interesting thing: If you change the needless
postincrement you're using into preincrement, you get:

GCC 3.4.4:
  Test 1 discarded

  Test 2
    with operator library: 1.485
    with iterator library: 1.453

  Test 3
    with operator library: 1.437
    with iterator library: 1.453

> My questions:
> 1. Maybe the test program is flawed and has some (unseen by me)
> bias in favor of bidirectional_iterator_helper?

The postincrement comes to mind.

> 2. If not so, why is iterator_facade so very expensive? Is there
> any way to alleviate the problem?

I don't know; you could experiment with defining postincrement in
terms of preincrement. You could also look at what type
postfix_increment_result is computing in iterator_facade.hpp

> As it stands, I'm not so sure it's a good idea to adopt
> boost::iterator_facade:
> my local tests for Boost.MultiIndex show an overall increase in
> compilation
> time of around 25% :(

If your code is correct with bidirectional_iterator_helper, of course
there's no need to switch.

Dave Abrahams
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at