[parameter] Compile-time performance
I have an in-house framework a part of which is very similar to Boost.Parameter so I tried to refactor it to use Boost.Parameter and, unfortunately, noticed a big compile-time hit (the project has a very large number instantiations of class templates with 'named non-type template parameters'). With my code (and MSVC++ 10) build time was ~56 seconds with a maximum cl.exe memory allocation size of ~720 MB. After switching to Boost.Parameter build time whent to ~2:24 seconds with a maximum cl.exe memory allocation size of ~815 MB. 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... 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)... Is there an inherent issue that forbids the use of an associative container for ArgumentPacks or can this be fixed? -- "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
At Fri, 25 Feb 2011 13:58:48 +0100, Domagoj Saric wrote:
I have an in-house framework a part of which is very similar to Boost.Parameter so I tried to refactor it to use Boost.Parameter and, unfortunately, noticed a big compile-time hit (the project has a very large number instantiations of class templates with 'named non-type template parameters'). With my code (and MSVC++ 10) build time was ~56 seconds with a maximum cl.exe memory allocation size of ~720 MB. After switching to Boost.Parameter build time whent to ~2:24 seconds with a maximum cl.exe memory allocation size of ~815 MB.
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.
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 :-)
Is there an inherent issue that forbids the use of an associative container for ArgumentPacks or can this be fixed?
ArgumentPacks are associative. 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. 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! -- Dave Abrahams BoostPro Computing http://www.boostpro.com
"Dave Abrahams" <dave@boostpro.com> wrote in message news:m2sjvc2l36.wl%dave@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
At Sat, 26 Feb 2011 17:37:03 +0100, Domagoj Saric wrote:
"Dave Abrahams" <dave@boostpro.com> wrote in message news:m2sjvc2l36.wl%dave@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...
So does MPL's map. It uses function overloading to do the lookup so you don't have to walk the map.
(although my knowledge of MPL and PP internals might quite be insufficient enough to mistake a list for a map...)...
It might :-)
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 think you don't understand how MPL maps work and you missed the mechanism in Boost.Parameter. Therefore, I think you don't understand the source of the slowdown.
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' :)...
We gave that approach serious consideration and would of course have preferred to do it that way. I don't recall the reasons we decided against it.
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.) ?
Not yet. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
"Dave Abrahams" <dave@boostpro.com> wrote in message news:m262s6r9pi.wl%dave@boostpro.com...
I think you don't understand how MPL maps work and you missed the mechanism in Boost.Parameter. Therefore, I think you don't understand the source of the slowdown.
It might well be so...but...the slowdown almost disappeared when I replaced argument packs with mpl::maps...and the only thing that I know of that went with along with that change is the type requirements checking...so it's either arg-pack lookup or the requirement checking...
We gave that approach serious consideration and would of course have preferred to do it that way. I don't recall the reasons we decided against it.
That's what comments are for :P Perhaps it was exactly compile time performance (i.e. you wanted more descriptive names, e.g. template_keyword instead of mpl::pair, and that would require wrapping mpl types which incurs additional instantiations...)...
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.) ?
Not yet.
Well if you are really into trying to improve Boost.Parameter the two obvious things to try is the elimination of the requirement checks and SW's template profiler...I am willing to help however I will not be by my work computer for the next 10 days... -- "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
At Sat, 26 Feb 2011 19:07:37 +0100, Domagoj Saric wrote:
"Dave Abrahams" <dave@boostpro.com> wrote in message news:m262s6r9pi.wl%dave@boostpro.com...
I think you don't understand how MPL maps work and you missed the mechanism in Boost.Parameter. Therefore, I think you don't understand the source of the slowdown.
It might well be so...but...the slowdown almost disappeared when I replaced argument packs with mpl::maps...and the only thing that I know of that went with along with that change is the type requirements checking...so it's either arg-pack lookup or the requirement checking...
Likely the latter, but it could still be something else. Template compilation speed is still something of a black art.
We gave that approach serious consideration and would of course have preferred to do it that way. I don't recall the reasons we decided against it.
That's what comments are for :P
Thanks, dad.
Perhaps it was exactly compile time performance (i.e. you wanted more descriptive names, e.g. template_keyword instead of mpl::pair, and that would require wrapping mpl types which incurs additional instantiations...)...
Probably.
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.) ?
Not yet.
Well if you are really into trying to improve Boost.Parameter the two obvious things to try is the elimination of the requirement checks and SW's template profiler...I am willing to help however I will not be by my work computer for the next 10 days...
I won't have time to get near that code in the next 10 days, so I can wait :-) -- Dave Abrahams BoostPro Computing http://www.boostpro.com
"Dave Abrahams" <dave@boostpro.com> wrote in message news:m24o7qr3tu.wl%dave@boostpro.com...
Well if you are really into trying to improve Boost.Parameter the two obvious things to try is the elimination of the requirement checks and SW's template profiler...I am willing to help however I will not be by my work computer for the next 10 days...
I won't have time to get near that code in the next 10 days, so I can wait :-)
It would help if you could give me a few pointers on how to most easily short-circuit the requirement checks.. Also the documentation should probably be fixed/updated to state that ArgumentPacks are actually associative sequences... -- "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
participants (3)
-
Dave Abrahams -
Domagoj Saric -
Domagoj Saric