[boost] Re: Preprocessor Library - ATTN: David Abrahams

From: Vesa Karvonen (vesa_karvonen_at_[hidden])
Date: 2002-04-18 10:57:37

"Paul Mensonides":
[...]
> Good. :) My conclusions are that the BPL should include functionality
like this
> for the purposes of debugging and error messages, etc..
[...]
> Ideally, you would like some things to be macro recursive (which always
ends up
> on one line) and some things to be file iterative (which always ends up
on
> different lines).

If I understand correctly, then file iteration has the following benefits:
- it can be faster on EDG based compilers.
- it expands stuff on separate lines, which may make debugging easier.

At the present, I don't know how readable the technique can be made, or
how generic it is. I'd like to see the "chaos" library headers, that
support the technique (I don't recall if they were available somewhere).
Anyway, I think that this technique might be worth including in the
preprocessor library or perhaps in some other library. If we decide to
provide such support, then I'd certainly like Paul to compose a submission
of some sort.

...

It seems to me that file based iteration can only provide functionality
similar to BOOST_PP_REPEAT(), but not functionality like BOOST_PP_FOR().
BOOST_PP_REPEAT(COUNT,MACRO,DATA) repeats the given MACRO(INDEX,DATA) like
this:

  MACRO(0,DATA) MACRO(1,DATA) ... MACRO(COUNT-1,DATA)

As you can see, the DATA is passed, as is, to MACRO, but INDEX ranges from
0 to COUNT-1.

On the other hand, BOOST_PP_FOR(STATE,PRED,OP,MACRO) makes it possible to
evolve the STATE using the OP macro (the following is slightly
simplified):

  MACRO(          STATE    )
  MACRO(       OP(STATE)   )
  MACRO(    OP(OP(STATE))  )
  MACRO( OP(OP(OP(STATE))) )
  ...

The repeated application of OP() to STATE is actually done incrementally.
So, there will be only a linear amount of OP() applications. The
incremental evolution of STATE allows many interesting repetitions to be
performed in O(N) time instead of O(N*N) time. Of course, BOOST_PP_FOR()
can do many things that are not possible with BOOST_PP_REPEAT().

...

I investigated the arg_tuple_size.h header, which uses the preprocessor
library, and found out that the reason why it is expanded so slowly, even
with g++, was that BOOST_MPL_TEMPLATE_PARAMETERS() uses BOOST_PP_ADD(), in
such a way that the time complexity of
BOOST_MPL_TEMPLATE_PARAMETERS(first, last, param) is
O((last-first)*(last-first)). This is because the time complexity of
BOOST_PP_ADD(X,Y) is currently O(Y).

When BOOST_PYTHON_MAX_ARITY is increased significantly, the time taken by
BOOST_PP_ADD() grows quickly. Because there are O(N*N) parameters, and the
expansion of a single parameter takes O(N) time, it takes O(N*N*N) time to
expand arg_tuple_size.h for large N.

Currently, a simple way to reduce time taken by BOOST_PP_ADD(X,Y) is to
make sure that Y < X. In this case it can be achieved simply by swapping
the order of parameters to BOOST_PP_ADD() in the macro
BOOST_MPL_AUX_TEMPLATE_PARAMETER(). This changes the time complexity of
BOOST_MPL_TEMPLATE_PARAMETERS(first, last, param) to O(first *
(last-first)), which, in this case, is much smaller than
O((last-first)*(last-first)). On g++, preprocessing time was reduced from
about 2 minutes to 8 seconds when BOOST_PYTHON_MAX_ARITY was 50.

There are many ways in which BOOST_PP_ADD(X,Y) could be implemented in
logarithmic time (without huge amounts of macro definitions, that is).
Unfortunately, my earlier attempts on this suggest that it only speeds
things up when the parameters X and Y become rather large (too large to be
really useful). I think I'll spend some more time on this when I get some
time.

...

I think that a long term solution, to avoid performance problems like
this, would be to drop BOOST_PP_REPEAT() and use BOOST_PP_FOR() based
solutions. In most cases, BOOST_PP_FOR() makes it possible to perform
repetition so that preprocessing time is O(N), where N is the number of
tokens produced.

For example, the time complexity of the recently added macro
BOOST_PP_REPEAT_FROM_TO(FIRST,LAST,MACRO,DATA) is O(FIRST*(LAST-FIRST)).
Using BOOST_PP_FOR(), it would be possible to provide a similar primitive
whose time complexity would be the optimal O(LAST-FIRST).

On the other hand, the use of BOOST_PP_FOR() means that the R parameter
needs to be passed around explicitly by the user, which is a nuisance. I
think I'll write up implementations of the BOOST_PP_ENUM and
BOOST_PP_REPEAT macros using BOOST_PP_FOR and post them on the list for
discussion.