Ticket #99 (closed defect: fixed)

Opened 5 years ago

Last modified 4 years ago

Finding which modules needs to be rebuilt is grossly inefficient.

Reported by: benl Owned by: erikd
Priority: blocker Milestone: 0.1.3
Component: Runtime System Version: 0.1.2
Keywords: Cc:

Description

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

Attachments

ddc_profile.png (131.7 kB) - added by erikd 4 years ago.
Profiler output showing huge memory usage of scapeGraphInsert and invalidateParents.
ddc-strict-state.png (45.9 kB) - added by erikd 4 years ago.
After switching to Control.Monad.State.Strict the profile output looks like this.

Change History

Changed 5 years ago by 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

Changed 4 years ago by erikd

  • owner set to erikd
  • status changed from new to assigned

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.

Changed 4 years ago by erikd

Profiler output showing huge memory usage of scapeGraphInsert and invalidateParents.

Changed 4 years ago by erikd

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

Changed 4 years ago by 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.

Changed 4 years ago by erikd

  • summary changed from Work out why test/90-Programs/Rover is crashing to Finding which modules needs to be rebuilt is grossly inefficient.

Changed 4 years ago by erikd

  • status changed from assigned to closed
  • resolution set to fixed

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(n2) (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.

Note: See TracTickets for help on using tickets.