This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GNU M4 source repository".
http://git.sv.gnu.org/gitweb/?p=m4.git;a=commitdiff;h=cfdd338da41015cee1ec0691fae84607d145e2ac The branch, master has been updated via cfdd338da41015cee1ec0691fae84607d145e2ac (commit) via ff7e7bf197df21b3e98eb54759ecbc8f8448dc8d (commit) from 2cdf327333be152135f021988c8e0eb6f3e10b51 (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit cfdd338da41015cee1ec0691fae84607d145e2ac Author: Eric Blake <[EMAIL PROTECTED]> Date: Fri Feb 22 19:54:48 2008 -0700 Stage 18: try harder to reuse argv in recursion. * m4/macro.c (make_argv_ref): Avoid wrapping $@ when possible. (m4_push_args): Let make_argv_ref take care of pending data. * doc/m4.texinfo (Improved foreach): Tweak wording to match new performance capability. * tests/others.at (recursion): Add tests to avoid performance regression. Signed-off-by: Eric Blake <[EMAIL PROTECTED]> commit ff7e7bf197df21b3e98eb54759ecbc8f8448dc8d Author: Eric Blake <[EMAIL PROTECTED]> Date: Fri Feb 22 12:57:57 2008 -0700 Update NEWS. * NEWS: Document change to __gnu__ on 2008-02-11. Signed-off-by: Eric Blake <[EMAIL PROTECTED]> ----------------------------------------------------------------------- Summary of changes: ChangeLog | 18 ++++++++++++ NEWS | 11 ++++++- doc/m4.texinfo | 35 ++++++++++++++++------- m4/macro.c | 83 ++++++++++++++++++++++++++++++------------------------ tests/others.at | 32 +++++++++++++++++++++ 5 files changed, 129 insertions(+), 50 deletions(-) diff --git a/ChangeLog b/ChangeLog index cb6a845..877cda7 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,23 @@ +2008-02-23 Eric Blake <[EMAIL PROTECTED]> + + Stage 18: try harder to reuse argv in recursion. + When pushing arguments that contain an existing $@ ref, reuse the + ref rather than creating another layer of wrappers. + Memory impact: noticeable improvement, due to better $@ reuse. + Speed impact: noticeable improvement, due to O(n^2) to O(n) + reduction in unboxed recursion. + * m4/macro.c (make_argv_ref): Avoid wrapping $@ when possible. + (m4_push_args): Let make_argv_ref take care of pending data. + * doc/m4.texinfo (Improved foreach): Tweak wording to match new + performance capability. + * tests/others.at (recursion): Add tests to avoid performance + regression. + 2008-02-22 Eric Blake <[EMAIL PROTECTED]> + Update NEWS. + * NEWS: Document change to __gnu__ on 2008-02-11. + Stage 17: pass argv through quoted strings. Allow the concatenation of $@ references with other text input inside quoted contexts, which requires distinguishing between a diff --git a/NEWS b/NEWS index 03627a4..ec63ef2 100644 --- a/NEWS +++ b/NEWS @@ -1,6 +1,6 @@ GNU m4 NEWS - History of user-visible changes. -*- outline -*- -Copyright (C) 1992, 1993, 1994, 1998, 2000, 2001, 2006, 2007 Free Software -Foundation, Inc. +Copyright (C) 1992, 1993, 1994, 1998, 2000, 2001, 2006, 2007, 2008 Free +Software Foundation, Inc. * Version beta 1.9b - ???, by ??? (git version 1.9a-*) @@ -134,6 +134,9 @@ promoted to 2.0. ** Changed behavior of builtins +*** The module identifier builtins, such as `__gnu__', `__m4_version__', + and `__unix__', now warn if given arguments. + *** The `builtin' builtin now has a special form, where if the first argument is exactly the special token representing defn(`builtin'), the expansion is the special token representing the builtin named in the @@ -204,6 +207,10 @@ promoted to 2.0. *** Improvements made in the 1.4.x stable series have been incorporated. +* Version 1.4.11 - ?? ??? 2008, by Eric Blake (git version 1.4.10a) + +** FIXME: import NEWS from branch once 1.4.11 is released. + * Version 1.4.10 - 09 Jul 2007, by Eric Blake (CVS version 1.4.9c) ** Upgrade from GPL version 2 to GPL version 3 or later. diff --git a/doc/m4.texinfo b/doc/m4.texinfo index ffc1949..909f8e3 100644 --- a/doc/m4.texinfo +++ b/doc/m4.texinfo @@ -8406,17 +8406,16 @@ helper method immediately, the @samp{defn([EMAIL PROTECTED]')} no longer contains unexpanded macros. The astute m4 programmer might notice that the solution above still uses -more memory, and thus more time, than strictly necessary. Note that [EMAIL PROTECTED], which contains an arbitrarily long quoted list, is expanded -and rescanned three times per iteration of @code{_foreachq}. -Furthermore, every iteration of the algorithm effectively unboxes then -reboxes the list, which costs a couple of macro invocations. It is -possible to rewrite the algorithm for a bit more speed by swapping the -order of the arguments to @code{_foreachq} in order to operate on an -unboxed list in the first place, and by using the fixed-length @samp{$#} -instead of an arbitrary length list as the key to end recursion. This -alternative approach is available as [EMAIL PROTECTED]@value{VERSION}/@/examples/@/foreach3.m4}: +more macro invocations than strictly necessary. Note that @samp{$2}, +which contains an arbitrarily long quoted list, is expanded and +rescanned three times per iteration of @code{_foreachq}. Furthermore, +every iteration of the algorithm effectively unboxes then reboxes the +list, which costs a couple of macro invocations. It is possible to +rewrite the algorithm by swapping the order of the arguments to [EMAIL PROTECTED] in order to operate on an unboxed list in the first +place, and by using the fixed-length @samp{$#} instead of an arbitrary +length list as the key to end recursion. This alternative approach is +available as @[EMAIL PROTECTED]/@/examples/@/foreach3.m4}: @comment examples @example @@ -8459,6 +8458,20 @@ foreachq(`x', ``1', `2', `3', `4'', `x @result{}4 @end example +Prior to M4 1.4.11, every instance of @samp{$@@} was rescanned as it was +encountered. Thus, the @file{foreachq3.m4} alternative used much less +memory than @file{foreachq2.m4}, and executed as much as 10% faster, +since each iteration encountered fewer @samp{$@@}. However, the +implementation of rescanning every byte in @samp{$@@} was quadratic in +the number of bytes scanned (for example, making the broken version in [EMAIL PROTECTED] cubic, rather than quadratic, in behavior). Once the +underlying M4 implementation was improved in 1.4.11 to reuse results of +previous scans, both styles of @code{foreachq} become linear in the +number of bytes scanned, and the difference in timing is no longer +noticeable; in fact, after the change, the @file{foreachq2.m4} version +uses slightly less memory since it tracks fewer arguments per macro +invocation. + For yet another approach, the improved version of @code{foreach}, available in @[EMAIL PROTECTED]/@/examples/@/foreach2.m4}, simply overquotes the arguments to @[EMAIL PROTECTED] to begin with, using diff --git a/m4/macro.c b/m4/macro.c index 0b86018..743d326 100644 --- a/m4/macro.c +++ b/m4/macro.c @@ -1081,24 +1081,56 @@ make_argv_ref (m4 *context, m4_symbol_value *value, m4_obstack *obs, { m4__symbol_chain *chain; - assert (obstack_object_size (obs) == 0); - /* TODO reuse $@ even if argv has multiple array slots. */ - if (argv->wrapper && argv->arraylen == 1) - { - assert (argv->array[0]->type == M4_SYMBOL_COMP - && argv->array[0]->u.u_c.wrapper); - chain= argv->array[0]->u.u_c.chain; - assert (!chain->next && chain->type == M4__CHAIN_ARGV - && !chain->u.u_a.skip_last); - argv = chain->u.u_a.argv; - index += chain->u.u_a.index - 1; - } if (argv->argc <= index) return NULL; + value->type = M4_SYMBOL_COMP; + value->u.u_c.chain = value->u.u_c.end = NULL; + + /* Cater to the common idiom of $0(`$1',shift(shift($@))), by + inlining the first few arguments and reusing the original $@ ref, + rather than creating another layer of wrappers. */ + while (argv->wrapper) + { + size_t i; + for (i = 0; i < argv->arraylen; i++) + { + if (argv->array[i]->type == M4_SYMBOL_COMP + && argv->array[i]->u.u_c.wrapper) + break; + if (index == 1) + { + m4__push_arg_quote (context, obs, argv, i + 1, quotes); + /* TODO support M4_SYNTAX_COMMA. */ + obstack_1grow (obs, ','); + } + else + index--; + } + assert (i < argv->arraylen); + if (i + 1 == argv->arraylen) + { + assert (argv->array[i]->type == M4_SYMBOL_COMP + && argv->array[i]->u.u_c.wrapper); + chain = argv->array[i]->u.u_c.chain; + assert (!chain->next && chain->type == M4__CHAIN_ARGV + && !chain->u.u_a.skip_last); + argv = chain->u.u_a.argv; + index += chain->u.u_a.index - 1; + } + else + { + index += i; + break; + } + } + m4__make_text_link (obs, &value->u.u_c.chain, &value->u.u_c.end); chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain); - value->type = M4_SYMBOL_COMP; - value->u.u_c.chain = value->u.u_c.end = chain; + if (value->u.u_c.end) + value->u.u_c.end->next = chain; + else + value->u.u_c.chain = chain; + value->u.u_c.end = chain; value->u.u_c.wrapper = true; value->u.u_c.has_func = argv->has_func; chain->next = NULL; @@ -1591,11 +1623,8 @@ m4_push_args (m4 *context, m4_obstack *obs, m4_macro_args *argv, bool skip, { m4_symbol_value tmp; m4_symbol_value *value; - m4__symbol_chain *chain; size_t i = skip ? 2 : 1; const m4_string_pair *quotes = m4_get_syntax_quotes (M4SYNTAX); - char *str = NULL; - size_t len = obstack_object_size (obs); if (argv->argc <= i) return; @@ -1606,30 +1635,10 @@ m4_push_args (m4 *context, m4_obstack *obs, m4_macro_args *argv, bool skip, return; } - /* Since make_argv_ref puts data on obs, we must first close any - pending data. The resulting symbol contents live entirely on - obs, so we call push_symbol with a level of -1. */ - if (len) - { - obstack_1grow (obs, '\0'); - str = (char *) obstack_finish (obs); - } - /* TODO allow shift, $@, to push builtins without flatten. */ value = make_argv_ref (context, &tmp, obs, -1, argv, i, true, quote ? quotes : NULL); assert (value == &tmp); - if (len) - { - chain = (m4__symbol_chain *) obstack_alloc (obs, sizeof *chain); - chain->next = value->u.u_c.chain; - value->u.u_c.chain = chain; - chain->type = M4__CHAIN_STR; - chain->quote_age = 0; - chain->u.u_s.str = str; - chain->u.u_s.len = len; - chain->u.u_s.level = SIZE_MAX; - } if (m4__push_symbol (context, value, -1, argv->inuse)) arg_mark (argv); } diff --git a/tests/others.at b/tests/others.at index 0b58c29..fbd692b 100644 --- a/tests/others.at +++ b/tests/others.at @@ -332,6 +332,38 @@ AT_CHECK_M4(["$abs_srcdir/null.m4"], [2], AT_CLEANUP +## --------- ## +## recursion ## +## --------- ## + +AT_SETUP([recursion]) + +dnl This input exploits contents of loop.m4 to print out the final value +dnl of the recursion. +AT_DATA([in.m4], +[[define(`debug', `define(`popdef', `divert`'i')')dnl +include(`loop.m4')dnl +]]) + +dnl boxed recursion +AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose loop.m4], [0], +[[ 1 2 3 4 5 6 7 8 9 10 +]]) +AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 loop.m4], [0]) +AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 in.m4], [0], [[10000 +]]) + +dnl unboxed recursion +AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10 -Dverbose -Dalt loop.m4], [0], +[[ 1 2 3 4 5 6 7 8 9 10 +]]) +AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=2500 -Dalt loop.m4], [0]) +AT_CHECK_M4([-I "$top_srcdir/examples" -Dlimit=10000 -Dalt in.m4], [0], [[10000 +]]) + +AT_CLEANUP + + ## ------- ## ## reverse ## ## ------- ## hooks/post-receive -- GNU M4 source repository
