{"action":"closed","number":97,"pull_request":{"url":"https://api.github.com/repos/mono/mono-addins/pulls/97","id":168448787,"html_url":"https://github.com/mono/mono-addins/pull/97","diff_url":"https://github.com/mono/mono-addins/pull/97.diff","patch_url":"https://github.com/mono/mono-addins/pull/97.patch","issue_url":"https://api.github.com/repos/mono/mono-addins/issues/97","number":97,"state":"closed","locked":false,"title":"[Database] Cache the dependency tree in AddinDependsOn","user":{"login":"Therzok","id":109974,"avatar_url":"https://avatars1.githubusercontent.com/u/109974?v=4","gravatar_id":"","url":"https://api.github.com/users/Therzok","html_url":"https://github.com/Therzok","followers_url":"https://api.github.com/users/Therzok/followers","following_url":"https://api.github.com/users/Therzok/following{/other_user}","gists_url":"https://api.github.com/users/Therzok/gists{/gist_id}","starred_url":"https://api.github.com/users/Therzok/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Therzok/subscriptions","organizations_url":"https://api.github.com/users/Therzok/orgs","repos_url":"https://api.github.com/users/Therzok/repos","events_url":"https://api.github.com/users/Therzok/events{/privacy}","received_events_url":"https://api.github.com/users/Therzok/received_events","type":"User","site_admin":false},"body":"Every time we load an extension point, we sort the data by the addin\r\ndependency tree.\r\n\r\nIn the case of 100 extensions, we end up doing a linear search with\r\nevery addin when inserting into the sorted list.\r\n\r\nThe old code's limitation was that we had to create an addin dependency\r\ntree on the spot for every addin with every addin.\r\n\r\nThat means we'd traverse the whole tree and construct it on every iteration,\r\nfor every check.\r\n\r\nThat potentially rounds up to O(N_DEPS) * O(N_EXTENSIONS^2).\r\n\r\nThis code makes the tree construction on demand, so the checking where it fits\r\nis an O(1) for constructed cache, and O(N_DEPS) for non-constructed.\r\n\r\nWe transitively propagate deps of an addin to the parent, for hitting O(1)\r\nin all cases.\r\n\r\nThe reason we now put the Name instead of FullId when doing recursive search is because,\r\nfor example, an addin written with AddinMaker will depend on MD.Core,7.0.\r\n\r\nIf 7.5 is installed, this would return false because we don't have an exact\r\nmatch in the cache.\r\n\r\nMaking the HashSet use a custom comparer or getting the addin parts from\r\nthe addin id would be allocation heavy, so resort to discarding the version\r\nwhen adding the list of addins (as the dependency code discards the version\r\nanyway by doing in-exact matches)\r\n\r\nFixes #95. This reduces an UI hang that takes 1.70s when loading the project model extensions\r\nin VSMac, and probably a lot more places are now faster because of this.","created_at":"2018-02-11T11:15:48Z","updated_at":"2018-02-19T19:11:35Z","closed_at":"2018-02-19T19:11:34Z","merged_at":"2018-02-19T19:11:34Z","merge_commit_sha":"136a3322119e147fa69d9a5a74a7a64da2199ce5","assignee":null,"assignees":[],"requested_reviewers":[{"login":"mhutch","id":183285,"avatar_url":"https://avatars2.githubusercontent.com/u/183285?v=4","gravatar_id":"","url":"https://api.github.com/users/mhutch","html_url":"https://github.com/mhutch","followers_url":"https://api.github.com/users/mhutch/followers","following_url":"https://api.github.com/users/mhutch/following{/other_user}","gists_url":"https://api.github.com/users/mhutch/gists{/gist_id}","starred_url":"https://api.github.com/users/mhutch/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mhutch/subscriptions","organizations_url":"https://api.github.com/users/mhutch/orgs","repos_url":"https://api.github.com/users/mhutch/repos","events_url":"https://api.github.com/users/mhutch/events{/privacy}","received_events_url":"https://api.github.com/users/mhutch/received_events","type":"User","site_admin":false},{"login":"alanmcgovern","id":264396,"avatar_url":"https://avatars3.githubusercontent.com/u/264396?v=4","gravatar_id":"","url":"https://api.github.com/users/alanmcgovern","html_url":"https://github.com/alanmcgovern","followers_url":"https://api.github.com/users/alanmcgovern/followers","following_url":"https://api.github.com/users/alanmcgovern/following{/other_user}","gists_url":"https://api.github.com/users/alanmcgovern/gists{/gist_id}","starred_url":"https://api.github.com/users/alanmcgovern/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/alanmcgovern/subscriptions","organizations_url":"https://api.github.com/users/alanmcgovern/orgs","repos_url":"https://api.github.com/users/alanmcgovern/repos","events_url":"https://api.github.com/users/alanmcgovern/events{/privacy}","received_events_url":"https://api.github.com/users/alanmcgovern/received_events","type":"User","site_admin":false}],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/mono/mono-addins/pulls/97/commits","review_comments_url":"https://api.github.com/repos/mono/mono-addins/pulls/97/comments","review_comment_url":"https://api.github.com/repos/mono/mono-addins/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mono/mono-addins/issues/97/comments","statuses_url":"https://api.github.com/repos/mono/mono-addins/statuses/eaee3f89a17f9aa541ed73c47d2841160954d3f1","head":{"label":"mono:dep-tree","ref":"dep-tree","sha":"eaee3f89a17f9aa541ed73c47d2841160954d3f1","user":{"login":"mono","id":53395,"avatar_url":"https://avatars3.githubusercontent.com/u/53395?v=4","gravatar_id":"","url":"https://api.github.com/users/mono","html_url":"https://github.com/mono","followers_url":"https://api.github.com/users/mono/followers","following_url":"https://api.github.com/users/mono/following{/other_user}","gists_url":"https://api.github.com/users/mono/gists{/gist_id}","starred_url":"https://api.github.com/users/mono/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mono/subscriptions","organizations_url":"https://api.github.com/users/mono/orgs","repos_url":"https://api.github.com/users/mono/repos","events_url":"https://api.github.com/users/mono/events{/privacy}","received_events_url":"https://api.github.com/users/mono/received_events","type":"Organization","site_admin":false},"repo":{"id":791290,"name":"mono-addins","full_name":"mono/mono-addins","owner":{"login":"mono","id":53395,"avatar_url":"https://avatars3.githubusercontent.com/u/53395?v=4","gravatar_id":"","url":"https://api.github.com/users/mono","html_url":"https://github.com/mono","followers_url":"https://api.github.com/users/mono/followers","following_url":"https://api.github.com/users/mono/following{/other_user}","gists_url":"https://api.github.com/users/mono/gists{/gist_id}","starred_url":"https://api.github.com/users/mono/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mono/subscriptions","organizations_url":"https://api.github.com/users/mono/orgs","repos_url":"https://api.github.com/users/mono/repos","events_url":"https://api.github.com/users/mono/events{/privacy}","received_events_url":"https://api.github.com/users/mono/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mono/mono-addins","description":"Mono.Addins is a generic framework for creating extensible applications, and for creating add-ins which extend those applications.","fork":false,"url":"https://api.github.com/repos/mono/mono-addins","forks_url":"https://api.github.com/repos/mono/mono-addins/forks","keys_url":"https://api.github.com/repos/mono/mono-addins/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mono/mono-addins/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mono/mono-addins/teams","hooks_url":"https://api.github.com/repos/mono/mono-addins/hooks","issue_events_url":"https://api.github.com/repos/mono/mono-addins/issues/events{/number}","events_url":"https://api.github.com/repos/mono/mono-addins/events","assignees_url":"https://api.github.com/repos/mono/mono-addins/assignees{/user}","branches_url":"https://api.github.com/repos/mono/mono-addins/branches{/branch}","tags_url":"https://api.github.com/repos/mono/mono-addins/tags","blobs_url":"https://api.github.com/repos/mono/mono-addins/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mono/mono-addins/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mono/mono-addins/git/refs{/sha}","trees_url":"https://api.github.com/repos/mono/mono-addins/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mono/mono-addins/statuses/{sha}","languages_url":"https://api.github.com/repos/mono/mono-addins/languages","stargazers_url":"https://api.github.com/repos/mono/mono-addins/stargazers","contributors_url":"https://api.github.com/repos/mono/mono-addins/contributors","subscribers_url":"https://api.github.com/repos/mono/mono-addins/subscribers","subscription_url":"https://api.github.com/repos/mono/mono-addins/subscription","commits_url":"https://api.github.com/repos/mono/mono-addins/commits{/sha}","git_commits_url":"https://api.github.com/repos/mono/mono-addins/git/commits{/sha}","comments_url":"https://api.github.com/repos/mono/mono-addins/comments{/number}","issue_comment_url":"https://api.github.com/repos/mono/mono-addins/issues/comments{/number}","contents_url":"https://api.github.com/repos/mono/mono-addins/contents/{+path}","compare_url":"https://api.github.com/repos/mono/mono-addins/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mono/mono-addins/merges","archive_url":"https://api.github.com/repos/mono/mono-addins/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mono/mono-addins/downloads","issues_url":"https://api.github.com/repos/mono/mono-addins/issues{/number}","pulls_url":"https://api.github.com/repos/mono/mono-addins/pulls{/number}","milestones_url":"https://api.github.com/repos/mono/mono-addins/milestones{/number}","notifications_url":"https://api.github.com/repos/mono/mono-addins/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mono/mono-addins/labels{/name}","releases_url":"https://api.github.com/repos/mono/mono-addins/releases{/id}","deployments_url":"https://api.github.com/repos/mono/mono-addins/deployments","created_at":"2010-07-22T16:06:31Z","updated_at":"2018-02-01T11:16:20Z","pushed_at":"2018-02-19T19:11:34Z","git_url":"git://github.com/mono/mono-addins.git","ssh_url":"git@github.com:mono/mono-addins.git","clone_url":"https://github.com/mono/mono-addins.git","svn_url":"https://github.com/mono/mono-addins","homepage":"","size":3978,"stargazers_count":123,"watchers_count":123,"language":"C#","has_issues":true,"has_projects":true,"has_downloads":false,"has_wiki":true,"has_pages":true,"forks_count":67,"mirror_url":null,"archived":false,"open_issues_count":23,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit"},"forks":67,"open_issues":23,"watchers":123,"default_branch":"master"}},"base":{"label":"mono:master","ref":"master","sha":"d213f8fb9f86330b02bbc2ca0f83ed7a41119fda","user":{"login":"mono","id":53395,"avatar_url":"https://avatars3.githubusercontent.com/u/53395?v=4","gravatar_id":"","url":"https://api.github.com/users/mono","html_url":"https://github.com/mono","followers_url":"https://api.github.com/users/mono/followers","following_url":"https://api.github.com/users/mono/following{/other_user}","gists_url":"https://api.github.com/users/mono/gists{/gist_id}","starred_url":"https://api.github.com/users/mono/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mono/subscriptions","organizations_url":"https://api.github.com/users/mono/orgs","repos_url":"https://api.github.com/users/mono/repos","events_url":"https://api.github.com/users/mono/events{/privacy}","received_events_url":"https://api.github.com/users/mono/received_events","type":"Organization","site_admin":false},"repo":{"id":791290,"name":"mono-addins","full_name":"mono/mono-addins","owner":{"login":"mono","id":53395,"avatar_url":"https://avatars3.githubusercontent.com/u/53395?v=4","gravatar_id":"","url":"https://api.github.com/users/mono","html_url":"https://github.com/mono","followers_url":"https://api.github.com/users/mono/followers","following_url":"https://api.github.com/users/mono/following{/other_user}","gists_url":"https://api.github.com/users/mono/gists{/gist_id}","starred_url":"https://api.github.com/users/mono/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mono/subscriptions","organizations_url":"https://api.github.com/users/mono/orgs","repos_url":"https://api.github.com/users/mono/repos","events_url":"https://api.github.com/users/mono/events{/privacy}","received_events_url":"https://api.github.com/users/mono/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mono/mono-addins","description":"Mono.Addins is a generic framework for creating extensible applications, and for creating add-ins which extend those applications.","fork":false,"url":"https://api.github.com/repos/mono/mono-addins","forks_url":"https://api.github.com/repos/mono/mono-addins/forks","keys_url":"https://api.github.com/repos/mono/mono-addins/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mono/mono-addins/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mono/mono-addins/teams","hooks_url":"https://api.github.com/repos/mono/mono-addins/hooks","issue_events_url":"https://api.github.com/repos/mono/mono-addins/issues/events{/number}","events_url":"https://api.github.com/repos/mono/mono-addins/events","assignees_url":"https://api.github.com/repos/mono/mono-addins/assignees{/user}","branches_url":"https://api.github.com/repos/mono/mono-addins/branches{/branch}","tags_url":"https://api.github.com/repos/mono/mono-addins/tags","blobs_url":"https://api.github.com/repos/mono/mono-addins/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mono/mono-addins/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mono/mono-addins/git/refs{/sha}","trees_url":"https://api.github.com/repos/mono/mono-addins/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mono/mono-addins/statuses/{sha}","languages_url":"https://api.github.com/repos/mono/mono-addins/languages","stargazers_url":"https://api.github.com/repos/mono/mono-addins/stargazers","contributors_url":"https://api.github.com/repos/mono/mono-addins/contributors","subscribers_url":"https://api.github.com/repos/mono/mono-addins/subscribers","subscription_url":"https://api.github.com/repos/mono/mono-addins/subscription","commits_url":"https://api.github.com/repos/mono/mono-addins/commits{/sha}","git_commits_url":"https://api.github.com/repos/mono/mono-addins/git/commits{/sha}","comments_url":"https://api.github.com/repos/mono/mono-addins/comments{/number}","issue_comment_url":"https://api.github.com/repos/mono/mono-addins/issues/comments{/number}","contents_url":"https://api.github.com/repos/mono/mono-addins/contents/{+path}","compare_url":"https://api.github.com/repos/mono/mono-addins/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mono/mono-addins/merges","archive_url":"https://api.github.com/repos/mono/mono-addins/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mono/mono-addins/downloads","issues_url":"https://api.github.com/repos/mono/mono-addins/issues{/number}","pulls_url":"https://api.github.com/repos/mono/mono-addins/pulls{/number}","milestones_url":"https://api.github.com/repos/mono/mono-addins/milestones{/number}","notifications_url":"https://api.github.com/repos/mono/mono-addins/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mono/mono-addins/labels{/name}","releases_url":"https://api.github.com/repos/mono/mono-addins/releases{/id}","deployments_url":"https://api.github.com/repos/mono/mono-addins/deployments","created_at":"2010-07-22T16:06:31Z","updated_at":"2018-02-01T11:16:20Z","pushed_at":"2018-02-19T19:11:34Z","git_url":"git://github.com/mono/mono-addins.git","ssh_url":"git@github.com:mono/mono-addins.git","clone_url":"https://github.com/mono/mono-addins.git","svn_url":"https://github.com/mono/mono-addins","homepage":"","size":3978,"stargazers_count":123,"watchers_count":123,"language":"C#","has_issues":true,"has_projects":true,"has_downloads":false,"has_wiki":true,"has_pages":true,"forks_count":67,"mirror_url":null,"archived":false,"open_issues_count":23,"license":{"key":"mit","name":"MIT License","spdx_id":"MIT","url":"https://api.github.com/licenses/mit"},"forks":67,"open_issues":23,"watchers":123,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mono/mono-addins/pulls/97"},"html":{"href":"https://github.com/mono/mono-addins/pull/97"},"issue":{"href":"https://api.github.com/repos/mono/mono-addins/issues/97"},"comments":{"href":"https://api.github.com/repos/mono/mono-addins/issues/97/comments"},"review_comments":{"href":"https://api.github.com/repos/mono/mono-addins/pulls/97/comments"},"review_comment":{"href":"https://api.github.com/repos/mono/mono-addins/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mono/mono-addins/pulls/97/commits"},"statuses":{"href":"https://api.github.com/repos/mono/mono-addins/statuses/eaee3f89a17f9aa541ed73c47d2841160954d3f1"}},"author_association":"MEMBER","merged":true,"mergeable":null,"rebaseable":null,"mergeable_state":"unknown","merged_by":{"login":"Therzok","id":109974,"avatar_url":"https://avatars1.githubusercontent.com/u/109974?v=4","gravatar_id":"","url":"https://api.github.com/users/Therzok","html_url":"https://github.com/Therzok","followers_url":"https://api.github.com/users/Therzok/followers","following_url":"https://api.github.com/users/Therzok/following{/other_user}","gists_url":"https://api.github.com/users/Therzok/gists{/gist_id}","starred_url":"https://api.github.com/users/Therzok/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Therzok/subscriptions","organizations_url":"https://api.github.com/users/Therzok/orgs","repos_url":"https://api.github.com/users/Therzok/repos","events_url":"https://api.github.com/users/Therzok/events{/privacy}","received_events_url":"https://api.github.com/users/Therzok/received_events","type":"User","site_admin":false},"comments":5,"review_comments":4,"maintainer_can_modify":false,"commits":3,"additions":43,"deletions":37,"changed_files":2}}
{"actor":{"display_login":"Therzok"}}