bugmake - Bugs: bug #15584, 3.81 does way too much work in...

 
 

bug #15584: 3.81 does way too much work in some pathalogical situations.

Submitted by:  Manoj Srivastava <srivasta>
Submitted on:  Tue 31 Jan 2006 02:58:17 AM UTC  
 
Severity: 2 - MinorItem Group: Enhancement
Status: NonePrivacy: Public
Assigned to: NoneOpen/Closed: Open
Component Version: 3.81Operating System: POSIX-Based
Fixed Release: NoneTriage Status: None

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

Fri 23 Mar 2012 08:55:24 PM UTC, comment #14:

I ran into this problem with some real work. I realize it's probably not common to have such a large tree of secondary/intermediate files, but due to the nature of our build process it would be nice if that worked without hitting this performance limitation.

In case it clarifies anything, I've attached a makefile (named BadMakefile) that replicates the problem. You can see the pattern; adding another level of hierarchy approximately doubles the time it takes to "make all". Also I predict that if you run this with "make -d" it will produce ~10GB of output.

Sol Swords <sswords>
Wed 15 Feb 2006 07:20:24 PM UTC, comment #13:

OK. I'm marking this as an enhancement and dropping the Severity level.

Thanks for looking at this Boris.

Paul D. Smith <psmith>
Project Administrator
Wed 15 Feb 2006 07:01:28 PM UTC, comment #12:

It appears that 3.80 has a bug in handling of .SECONDARY. It does not actually mark individual targets as intermedite. As a result, check_dep doesn't treat any target in this makefile as intermediate. In CVS the following code was added in file.c around line 692:

hash_map (&files, set_intermediate);

Boris Kolpackov <bosk>
Project Member
Mon 13 Feb 2006 03:59:39 PM UTC, comment #11:

Hm. OK. I guess the only question is, why does the older version of GNU make not have this problem? We must have changed the behavior of intermediate files or something that caused this change in behavior. If we can understand what change we made and that it was legitimate (to fix another bug) then I'm happy to leave this alone for 3.81. Thanks for looking into this one Boris!

Paul D. Smith <psmith>
Project Administrator
Mon 13 Feb 2006 03:28:04 PM UTC, comment #10:

So I did some mode digging and it appears that make just does what it's supposed to do. If you look into this makefile carefully you will see the pattern rule that looks like this %.hi: %.o which pretty much makes every single .o file depend (directly and inderectly) on all others. Now because all of the targets in this makefile are intermediate and non-existed, make dutifully traverses the whole grpath for every .o file and figures out that it cannot build anyhting. Since it doesn't set any flags like updated or this_target_is_intermediate_and_does_not_exist_and_i_already_tried_to_build _it, it does complete graph traversal for every .o file it tries to build. I don't see any way (and don't really want) to fix this in make without doing a major surgery on of how things work. To summarize, the long time is the result of three things:

1. Strange desire of the makefile author to have all files intermediate.

2. Pretty much fully-connected dependency graph.

3. Brain-damaged intermediate file logic in GNU make.

I therefore suggest that we leave this corner case alone.

Boris Kolpackov <bosk>
Project Member
Fri 10 Feb 2006 07:28:21 PM UTC, comment #9:

Actually, now that I think about it I'm confused. You can't have a situation like this:

target : B.x ; @echo cp $< $@
%.x : %.y
B.y : ; @echo cp $< $@

because you can't define an empty pattern rule... an empty pattern rule deletes the pattern.

So, I don't see how the situation you describe: "an intermediate, non-existent file for which there is no implicit rule" could ever be correct... let me think. I suppose there could be an explicit rule; does that make a difference? That could happen because people can declare targets as intermediate even though they are explicitly mentioned (which normally would disqualify them from being intermediate). So, something like this:

target : B.x ; @echo cp $< $@
B.x : B.y
B.y : ; @echo cp $< $@
.INTERMEDIATE: B.x

Offhand this seems legal to me; would this trigger the issue?

If there's no implicit OR explicit rule, then I guess we have one of two cases: either make should check all the prerequisites of the intermediate file (B.x above) and if none of them need to be rebuilt, make says "OK". Or, make should fail immediately because it doesn't know how to build the intermediate file (B.x) regardless of whether or not it actually needs to know.

For explicit rules this is perfectly legal: if there's no command to update a target then it's just considered "magically updated" without actually doing anything.

