Re: glibc build process slowness
On Sun, Feb 25, 2007 at 09:18:27PM -0500, Paul Smith wrote: On Wed, 2007-02-21 at 20:15 +, 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 ___ Bug-make mailing list Bug-make@gnu.org http://lists.gnu.org/mailman/listinfo/bug-make
Re: glibc build process slowness
On Wed, 2007-02-21 at 20:15 +, 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 [EMAIL PROTECTED] 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 ___ Bug-make mailing list Bug-make@gnu.org http://lists.gnu.org/mailman/listinfo/bug-make
glibc build process slowness
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
___
Bug-make mailing list
Bug-make@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-make
