#35 Scanner causes build serialization
A number of the calls in Scanner.pm are blocking, waiting for a file to be built before continuting to scan the file. If files being scanned take a non-trivial amount of time to generate this blocking behavior drastically reduces the effectiveness of parallel builds. Here's a simple Makeppfile showing the issue:
SLEEPERS = sleep_a sleep_b sleep_c sleep_d
sleeper_top: $(SLEEPERS)
touch $@
sleep_%: sleep_%.c
ifeq(1,$(NO_SCANNER))
:scanner none
endif
sleep 1
gcc -E $< -o $@
$(foreach).c: :foreach $(SLEEPERS)
sleep 1
touch $@
Running this we see the max parallelism is 2:
$ time makepp
real 0m10.579s
$ time makepp -j2
real 0m6.582s
$ time makepp -j4
real 0m6.632s
$ time makepp -j 4 NO_SCANNER=1
real 0m3.502s
Digging through the code the problem is that Mpp:build calls $rule->find_all_targets_dependencies, which is a blocking call. That eventually calls CommandParser which calls Scanner->scan_file, which explicitly says it's a blocking call. Within scan_file any call to include is also blocking.
I haven't thought of any good way to handle this other than completely restructuring that entire call chain to return a handler instead of returning immediately.
Sorry for the broken fromatting, sf.net is weird. Maybe this will work?
Hi Peter,
you are alas right, it requires a major redesign. The idea was already discussed back in 2007, but never implemented, due to the huge effort.
The paralellization code is there, but subprocesses most importantly return only their exit code, besides stdout & -err, just for display. But here we would need the requests that the scanner generates to be fed back to the parent process, because there should be only one scheduler and one writer of meta-data to disc. The communication would have to be two-way, so that, as you write, once the file is generated, scanning continues.
Lots of pipe and select (are they portably reliable, e.g. ActiveState Windows?) if not done right might open the risk of dead-lock. This had better be done by someone who is good at schedulers.
regards -- Daniel
Man SF.net really dislikes me. I just typed out this whole response and it disappeared when I hit submit.
Anyway I don't speak German but the call trace and google translate are enough for me to get the gist of the link.
I agree that restructuring the scanner code to be actually parallel would be a huge undertaking. It's also not entirely clear where in the tree you want to spawn parallelism - if you have a 20 deep/20 wide binary tree, which nodes should be running in parallel? What if it's completely unbalanced?
Anyway instead of trying to tackle that I've been thinking of how to use the existing Event mechanism, which is basically cooperative multithreading, to solve my problem. I've come up with a general solution and specific hack.
General: refactor the call tree from Scanner::include/scan_file up through Rule::find_all_targets_dependencies to return handles instead of a status or explicit values. The current Mpp::build function would then be split into 2, build and build_dependencies_known, which would then eventually call build_dependencies_done as it does today. Conceptually I can see how this would work without changing much outside of the direct call tree shown in your link. The downside is that call tree is fairly deep. Also to prevent the need for rewriting every existing scanner a number of functions would need to be duplicated into Scanner::nonblock_include/nonblock_scan_file and similar.
Hack: in my case I know the file that takes a long time to generate. I'm thinking of adding a :pre_depend option to rules that specifices a dependency that needs to be built first, before the scanner runs. I would split the build() function as above, calling build($pre_depend) as the last thing in build() and find_all_targets_dependencies would be the first thing in the new function.
Thoughts? Thanks for the quick response!
My local hack of adding a :pre_depend option was easier than I expected. It's working properly and I'm seeing it go 8 wide when run with -j8.
Some basic local testing it seems to be behaving properly with both sequential (-j1) and parallel (-j8) compiles. You might not want to accept this hack into mainline, but can you review and see if you spot any issues?
Also the line numbers might be slightly off, they're against our unternally hacked version of makepp, but they should be fairly close.
Hi Peter!
So sorry for your effort in vain! It just happened to me too, because I middle-mouse-button pasted a URL into the textarea, which didn't get inserted, but rather caused the page to load over the form :-(
As for 20-deep or wide, thats normal build work. You can depend on many inputs (libs or exes do) or have a long chain like rpm < exe < lib < .o < .c < .proc < ... Everything gets built in a seemingly random order but before needed.
I'm amazed how fast you produce results in this complex environment. Kudos! But I reformatted your diff headers to look like a normal one, yet the patch command is still complaining about it -- dunno why.
But why don't you just either use prebuild (http://makepp.sourceforge.net/2.1/makepp_statements.html#prebuild_target) or if that might prebuild too much, make the source to be scanned depend on the file that needs to be prebuilt?
a.c: slowtobuild.h
&echo no body needed
instead of (what I assume you try to do)
a.o: a.c :pre_depend slowtobuild.h
regards -- Daniel
Thanks :)
Sorry for the broken diff, new one attached should work.
From poking at the source prebuild behaves as the docs say - it immediately builds the result. Basically every target we're building has a pre_depend, so this would build result in half our targets being prebuilt serially. Back to no parallelism.
I haven't figured out how to setup simple dependencies to accomplish what we need. The problem is our flow has intermediate generated files. The rules, heavily simplified, are along the lines of:
Both the generate_deps and build_result programs are slow. Our custom scanner for the build_result program reads in the generated %.deps file to find the dependencies. Our dependencies look like a tree, where top.out could depend on child_a.out and child_b.out and child_a.out depends on child_a_a.out and child_a_b.out. In our Makeppfiles we only list the top.out target and let the scanner find everything else.
Also your suggestion of a.c explicitly depend on slowtobuild.h doesn't end up helping. The problem is the CommandParser runs on the gcc command that's part of compiling a.o. That calls $scanner->scan_file("a.c"), which is a blocking call that doesn't return until a.c has finished building. The call to build("a.c") returns quickly and it could go in the background, but scan_file will wait for it to finish before going on.
Hi Peter,
I finally found time to port your patch to the latest version from CVS. It's still lacking doc.
I'd like it to be integrated into stress-test.pl in such a way that it can be controlled by an environment variable. Then the same build can be compared as to the effect of your optimization. Could you provide those 2 points?
thanks -- Daniel
I'm wondering instead if switching the scanner to a simple Promise API wouldn't be a much cleaner solution. That way there'd be no need for the Makefile writer to worry about such low down interna. And it would automatically parallelize as much as possible.