Paul D. Smith <psmith>
Project Administrator
Fri 10 Feb 2006 04:20:58 PM UTC, comment #8:

> This means if you have a rule like "target: B" and B is
> intermediate but does not exist, then target will only be updated
> if B has to be rebuilt because one of B's prereqs is newer: B
> will not be rebuilt just because it does not exist.


Then, since none of the targets in this makefile exist and all of them are intermediate, we shouldn't build anything and should not fail. Or if the target is also a goal then this logic does not apply? Even if that's the case we should fail to build stage1/ghc-6.4.1, not profiling/CostCentre.lhs or stage1/profiling/CostCentre.o?

> "Some other reason" means if you have a rule "target: B A" in
> the same situation above, then target could be rebuilt because > of A, even if it doesn't need to be rebuilt because of B.


Ok, got it. Thanks for the clarification.

> Your description of how check_dep() behaves sounds correct on
> the surface: you can't know whether B needs to be rebuilt
> unless you check all its prerequisites.


That's definitely not how 3.80 works. So we are talking about some new way of doing things in 3.81 that caused this behavior.

> However, there's SOMETHING pathalogical going on here: if you
> run the test with -d and capture all the output you can see
> that as the processing goes along the dep check make performs
> gets more and more elaborate and the number of times it does
> "Pruning file `Config.hs'." increases almost exponentially.


I see those except my log is full of "Prunning file `Makefile'.". This seems to happen multiple times in a row at different nesting levels. I will try to investigate this.

> I see you qualify the situation by saying there is no implicit
> rule for the non-existent file... if there's no implicit or
> explicit rule for that target then does it make sense to
> continue looking at that target's prerequisites?


Well, if there is no rule and we don't need to rebuild it then I suppose we don't fail.

> Suppose we found one of them and it needed to be rebuilt: what

then?

Then we fail.

For now I am going to assume that what check_dep does is correct and will try to find out why do we get all those "Prunning..." messages.

Boris Kolpackov <bosk>
Project Member
Fri 10 Feb 2006 03:09:10 PM UTC, comment #7:

> It won't bother updating B, or the ultimate target, unless some
> prerequisite of B is newer than that target or there is some
> other reason to update that target.


This means if you have a rule like "target: B" and B is intermediate but does not exist, then target will only be updated if B has to be rebuilt because one of B's prereqs is newer: B will not be rebuilt just because it does not exist.

"Some other reason" means if you have a rule "target: B A" in the same situation above, then target could be rebuilt because of A, even if it doesn't need to be rebuilt because of B.

Your description of how check_dep() behaves sounds correct on the surface: you can't know whether B needs to be rebuilt unless you check all its prerequisites. However, there's SOMETHING pathalogical going on here: if you run the test with -d and capture all the output you can see that as the processing goes along the dep check make performs gets more and more elaborate and the number of times it does "Pruning file `Config.hs'." increases almost exponentially. I can't see any justification for that behavior offhand... is there one?

I see you qualify the situation by saying there is no implicit rule for the non-existent file... if there's no implicit or explicit rule for that target then does it make sense to continue looking at that target's prerequisites? Suppose we found one of them and it needed to be rebuilt: what then? Does that mean the same thing as an empty rule:

target : B.x ; @echo cp $< $@
%.x : %.y
B.y : ; @echo cp $< $@
.INTERMEDIATE: B.x

?? Hm.

Paul D. Smith <psmith>
Project Administrator
Fri 10 Feb 2006 02:53:29 PM UTC, comment #6:

After all, this problem does not appear to be related to my implicit.c change. It's actually quite obvious from the -d output: both versions conclude that there is no implicit rule for profiling/CostCentre.lhs and while 3.80 stops, 3.81 goes on.

Next thing that I found is that if we remove .SECONDARY: from the original makefile, make 3.81 returns immediately. So it is related to the fact that all targets are treated as intermediates.

I was trying to figure out what are all the differences between normal and intermediate targets. GNU make manuall has this strange text:

"The first difference is what happens if the intermediate file does not exist. If an ordinary file B does not exist, and `make' considers a target that depends on B, it invariably creates B and then updates the target from B. But if B is an intermediate file, then `make' can leave well enough alone. It won't bother updating B, or the ultimate target, unless some prerequisite of B is newer than that target or there is some other reason to update that target."

I wonder what those "other reasons" are. Like, does mentioning an intermediate target as a goal quilify? What about depending on the target that was mentioned as a goal?

