upstream: avoid quadratic time complexity in server initialization#15237
upstream: avoid quadratic time complexity in server initialization#15237mattklein123 merged 1 commit intoenvoyproxy:mainfrom
Conversation
Currently ClusterManagerInitHelper.secondary_init_clusters_ is a list. Upon every insert the list gets searched for an already added cluster with the same name. Since in normal circumstances all new clusters have unique names the worst case scenario is triggered and all elements of the list are checked sequentially upon every cluster added. Replace the list with a hash map. Signed-off-by: Dmitry Rozhkov <dmitry.rozhkov@intel.com>
| cluster_list->remove(&cluster); | ||
| // present in the initializer map. If so, this is fine. | ||
| absl::string_view cluster_name = cluster.cluster().info()->name(); | ||
| if (cluster_map->at(cluster_name) == &cluster) { |
There was a problem hiding this comment.
How come we now make this check? Was this not necessary previously?
There was a problem hiding this comment.
This may need to be an ASSERT
There was a problem hiding this comment.
This code is equivalent to the original: the remove() method of std::list checks if the argument is identical to any element and removes all of them for which the check is true.
As the comment above suggests it's possible that the cluster we are removing has already been initialized and is not present in the map. Without the check we'd remove a wrong cluster: the one updated once again after it had been initialized. There is a test case that tests this: bazel test //test/common/upstream:cluster_manager_impl_test --gtest_filter=*UpdateAlreadyInitialized*. It starts to fail without the check.
There was a problem hiding this comment.
Makes sense, thanks for the explanation!
There was a problem hiding this comment.
@tbarrella if this is crashing can you do a revert PR and we can reapply later?
There was a problem hiding this comment.
I thought the comment was about the case when a cluster gets removed, but another one with the same name still exists.
Anyway I should have checked the code was exception safe. Will submit a new fix shortly with a test checking for removal of an unknown cluster.
|
Initially I used |
…ation (envoyproxy#15237)" This reverts commit b5e47bf. Signed-off-by: Taylor Barrella <tabarr@google.com>
…nvoyproxy#15237) Currently ClusterManagerInitHelper.secondary_init_clusters_ is a list. Upon every insert the list gets searched for an already added cluster with the same name. Since in normal circumstances all new clusters have unique names the worst case scenario is triggered and all elements of the list are checked sequentially upon every cluster added. Replace the list with a hash map. Signed-off-by: Dmitry Rozhkov <dmitry.rozhkov@intel.com>
Commit Message: upstream: avoid quadratic time complexity in server initialization
Additional Description:
Currently ClusterManagerInitHelper.secondary_init_clusters_ is a list. Upon every insert the list gets searched for an already added cluster with the same name. Since in normal circumstances all new clusters have unique names the worst case scenario is triggered and all elements of the list are checked sequentially.
Replace the list with a hash map.
Risk Level: low
Testing: unit tests, manual tests
Docs Changes: N/A
Release Notes: N/A
Platform Specific Features: N/A
Contributes to #12138
For the case of 30k clusters added the difference in
CdsApiImpl::onConfigUpdate()execution time is about 68 sec on i9-7920X.Before
After