Skip to content
  • kristenk's avatar
    Solver: Avoid removing goal choices from the tree when applying heuristics. · 3b8cdbcb
    kristenk authored
    Previously, the solver applied goal-ordering heuristics by removing all
    non-preferred goal choices when there was at least one preferred choice. This
    left fewer goals for later steps, such as conflict counting, to work with.
    
    This commit changes the heuristics so that they only sort the goals. I didn't
    change the preferBaseGoalChoice heuristic, though, because it made the solver
    slower in some cases. I also think that it is safe to always choose the version
    of base first, because there is usually only one choice anyway.
    
    I reversed the order of the heuristics, because sorting gives the most weight to
    the last step, and pruning gives the most weight to the first step. The solver's
    behavior should be unchanged with --no-count-conflicts.
    
    Some notes on how I tested it:
    
    I expected this change to improve performance in many cases by giving the
    "conflict counting" heuristic more goals to choose from. However, I wasn't able
    to find any cases where the solver made different choices compared with master,
    except when I also used --reorder-goals. I spent a while looking, because it was
    hard to believe.
    
    I searched for examples first by comparing the verbose logs from this branch and
    master for a few packages with many dependencies. Then I compared runtimes with
    master when solving for each package on Hackage (with GHC 8.0.1), in order to
    find packages with very large differences in runtime. Surprisingly, I didn't see
    any where the change was over 50% in either direction. I reran ~10 with the
    biggest difference and found two where the difference was more than noise. I
    compared their logs, but they were also unchanged. Both were slower than master.
    I profiled solving for grapefruit-ui-gtk, which was the slowest (18% slower than
    master, with a runtime of ~20 seconds). I found that this branch spent about
    twice as much time in Explore.getBestGoal. That makes sense, because getBestGoal
    now has more goals to choose from. I didn't look into why the change had such a
    big impact on that particular package.
    
    I also tried running the solver on grapefruit-ui-gtk with --reorder-goals and no
    backjump limit. This branch finished in about 67 seconds, and I stopped master
    after ~8 minutes.
    
    Then I compared runtime for another long-running combination of packages to test
    the overhead of this change when the solver makes the same choices as master. I
    ran 'cabal install --dry-run yesod phooey --max-backjumps -1' with GHC 8.0.1 and
    took the average of 4 runs. master ran for 8.44 seconds, and this branch ran for
    8.50 seconds, which is a difference of less than 1%.
    
    Even though this change doesn't improve performance now, I think it's worthwhile
    for simplifying the interactions between goal-ordering heuristics, and working
    towards issue #3488 (Solver: Combine goal-ordering heuristics more effectively
    by assigning scores to goal choices).
    3b8cdbcb