Subject: Re: [boost] [parameter] Compile-time performance
From: Domagoj Saric (dsaritz_at_[hidden])
Date: 2011-02-26 11:37:03
"Dave Abrahams" <dave_at_[hidden]> wrote in message
news:m2sjvc2l36.wl%dave_at_boostpro.com...
> At Fri, 25 Feb 2011 13:58:48 +0100,
> Domagoj Saric wrote:
>> The most likely suspect is the usage of a forward-sequence for parameter
>> type storage (argument packs) from which you fetch passed parameters
>> using
>> key-based lookup with the value_type<> metafunction. In my code I use an
>> associative container (mpl::map) for the task which has a
>> 'natural'/'efficient' key-based lookup...
>
> Heh, I came up with the idea for the O(1) instantiation mpl::map
> mechanism and used the same basic mechanism for lookup in
> Boost.Parameter, so what you're saying is a bit surprising.
Well, the documentation
(http://www.boost.org/doc/libs/release/libs/parameter/doc/html/reference.html
@ 3.1 ArgumentPack) says "Every ArgumentPack is also a valid MPL Forward
Sequence..." and by looking at the ParametersSpec::bind<> implementation it
did look to me like a list/'chained'-like structure...(although my knowledge
of MPL and PP internals might quite be insufficient enough to mistake a list
for a map...)...
>> To confirm this I minimally changed the Boost.Parameter-based version of
>> my
>> code only to use mpl::maps instead of Boost.Parameter ArgumentPacks and
>> built time fell to ~58 seconds...(true, this does not have all the
>> compile-time check for correct usage and concept validation that
>> ParameterSpecs and ArgumentPacks have but I'd expect this to have a much
>> smaller effect than key-based lookup on a forward sequence)...
>
> I think you should do some more measurement :-)
Why? / You think that I am wrong in my assumption that key-based lookup on a
'plain forward sequence' would trump type requirements validation?
I'm assuming this solely from my TMP experience, where most of compile-time
inefficiencies were caused by 'incorrect'/'unhappy' combination of lookup
type (key, index...) and container type (random, associative)...and
sometimes they were/are unsolvable (e.g. Fusion's lack of proper associative
containers https://svn.boost.org/trac/boost/ticket/4228 ...)...
+ I used only a single type requirement (mpl::is_sequence<>) for one of the
parameters and did not notice an improvement/difference without it...If you
think that even the existence of the type requirement validating machinery
(within Boost.Parameter) has an effect comparable or even greater than
container lookup perhaps we could test with that code commented out (if you
could explain which parts to comment out I could do it when I catch the
time)...
>> Is there an inherent issue that forbids the use of an associative
>> container
>> for ArgumentPacks or can this be fixed?
>
> ArgumentPacks are associative.
As previously said, the documentation only says forward (not also
associative) sequence...
> In fact, though, Matt Calabrese proved
> that the basic strategy of MPL associative containers did not produce
> the expected speedups. See "Instantiations Must Go" at
> https://www.boostcon.com/community/wiki/show/private/2010/ for more
> details.
Hm...I read the two PDFs with the video playing along side and noticed
nothing about MPL associative containers...only about how FTMPL failed to
produce expected speedups...
+ From my experience, MPL associative containers do produce a very
significant improvement for key-based lookup...
> I would, however, love to speed up Boost.Parameter so if you find the
> actual cause or a way to do it, I'm all ears!
If only it internally used MPL (and Fusion perhaps) instead of doing things
from scratch (e.g. template_keyword -> mpl::pair, argument pack -> mpl:map
...) I might have an easier time following its internal flow (in the short
pauses from 'real work' :)...
Well, the first step I guess would be to disable type requirement validation
and measure the difference...
ps. have you used SW's template profiler (with B.P.) ?
-- "What Huxley teaches is that in the age of advanced technology, spiritual devastation is more likely to come from an enemy with a smiling face than from one whose countenance exudes suspicion and hate." Neil Postman