Re: [boost] [parameter] Compile-time performance

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