Re: Fix m4_join

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Ideas from an interesting thread on the autoconf-patches list:

According to Eric Blake on 10/15/2007 1:45 PM:
> Ralf Wildenhues <Ralf.Wildenhues <at> gmx.de> writes:
> 
>> Now it would be even better if m4_join were
>> efficient in that it would not scale quadratically:
>>
>> m4_join([:
>> ], m4_for([i], 1, 1000, [], [i,]))
> 
> Yes, some improvements from cubic to quadratic were due to bug fixes in 
> m4sugar - the rule of thumb here for optimal behavior is that when writing a 
> recursive algorithm, you should limit the parsing of $@ per macro invocation, 
> and you should completely output all text related to the first element of the 
> list before resuming recursion on the rest of the list.  Although I don't see 
> evidence of m4_join being cubic, I do know for certain that m4_foreach was 
> cubic in autoconf 2.52, fixed 2002-03-04 for 2.53.  There, prior to the fix, 
> each recursion of _m4_foreach resulted in more text around the previous 
> invocation, saving the final expansion until the recursion completed, and 
> with 
> each iteration requiring one more m4_shift than the previous round.  After 
> the 
> fix, the first list element is completely processed before moving on to the 
> recursion for the rest of the list, with a constant number of m4_shift's per 
> round.
> 
> But to go from quadratic to linear, that's a different story.  Here's where 
> m4sugar can no longer fix things, but where a fundamental improvement needs 
> to 
> be made in M4 itself.  It may be rather invasive, but the payoffs would be 
> tremendous for any use of address@hidden
> 
> The problem lies in the current m4 implementation of $@ - namely, it spends 
> time constructing a string consisting of every quoted argument, and pushes it 
> on the obstack, only to then reparse the obstack and turn it back into a list 
> of arguments for the next macro in the recursion, even though only the first 
> 2 
> or 3 elements of the list even factor into the current iteration.  In other 
> words, since iterating through n items results in n obstack growth/parse 
> cycles, you have quadratic behavior.  Because of the rules of m4, there are 
> some cases where this MUST be done (for example, if the user does a 
> changequote 
> in between, or if some of the arguments contain unbalanced quotes).  But in 
> the 
> common case, it would be much nicer if m4 would recognize $@ in a macro 
> expansion, and simply store a placeholder on the obstack pointing to the 
> previous list of parsed arguments.  Most macros simply use accessor methods 
> that would expand the placeholder as it is encountered.  But the ifelse, 
> ifdef, 
> and shift builtins should be taught how to recognize the placeholder 
> directly, 
> where the conditionals avoid the overhead of expanding the placeholder if it 
> occurred in an untaken branch, and where the shift merely adjusts where the 
> placeholder points to.
> 
> Unrelated, but also inherent in m4, is the fact that m4_append is quadratic - 
> every invocation concatenates the old definition with the new text, and 
> mallocs 
> a new definition for the macro.  That would be another nice idiom to 
> optimize, 
> by making the defn builtin expand to a special placeholder.  Most macros 
> simply 
> use accessor methods that would expand the placeholder as it is encountered.  
> But the define and popdef builtins should recognize a placeholder followed by 
> new text as an append operation, then grow the malloc area in a geometric 
> fashion (if it isn't large enough already) without wasting time revisiting 
> all 
> of the former definition (similar to the speedups possible when bash added 
> the 
> += variable assignment operator).
> 

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHFAhv84KuGfSFAYARAhA6AJ9EWv91WFzIzSapOJ17yYUFgMNAUACeOLut
LBzKUNUpGctLoIjQbLuR3B8=
=b6GW
-----END PGP SIGNATURE-----