Re: address@hidden: libjava build times]

[Joe Buck]

On Thu, May 05, 2005 at 11:25:53PM +0200, Ralf Wildenhues wrote:
> Hi Albert,
> 
> * Albert Chin wrote on Thu, May 05, 2005 at 09:20:50PM CEST:
> > On Thu, May 05, 2005 at 03:17:26PM +0200, Ralf Wildenhues wrote:
> > > That one still needs testing, but the idea is to kill all quadratic
> > > loops in the func_mode_link initialization:
> > > 
> > > Stuff like
> > >   compile_command="$compile_command $qarg"
> > > is better written as
> > >   $ECHO " $qarg" >&FD_COMPILE_COMMAND
> *snip*
> > >   compile_command=`$SED 's/^ //' <"$compile_command_file" | $NL2SP`
> > 
> > Can you explain how the latter is faster? From inspection, I'd believe
> > the first to be faster.
> 
> The former scales quadratically with some shells (all I tested on
> GNU/Linux), presumably because they do repeated reallocs.

Wow.  One of my favorite job interview questions is how to implement
a string class or (for C types) dynamic string library that can grow
strings without producing quadratic behavior.  Are you saying that bash
fails the test?

(The usual mistake is to allocate just enough memory for the the
appended-to string, which means you have to reallocate it every time,
or to allocate extra room in a way that still fails to avoid the
quadratic behavior).