4 ms·

That recursive macro approach allows FOR_EACH to accept up to 4^N arguments (where N is the number of lines in the definition)… at the cost of making every use

by comex 3y ago

That recursive macro approach allows FOR_EACH to accept up to 4^N arguments (where N is the number of lines in the definition)… at the cost of making every use of FOR_EACH perform O(4^N) expansions, a fixed number regardless of the actual number of arguments. For high N that can slow down preprocessing. In the past I've used a style like #define FOR_EACH(macro, ...) __VA_OPT__(FOR_EACH1(macro, __VA_ARGS__)) #define FOR_EACH1(macro, arg, ...) macro(arg) __VA_OPT__(FOR_EACH2(macro, __VA_ARGS__)) #define FOR_EACH2(macro, arg, ...) macro(arg) __VA_OPT__(FOR_EACH3(macro, __VA_ARGS__)) #define FOR_EACH3(macro, arg, ...) macro(arg) __VA_OPT__(FOR_EACH4(macro, __VA_ARGS__)) [etc...] which doesn't provide exponential growth in the maximum argument count, but does decouple the maximum count from the number of expansions. Even if you continue the pattern up to FOR_EACH100, calling FOR_EACH with 3 arguments will still only do 3+1 expansions. The author chose N=4 for the recursive macro approach, supporting up to 256 arguments, at the cost of performing 342 expansions for each use. That sounds reasonable; preprocessing is much faster than other compiler passes and you probably won't notice the cost at all. So it's probably better than my approach. On the other hand, if I bump the recursive approach up to N=10, supporting up to 1048576 arguments at the cost of performing around that many expansions per use, then performance becomes obviously unacceptable (when running `clang -E`, you can watch the tokens being emitted one by one). So you do have to set a limit somewhere. I wonder if there is some way to get the best of both worlds – exponential maximum number of arguments per line of code, but still only a linear number of expansions per actual argument.

foundry27 3y ago
(Grumpy old man edit: __VA_OPT__ has been implemented in macro libraries by users for decades without language support. Making it a keyword made no more sense to me than if vector was made a language primitive in C++) Tree-based expansion machines are the usual way to do preprocessor recursion for non-trivial applications (see: order-pp, chaos-pp). They have that desirable property of letting you process an exponential number of tokens using a linear number of macros, while letting you “bail out” at any time and avoid needing to resolve all of those deeply-nested macro expansions when there isn’t more work to be done. Getting the linear->exponential property is actually the easy part, since you just need two parallel hierarchies of macros (shamelessly plugging https:.//github.com/notfoundry/pp2/blob/master/include/pp2/machine/vm.h as the most readable implementation). It’s how you stop expanding before the heat death of the universe once you have an effectively unlimited number of recursive expansions available that’s really interesting: if you design all of your recursive macros to return their output wrapped in parentheses, you can write your recursion machine in such a way that at the end of every recursion step, those parentheses are used to complete a function-like macro expansion to get to each next recursion step downstream. When you want to stop computation, you make your recursive macro stop expanding to something parenthesized, and the system naturally stops making progress. In a sense, each recursive macro provide its own potential energy to power the whole recursion system!

by comex 3y ago

foundry27 3y ago

(Grumpy old man edit: __VA_OPT__ has been implemented in macro libraries by users for decades without language support. Making it a keyword made no more sense to me than if vector was made a language primitive in C++) Tree-based expansion machines are the usual way to do preprocessor recursion for non-trivial applications (see: order-pp, chaos-pp). They have that desirable property of letting you process an exponential number of tokens using a linear number of macros, while letting you “bail out” at any time and avoid needing to resolve all of those deeply-nested macro expansions when there isn’t more work to be done. Getting the linear->exponential property is actually the easy part, since you just need two parallel hierarchies of macros (shamelessly plugging https:.//github.com/notfoundry/pp2/blob/master/include/pp2/machine/vm.h as the most readable implementation). It’s how you stop expanding before the heat death of the universe once you have an effectively unlimited number of recursive expansions available that’s really interesting: if you design all of your recursive macros to return their output wrapped in parentheses, you can write your recursion machine in such a way that at the end of every recursion step, those parentheses are used to complete a function-like macro expansion to get to each next recursion step downstream. When you want to stop computation, you make your recursive macro stop expanding to something parenthesized, and the system naturally stops making progress. In a sense, each recursive macro provide its own potential energy to power the whole recursion system!