glibc build process slowness

[Mark Seaborn <mrs at mythic-beasts dot com>]

I've been investigating why the glibc build process takes so long.  It
takes about 1m26s on my machine for the nothing-to-do case when all
files are up-to-date.

I profiled make.  It's spending around 60% of the time in
new_pattern_rule(), which does a linear search through the list of
pattern rules to check for duplicate rules.  glibc generates ~2500
rules (in sysd-rules).

The patch below reduces make's time to 43s for the nothing-to-do case.
It removes the check for duplicate rules.  This passes make's test
suite, but it changes make's behaviour (see attached makefile).

I was considering refactoring this properly, but the current
new_pattern_rule() doesn't look quite right.  The comment says it
looks for an identical rule.  The actual test is

  the old rule has 1 target (or multiple identical targets)
  and
  there exists a target in the new rule the same as the old rule's target

See attached makefile which demonstrates this.  Is that the correct
behaviour?  It seems like it would make more sense to compare the
target lists for equality.

Mark


diff --git a/rule.c b/rule.c
index e988db5..6e12439 100644
--- a/rule.c
+++ b/rule.c
@@ -284,68 +284,15 @@ convert_to_pattern (void)
 int
 new_pattern_rule (struct rule *rule, int override)
 {
-  register struct rule *r, *lastrule;
-  register unsigned int i, j;
-
   rule->in_use = 0;
   rule->terminal = 0;
 
   rule->next = 0;
-
-  /* Search for an identical rule.  */
-  lastrule = 0;
-  for (r = pattern_rules; r != 0; lastrule = r, r = r->next)
-    for (i = 0; rule->targets[i] != 0; ++i)
-      {
-	for (j = 0; r->targets[j] != 0; ++j)
-	  if (!streq (rule->targets[i], r->targets[j]))
-	    break;
-	if (r->targets[j] == 0)
-	  /* All the targets matched.  */
-	  {
-	    register struct dep *d, *d2;
-	    for (d = rule->deps, d2 = r->deps;
-		 d != 0 && d2 != 0; d = d->next, d2 = d2->next)
-	      if (!streq (dep_name (d), dep_name (d2)))
-		break;
-	    if (d == 0 && d2 == 0)
-	      {
-		/* All the dependencies matched.  */
-		if (override)
-		  {
-		    /* Remove the old rule.  */
-		    freerule (r, lastrule);
-		    /* Install the new one.  */
-		    if (pattern_rules == 0)
-		      pattern_rules = rule;
-		    else
-		      last_pattern_rule->next = rule;
-		    last_pattern_rule = rule;
-
-		    /* We got one.  Stop looking.  */
-		    goto matched;
-		  }
-		else
-		  {
-		    /* The old rule stays intact.  Destroy the new one.  */
-		    freerule (rule, (struct rule *) 0);
-		    return 0;
-		  }
-	      }
-	  }
-      }
-
- matched:;
-
-  if (r == 0)
-    {
-      /* There was no rule to replace.  */
-      if (pattern_rules == 0)
-	pattern_rules = rule;
-      else
-	last_pattern_rule->next = rule;
-      last_pattern_rule = rule;
-    }
+  if (pattern_rules == 0)
+    pattern_rules = rule;
+  else
+    last_pattern_rule->next = rule;
+  last_pattern_rule = rule;
 
   return 1;
 }

all:	target_a.test \
	target_b.test \
	target_c1.test target_c2.test \
	target_d1.test target_d2.test


exists.test:
exists2.test:



target_a.%: exists.%
	@echo $@: first rule -- should not happen

target_a.%: exists.%
	@echo $@: second rule -- should happen



target_b.%: exists.% exists2.%
	@echo $@: first rule -- should not happen

target_b.%: exists.% exists2.%
	@echo $@: second rule -- should happen



target_c1.% target_c2.%: exists.%
	@echo $@: first rule -- make 3.81 behaviour

target_c1.% target_c2.%: exists.%
	@echo $@: second rule -- does not override in make 3.81



target_d1.%: exists.%
	@echo $@: first rule -- does not get overridden in make 3.81

target_d1.% target_d2.%: exists.%
	@echo $@: second rule -- make 3.81 behaviour