Skip to content

[libc++] Optimize __tree::find and __tree::__erase_unique #152370

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Aug 15, 2025
Merged

[libc++] Optimize __tree::find and __tree::__erase_unique #152370

merged 1 commit into from
Aug 15, 2025

Conversation

philnik777
Copy link
Contributor

@philnik777 philnik777 commented Aug 6, 2025 •
edited
Loading

This patch changes __tree::find to return when it has found any equal element instead of the lower bound of the equal elements. For map and set there is no observable difference, since the keys are unique. However for their multi versions this can mean a change in behaviour since it's not longer guaranteed that find will return the first element.

------------------------------------------------------------------------------------------
Benchmark                                                                  old         new
------------------------------------------------------------------------------------------
std::map<int, int>::erase(key) (existent)/0                           24.4 ns      24.9 ns
std::map<int, int>::erase(key) (existent)/32                          39.8 ns      32.1 ns
std::map<int, int>::erase(key) (existent)/1024                        83.8 ns      52.5 ns
std::map<int, int>::erase(key) (existent)/8192                        91.4 ns      66.4 ns
std::map<int, int>::erase(key) (non-existent)/0                      0.511 ns     0.328 ns
std::map<int, int>::erase(key) (non-existent)/32                      9.12 ns      5.62 ns
std::map<int, int>::erase(key) (non-existent)/1024                    26.6 ns      11.3 ns
std::map<int, int>::erase(key) (non-existent)/8192                    37.0 ns      16.9 ns
std::map<int, int>::find(key) (existent)/0                           0.007 ns     0.007 ns
std::map<int, int>::find(key) (existent)/32                           6.02 ns      4.32 ns
std::map<int, int>::find(key) (existent)/1024                         13.6 ns      8.35 ns
std::map<int, int>::find(key) (existent)/8192                         30.3 ns      12.8 ns
std::map<int, int>::find(key) (non-existent)/0                       0.299 ns     0.545 ns
std::map<int, int>::find(key) (non-existent)/32                       8.78 ns      4.60 ns
std::map<int, int>::find(key) (non-existent)/1024                     26.1 ns      21.8 ns
std::map<int, int>::find(key) (non-existent)/8192                     36.2 ns      27.9 ns
std::map<std::string, int>::erase(key) (existent)/0                   74.1 ns      76.7 ns
std::map<std::string, int>::erase(key) (existent)/32                   161 ns       114 ns
std::map<std::string, int>::erase(key) (existent)/1024                 196 ns       126 ns
std::map<std::string, int>::erase(key) (existent)/8192                 207 ns       160 ns
std::map<std::string, int>::erase(key) (non-existent)/0              0.754 ns     0.328 ns
std::map<std::string, int>::erase(key) (non-existent)/32              47.3 ns      40.7 ns
std::map<std::string, int>::erase(key) (non-existent)/1024             122 ns      96.1 ns
std::map<std::string, int>::erase(key) (non-existent)/8192             168 ns       123 ns
std::map<std::string, int>::find(key) (existent)/0                   0.059 ns     0.058 ns
std::map<std::string, int>::find(key) (existent)/32                   54.3 ns      34.6 ns
std::map<std::string, int>::find(key) (existent)/1024                  125 ns      64.5 ns
std::map<std::string, int>::find(key) (existent)/8192                  159 ns      79.2 ns
std::map<std::string, int>::find(key) (non-existent)/0               0.311 ns     0.299 ns
std::map<std::string, int>::find(key) (non-existent)/32               44.0 ns      42.7 ns
std::map<std::string, int>::find(key) (non-existent)/1024              120 ns      92.6 ns
std::map<std::string, int>::find(key) (non-existent)/8192              189 ns       124 ns
std::set<int>::erase(key) (existent)/0                                25.1 ns      25.1 ns
std::set<int>::erase(key) (existent)/32                               42.1 ns      33.1 ns
std::set<int>::erase(key) (existent)/1024                             73.8 ns      55.5 ns
std::set<int>::erase(key) (existent)/8192                              101 ns      68.8 ns
std::set<int>::erase(key) (non-existent)/0                           0.511 ns     0.328 ns
std::set<int>::erase(key) (non-existent)/32                           9.60 ns      4.67 ns
std::set<int>::erase(key) (non-existent)/1024                         26.5 ns      11.2 ns
std::set<int>::erase(key) (non-existent)/8192                         46.2 ns      16.8 ns
std::set<int>::find(key) (existent)/0                                0.008 ns     0.007 ns
std::set<int>::find(key) (existent)/32                                5.87 ns      4.51 ns
std::set<int>::find(key) (existent)/1024                              14.3 ns      8.69 ns
std::set<int>::find(key) (existent)/8192                              30.2 ns      12.8 ns
std::set<int>::find(key) (non-existent)/0                            0.531 ns     0.530 ns
std::set<int>::find(key) (non-existent)/32                            8.77 ns      4.64 ns
std::set<int>::find(key) (non-existent)/1024                          26.1 ns      21.7 ns
std::set<int>::find(key) (non-existent)/8192                          36.3 ns      27.8 ns
std::set<std::string>::erase(key) (existent)/0                        93.2 ns      70.2 ns
std::set<std::string>::erase(key) (existent)/32                        164 ns       116 ns
std::set<std::string>::erase(key) (existent)/1024                      161 ns       136 ns
std::set<std::string>::erase(key) (existent)/8192                      231 ns       140 ns
std::set<std::string>::erase(key) (non-existent)/0                   0.532 ns     0.326 ns
std::set<std::string>::erase(key) (non-existent)/32                   43.4 ns      40.1 ns
std::set<std::string>::erase(key) (non-existent)/1024                  122 ns      99.5 ns
std::set<std::string>::erase(key) (non-existent)/8192                  168 ns       125 ns
std::set<std::string>::find(key) (existent)/0                        0.059 ns     0.059 ns
std::set<std::string>::find(key) (existent)/32                        53.1 ns      35.5 ns
std::set<std::string>::find(key) (existent)/1024                       124 ns      61.2 ns
std::set<std::string>::find(key) (existent)/8192                       154 ns      73.9 ns
std::set<std::string>::find(key) (non-existent)/0                    0.532 ns     0.301 ns
std::set<std::string>::find(key) (non-existent)/32                    44.4 ns      39.5 ns
std::set<std::string>::find(key) (non-existent)/1024                   120 ns      95.5 ns
std::set<std::string>::find(key) (non-existent)/8192                   193 ns       119 ns
std::multimap<int, int>::erase(key) (existent)/0                       26.5 ns     26.6 ns
std::multimap<int, int>::erase(key) (existent)/32                      33.5 ns     32.9 ns
std::multimap<int, int>::erase(key) (existent)/1024                    55.5 ns     58.0 ns
std::multimap<int, int>::erase(key) (existent)/8192                    67.4 ns     70.0 ns
std::multimap<int, int>::erase(key) (non-existent)/0                  0.523 ns    0.532 ns
std::multimap<int, int>::erase(key) (non-existent)/32                  5.08 ns     5.09 ns
std::multimap<int, int>::erase(key) (non-existent)/1024                13.0 ns     12.9 ns
std::multimap<int, int>::erase(key) (non-existent)/8192                19.6 ns     19.8 ns
std::multimap<int, int>::find(key) (existent)/0                       0.015 ns    0.037 ns
std::multimap<int, int>::find(key) (existent)/32                       7.07 ns     3.85 ns
std::multimap<int, int>::find(key) (existent)/1024                     22.0 ns     7.44 ns
std::multimap<int, int>::find(key) (existent)/8192                     37.6 ns     12.0 ns
std::multimap<int, int>::find(key) (non-existent)/0                   0.297 ns    0.305 ns
std::multimap<int, int>::find(key) (non-existent)/32                   8.79 ns     4.59 ns
std::multimap<int, int>::find(key) (non-existent)/1024                 26.0 ns     11.2 ns
std::multimap<int, int>::find(key) (non-existent)/8192                 36.4 ns     16.8 ns
std::multimap<std::string, int>::erase(key) (existent)/0               93.4 ns     84.5 ns
std::multimap<std::string, int>::erase(key) (existent)/32               101 ns      101 ns
std::multimap<std::string, int>::erase(key) (existent)/1024             118 ns      126 ns
std::multimap<std::string, int>::erase(key) (existent)/8192             108 ns      124 ns
std::multimap<std::string, int>::erase(key) (non-existent)/0           2.39 ns     2.43 ns
std::multimap<std::string, int>::erase(key) (non-existent)/32          44.4 ns     49.7 ns
std::multimap<std::string, int>::erase(key) (non-existent)/1024         108 ns      103 ns
std::multimap<std::string, int>::erase(key) (non-existent)/8192         140 ns      125 ns
std::multimap<std::string, int>::find(key) (existent)/0               0.059 ns    0.058 ns
std::multimap<std::string, int>::find(key) (existent)/32               52.3 ns     32.6 ns
std::multimap<std::string, int>::find(key) (existent)/1024              122 ns     58.9 ns
std::multimap<std::string, int>::find(key) (existent)/8192              160 ns     72.7 ns
std::multimap<std::string, int>::find(key) (non-existent)/0           0.524 ns    0.494 ns
std::multimap<std::string, int>::find(key) (non-existent)/32           43.8 ns     38.9 ns
std::multimap<std::string, int>::find(key) (non-existent)/1024          123 ns     90.8 ns
std::multimap<std::string, int>::find(key) (non-existent)/8192          190 ns      126 ns
std::multiset<int>::erase(key) (existent)/0                            27.1 ns     26.8 ns
std::multiset<int>::erase(key) (existent)/32                           33.3 ns     34.1 ns
std::multiset<int>::erase(key) (existent)/1024                         58.5 ns     58.8 ns
std::multiset<int>::erase(key) (existent)/8192                         66.7 ns     64.1 ns
std::multiset<int>::erase(key) (non-existent)/0                       0.318 ns    0.325 ns
std::multiset<int>::erase(key) (non-existent)/32                       5.15 ns     5.25 ns
std::multiset<int>::erase(key) (non-existent)/1024                     12.9 ns     12.7 ns
std::multiset<int>::erase(key) (non-existent)/8192                     20.3 ns     20.3 ns
std::multiset<int>::find(key) (existent)/0                            0.043 ns    0.015 ns
std::multiset<int>::find(key) (existent)/32                            6.94 ns     4.22 ns
std::multiset<int>::find(key) (existent)/1024                          21.4 ns     8.23 ns
std::multiset<int>::find(key) (existent)/8192                          37.4 ns     12.6 ns
std::multiset<int>::find(key) (non-existent)/0                        0.515 ns    0.300 ns
std::multiset<int>::find(key) (non-existent)/32                        8.52 ns     4.62 ns
std::multiset<int>::find(key) (non-existent)/1024                      25.5 ns     11.3 ns
std::multiset<int>::find(key) (non-existent)/8192                      36.5 ns     27.0 ns
std::multiset<std::string>::erase(key) (existent)/0                    81.9 ns     77.5 ns
std::multiset<std::string>::erase(key) (existent)/32                    113 ns      129 ns
std::multiset<std::string>::erase(key) (existent)/1024                  132 ns      148 ns
std::multiset<std::string>::erase(key) (existent)/8192                  114 ns      165 ns
std::multiset<std::string>::erase(key) (non-existent)/0                2.33 ns     2.32 ns
std::multiset<std::string>::erase(key) (non-existent)/32               44.4 ns     42.0 ns
std::multiset<std::string>::erase(key) (non-existent)/1024             97.3 ns     95.1 ns
std::multiset<std::string>::erase(key) (non-existent)/8192              132 ns      123 ns
std::multiset<std::string>::find(key) (existent)/0                    0.058 ns    0.059 ns
std::multiset<std::string>::find(key) (existent)/32                    48.3 ns     34.4 ns
std::multiset<std::string>::find(key) (existent)/1024                   121 ns     61.9 ns
std::multiset<std::string>::find(key) (existent)/8192                   155 ns     77.7 ns
std::multiset<std::string>::find(key) (non-existent)/0                0.524 ns    0.306 ns
std::multiset<std::string>::find(key) (non-existent)/32                44.1 ns     40.4 ns
std::multiset<std::string>::find(key) (non-existent)/1024               121 ns     96.3 ns
std::multiset<std::string>::find(key) (non-existent)/8192               193 ns      121 ns

