{"action":"closed","number":3208,"pull_request":{"url":"https://api.github.com/repos/haskell/cabal/pulls/3208","id":61618744,"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","issue_url":"https://api.github.com/repos/haskell/cabal/issues/3208","number":3208,"state":"closed","locked":false,"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},"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.","created_at":"2016-03-03T20:20:13Z","updated_at":"2016-03-04T11:35:36Z","closed_at":"2016-03-04T11:35:36Z","merged_at":"2016-03-04T11:35:36Z","merge_commit_sha":"b480a0e77d2a7a417c7ac322f6e44397fe5a2522","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,"commits_url":"https://api.github.com/repos/haskell/cabal/pulls/3208/commits","review_comments_url":"https://api.github.com/repos/haskell/cabal/pulls/3208/comments","review_comment_url":"https://api.github.com/repos/haskell/cabal/pulls/comments{/number}","comments_url":"https://api.github.com/repos/haskell/cabal/issues/3208/comments","statuses_url":"https://api.github.com/repos/haskell/cabal/statuses/150d6ca9b706498659b0c905dcd8ff661ee466e3","head":{"label":"kosmikus:new-lazy-reorder-goals","ref":"new-lazy-reorder-goals","sha":"150d6ca9b706498659b0c905dcd8ff661ee466e3","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},"repo":{"id":9853285,"name":"cabal","full_name":"kosmikus/cabal","owner":{"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},"private":false,"html_url":"https://github.com/kosmikus/cabal","description":"Official upstream development repository for Cabal and cabal-install","fork":true,"url":"https://api.github.com/repos/kosmikus/cabal","forks_url":"https://api.github.com/repos/kosmikus/cabal/forks","keys_url":"https://api.github.com/repos/kosmikus/cabal/keys{/key_id}","collaborators_url":"https://api.github.com/repos/kosmikus/cabal/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/kosmikus/cabal/teams","hooks_url":"https://api.github.com/repos/kosmikus/cabal/hooks","issue_events_url":"https://api.github.com/repos/kosmikus/cabal/issues/events{/number}","events_url":"https://api.github.com/repos/kosmikus/cabal/events","assignees_url":"https://api.github.com/repos/kosmikus/cabal/assignees{/user}","branches_url":"https://api.github.com/repos/kosmikus/cabal/branches{/branch}","tags_url":"https://api.github.com/repos/kosmikus/cabal/tags","blobs_url":"https://api.github.com/repos/kosmikus/cabal/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/kosmikus/cabal/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/kosmikus/cabal/git/refs{/sha}","trees_url":"https://api.github.com/repos/kosmikus/cabal/git/trees{/sha}","statuses_url":"https://api.github.com/repos/kosmikus/cabal/statuses/{sha}","languages_url":"https://api.github.com/repos/kosmikus/cabal/languages","stargazers_url":"https://api.github.com/repos/kosmikus/cabal/stargazers","contributors_url":"https://api.github.com/repos/kosmikus/cabal/contributors","subscribers_url":"https://api.github.com/repos/kosmikus/cabal/subscribers","subscription_url":"https://api.github.com/repos/kosmikus/cabal/subscription","commits_url":"https://api.github.com/repos/kosmikus/cabal/commits{/sha}","git_commits_url":"https://api.github.com/repos/kosmikus/cabal/git/commits{/sha}","comments_url":"https://api.github.com/repos/kosmikus/cabal/comments{/number}","issue_comment_url":"https://api.github.com/repos/kosmikus/cabal/issues/comments{/number}","contents_url":"https://api.github.com/repos/kosmikus/cabal/contents/{+path}","compare_url":"https://api.github.com/repos/kosmikus/cabal/compare/{base}...{head}","merges_url":"https://api.github.com/repos/kosmikus/cabal/merges","archive_url":"https://api.github.com/repos/kosmikus/cabal/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/kosmikus/cabal/downloads","issues_url":"https://api.github.com/repos/kosmikus/cabal/issues{/number}","pulls_url":"https://api.github.com/repos/kosmikus/cabal/pulls{/number}","milestones_url":"https://api.github.com/repos/kosmikus/cabal/milestones{/number}","notifications_url":"https://api.github.com/repos/kosmikus/cabal/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/kosmikus/cabal/labels{/name}","releases_url":"https://api.github.com/repos/kosmikus/cabal/releases{/id}","deployments_url":"https://api.github.com/repos/kosmikus/cabal/deployments","created_at":"2013-05-04T11:47:26Z","updated_at":"2015-05-05T20:10:10Z","pushed_at":"2016-03-03T20:13:36Z","git_url":"git://github.com/kosmikus/cabal.git","ssh_url":"git@github.com:kosmikus/cabal.git","clone_url":"https://github.com/kosmikus/cabal.git","svn_url":"https://github.com/kosmikus/cabal","homepage":"http://haskell.org/cabal","size":27884,"stargazers_count":0,"watchers_count":0,"language":"Haskell","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"haskell:master","ref":"master","sha":"cc7aed37b053cec5f0d284bb53df4b70026d7d82","user":{"login":"haskell","id":450574,"avatar_url":"https://avatars.githubusercontent.com/u/450574?v=3","gravatar_id":"","url":"https://api.github.com/users/haskell","html_url":"https://github.com/haskell","followers_url":"https://api.github.com/users/haskell/followers","following_url":"https://api.github.com/users/haskell/following{/other_user}","gists_url":"https://api.github.com/users/haskell/gists{/gist_id}","starred_url":"https://api.github.com/users/haskell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haskell/subscriptions","organizations_url":"https://api.github.com/users/haskell/orgs","repos_url":"https://api.github.com/users/haskell/repos","events_url":"https://api.github.com/users/haskell/events{/privacy}","received_events_url":"https://api.github.com/users/haskell/received_events","type":"Organization","site_admin":false},"repo":{"id":3728161,"name":"cabal","full_name":"haskell/cabal","owner":{"login":"haskell","id":450574,"avatar_url":"https://avatars.githubusercontent.com/u/450574?v=3","gravatar_id":"","url":"https://api.github.com/users/haskell","html_url":"https://github.com/haskell","followers_url":"https://api.github.com/users/haskell/followers","following_url":"https://api.github.com/users/haskell/following{/other_user}","gists_url":"https://api.github.com/users/haskell/gists{/gist_id}","starred_url":"https://api.github.com/users/haskell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/haskell/subscriptions","organizations_url":"https://api.github.com/users/haskell/orgs","repos_url":"https://api.github.com/users/haskell/repos","events_url":"https://api.github.com/users/haskell/events{/privacy}","received_events_url":"https://api.github.com/users/haskell/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/haskell/cabal","description":"Official upstream development repository for Cabal and cabal-install","fork":false,"url":"https://api.github.com/repos/haskell/cabal","forks_url":"https://api.github.com/repos/haskell/cabal/forks","keys_url":"https://api.github.com/repos/haskell/cabal/keys{/key_id}","collaborators_url":"https://api.github.com/repos/haskell/cabal/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/haskell/cabal/teams","hooks_url":"https://api.github.com/repos/haskell/cabal/hooks","issue_events_url":"https://api.github.com/repos/haskell/cabal/issues/events{/number}","events_url":"https://api.github.com/repos/haskell/cabal/events","assignees_url":"https://api.github.com/repos/haskell/cabal/assignees{/user}","branches_url":"https://api.github.com/repos/haskell/cabal/branches{/branch}","tags_url":"https://api.github.com/repos/haskell/cabal/tags","blobs_url":"https://api.github.com/repos/haskell/cabal/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/haskell/cabal/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/haskell/cabal/git/refs{/sha}","trees_url":"https://api.github.com/repos/haskell/cabal/git/trees{/sha}","statuses_url":"https://api.github.com/repos/haskell/cabal/statuses/{sha}","languages_url":"https://api.github.com/repos/haskell/cabal/languages","stargazers_url":"https://api.github.com/repos/haskell/cabal/stargazers","contributors_url":"https://api.github.com/repos/haskell/cabal/contributors","subscribers_url":"https://api.github.com/repos/haskell/cabal/subscribers","subscription_url":"https://api.github.com/repos/haskell/cabal/subscription","commits_url":"https://api.github.com/repos/haskell/cabal/commits{/sha}","git_commits_url":"https://api.github.com/repos/haskell/cabal/git/commits{/sha}","comments_url":"https://api.github.com/repos/haskell/cabal/comments{/number}","issue_comment_url":"https://api.github.com/repos/haskell/cabal/issues/comments{/number}","contents_url":"https://api.github.com/repos/haskell/cabal/contents/{+path}","compare_url":"https://api.github.com/repos/haskell/cabal/compare/{base}...{head}","merges_url":"https://api.github.com/repos/haskell/cabal/merges","archive_url":"https://api.github.com/repos/haskell/cabal/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/haskell/cabal/downloads","issues_url":"https://api.github.com/repos/haskell/cabal/issues{/number}","pulls_url":"https://api.github.com/repos/haskell/cabal/pulls{/number}","milestones_url":"https://api.github.com/repos/haskell/cabal/milestones{/number}","notifications_url":"https://api.github.com/repos/haskell/cabal/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/haskell/cabal/labels{/name}","releases_url":"https://api.github.com/repos/haskell/cabal/releases{/id}","deployments_url":"https://api.github.com/repos/haskell/cabal/deployments","created_at":"2012-03-15T12:53:38Z","updated_at":"2016-03-03T16:45:09Z","pushed_at":"2016-03-04T11:35:36Z","git_url":"git://github.com/haskell/cabal.git","ssh_url":"git@github.com:haskell/cabal.git","clone_url":"https://github.com/haskell/cabal.git","svn_url":"https://github.com/haskell/cabal","homepage":"http://haskell.org/cabal","size":32545,"stargazers_count":585,"watchers_count":585,"language":"Haskell","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":313,"mirror_url":null,"open_issues_count":687,"forks":313,"open_issues":687,"watchers":585,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/haskell/cabal/pulls/3208"},"html":{"href":"https://github.com/haskell/cabal/pull/3208"},"issue":{"href":"https://api.github.com/repos/haskell/cabal/issues/3208"},"comments":{"href":"https://api.github.com/repos/haskell/cabal/issues/3208/comments"},"review_comments":{"href":"https://api.github.com/repos/haskell/cabal/pulls/3208/comments"},"review_comment":{"href":"https://api.github.com/repos/haskell/cabal/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/haskell/cabal/pulls/3208/commits"},"statuses":{"href":"https://api.github.com/repos/haskell/cabal/statuses/150d6ca9b706498659b0c905dcd8ff661ee466e3"}},"merged":true,"mergeable":null,"mergeable_state":"unknown","merged_by":{"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},"comments":4,"review_comments":0,"commits":1,"additions":166,"deletions":55,"changed_files":4}}