[PATCH 3/5] Refactor: Use a doubly-linked list of rules instead of a singly-linked list
---
implicit.c |2 +-
rule.c | 86 +---
rule.h |7 +++--
3 files changed, 41 insertions(+), 54 deletions(-)
diff --git a/implicit.c b/implicit.c
index d239952..82f2c79 100644
--- a/implicit.c
+++ b/implicit.c
@@ -301,7 +301,7 @@ pattern_search (struct file *file, int archive,
and may be considered. Put them in TRYRULES. */
nrules = 0;
- for (rule = pattern_rules; rule != 0; rule = rule-next)
+ for (rule = pattern_rules.next; !rule-list_head; rule = rule-next)
{
unsigned int ti;
diff --git a/rule.c b/rule.c
index a12f9d1..311400e 100644
--- a/rule.c
+++ b/rule.c
@@ -24,15 +24,13 @@ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
02110-1301 USA. */
#include variable.h
#include rule.h
-static void freerule (struct rule *rule, struct rule *lastrule);
+static void add_rule (struct rule *rule);
+static void remove_rule (struct rule *rule);
+static void free_rule (struct rule *rule);
/* Chain of all pattern rules. */
-struct rule *pattern_rules;
-
-/* Pointer to last rule in the chain, so we can add onto the end. */
-
-struct rule *last_pattern_rule;
+struct rule pattern_rules = { 1, pattern_rules, pattern_rules };
/* Number of rules in the chain. */
@@ -75,7 +73,7 @@ count_implicit_rule_limits (void)
name = 0;
namelen = 0;
- for (rule = pattern_rules; rule != NULL; rule = rule-next)
+ for (rule = pattern_rules.next; !rule-list_head; rule = rule-next)
{
unsigned int ndeps = 0;
register struct dep *dep;
@@ -305,16 +303,13 @@ rule_dependency_lists_equal (struct rule *rule1, struct
rule *rule2)
int
new_pattern_rule (struct rule *rule, int override)
{
- register struct rule *r, *lastrule;
+ register struct rule *r;
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 (r = pattern_rules.next; !r-list_head; r = r-next)
{
if (rule_targets_superset (rule, r)
rule_dependency_lists_equal (rule, r))
@@ -322,42 +317,46 @@ new_pattern_rule (struct rule *rule, int override)
/* 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;
-
+ remove_rule (r);
+ free_rule (r);
+
+ add_rule (rule);
+
/* We got one. Stop looking. */
- goto matched;
+ return 1;
}
else
{
/* The old rule stays intact. Destroy the new one. */
- freerule (rule, (struct rule *) 0);
+ free_rule (rule);
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;
-}
+ /* There was no rule to replace. */
+ add_rule (rule);
return 1;
}
+static void
+add_rule (struct rule *rule)
+{
+ rule-list_head = 0;
+ rule-next = pattern_rules;
+ rule-prev = pattern_rules.prev;
+ pattern_rules.prev-next = rule;
+ pattern_rules.prev = rule;
+}
+
+static void
+remove_rule (struct rule *rule)
+{
+ rule-prev-next = rule-next;
+ rule-next-prev = rule-prev;
+}
+
/* Install an implicit pattern rule based on the three text strings
in the structure P points to. These strings come from one of
@@ -410,14 +409,11 @@ install_pattern_rule (struct pspec *p, int terminal)
}
-/* Free all the storage used in RULE and take it out of the
- pattern_rules chain. LASTRULE is the rule whose next pointer
- points to RULE. */
+/* Free all the storage used in RULE. */
static void
-freerule (struct rule *rule, struct rule *lastrule)
+free_rule (struct rule *rule)
{
- struct rule *next = rule-next;
register unsigned int i;
register struct dep *dep;
@@ -453,16 +449,6 @@ freerule (struct rule *rule, struct rule *lastrule)
pointer from the `struct file' for the suffix rule. */
free (rule);
-
- if (pattern_rules == rule)
-if (lastrule != 0)
- abort ();
-else
- pattern_rules = next;
- else if (lastrule != 0)
-lastrule-next = next;
- if (last_pattern_rule == rule)
-last_pattern_rule = lastrule;
}
/* Create a new pattern rule with the targets in the nil-terminated
@@ -552,7 +538,7 @@ print_rule_data_base (void)
puts (_(\n# Implicit Rules));
rules = terminal = 0;
- for (r = pattern_rules; r != 0; r = r-next)
+ for (r = pattern_rules.next; !r-list_head; r = r-next)
[PATCH 1/5] Refactor: Move rule comparisons into separate functions
---
rule.c | 95 +---
1 files changed, 55 insertions(+), 40 deletions(-)
diff --git a/rule.c b/rule.c
index ee96ec1..d08383b 100644
--- a/rule.c
+++ b/rule.c
@@ -273,6 +273,34 @@ convert_to_pattern (void)
}
+static int
+rule_targets_superset (struct rule *rule1, struct rule *rule2)
+{
+ int i;
+ for (i = 0; rule1-targets[i] != NULL; i++)
+{
+ int j;
+ for (j = 0; rule2-targets[j] != NULL; j++)
+ if (!streq (rule1-targets[i], rule2-targets[j]))
+ break;
+ if (rule2-targets[j] == NULL)
+ return 1;
+}
+ return 0;
+}
+
+static int
+rule_dependency_lists_equal (struct rule *rule1, struct rule *rule2)
+{
+ struct dep *dep1, *dep2;
+ for (dep1 = rule1-deps, dep2 = rule2-deps;
+ dep1 != NULL dep2 != NULL;
+ dep1 = dep1-next, dep2 = dep2-next)
+if (!streq (dep_name (dep1), dep_name (dep2)))
+ return 0;
+ return dep1 == NULL dep2 == NULL;
+}
+
/* Install the pattern rule RULE (whose fields have been filled in)
at the end of the list (so that any rules previously defined
will take precedence). If this rule duplicates a previous one
@@ -285,7 +313,6 @@ 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;
@@ -295,45 +322,33 @@ new_pattern_rule (struct rule *rule, int override)
/* 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;
- }
- }
- }
- }
+{
+ if (rule_targets_superset (rule, r)
+ rule_dependency_lists_equal (rule, r))
+ {
+ /* 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:;
--
___
Bug-make mailing list
Bug-make@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-make
[PATCH 0/5] Improve performance of rule handling
Here is a series of patches to improve make's performance in handling large numbers of pattern rules. The motivation is to make glibc's build process faster. The change speeds up adding new pattern rules, but it does not speed up finding pattern rules that match a given filename. I have not changed the logic that decides whether one rule should override another. The patches are based on CVS HEAD. Cheers, Mark ___ Bug-make mailing list Bug-make@gnu.org http://lists.gnu.org/mailman/listinfo/bug-make
[PATCH 2/5] Clean up count_implicit_rule_limits()
* Removed unused variable, simplify loop.
* Corrected comment.
---
rule.c | 13 +++--
1 files changed, 3 insertions(+), 10 deletions(-)
diff --git a/rule.c b/rule.c
index d08383b..a12f9d1 100644
--- a/rule.c
+++ b/rule.c
@@ -61,28 +61,24 @@ unsigned int maxsuffix;
/* Compute the maximum dependency length and maximum number of
dependencies of all implicit rules. Also sets the subdir
- flag for a rule when appropriate, possibly removing the rule
- completely when appropriate. */
+ flag for a rule when appropriate. */
void
count_implicit_rule_limits (void)
{
char *name;
int namelen;
- register struct rule *rule, *lastrule;
+ register struct rule *rule;
num_pattern_rules = max_pattern_targets = max_pattern_deps = 0;
max_pattern_dep_length = 0;
name = 0;
namelen = 0;
- rule = pattern_rules;
- lastrule = 0;
- while (rule != 0)
+ for (rule = pattern_rules; rule != NULL; rule = rule-next)
{
unsigned int ndeps = 0;
register struct dep *dep;
- struct rule *next = rule-next;
unsigned int ntargets;
++num_pattern_rules;
@@ -142,9 +138,6 @@ count_implicit_rule_limits (void)
if (ndeps max_pattern_deps)
max_pattern_deps = ndeps;
-
- lastrule = rule;
- rule = next;
}
if (name != 0)
--
___
Bug-make mailing list
Bug-make@gnu.org
http://lists.gnu.org/mailman/listinfo/bug-make
Re: multi-line commands with quoted SHELL
On Thu, 2007-02-22 at 19:00 +0100, Petr Machata wrote: There is a bug tracked in Red Hat bugzilla http://bugzilla.redhat.com/bugzilla/show_bug.cgi?id=219409 The problem is best demonstrated by this Makefile snippet: all:;@echo e\ cho With this make invocation, it works as intended: $ make 'SHELL=/bin/sh' echo But when the SHELL variable contains quotes, it fails: $ make 'SHELL=/bin/sh' e /bin/sh: line 1: cho: command not found make: *** [all] Error 127 The problem is that when SHELL contains quotations etc., /bin/sh is invoked, and whole command is passed through that. But the outer shell then destroys the backslash-newline sequences. The solution is to singly-quote these. The attached patch against make 3.81 does this. Hm. Personally I think this is an error and should not be handled, even as it is currently handled. If the user sets: SHELL = /bin/sh in my opinion make should try to invoke the program '/bin/sh' (including the quotes). Having a quoted value of SHELL invoked using /bin/sh -c (with another level of indirectness) is, in my opinion, wrong. I can only assume this behavior of trying to manage quotes in the value of SHELL is due to some bizarre behavior of some long-forgotten make that GNU make tried to duplicate. -- --- 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
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
