Opened 10 years ago

Closed 9 years ago

Last modified 7 years ago

#99 closed defect (fixed)

Finding which modules needs to be rebuilt is grossly inefficient.

Reported by: benl Owned by: erikd
Priority: blocker Milestone:
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 (2)

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

Download all attachments as: .zip

Change History (8)

comment:1 Changed 10 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

comment:2 Changed 9 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 9 years ago by erikd

Profiler output showing huge memory usage of scapeGraphInsert and invalidateParents.

Changed 9 years ago by erikd

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

comment:3 Changed 9 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.

comment:4 Changed 9 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.

comment:5 Changed 9 years ago by erikd

  • Resolution set to fixed
  • Status changed from assigned to closed

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.

comment:6 Changed 7 years ago by benl

  • Milestone 0.1.3 deleted

Milestone 0.1.3 deleted

Note: See TracTickets for help on using tickets.