{"action":"created","comment":{"url":"https://api.github.com/repos/docker/swarmkit/pulls/comments/79481040","id":79481040,"diff_hunk":"@@ -45,42 +43,73 @@ func (ns *nodeSet) remove(nodeID string) {\n \tdelete(ns.nodes, nodeID)\n }\n \n-type nodeSorter struct {\n+type nodeMaxHeap struct {\n \tnodes    []NodeInfo\n \tlessFunc func(*NodeInfo, *NodeInfo) bool\n+\tlength   int\n+}\n+\n+func (h nodeMaxHeap) Len() int {\n+\treturn h.length\n+}\n+\n+func (h nodeMaxHeap) Swap(i, j int) {\n+\th.nodes[i], h.nodes[j] = h.nodes[j], h.nodes[i]\n }\n \n-func (s nodeSorter) Len() int {\n-\treturn len(s.nodes)\n+func (h nodeMaxHeap) Less(i, j int) bool {\n+\t// reversed to make a max-heap\n+\treturn h.lessFunc(&h.nodes[j], &h.nodes[i])\n }\n \n-func (s nodeSorter) Swap(i, j int) {\n-\ts.nodes[i], s.nodes[j] = s.nodes[j], s.nodes[i]\n+func (h *nodeMaxHeap) Push(x interface{}) {\n+\th.nodes = append(h.nodes, x.(NodeInfo))\n+\th.length++\n }\n \n-func (s nodeSorter) Less(i, j int) bool {\n-\treturn s.lessFunc(&s.nodes[i], &s.nodes[j])\n+func (h *nodeMaxHeap) Pop() interface{} {\n+\th.length--\n+\t// return value is never used\n+\treturn nil\n }\n \n // findBestNodes returns n nodes (or < n if fewer nodes are available) that\n // rank best (lowest) according to the sorting function.\n func (ns *nodeSet) findBestNodes(n int, meetsConstraints func(*NodeInfo) bool, nodeLess func(*NodeInfo, *NodeInfo) bool) []NodeInfo {","path":"manager/scheduler/nodeset.go","position":55,"original_position":55,"commit_id":"6c8cb806fbe3e77c51cb766e2c0410279dfca21d","original_commit_id":"6c8cb806fbe3e77c51cb766e2c0410279dfca21d","user":{"login":"nishanttotla","id":1872537,"avatar_url":"https://avatars.githubusercontent.com/u/1872537?v=3","gravatar_id":"","url":"https://api.github.com/users/nishanttotla","html_url":"https://github.com/nishanttotla","followers_url":"https://api.github.com/users/nishanttotla/followers","following_url":"https://api.github.com/users/nishanttotla/following{/other_user}","gists_url":"https://api.github.com/users/nishanttotla/gists{/gist_id}","starred_url":"https://api.github.com/users/nishanttotla/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/nishanttotla/subscriptions","organizations_url":"https://api.github.com/users/nishanttotla/orgs","repos_url":"https://api.github.com/users/nishanttotla/repos","events_url":"https://api.github.com/users/nishanttotla/events{/privacy}","received_events_url":"https://api.github.com/users/nishanttotla/received_events","type":"User","site_admin":false},"body":"Just to confirm: Is this argument `n` the same as `k` in the above description, when `findBestNodes` actually gets called?","created_at":"2016-09-19T20:26:19Z","updated_at":"2016-09-19T20:26:19Z","html_url":"https://github.com/docker/swarmkit/pull/1550#discussion_r79481040","pull_request_url":"https://api.github.com/repos/docker/swarmkit/pulls/1550","_links":{"self":{"href":"https://api.github.com/repos/docker/swarmkit/pulls/comments/79481040"},"html":{"href":"https://github.com/docker/swarmkit/pull/1550#discussion_r79481040"},"pull_request":{"href":"https://api.github.com/repos/docker/swarmkit/pulls/1550"}}},"pull_request":{"url":"https://api.github.com/repos/docker/swarmkit/pulls/1550","id":85853510,"html_url":"https://github.com/docker/swarmkit/pull/1550","diff_url":"https://github.com/docker/swarmkit/pull/1550.diff","patch_url":"https://github.com/docker/swarmkit/pull/1550.patch","issue_url":"https://api.github.com/repos/docker/swarmkit/issues/1550","number":1550,"state":"open","locked":false,"title":"scheduler: Use heap-sort instead of quickselect","user":{"login":"aaronlehmann","id":10601430,"avatar_url":"https://avatars.githubusercontent.com/u/10601430?v=3","gravatar_id":"","url":"https://api.github.com/users/aaronlehmann","html_url":"https://github.com/aaronlehmann","followers_url":"https://api.github.com/users/aaronlehmann/followers","following_url":"https://api.github.com/users/aaronlehmann/following{/other_user}","gists_url":"https://api.github.com/users/aaronlehmann/gists{/gist_id}","starred_url":"https://api.github.com/users/aaronlehmann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aaronlehmann/subscriptions","organizations_url":"https://api.github.com/users/aaronlehmann/orgs","repos_url":"https://api.github.com/users/aaronlehmann/repos","events_url":"https://api.github.com/users/aaronlehmann/events{/privacy}","received_events_url":"https://api.github.com/users/aaronlehmann/received_events","type":"User","site_admin":false},"body":"The HA scheduling algorithm introduced code that built a slice of all\r\nnodes meeting the constraints, then selected the k best nodes from that\r\nslice.\r\n\r\nBuilding the slice can be expensive if there are a lot of nodes.\r\n\r\nTo improve performance, we can build a max-heap of nodes and pop all of\r\nthe elements to perform a heap sort. We never need to have more than k\r\nitems in the heap at any time, since the heap enables a trivial\r\noptimization to check if a node is \"better\" than the root of the heap.\r\nIf it isn't, we can skip that node, and if it is, we can replace the\r\nroot of the heap with it.\r\n\r\nThis approach needs less memory allocation with k << len(nodes).\r\n\r\nIt also removes the dependency on quickselect.\r\n\r\nThanks to @LK4D4 for the idea.","created_at":"2016-09-19T19:24:09Z","updated_at":"2016-09-19T20:26:19Z","closed_at":null,"merged_at":null,"merge_commit_sha":"fc21937df325f47810cd93ac591dadca080949cd","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/docker/swarmkit/pulls/1550/commits","review_comments_url":"https://api.github.com/repos/docker/swarmkit/pulls/1550/comments","review_comment_url":"https://api.github.com/repos/docker/swarmkit/pulls/comments{/number}","comments_url":"https://api.github.com/repos/docker/swarmkit/issues/1550/comments","statuses_url":"https://api.github.com/repos/docker/swarmkit/statuses/6c8cb806fbe3e77c51cb766e2c0410279dfca21d","head":{"label":"aaronlehmann:faster-node-selection","ref":"faster-node-selection","sha":"6c8cb806fbe3e77c51cb766e2c0410279dfca21d","user":{"login":"aaronlehmann","id":10601430,"avatar_url":"https://avatars.githubusercontent.com/u/10601430?v=3","gravatar_id":"","url":"https://api.github.com/users/aaronlehmann","html_url":"https://github.com/aaronlehmann","followers_url":"https://api.github.com/users/aaronlehmann/followers","following_url":"https://api.github.com/users/aaronlehmann/following{/other_user}","gists_url":"https://api.github.com/users/aaronlehmann/gists{/gist_id}","starred_url":"https://api.github.com/users/aaronlehmann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aaronlehmann/subscriptions","organizations_url":"https://api.github.com/users/aaronlehmann/orgs","repos_url":"https://api.github.com/users/aaronlehmann/repos","events_url":"https://api.github.com/users/aaronlehmann/events{/privacy}","received_events_url":"https://api.github.com/users/aaronlehmann/received_events","type":"User","site_admin":false},"repo":{"id":61081831,"name":"swarmkit","full_name":"aaronlehmann/swarmkit","owner":{"login":"aaronlehmann","id":10601430,"avatar_url":"https://avatars.githubusercontent.com/u/10601430?v=3","gravatar_id":"","url":"https://api.github.com/users/aaronlehmann","html_url":"https://github.com/aaronlehmann","followers_url":"https://api.github.com/users/aaronlehmann/followers","following_url":"https://api.github.com/users/aaronlehmann/following{/other_user}","gists_url":"https://api.github.com/users/aaronlehmann/gists{/gist_id}","starred_url":"https://api.github.com/users/aaronlehmann/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/aaronlehmann/subscriptions","organizations_url":"https://api.github.com/users/aaronlehmann/orgs","repos_url":"https://api.github.com/users/aaronlehmann/repos","events_url":"https://api.github.com/users/aaronlehmann/events{/privacy}","received_events_url":"https://api.github.com/users/aaronlehmann/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/aaronlehmann/swarmkit","description":"A toolkit for orchestrating distributed systems at any scale. It includes primitives for node discovery, raft-based consensus, task scheduling and more.","fork":true,"url":"https://api.github.com/repos/aaronlehmann/swarmkit","forks_url":"https://api.github.com/repos/aaronlehmann/swarmkit/forks","keys_url":"https://api.github.com/repos/aaronlehmann/swarmkit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/aaronlehmann/swarmkit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/aaronlehmann/swarmkit/teams","hooks_url":"https://api.github.com/repos/aaronlehmann/swarmkit/hooks","issue_events_url":"https://api.github.com/repos/aaronlehmann/swarmkit/issues/events{/number}","events_url":"https://api.github.com/repos/aaronlehmann/swarmkit/events","assignees_url":"https://api.github.com/repos/aaronlehmann/swarmkit/assignees{/user}","branches_url":"https://api.github.com/repos/aaronlehmann/swarmkit/branches{/branch}","tags_url":"https://api.github.com/repos/aaronlehmann/swarmkit/tags","blobs_url":"https://api.github.com/repos/aaronlehmann/swarmkit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/aaronlehmann/swarmkit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/aaronlehmann/swarmkit/git/refs{/sha}","trees_url":"https://api.github.com/repos/aaronlehmann/swarmkit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/aaronlehmann/swarmkit/statuses/{sha}","languages_url":"https://api.github.com/repos/aaronlehmann/swarmkit/languages","stargazers_url":"https://api.github.com/repos/aaronlehmann/swarmkit/stargazers","contributors_url":"https://api.github.com/repos/aaronlehmann/swarmkit/contributors","subscribers_url":"https://api.github.com/repos/aaronlehmann/swarmkit/subscribers","subscription_url":"https://api.github.com/repos/aaronlehmann/swarmkit/subscription","commits_url":"https://api.github.com/repos/aaronlehmann/swarmkit/commits{/sha}","git_commits_url":"https://api.github.com/repos/aaronlehmann/swarmkit/git/commits{/sha}","comments_url":"https://api.github.com/repos/aaronlehmann/swarmkit/comments{/number}","issue_comment_url":"https://api.github.com/repos/aaronlehmann/swarmkit/issues/comments{/number}","contents_url":"https://api.github.com/repos/aaronlehmann/swarmkit/contents/{+path}","compare_url":"https://api.github.com/repos/aaronlehmann/swarmkit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/aaronlehmann/swarmkit/merges","archive_url":"https://api.github.com/repos/aaronlehmann/swarmkit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/aaronlehmann/swarmkit/downloads","issues_url":"https://api.github.com/repos/aaronlehmann/swarmkit/issues{/number}","pulls_url":"https://api.github.com/repos/aaronlehmann/swarmkit/pulls{/number}","milestones_url":"https://api.github.com/repos/aaronlehmann/swarmkit/milestones{/number}","notifications_url":"https://api.github.com/repos/aaronlehmann/swarmkit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/aaronlehmann/swarmkit/labels{/name}","releases_url":"https://api.github.com/repos/aaronlehmann/swarmkit/releases{/id}","deployments_url":"https://api.github.com/repos/aaronlehmann/swarmkit/deployments","created_at":"2016-06-14T01:29:55Z","updated_at":"2016-06-14T01:29:56Z","pushed_at":"2016-09-19T19:31:09Z","git_url":"git://github.com/aaronlehmann/swarmkit.git","ssh_url":"git@github.com:aaronlehmann/swarmkit.git","clone_url":"https://github.com/aaronlehmann/swarmkit.git","svn_url":"https://github.com/aaronlehmann/swarmkit","homepage":"","size":10114,"stargazers_count":0,"watchers_count":0,"language":"Go","has_issues":false,"has_downloads":true,"has_wiki":false,"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":"docker:master","ref":"master","sha":"a2e755ddc316cb91c5a01840834ebc3ce8c5aa4b","user":{"login":"docker","id":5429470,"avatar_url":"https://avatars.githubusercontent.com/u/5429470?v=3","gravatar_id":"","url":"https://api.github.com/users/docker","html_url":"https://github.com/docker","followers_url":"https://api.github.com/users/docker/followers","following_url":"https://api.github.com/users/docker/following{/other_user}","gists_url":"https://api.github.com/users/docker/gists{/gist_id}","starred_url":"https://api.github.com/users/docker/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/docker/subscriptions","organizations_url":"https://api.github.com/users/docker/orgs","repos_url":"https://api.github.com/users/docker/repos","events_url":"https://api.github.com/users/docker/events{/privacy}","received_events_url":"https://api.github.com/users/docker/received_events","type":"Organization","site_admin":false},"repo":{"id":51556828,"name":"swarmkit","full_name":"docker/swarmkit","owner":{"login":"docker","id":5429470,"avatar_url":"https://avatars.githubusercontent.com/u/5429470?v=3","gravatar_id":"","url":"https://api.github.com/users/docker","html_url":"https://github.com/docker","followers_url":"https://api.github.com/users/docker/followers","following_url":"https://api.github.com/users/docker/following{/other_user}","gists_url":"https://api.github.com/users/docker/gists{/gist_id}","starred_url":"https://api.github.com/users/docker/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/docker/subscriptions","organizations_url":"https://api.github.com/users/docker/orgs","repos_url":"https://api.github.com/users/docker/repos","events_url":"https://api.github.com/users/docker/events{/privacy}","received_events_url":"https://api.github.com/users/docker/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/docker/swarmkit","description":"A toolkit for orchestrating distributed systems at any scale. It includes primitives for node discovery, raft-based consensus, task scheduling and more.","fork":false,"url":"https://api.github.com/repos/docker/swarmkit","forks_url":"https://api.github.com/repos/docker/swarmkit/forks","keys_url":"https://api.github.com/repos/docker/swarmkit/keys{/key_id}","collaborators_url":"https://api.github.com/repos/docker/swarmkit/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/docker/swarmkit/teams","hooks_url":"https://api.github.com/repos/docker/swarmkit/hooks","issue_events_url":"https://api.github.com/repos/docker/swarmkit/issues/events{/number}","events_url":"https://api.github.com/repos/docker/swarmkit/events","assignees_url":"https://api.github.com/repos/docker/swarmkit/assignees{/user}","branches_url":"https://api.github.com/repos/docker/swarmkit/branches{/branch}","tags_url":"https://api.github.com/repos/docker/swarmkit/tags","blobs_url":"https://api.github.com/repos/docker/swarmkit/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/docker/swarmkit/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/docker/swarmkit/git/refs{/sha}","trees_url":"https://api.github.com/repos/docker/swarmkit/git/trees{/sha}","statuses_url":"https://api.github.com/repos/docker/swarmkit/statuses/{sha}","languages_url":"https://api.github.com/repos/docker/swarmkit/languages","stargazers_url":"https://api.github.com/repos/docker/swarmkit/stargazers","contributors_url":"https://api.github.com/repos/docker/swarmkit/contributors","subscribers_url":"https://api.github.com/repos/docker/swarmkit/subscribers","subscription_url":"https://api.github.com/repos/docker/swarmkit/subscription","commits_url":"https://api.github.com/repos/docker/swarmkit/commits{/sha}","git_commits_url":"https://api.github.com/repos/docker/swarmkit/git/commits{/sha}","comments_url":"https://api.github.com/repos/docker/swarmkit/comments{/number}","issue_comment_url":"https://api.github.com/repos/docker/swarmkit/issues/comments{/number}","contents_url":"https://api.github.com/repos/docker/swarmkit/contents/{+path}","compare_url":"https://api.github.com/repos/docker/swarmkit/compare/{base}...{head}","merges_url":"https://api.github.com/repos/docker/swarmkit/merges","archive_url":"https://api.github.com/repos/docker/swarmkit/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/docker/swarmkit/downloads","issues_url":"https://api.github.com/repos/docker/swarmkit/issues{/number}","pulls_url":"https://api.github.com/repos/docker/swarmkit/pulls{/number}","milestones_url":"https://api.github.com/repos/docker/swarmkit/milestones{/number}","notifications_url":"https://api.github.com/repos/docker/swarmkit/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/docker/swarmkit/labels{/name}","releases_url":"https://api.github.com/repos/docker/swarmkit/releases{/id}","deployments_url":"https://api.github.com/repos/docker/swarmkit/deployments","created_at":"2016-02-12T00:02:15Z","updated_at":"2016-09-19T15:18:06Z","pushed_at":"2016-09-19T19:31:09Z","git_url":"git://github.com/docker/swarmkit.git","ssh_url":"git@github.com:docker/swarmkit.git","clone_url":"https://github.com/docker/swarmkit.git","svn_url":"https://github.com/docker/swarmkit","homepage":"","size":21256,"stargazers_count":945,"watchers_count":945,"language":"Go","has_issues":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":179,"mirror_url":null,"open_issues_count":180,"forks":179,"open_issues":180,"watchers":945,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/docker/swarmkit/pulls/1550"},"html":{"href":"https://github.com/docker/swarmkit/pull/1550"},"issue":{"href":"https://api.github.com/repos/docker/swarmkit/issues/1550"},"comments":{"href":"https://api.github.com/repos/docker/swarmkit/issues/1550/comments"},"review_comments":{"href":"https://api.github.com/repos/docker/swarmkit/pulls/1550/comments"},"review_comment":{"href":"https://api.github.com/repos/docker/swarmkit/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/docker/swarmkit/pulls/1550/commits"},"statuses":{"href":"https://api.github.com/repos/docker/swarmkit/statuses/6c8cb806fbe3e77c51cb766e2c0410279dfca21d"}}}}
{"actor":{"display_login":"nishanttotla"}}