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.
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...
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk