Boost logo

Boost :

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
> (*) "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

Boost list run by bdawes at, gregod at, cpdaniel at, john at