staelin@PRINCETON.EDU (Carl Staelin) (11/20/89)
I have a bug-fix for GNU Make 3.57. This fix works on BSD machines, and I don't expect any problems with it on other machines (so long as "qsort" exists in the standard form). For really large makefiles (such as those sometimes automatically generated for large projects), GNUMake spends most of its time in a procedure calls "record files", and it spends most of its time eliminating duplicates from lists of dependencies. I have modified this code (in read.c) to use qsort, and in my case I gained a 5x performance improvement. The diffs follow. Carl Staelin staelin@princeton.edu % diff read.c.old read.c.new 98a99,110 > /* > * compare two dep's (using lexicographic comparison of the names) > * > * used in record_files > */ > int dep_compare (a, b) > char *a; > char *b; > { > return strcmp (dep_name (*(struct dep **)a), dep_name(*(struct dep **)b)); > } > 982c994 < /* Make sure that no dependencies are repeated. This does not --- > /* Make sure that no dependencies are repeated. This does not 985,1006c997,1037 < for (d = f->deps; d != 0; d = d->next) < { < struct dep *last, *next; < last = d; < next = d->next; < while (next != 0) < if (streq (dep_name (d), dep_name (next))) < { < struct dep *n = next->next; < last->next = n; < if (next->name != 0 && next->name != d->name) < free (next->name); < if (next != d) < free ((char *) next); < next = n; < } < else < { < last = next; < next = next->next; < } < } --- > { > int count; > register struct dep **array; > > for (count = 0, d = f->deps ; d ; d = d->next) > count ++; > > if (count) > { > int dummy; > > array = (struct dep **)xmalloc (count * sizeof (struct dep *)); > > for (dummy = 0, d = f->deps ; d ; dummy ++, d = d->next) > array[dummy] = d; > > qsort ((char *)array, count, sizeof(struct dep *), dep_compare); > > f->deps = d = array[0]; > d->next = (struct dep *)0; > > for (dummy = 1 ; dummy < count ; dummy ++) > if (streq (dep_name(d), dep_name(array[dummy]))) > { > if (array[dummy]->name && array[dummy]->name != d->name) > free (array[dummy]->name); > if (array[dummy] != d) > free (array[dummy]); > } > else > { > d->next = array[dummy]; > d = array[dummy]; > d->next = (struct dep *)0; > } > > free (array); > } > > } >