@philnik777 philnik777 marked this pull request as ready for review August 11, 2025 19:52
@philnik777 philnik777 requested a review from a team as a code owner August 11, 2025 19:52
@llvmbot llvmbot added the libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. label Aug 11, 2025
@llvmbot
Copy link
Member

llvmbot commented Aug 11, 2025

@llvm/pr-subscribers-libcxx

Author: Nikolas Klauser (philnik777)

Changes 
-----------------------------------------------------------------------------------
Benchmark                                                          old          new
-----------------------------------------------------------------------------------
std::map&lt;int, int&gt;::erase(key) (existent)/0                    24.6 ns      24.5 ns
std::map&lt;int, int&gt;::erase(key) (existent)/32                   42.6 ns      31.5 ns
std::map&lt;int, int&gt;::erase(key) (existent)/1024                 68.7 ns      53.2 ns
std::map&lt;int, int&gt;::erase(key) (existent)/8192                 88.7 ns      60.0 ns
std::map&lt;int, int&gt;::erase(key) (non-existent)/0               0.321 ns     0.318 ns
std::map&lt;int, int&gt;::erase(key) (non-existent)/32               8.89 ns      4.63 ns
std::map&lt;int, int&gt;::erase(key) (non-existent)/1024             26.3 ns      11.2 ns
std::map&lt;int, int&gt;::erase(key) (non-existent)/8192             36.1 ns      16.7 ns
std::map&lt;std::string, int&gt;::erase(key) (existent)/0            76.9 ns      89.8 ns
std::map&lt;std::string, int&gt;::erase(key) (existent)/32            167 ns      94.1 ns
std::map&lt;std::string, int&gt;::erase(key) (existent)/1024          198 ns       100 ns
std::map&lt;std::string, int&gt;::erase(key) (existent)/8192          236 ns       157 ns
std::map&lt;std::string, int&gt;::erase(key) (non-existent)/0       0.749 ns     0.310 ns
std::map&lt;std::string, int&gt;::erase(key) (non-existent)/32       43.0 ns      41.2 ns
std::map&lt;std::string, int&gt;::erase(key) (non-existent)/1024      119 ns      96.4 ns
std::map&lt;std::string, int&gt;::erase(key) (non-existent)/8192      189 ns       135 ns

