glibc build process slowness

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

glibc build process slowness

Mark Seaborn-2
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
Reply | Threaded
Open this post in threaded view
|

Re: glibc build process slowness

Paul Smith-20
On Wed, 2007-02-21 at 20:15 +0000, Mark Seaborn wrote:

> 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).

Holy moly!  How in the world do you get that many pattern rules?!?!  The
point of pattern rules is that they represent an entire class of
targets, which means you typically would have orders of magnitude fewer
pattern rules than you have targets.

I don't have anything against making this more efficient, I'm just...
surprised.

> 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

I agree that this doesn't seem correct.

I got your set of patches, and I'll take a look.  Thanks!

--
-------------------------------------------------------------------------------
 Paul D. Smith <[hidden email]>          Find some GNU make tips at:
 http://www.gnu.org                      http://make.paulandlesley.org
 "Please remain calm...I may be mad, but I am a professional." --Mad Scientist
Reply | Threaded
Open this post in threaded view
|

Re: glibc build process slowness

Jakub Jelinek
On Sun, Feb 25, 2007 at 09:18:27PM -0500, Paul Smith wrote:

> On Wed, 2007-02-21 at 20:15 +0000, Mark Seaborn wrote:
>
> > 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).
>
> Holy moly!  How in the world do you get that many pattern rules?!?!  The
> point of pattern rules is that they represent an entire class of
> targets, which means you typically would have orders of magnitude fewer
> pattern rules than you have targets.

Several pattern rules for each directory in which sources should be looked up.
There are usually 30-40 directories in which files should be searched
and glibc needs a well defined order how to pick up the desired source
location for particular object file.  E.g. pick .S in preference of .s,
then .c, repeated by several different prefixes (none, rtld-, ptw-, m_),
times the number of different object file types (.o, .os, .og, .op, .oS).
So that is 5 * 4 * 3 * 30 at minimum.
...
$(objpfx)%.o: $(..)sysdeps/pthread/%.S $(before-compile);         $(compile-command.S)
$(objpfx)%.o: $(..)sysdeps/pthread/%.s $(before-compile);         $(compile-command.s)
$(objpfx)rtld-%.o: $(..)sysdeps/pthread/%.S $(before-compile);    $(compile-command.S)
$(objpfx)rtld-%.o: $(..)sysdeps/pthread/%.s $(before-compile);    $(compile-command.s)
$(objpfx)ptw-%.o: $(..)sysdeps/pthread/%.S $(before-compile);     $(compile-command.S)
$(objpfx)ptw-%.o: $(..)sysdeps/pthread/%.s $(before-compile);     $(compile-command.s)
$(objpfx)m_%.o: $(..)sysdeps/pthread/s_%.S $(before-compile);     $(compile-command.S)
$(objpfx)m_%.o: $(..)sysdeps/pthread/s_%.s $(before-compile);     $(compile-command.s)
$(objpfx)%.o: $(..)sysdeps/pthread/%.c $(before-compile);         $(compile-command.c)
$(objpfx)rtld-%.o: $(..)sysdeps/pthread/%.c $(before-compile);    $(compile-command.c)
$(objpfx)ptw-%.o: $(..)sysdeps/pthread/%.c $(before-compile);     $(compile-command.c)
$(objpfx)m_%.o: $(..)sysdeps/pthread/s_%.c $(before-compile);     $(compile-command.c)
$(objpfx)%.os: $(..)sysdeps/pthread/%.S $(before-compile);        $(compile-command.S)
$(objpfx)%.os: $(..)sysdeps/pthread/%.s $(before-compile);        $(compile-command.s)
$(objpfx)rtld-%.os: $(..)sysdeps/pthread/%.S $(before-compile);           $(compile-command.S)
$(objpfx)rtld-%.os: $(..)sysdeps/pthread/%.s $(before-compile);           $(compile-command.s)
$(objpfx)ptw-%.os: $(..)sysdeps/pthread/%.S $(before-compile);    $(compile-command.S)
$(objpfx)ptw-%.os: $(..)sysdeps/pthread/%.s $(before-compile);    $(compile-command.s)
$(objpfx)m_%.os: $(..)sysdeps/pthread/s_%.S $(before-compile);    $(compile-command.S)
$(objpfx)m_%.os: $(..)sysdeps/pthread/s_%.s $(before-compile);    $(compile-command.s)
$(objpfx)%.os: $(..)sysdeps/pthread/%.c $(before-compile);        $(compile-command.c)
$(objpfx)rtld-%.os: $(..)sysdeps/pthread/%.c $(before-compile);           $(compile-command.c)
$(objpfx)ptw-%.os: $(..)sysdeps/pthread/%.c $(before-compile);    $(compile-command.c)
$(objpfx)m_%.os: $(..)sysdeps/pthread/s_%.c $(before-compile);    $(compile-command.c)
$(objpfx)%.op: $(..)sysdeps/pthread/%.S $(before-compile);        $(compile-command.S)
$(objpfx)%.op: $(..)sysdeps/pthread/%.s $(before-compile);        $(compile-command.s)
$(objpfx)rtld-%.op: $(..)sysdeps/pthread/%.S $(before-compile);           $(compile-command.S)
$(objpfx)rtld-%.op: $(..)sysdeps/pthread/%.s $(before-compile);           $(compile-command.s)
$(objpfx)ptw-%.op: $(..)sysdeps/pthread/%.S $(before-compile);    $(compile-command.S)
$(objpfx)ptw-%.op: $(..)sysdeps/pthread/%.s $(before-compile);    $(compile-command.s)
$(objpfx)m_%.op: $(..)sysdeps/pthread/s_%.S $(before-compile);    $(compile-command.S)
$(objpfx)m_%.op: $(..)sysdeps/pthread/s_%.s $(before-compile);    $(compile-command.s)
$(objpfx)%.op: $(..)sysdeps/pthread/%.c $(before-compile);        $(compile-command.c)
$(objpfx)rtld-%.op: $(..)sysdeps/pthread/%.c $(before-compile);           $(compile-command.c)
$(objpfx)ptw-%.op: $(..)sysdeps/pthread/%.c $(before-compile);    $(compile-command.c)
$(objpfx)m_%.op: $(..)sysdeps/pthread/s_%.c $(before-compile);    $(compile-command.c)
$(objpfx)%.og: $(..)sysdeps/pthread/%.S $(before-compile);        $(compile-command.S)
$(objpfx)%.og: $(..)sysdeps/pthread/%.s $(before-compile);        $(compile-command.s)
...
and so on.

        Jakub