Re: Fix m4_join

[Ralf Wildenhues]

Hi Eric,

* Eric Blake wrote on Mon, Oct 15, 2007 at 09:45:10PM CEST:
> 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.

Oh, the bug may have been entirely in lt_join/lt_combine, I don't
remember.

> 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

OK, thanks for confirming this.  I gather that the only way to currently
avoid quadratic scaling with a number of things defined (here: with
_LT_DECL) is to let the definition output all needed code in different
diversions, and to skip any uniqueness checks.  Hmm, dunno if I want to
invest that work.  It may be more useful if M4 itself were fixed.

Thanks again for all your explanations!

Cheers,
Ralf