[preprocessor] Computational complexity analysis
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
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
On Sat, Mar 20, 2010 at 5:52 PM, Jeffrey Hellrung <jhellrung@ucla.edu> wrote:
"Number of macro invocations" (as it depends on an argument) should be
Yes, "number of macro invocations" or "number of macro expansions" (would these be the same??) should be a reasonable metric for the preprocessing time and it should be abstracted enough from the preprocessor implementation specifics.
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
What about other operations? BOOST_PP_ARRAY_PUSH_BACK(), the PP_ARRAY_INSERT/REMOVEs/POPs, the PP_SEQ_FOLDs, PP_ENUM, PP_WHILE, PP_REPEAT, ... Thanks a lot. Lorenzo
On Sat, Mar 20, 2010 at 1:43 PM, Lorenzo Caminiti <lorcaminiti@gmail.com> wrote:
Is there a computational complexity analysis of Boost.Preprocessor data structures? This would be in terms of preprocessing time.
Can the authors/maintainers of Boost.Preprocessor please reply to my inquiry? If such computational analysis does not exist, it's OK -- I will do the analysis myself (at least for the operations I am interested in like BOOST_PP_ARRAY_PUSH_BACK(), etc). However, I do not want to duplicate work if it has already been done. Thanks. Lorenzo
participants (2)
-
Jeffrey Hellrung -
Lorenzo Caminiti