Re: [boost] [preprocessor] Computational complexity analysis

Subject: Re: [boost] [preprocessor] Computational complexity analysis
From: Jeffrey Hellrung (jhellrung_at_[hidden])
Date: 2010-03-20 17:52:58

Lorenzo Caminiti wrote:
> Hello all:
> 
> Is there a computational complexity analysis of Boost.Preprocessor
> data structures? This would be in terms of preprocessing time.
> 
> For example: Does BOOST_PP_SEQ_ELEM() run* in O(n)? Do
> BOOST_PP_TUPLE_ELEM() and BOOST_PP_ARRAY_ELEM() run* in O(1)?
> (*) "Run" within the preprocessor so maybe "expand" is a better term...
> 
> Thank you.
> Lorenzo

I've used the Boost.Preprocessor library quite a bit, so I'm only 
responding in light of that.

"Number of macro invocations" (as it depends on an argument) should be 
immediately inferred from a quick glance through the code.  E.g., 
BOOST_PP_SEQ_ELEM( n, seq ) requires O(n) macro invocations, and 
BOOST_PP_TUPLE_ELEM( n, k, tuple ) (in terms of which 
BOOST_PP_ARRAY_ELEM is implemented) requires O(1) macro invocations.  Of 
course, Boost.PP tuple/array sizes is capped at a smaller limit than 
Boost.PP seq sizes (25 vs. 255, I believe).

I'm guessing "preprocessing time" could have a more elusive relationship 
that depends on the implementation of the preprocessor.  E.g., is the 
time for a single macro invocation independent of the number of 
arguments, or the size of the arguments?  If not, how does it scale? 
Seems to me you're now asking a preprocessor implementation question...

- Jeff