{"action":"created","issue":{"url":"https://api.github.com/repos/haskell/cabal/issues/3208","repository_url":"https://api.github.com/repos/haskell/cabal","labels_url":"https://api.github.com/repos/haskell/cabal/issues/3208/labels{/name}","comments_url":"https://api.github.com/repos/haskell/cabal/issues/3208/comments","events_url":"https://api.github.com/repos/haskell/cabal/issues/3208/events","html_url":"https://github.com/haskell/cabal/pull/3208","id":138286704,"number":3208,"title":"Improve goal reorder heuristics.","user":{"login":"kosmikus","id":293191,"avatar_url":"https://avatars.githubusercontent.com/u/293191?v=3","gravatar_id":"","url":"https://api.github.com/users/kosmikus","html_url":"https://github.com/kosmikus","followers_url":"https://api.github.com/users/kosmikus/followers","following_url":"https://api.github.com/users/kosmikus/following{/other_user}","gists_url":"https://api.github.com/users/kosmikus/gists{/gist_id}","starred_url":"https://api.github.com/users/kosmikus/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kosmikus/subscriptions","organizations_url":"https://api.github.com/users/kosmikus/orgs","repos_url":"https://api.github.com/users/kosmikus/repos","events_url":"https://api.github.com/users/kosmikus/events{/privacy}","received_events_url":"https://api.github.com/users/kosmikus/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/haskell/cabal/labels/cabal-install","name":"cabal-install","color":"68CFC4"},{"url":"https://api.github.com/repos/haskell/cabal/labels/solver","name":"solver","color":"009800"}],"state":"open","locked":false,"assignee":{"login":"kosmikus","id":293191,"avatar_url":"https://avatars.githubusercontent.com/u/293191?v=3","gravatar_id":"","url":"https://api.github.com/users/kosmikus","html_url":"https://github.com/kosmikus","followers_url":"https://api.github.com/users/kosmikus/followers","following_url":"https://api.github.com/users/kosmikus/following{/other_user}","gists_url":"https://api.github.com/users/kosmikus/gists{/gist_id}","starred_url":"https://api.github.com/users/kosmikus/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kosmikus/subscriptions","organizations_url":"https://api.github.com/users/kosmikus/orgs","repos_url":"https://api.github.com/users/kosmikus/repos","events_url":"https://api.github.com/users/kosmikus/events{/privacy}","received_events_url":"https://api.github.com/users/kosmikus/received_events","type":"User","site_admin":false},"milestone":null,"comments":2,"created_at":"2016-03-03T20:20:13Z","updated_at":"2016-03-03T21:01:45Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/haskell/cabal/pulls/3208","html_url":"https://github.com/haskell/cabal/pull/3208","diff_url":"https://github.com/haskell/cabal/pull/3208.diff","patch_url":"https://github.com/haskell/cabal/pull/3208.patch"},"body":"This change primarily does two things:\r\n\r\n1. For `--reorder-goals`, we use a dedicated datatype `Degree`\r\n   rather than an `Int` to compute the approximate branching\r\n   degree. We map 0 and 1 to the same value. We then use a\r\n   lazy ordering and a shortcutting minimum function to look\r\n   for the \"best\" goal.\r\n\r\n   The motivation here is that we do not want to spend\r\n   unnecessary work. Following any goal that has 0 or 1 as degree\r\n   cannot really be \"wrong\", so we should not look at any others\r\n   and waste time.\r\n\r\n   This will still not always make the use of `--reorder-goals`\r\n   better than not using it, but it will reduce the overhead\r\n   introduced by it.\r\n\r\n2. We use partitioning rather than sorting for most of the other\r\n   goal reordering heuristics that are active in all situations.\r\n   I think this is slightly more straightforward and also slightly\r\n   more efficient, whether `--reorder-goals` is used or not.\r\n\r\nI have run some preliminary performance comparisons and they\r\nseem to confirm that in both cases separately (with or without\r\n`--reorder-goals`), these changes are a relative improvement\r\nover the status quo. I will run additional tests before\r\nmerging this into master."},"comment":{"url":"https://api.github.com/repos/haskell/cabal/issues/comments/191961225","html_url":"https://github.com/haskell/cabal/pull/3208#issuecomment-191961225","issue_url":"https://api.github.com/repos/haskell/cabal/issues/3208","id":191961225,"user":{"login":"hvr","id":285533,"avatar_url":"https://avatars.githubusercontent.com/u/285533?v=3","gravatar_id":"","url":"https://api.github.com/users/hvr","html_url":"https://github.com/hvr","followers_url":"https://api.github.com/users/hvr/followers","following_url":"https://api.github.com/users/hvr/following{/other_user}","gists_url":"https://api.github.com/users/hvr/gists{/gist_id}","starred_url":"https://api.github.com/users/hvr/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/hvr/subscriptions","organizations_url":"https://api.github.com/users/hvr/orgs","repos_url":"https://api.github.com/users/hvr/repos","events_url":"https://api.github.com/users/hvr/events{/privacy}","received_events_url":"https://api.github.com/users/hvr/received_events","type":"User","site_admin":false},"created_at":"2016-03-03T21:01:45Z","updated_at":"2016-03-03T21:01:45Z","body":"I've ran a few random tests for cases which stress the solver a bit (solving a full stackage-set, trying to find (when there isn't any) install plans for packages for GHC8, etc..), and they all show a significant improvement of `--reorder-goals`. This looks very promising!"}}