Anyway, the problem appears to be in check_dep() in remake.c. Apparently if check_dep is called for an intermediate, non-existent file for which there is no implicit rule and which has intermediate non-existent prereqs (for which there is no implicit rule, etc.), it will recursively check every prereq and at the end return 0, without updating anything. That's exactly what happens in this case. Whether it is correct behaviour or not - I don't know. It depends on what that piece of the manual above actualy means.

Boris Kolpackov <bosk>
Project Member
Wed 08 Feb 2006 05:49:18 PM UTC, comment #5:

It's a bit tricky when it comes to intermediates. Old algo would sometimes choose subsequent rules because one of the pattern prereqs can only satisfy as an intermediate (even though it is explicitly mentioned in the non-pattern rule). Also the new algorithm improves diagnostics: make will print that it was unable to build foo.h instead of saying that it could not find a rule to build foo.c. I will take care of this bug.

Boris Kolpackov <bosk>
Project Member
Wed 08 Feb 2006 02:30:18 PM UTC, comment #4:

Hm. So, the skipping doesn't impact which implicit rule matches, right? Because, even though a prereq might be explicitly declared it's still the case that you have to consider it during the SELECTION of implicit rules. If there's a prereq pattern in the implicit rule that cannot be satisfied, then make needs to keep looking for another implicit rule which does match. I'm trying to think of a situation where this might make a difference in which implicit rule was selected.

Is that the failure mode here: in the old code make wouldn't be able to find any implicit rule because that prerequisite cannot be constructed, while the new code it does match because of the explicit prereq?

I think this is a regression and needs to be fixed for 3.81. Since it seemed like the short-circuit code in implicit.c was just a performance improvement, I tried just commenting it out but that cause 6 test suite failures (5 in features/INTERMEDIATE), so it's more involved than that...

Paul D. Smith <psmith>
Project Administrator
Wed 01 Feb 2006 08:02:06 PM UTC, comment #3:

Seem like my improvement in implicit.c around line 668 uncovered this. Before make would return from pattern_search with either failure or an implicit rule for which all implicit prerequisites either exist or can be built. Now, if an implicit prerequisite is also an explicit prerequisite for this target, pattern_search skips its normal checks because this prerequisite has to be built no matter which implicit rule we choose. Sometimes, like in our case, there may actually be no rule to built such a prerequisite (profiling/CostCentre.lhs here). Some code in remake.c (either around line 451, or 957, or both) "assumes" that there is a rule for each implicit prerequisite if pattern_search did not fail. Just need to find that piece of code and fix it.

Boris Kolpackov <bosk>
Project Member
Wed 01 Feb 2006 12:32:22 PM UTC, comment #2:

Actually, Boris, this makefile IS sufficient to reproduce the problem. Stick it in an empty directory. Run it as shown in the example. You'll see that older versions of make fail as shown almost immediately, while the latest CVS version will do a LOT of work, then fail after a few seconds.

Using -d you can see what's going on: the old version of make will see that the first prereq cannot be created, then stop:

Considering target file `stage1/profiling/CostCentre.o'.
File `stage1/profiling/CostCentre.o' does not exist.
Looking for an implicit rule for `stage1/profiling/CostCentre.o'.
Trying pattern rule with stem `profiling/CostCentre'.
Trying implicit prerequisite `profiling/CostCentre.hs'.
Trying pattern rule with stem `profiling/CostCentre'.
Trying implicit prerequisite `profiling/CostCentre.lhs'.
Found an implicit rule for `stage1/profiling/CostCentre.o'.
Considering target file `profiling/CostCentre.lhs'.
File `profiling/CostCentre.lhs' does not exist.
Looking for an implicit rule for `profiling/CostCentre.lhs'.
No implicit rule found for `profiling/CostCentre.lhs'.
Finished prerequisites of target file `profiling/CostCentre.lhs'.
Must remake target `profiling/CostCentre.lhs'.
make: *** No rule to make target `profiling/CostCentre.lhs', needed by `stage1/profiling/CostCentre.o'. Stop.

However, the new version of make does NOT stop and continues to look for other prerequisites, and gets into some bizarre sort of full-tree walk. The full -d output I got was 2297723 LINES long! The first part, matching the above, was:

