Finding which modules needs to be rebuilt is grossly inefficient.

[benl]

We should also record its interaction with the server, so we can replay it during offline testing.

[erikd]

Rover crashes on Linux x86_64 due to a stack overflow.

> bin/ddc test/90-Programs/Rover/Main.ds -o test/90-Programs/Rover/Main.bin Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize' to increase it.

Doubling the stack size like this works:

> bin/ddc +RTS -K16M -RTS test/90-Programs/Rover/Main.ds -o test/90-Programs/Rover/Main.bin

[erikd]

Stephen Blackheath ran the ddc building the Rover project under the profiler which show that huge amounts of memory were being chewed up the functions scrapeGraphInsert and invalidateParents when DDC figures out which files need to be rebuilt.

After this stage the compiler is actually quite well behaved.

[erikd]

Profiler output showing huge memory usage of scapeGraphInsert and invalidateParents.

[erikd]

After switching to Control.Monad.State.Strict the profile output looks like this.

[erikd]

It seems the code to detect cycles in the import graph is grossly inefficient. Since I added that code I'll fix this bug.

[erikd]

Fixed in the following commit:

• Sat Feb 6 07:03:35 EST 2010 Erik de Castro Lopo <erikd@…>

Fix #99 : Finding which modules need to be rebuilt is inefficient.

Profiling of the build of the Rover program in the test suite show that as much as 90% of the run time and 90% of the memory usage was used just to figure out which modules needed to be rebuilt.

The problem turned out to be an O(n²) (and possibly worse) algorithm which tried to build the ScrapeGraph and figure out which modules needed to be rebuild in a single pass. Separating this into two passed, one to build the ScrapeGraph and one to propagate the NeedsRebuild flag fixed the problem. Building the ScrapeGraph now takes less than 1% of the compile run time.