The fix for bug #14334 introduced O(n^2) time behavior for double colon rules.
Specifically remake.c:notice_finished_file does a linear search to determine
whether all double colon rules for the current file have been updated yet.
This can be safely short-circuited by checking if the next file has been
updated. Under normal circumstances we process double colon rules in order,
so O(n^2) worst-case behaviour is reduced to O(n) in practice.
In a project with ~100k double colon rules this cuts make overhead from
several minutes to a few seconds.
Paul
2007-11-20 Paul Brook <[EMAIL PROTECTED]>
* remake.c (notice_finished_file): Avoid O(N) search in common case.
Index: remake.c
===================================================================
--- remake.c (revision 187570)
+++ remake.c (working copy)
@@ -887,15 +887,21 @@ notice_finished_file (struct file *file)
/* Check that all rules were updated and at the same time find
the max timestamp. We assume UNKNOWN_MTIME is newer then
- any other value. */
- for (f = file->double_colon; f != 0 && f->updated; f = f->prev)
- if (max_mtime != UNKNOWN_MTIME
- && (f->last_mtime == UNKNOWN_MTIME || f->last_mtime > max_mtime))
- max_mtime = f->last_mtime;
-
- if (f == 0)
- for (f = file->double_colon; f != 0; f = f->prev)
- f->last_mtime = max_mtime;
+ any other value. Avoid doing a full linear search in the common
+ case that we are updating the rules in order, and file->prev has
+ not been updated yet.*/
+ if (!file->prev || file->prev->updated)
+ {
+ for (f = file->double_colon; f != 0 && f->updated; f = f->prev)
+ if (max_mtime != UNKNOWN_MTIME
+ && (f->last_mtime == UNKNOWN_MTIME
+ || f->last_mtime > max_mtime))
+ max_mtime = f->last_mtime;
+
+ if (f == 0)
+ for (f = file->double_colon; f != 0; f = f->prev)
+ f->last_mtime = max_mtime;
+ }
}
if (ran && file->update_status != -1)
_______________________________________________
Bug-make mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/bug-make
