Re: [bug #35485] New $(.MFDIR) built-in variable

[Howard Chu]

Paul Smith wrote:
> On Thu, 2012-02-09 at 17:25 +0000, Tim Murphy wrote:
> > I also think that it can be expensive to append things onto very long
> > lists in make but that's just suspicion and I really need to take a
> > proper look at it instead of making accusations.
>
> Appending is not very expensive.  Make doesn't know anything about
> "lists" internally.  Everything in make is a string.  If you append to a
> variable then make basically does a strlen() of the string, makes sure
> there's enough memory for the new content in the buffer (or if not,
> reallocs enough space), then strcat()'s the value.  Or the equivalent.
> So I suppose yes, in some ways the longer the string the longer it takes
> to do the strlen() but this should be very fast I'd expect.  Much of the
> string manipulation in make (and make does a LOT of string manipulation)
> is bog-stupid strlen, strcat, strcpy, strdup which gets expensive in
> some situations.  I've considered implementing some kind of fancy string
> encoding .

You've just described an O(n^2) behavior. This is definitely a drag; but it 
really depends on how heavily you make use of macros. In OpenLDAP 2.0 70% of 
our execution time was in libc; 35% in malloc/free and 35% in strlen/strcat 
and friends. I instituted a top-down replacement of all bare char *s in the 
code to struct bervals (char *ptr; int len) and eliminated all use of strlen 
in the code and our code base was immediately 60% faster. A number of other 
profiling and optimization exercises made OpenLDAP 2.1 *20* times faster than 
OpenLDAP 2.0, but getting rid of moronic uses of libc was the number 1 priority.

> The thing that DOES get noticeably more complex is manipulating the
> variable as if it were a list, with functions like firstword, lastword,
> etc. because those functions must first chop the string up into words,
> then operate on those, and that happens every time the function is
> invoked.

If that happens a lot, then you should simply construct the lists once and 
keep them...

--
  -- Howard Chu
  CTO, Symas Corp.           http://www.symas.com
  Director, Highland Sun     http://highlandsun.com/hyc/
  Chief Architect, OpenLDAP  http://www.openldap.org/project/