Full diff: https://github.com/llvm/llvm-project/pull/152370.diff

1 Files Affected:

  • (modified) libcxx/include/__tree (+4-3)
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 6ca1a623536f2..1a3d4afa2d8fc 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -2062,10 +2062,11 @@ template <class _Tp, class _Compare, class _Allocator>
 template <class _Key>
 typename __tree<_Tp, _Compare, _Allocator>::size_type
 __tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k) {
-  iterator __i = find(__k);
-  if (__i == end())
+  __end_node_pointer __parent;
+  __node_base_pointer __i = __find_equal(__parent, __k);
+  if (__i == nullptr)
     return 0;
-  erase(__i);
+  erase(iterator(static_cast<__node_pointer>(__i)));
   return 1;
 }

ldionne
ldionne reviewed Aug 11, 2025
View reviewed changes
@philnik777 philnik777 force-pushed the tree_optimize_erase branch 2 times, most recently from 03855dd to e774294 Compare August 12, 2025 08:30
@philnik777 philnik777 changed the title [libc++] Optimize __tree::__erase_unique [libc++] Optimize __tree::find and __tree::__erase_unique Aug 12, 2025
ldionne
ldionne requested changes Aug 12, 2025
View reviewed changes
@philnik777 philnik777 force-pushed the tree_optimize_erase branch from e774294 to 1995180 Compare August 13, 2025 10:17
ldionne
ldionne approved these changes Aug 13, 2025
View reviewed changes
Copy link
Member

