{"action":"created","comment":{"url":"https://api.github.com/repos/envoyproxy/envoy/pulls/comments/209816341","pull_request_review_id":145902378,"id":209816341,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIwOTgxNjM0MQ==","diff_hunk":"@@ -575,21 +568,23 @@ template <class T> class LcTrie {\n      */\n     void buildRecursive(uint32_t prefix, uint32_t first, uint32_t n, uint32_t position,\n                         uint32_t& next_free_index) {\n-      // Setting a leaf, the branch and skip are 0.\n-      if (n == 1) {\n+      if (position >= trie_.size()) {\n         // There is no way to predictably determine the number of trie nodes required to build a\n         // LC-Trie. If while building the trie the position that is being set exceeds the maximum\n         // number of supported trie_ entries, throw an Envoy Exception.\n-        if (position >= maximum_trie_node_size) {\n+        if (position >= MaxLcTrieNodes) {\n           // Adding 1 to the position to count how many nodes are trying to be set.\n           throw EnvoyException(\n               fmt::format(\"The number of internal nodes required for the LC-Trie \"\n                           \"exceeded the maximum number of \"\n                           \"supported nodes. Minimum number of internal nodes required: \"\n                           \"'{0}'. Maximum number of supported nodes: '{1}'.\",\n-                          (position + 1), maximum_trie_node_size));\n+                          (position + 1), MaxLcTrieNodes));\n         }\n-\n+        trie_.resize(position + 1);","path":"source/common/network/lc_trie.h","position":44,"original_position":46,"commit_id":"d8015126e0e0afc2ea53f67145d8ee79e778fe4f","original_commit_id":"96755095cae2869ba75656b9f49c070076f60c5d","user":{"login":"brian-pane","id":24847780,"node_id":"MDQ6VXNlcjI0ODQ3Nzgw","avatar_url":"https://avatars3.githubusercontent.com/u/24847780?v=4","gravatar_id":"","url":"https://api.github.com/users/brian-pane","html_url":"https://github.com/brian-pane","followers_url":"https://api.github.com/users/brian-pane/followers","following_url":"https://api.github.com/users/brian-pane/following{/other_user}","gists_url":"https://api.github.com/users/brian-pane/gists{/gist_id}","starred_url":"https://api.github.com/users/brian-pane/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brian-pane/subscriptions","organizations_url":"https://api.github.com/users/brian-pane/orgs","repos_url":"https://api.github.com/users/brian-pane/repos","events_url":"https://api.github.com/users/brian-pane/events{/privacy}","received_events_url":"https://api.github.com/users/brian-pane/received_events","type":"User","site_admin":false},"body":"They both have the potential to increase capacity. But what's needed in order for `trie_[position]` to be valid isn't an increase in `trie_`'s capacity, but rather an increase in its size. The `reserve` method doesn't increase the size, whereas `resize` does.","created_at":"2018-08-14T02:58:28Z","updated_at":"2018-08-14T02:58:28Z","html_url":"https://github.com/envoyproxy/envoy/pull/4117#discussion_r209816341","pull_request_url":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/envoyproxy/envoy/pulls/comments/209816341"},"html":{"href":"https://github.com/envoyproxy/envoy/pull/4117#discussion_r209816341"},"pull_request":{"href":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117"}},"in_reply_to_id":209788854},"pull_request":{"url":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117","id":207804762,"node_id":"MDExOlB1bGxSZXF1ZXN0MjA3ODA0NzYy","html_url":"https://github.com/envoyproxy/envoy/pull/4117","diff_url":"https://github.com/envoyproxy/envoy/pull/4117.diff","patch_url":"https://github.com/envoyproxy/envoy/pull/4117.patch","issue_url":"https://api.github.com/repos/envoyproxy/envoy/issues/4117","number":4117,"state":"open","locked":false,"title":"perf: reduce the memory usage of LC Trie construction","user":{"login":"brian-pane","id":24847780,"node_id":"MDQ6VXNlcjI0ODQ3Nzgw","avatar_url":"https://avatars3.githubusercontent.com/u/24847780?v=4","gravatar_id":"","url":"https://api.github.com/users/brian-pane","html_url":"https://github.com/brian-pane","followers_url":"https://api.github.com/users/brian-pane/followers","following_url":"https://api.github.com/users/brian-pane/following{/other_user}","gists_url":"https://api.github.com/users/brian-pane/gists{/gist_id}","starred_url":"https://api.github.com/users/brian-pane/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brian-pane/subscriptions","organizations_url":"https://api.github.com/users/brian-pane/orgs","repos_url":"https://api.github.com/users/brian-pane/repos","events_url":"https://api.github.com/users/brian-pane/events{/privacy}","received_events_url":"https://api.github.com/users/brian-pane/received_events","type":"User","site_admin":false},"body":"*Description*:\r\nRather than preallocating a very large buffer to hold the LC Trie nodes\r\nthe way the reference implementation from the original  Nilsson & Karlsson\r\npaper did, the trie construction now starts out with a size based on the\r\nnumber of prefixes and lets the `std::vector` manage any needed reallocation\r\nduring trie construction.\r\n\r\nIn addition to using less memory during trie construction, this new approach\r\nended up being faster:\r\n\r\n```\r\nBenchmark                                  Time           CPU Iterations\r\n-------------------------------------------------------------------------\r\nBefore:\r\nBM_LcTrieConstruct                  26631971 ns   26522462 ns         26\r\n\r\nAfter:\r\nBM_LcTrieConstruct                   3654633 ns    3646942 ns        189\r\n```\r\n\r\n*Risk Level*: medium\r\n*Testing*: unit tests plus new speed benchmark test\r\n*Docs Changes*: N/A\r\n*Release Notes*: N/A\r\n\r\nSigned-off-by: Brian Pane <bpane@pinterest.com>\r\n","created_at":"2018-08-12T04:51:01Z","updated_at":"2018-08-14T02:58:28Z","closed_at":null,"merged_at":null,"merge_commit_sha":"63a9a06405271cfab21338c2d0c728481ec9a8a1","assignee":{"login":"ccaraman","id":19931185,"node_id":"MDQ6VXNlcjE5OTMxMTg1","avatar_url":"https://avatars2.githubusercontent.com/u/19931185?v=4","gravatar_id":"","url":"https://api.github.com/users/ccaraman","html_url":"https://github.com/ccaraman","followers_url":"https://api.github.com/users/ccaraman/followers","following_url":"https://api.github.com/users/ccaraman/following{/other_user}","gists_url":"https://api.github.com/users/ccaraman/gists{/gist_id}","starred_url":"https://api.github.com/users/ccaraman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ccaraman/subscriptions","organizations_url":"https://api.github.com/users/ccaraman/orgs","repos_url":"https://api.github.com/users/ccaraman/repos","events_url":"https://api.github.com/users/ccaraman/events{/privacy}","received_events_url":"https://api.github.com/users/ccaraman/received_events","type":"User","site_admin":false},"assignees":[{"login":"ccaraman","id":19931185,"node_id":"MDQ6VXNlcjE5OTMxMTg1","avatar_url":"https://avatars2.githubusercontent.com/u/19931185?v=4","gravatar_id":"","url":"https://api.github.com/users/ccaraman","html_url":"https://github.com/ccaraman","followers_url":"https://api.github.com/users/ccaraman/followers","following_url":"https://api.github.com/users/ccaraman/following{/other_user}","gists_url":"https://api.github.com/users/ccaraman/gists{/gist_id}","starred_url":"https://api.github.com/users/ccaraman/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ccaraman/subscriptions","organizations_url":"https://api.github.com/users/ccaraman/orgs","repos_url":"https://api.github.com/users/ccaraman/repos","events_url":"https://api.github.com/users/ccaraman/events{/privacy}","received_events_url":"https://api.github.com/users/ccaraman/received_events","type":"User","site_admin":false}],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117/commits","review_comments_url":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117/comments","review_comment_url":"https://api.github.com/repos/envoyproxy/envoy/pulls/comments{/number}","comments_url":"https://api.github.com/repos/envoyproxy/envoy/issues/4117/comments","statuses_url":"https://api.github.com/repos/envoyproxy/envoy/statuses/d8015126e0e0afc2ea53f67145d8ee79e778fe4f","head":{"label":"brian-pane:lc_trie_memory","ref":"lc_trie_memory","sha":"d8015126e0e0afc2ea53f67145d8ee79e778fe4f","user":{"login":"brian-pane","id":24847780,"node_id":"MDQ6VXNlcjI0ODQ3Nzgw","avatar_url":"https://avatars3.githubusercontent.com/u/24847780?v=4","gravatar_id":"","url":"https://api.github.com/users/brian-pane","html_url":"https://github.com/brian-pane","followers_url":"https://api.github.com/users/brian-pane/followers","following_url":"https://api.github.com/users/brian-pane/following{/other_user}","gists_url":"https://api.github.com/users/brian-pane/gists{/gist_id}","starred_url":"https://api.github.com/users/brian-pane/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brian-pane/subscriptions","organizations_url":"https://api.github.com/users/brian-pane/orgs","repos_url":"https://api.github.com/users/brian-pane/repos","events_url":"https://api.github.com/users/brian-pane/events{/privacy}","received_events_url":"https://api.github.com/users/brian-pane/received_events","type":"User","site_admin":false},"repo":{"id":130001927,"node_id":"MDEwOlJlcG9zaXRvcnkxMzAwMDE5Mjc=","name":"envoy","full_name":"brian-pane/envoy","owner":{"login":"brian-pane","id":24847780,"node_id":"MDQ6VXNlcjI0ODQ3Nzgw","avatar_url":"https://avatars3.githubusercontent.com/u/24847780?v=4","gravatar_id":"","url":"https://api.github.com/users/brian-pane","html_url":"https://github.com/brian-pane","followers_url":"https://api.github.com/users/brian-pane/followers","following_url":"https://api.github.com/users/brian-pane/following{/other_user}","gists_url":"https://api.github.com/users/brian-pane/gists{/gist_id}","starred_url":"https://api.github.com/users/brian-pane/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/brian-pane/subscriptions","organizations_url":"https://api.github.com/users/brian-pane/orgs","repos_url":"https://api.github.com/users/brian-pane/repos","events_url":"https://api.github.com/users/brian-pane/events{/privacy}","received_events_url":"https://api.github.com/users/brian-pane/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/brian-pane/envoy","description":"C++ front/service proxy","fork":true,"url":"https://api.github.com/repos/brian-pane/envoy","forks_url":"https://api.github.com/repos/brian-pane/envoy/forks","keys_url":"https://api.github.com/repos/brian-pane/envoy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/brian-pane/envoy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/brian-pane/envoy/teams","hooks_url":"https://api.github.com/repos/brian-pane/envoy/hooks","issue_events_url":"https://api.github.com/repos/brian-pane/envoy/issues/events{/number}","events_url":"https://api.github.com/repos/brian-pane/envoy/events","assignees_url":"https://api.github.com/repos/brian-pane/envoy/assignees{/user}","branches_url":"https://api.github.com/repos/brian-pane/envoy/branches{/branch}","tags_url":"https://api.github.com/repos/brian-pane/envoy/tags","blobs_url":"https://api.github.com/repos/brian-pane/envoy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/brian-pane/envoy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/brian-pane/envoy/git/refs{/sha}","trees_url":"https://api.github.com/repos/brian-pane/envoy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/brian-pane/envoy/statuses/{sha}","languages_url":"https://api.github.com/repos/brian-pane/envoy/languages","stargazers_url":"https://api.github.com/repos/brian-pane/envoy/stargazers","contributors_url":"https://api.github.com/repos/brian-pane/envoy/contributors","subscribers_url":"https://api.github.com/repos/brian-pane/envoy/subscribers","subscription_url":"https://api.github.com/repos/brian-pane/envoy/subscription","commits_url":"https://api.github.com/repos/brian-pane/envoy/commits{/sha}","git_commits_url":"https://api.github.com/repos/brian-pane/envoy/git/commits{/sha}","comments_url":"https://api.github.com/repos/brian-pane/envoy/comments{/number}","issue_comment_url":"https://api.github.com/repos/brian-pane/envoy/issues/comments{/number}","contents_url":"https://api.github.com/repos/brian-pane/envoy/contents/{+path}","compare_url":"https://api.github.com/repos/brian-pane/envoy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/brian-pane/envoy/merges","archive_url":"https://api.github.com/repos/brian-pane/envoy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/brian-pane/envoy/downloads","issues_url":"https://api.github.com/repos/brian-pane/envoy/issues{/number}","pulls_url":"https://api.github.com/repos/brian-pane/envoy/pulls{/number}","milestones_url":"https://api.github.com/repos/brian-pane/envoy/milestones{/number}","notifications_url":"https://api.github.com/repos/brian-pane/envoy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/brian-pane/envoy/labels{/name}","releases_url":"https://api.github.com/repos/brian-pane/envoy/releases{/id}","deployments_url":"https://api.github.com/repos/brian-pane/envoy/deployments","created_at":"2018-04-18T04:04:11Z","updated_at":"2018-08-11T17:47:54Z","pushed_at":"2018-08-14T02:48:15Z","git_url":"git://github.com/brian-pane/envoy.git","ssh_url":"git@github.com:brian-pane/envoy.git","clone_url":"https://github.com/brian-pane/envoy.git","svn_url":"https://github.com/brian-pane/envoy","homepage":"https://www.envoyproxy.io","size":18818,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"envoyproxy:master","ref":"master","sha":"2662bf1f220a0c86289c8ead6a85cab388e8c14a","user":{"login":"envoyproxy","id":30125649,"node_id":"MDEyOk9yZ2FuaXphdGlvbjMwMTI1NjQ5","avatar_url":"https://avatars1.githubusercontent.com/u/30125649?v=4","gravatar_id":"","url":"https://api.github.com/users/envoyproxy","html_url":"https://github.com/envoyproxy","followers_url":"https://api.github.com/users/envoyproxy/followers","following_url":"https://api.github.com/users/envoyproxy/following{/other_user}","gists_url":"https://api.github.com/users/envoyproxy/gists{/gist_id}","starred_url":"https://api.github.com/users/envoyproxy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/envoyproxy/subscriptions","organizations_url":"https://api.github.com/users/envoyproxy/orgs","repos_url":"https://api.github.com/users/envoyproxy/repos","events_url":"https://api.github.com/users/envoyproxy/events{/privacy}","received_events_url":"https://api.github.com/users/envoyproxy/received_events","type":"Organization","site_admin":false},"repo":{"id":65214191,"node_id":"MDEwOlJlcG9zaXRvcnk2NTIxNDE5MQ==","name":"envoy","full_name":"envoyproxy/envoy","owner":{"login":"envoyproxy","id":30125649,"node_id":"MDEyOk9yZ2FuaXphdGlvbjMwMTI1NjQ5","avatar_url":"https://avatars1.githubusercontent.com/u/30125649?v=4","gravatar_id":"","url":"https://api.github.com/users/envoyproxy","html_url":"https://github.com/envoyproxy","followers_url":"https://api.github.com/users/envoyproxy/followers","following_url":"https://api.github.com/users/envoyproxy/following{/other_user}","gists_url":"https://api.github.com/users/envoyproxy/gists{/gist_id}","starred_url":"https://api.github.com/users/envoyproxy/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/envoyproxy/subscriptions","organizations_url":"https://api.github.com/users/envoyproxy/orgs","repos_url":"https://api.github.com/users/envoyproxy/repos","events_url":"https://api.github.com/users/envoyproxy/events{/privacy}","received_events_url":"https://api.github.com/users/envoyproxy/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/envoyproxy/envoy","description":"C++ front/service proxy","fork":false,"url":"https://api.github.com/repos/envoyproxy/envoy","forks_url":"https://api.github.com/repos/envoyproxy/envoy/forks","keys_url":"https://api.github.com/repos/envoyproxy/envoy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/envoyproxy/envoy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/envoyproxy/envoy/teams","hooks_url":"https://api.github.com/repos/envoyproxy/envoy/hooks","issue_events_url":"https://api.github.com/repos/envoyproxy/envoy/issues/events{/number}","events_url":"https://api.github.com/repos/envoyproxy/envoy/events","assignees_url":"https://api.github.com/repos/envoyproxy/envoy/assignees{/user}","branches_url":"https://api.github.com/repos/envoyproxy/envoy/branches{/branch}","tags_url":"https://api.github.com/repos/envoyproxy/envoy/tags","blobs_url":"https://api.github.com/repos/envoyproxy/envoy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/envoyproxy/envoy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/envoyproxy/envoy/git/refs{/sha}","trees_url":"https://api.github.com/repos/envoyproxy/envoy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/envoyproxy/envoy/statuses/{sha}","languages_url":"https://api.github.com/repos/envoyproxy/envoy/languages","stargazers_url":"https://api.github.com/repos/envoyproxy/envoy/stargazers","contributors_url":"https://api.github.com/repos/envoyproxy/envoy/contributors","subscribers_url":"https://api.github.com/repos/envoyproxy/envoy/subscribers","subscription_url":"https://api.github.com/repos/envoyproxy/envoy/subscription","commits_url":"https://api.github.com/repos/envoyproxy/envoy/commits{/sha}","git_commits_url":"https://api.github.com/repos/envoyproxy/envoy/git/commits{/sha}","comments_url":"https://api.github.com/repos/envoyproxy/envoy/comments{/number}","issue_comment_url":"https://api.github.com/repos/envoyproxy/envoy/issues/comments{/number}","contents_url":"https://api.github.com/repos/envoyproxy/envoy/contents/{+path}","compare_url":"https://api.github.com/repos/envoyproxy/envoy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/envoyproxy/envoy/merges","archive_url":"https://api.github.com/repos/envoyproxy/envoy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/envoyproxy/envoy/downloads","issues_url":"https://api.github.com/repos/envoyproxy/envoy/issues{/number}","pulls_url":"https://api.github.com/repos/envoyproxy/envoy/pulls{/number}","milestones_url":"https://api.github.com/repos/envoyproxy/envoy/milestones{/number}","notifications_url":"https://api.github.com/repos/envoyproxy/envoy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/envoyproxy/envoy/labels{/name}","releases_url":"https://api.github.com/repos/envoyproxy/envoy/releases{/id}","deployments_url":"https://api.github.com/repos/envoyproxy/envoy/deployments","created_at":"2016-08-08T15:07:24Z","updated_at":"2018-08-14T02:53:44Z","pushed_at":"2018-08-14T02:48:17Z","git_url":"git://github.com/envoyproxy/envoy.git","ssh_url":"git@github.com:envoyproxy/envoy.git","clone_url":"https://github.com/envoyproxy/envoy.git","svn_url":"https://github.com/envoyproxy/envoy","homepage":"https://www.envoyproxy.io","size":18896,"stargazers_count":6182,"watchers_count":6182,"language":"C++","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":814,"mirror_url":null,"archived":false,"open_issues_count":331,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":814,"open_issues":331,"watchers":6182,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117"},"html":{"href":"https://github.com/envoyproxy/envoy/pull/4117"},"issue":{"href":"https://api.github.com/repos/envoyproxy/envoy/issues/4117"},"comments":{"href":"https://api.github.com/repos/envoyproxy/envoy/issues/4117/comments"},"review_comments":{"href":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117/comments"},"review_comment":{"href":"https://api.github.com/repos/envoyproxy/envoy/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/envoyproxy/envoy/pulls/4117/commits"},"statuses":{"href":"https://api.github.com/repos/envoyproxy/envoy/statuses/d8015126e0e0afc2ea53f67145d8ee79e778fe4f"}},"author_association":"CONTRIBUTOR"}}
{"actor":{"display_login":"brian-pane"}}