Considering target file `stage1/ghc-6.4.1'.
File `stage1/ghc-6.4.1' does not exist.
Looking for an implicit rule for `stage1/profiling/CostCentre.o'.
Trying pattern rule with stem `profiling/CostCentre'.
Trying implicit prerequisite `profiling/CostCentre.hs'.
Trying pattern rule with stem `profiling/CostCentre'.
Trying implicit prerequisite `profiling/CostCentre.lhs'.
Found an implicit rule for `stage1/profiling/CostCentre.o'.
Looking for an implicit rule for `profiling/CostCentre.lhs'.
No implicit rule found for `profiling/CostCentre.lhs'.
Looking for an implicit rule for `stage1/utils/Util.hi'.
Trying pattern rule with stem `Util'.

After make sees that it can't find an implicit rule for one of the prereqs, instead of stopping it continues with the next prereq. Then, later on it gets into some kind of pathological recursion, "Pruning file `Config.hs'." over and over at different depths.

Unfortunately I didn't have time to get any further into this last night.

Paul D. Smith <psmith>
Project Administrator
Wed 01 Feb 2006 08:07:00 AM UTC, comment #1:

The makefile itself does not give me any idea what might be wrong. Can you provide a minimal but complete test case that reproduces the problem (I don't know what stage1/ghc-6.4.1 is).

Boris Kolpackov <bosk>
Project Member
Tue 31 Jan 2006 02:58:17 AM UTC, original submission:

Hi,

This was reported by a debian user. Please retain a CC to -unavailable- so that the Debian BTS has a copy of your input.

With the attached Makefile, make 3.80+3.81.b4-1 is much slower than 3.80-9 at running "make -wr stage1/ghc-6.4.1" (only a few seconds in the cutdown case, but more in the real thing).

Variously, this has been reported to terminate, in 8, 11, or >24 hour, on different machines/architectures.

Thanks

Manoj

$ dpkg -s make | grep Version
Version: 3.80+3.81.b4-1
$ time make -wr stage1/ghc-6.4.1
make: Entering directory `/tmp/wibble'
Makefile:20: stage1/profiling/CostCentre.o stage1/profiling/SCCfinal.o stage1/main/Config.o
make: *** No rule to make target `profiling/CostCentre.lhs', needed by `stage1/profiling/CostCentre.o'. Stop.
make: Leaving directory `/tmp/wibble'

real 0m4.318s
user 0m4.315s
sys 0m0.002s
$

$ dpkg -s make | grep Version
Version: 3.80-9
$ time make -wr stage1/ghc-6.4.1
make: Entering directory `/tmp/wibble'
Makefile:20: stage1/profiling/CostCentre.o stage1/profiling/SCCfinal.o stage1/main/Config.o
make: *** No rule to make target `profiling/CostCentre.lhs', needed by `stage1/profiling/CostCentre.o'. Stop.
make: Leaving directory `/tmp/wibble'

real 0m0.008s
user 0m0.006s
sys 0m0.003s

Manoj Srivastava <srivasta>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach File(s):
   
   
Comment:
   

Attached Files
file #25459:  BadMakefile added by sswords (2KiB - application/octet-stream - very simple way to recreate this problem)
file #2080:  Makefile added by srivasta (28KiB - application/octet-stream - Test Makefile)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by psmith (Updated the item)
  • -unavailable- added by sswords (Updated the item)
  • -unavailable- added by psmith (Debian Bug Tracker)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 11 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Wed 09 Oct 2013 04:55:58 AM UTCpsmithComponent Version4.0=>3.81
    Fri 23 Mar 2012 08:46:07 PM UTCsswordsAttached File-=>Added BadMakefile, #25459
    Wed 15 Feb 2006 07:36:00 PM UTCboskAssigned tobosk=>None
    Wed 15 Feb 2006 07:20:24 PM UTCpsmithSeverity5 - Blocker=>2 - Minor
      Item GroupBug=>Enhancement
      Component VersionNone=>4.0
      Summary3.81.b4 much slower than 3.80 in some situations=>3.81 does way too much work in some pathalogical situations.
    Wed 08 Feb 2006 05:30:28 PM UTCboskAssigned toNone=>bosk
    Wed 08 Feb 2006 02:30:18 PM UTCpsmithSeverity3 - Normal=>5 - Blocker
    Tue 31 Jan 2006 05:46:02 PM UTCpsmithCarbon-Copy-=>Added -unavailable-
    Tue 31 Jan 2006 02:58:17 AM UTCsrivastaAttached File-=>Added Makefile, #3343

    Back to the top


    Powered by Savane 3.1-cleanup1