@ldionne ldionne left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM with small comments

@philnik777 philnik777 force-pushed the tree_optimize_erase branch from 1995180 to fc6edb7 Compare August 14, 2025 07:14
@philnik777 philnik777 force-pushed the tree_optimize_erase branch from fc6edb7 to 34e9a72 Compare August 15, 2025 06:59
@philnik777 philnik777 merged commit d9bc548 into llvm:main Aug 15, 2025
13 of 16 checks passed
@philnik777 philnik777 deleted the tree_optimize_erase branch August 15, 2025 06:59
@nico
Copy link
Contributor

nico commented Aug 22, 2025

However for their multi versions this can mean a change in behaviour since it's not longer guaranteed that find will return the first element.

Should that go in the release notes as well?

@nico
Copy link
Contributor

nico commented Aug 25, 2025

We have this function that tries to find all bookmark nodes with a given URL:

std::vector<BookmarkNode*> BookmarkModel::GetNodesByURL(GURL url) {
  std::vector<BookmarkNode*> nodes;
  auto i = nodes_ordered_by_url_set_.find<GURL>(url);
  while (i != nodes_ordered_by_url_set_.end() && (*i)->url() == url) {
    nodes.push_back(*i);
    ++i;
  }
  return nodes;
}

nodes_ordered_by_url_set_ looks like so:

  // Used to order BookmarkNodes by URL as well as lookups using GURL.
  class NodeUrlComparator {
   public:
    // Required by std::set to support GURL-based lookups.
    using is_transparent = void;

    bool operator()(const BookmarkNode* n1, const BookmarkNode* n2) const {
      return n1->url() < n2->url();
    }
    bool operator()(const BookmarkNode* n1, const GURL& url2) const {
      return n1->url() < url2;
    }
    bool operator()(const GURL& url1, const BookmarkNode* n2) const {
      return url1 < n2->url();
    }
  };

  using NodesOrderedByUrlSet = std::multiset<BookmarkNode*, NodeUrlComparator>;
  NodesOrderedByUrlSet nodes_ordered_by_url_set_;

The whole thing as a standalone repro (the .sh is meant to run on a mac; needs minor tweaks to run on linux):
repro.zip This includes a single standalone .cc file that prints count: 2 without this commit but count: 1 with it. It also includes a .sh script to compile libc++ and link the included .cc file against the just-built libc++. You probably have a local script for the latter part that you like better :)

From what I understand, our code is incorrect, and we should use e.g. equal_range() instead. I'm only mentioning this here in case other folks run into it.

(But, see question in the comment above please :))

@philnik777
Copy link
Contributor Author

However for their multi versions this can mean a change in behaviour since it's not longer guaranteed that find will return the first element.

Should that go in the release notes as well?

Yes, this should probably be release noted. I'll make a patch.

We have this function that tries to find all bookmark nodes with a given URL:

std::vector<BookmarkNode*> BookmarkModel::GetNodesByURL(GURL url) {
  std::vector<BookmarkNode*> nodes;
  auto i = nodes_ordered_by_url_set_.find<GURL>(url);
  while (i != nodes_ordered_by_url_set_.end() && (*i)->url() == url) {
    nodes.push_back(*i);
    ++i;
  }
  return nodes;
}

nodes_ordered_by_url_set_ looks like so:

  // Used to order BookmarkNodes by URL as well as lookups using GURL.
  class NodeUrlComparator {
   public:
    // Required by std::set to support GURL-based lookups.
    using is_transparent = void;

    bool operator()(const BookmarkNode* n1, const BookmarkNode* n2) const {
      return n1->url() < n2->url();
    }
    bool operator()(const BookmarkNode* n1, const GURL& url2) const {
      return n1->url() < url2;
    }
    bool operator()(const GURL& url1, const BookmarkNode* n2) const {
      return url1 < n2->url();
    }
  };

  using NodesOrderedByUrlSet = std::multiset<BookmarkNode*, NodeUrlComparator>;
  NodesOrderedByUrlSet nodes_ordered_by_url_set_;

The whole thing as a standalone repro (the .sh is meant to run on a mac; needs minor tweaks to run on linux): repro.zip This includes a single standalone .cc file that prints count: 2 without this commit but count: 1 with it. It also includes a .sh script to compile libc++ and link the included .cc file against the just-built libc++. You probably have a local script for the latter part that you like better :)

From what I understand, our code is incorrect, and we should use e.g. equal_range() instead. I'm only mentioning this here in case other folks run into it.

(But, see question in the comment above please :))

Yeah, this looks incorrect to me. You want to either use lower_bound() to get the first element, or equal_range() so you can simply iterate through the equal elements.

@philnik777 philnik777 mentioned this pull request Aug 25, 2025
Merged
philnik777 added a commit that referenced this pull request Aug 26, 2025
@philnik777
[libc++] Add a release note about multi{map,set}::find not returning …
62da805 
…the first element anymore (#155252)

We've modified the algorithm of `__tree::find` in #152370, which can
change the return value. Since we're always returned the lower bound
before some users started relying on it. This patch adds a release note
so users are aware that this might break their code.
@aemerson aemerson mentioned this pull request Aug 30, 2025
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@ldionne ldionne ldionne approved these changes

Assignees

@philnik777 philnik777

Labels
libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. performance
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
4 participants
@philnik777 @llvmbot @nico @ldionne