Skip to content

[libc++] Optimize {map,set}::insert(InputIterator, InputIterator) #154703

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
Open
wants to merge 1 commit into
base: main
Choose a base branch
from
Open

[libc++] Optimize {map,set}::insert(InputIterator, InputIterator) #154703

wants to merge 1 commit into from
+402 −93

Conversation

philnik777
Copy link
Contributor

@philnik777 philnik777 commented Aug 21, 2025 •
edited
Loading 

----------------------------------------------------------------------------------------------------------------------------
Benchmark                                                                                                old             new
----------------------------------------------------------------------------------------------------------------------------
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/0                                   14.2 ns         14.8 ns
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/32                                   519 ns          404 ns
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/1024                               52460 ns        36242 ns
std::map<int, int>::ctor(iterator, iterator) (unsorted sequence)/8192                              724222 ns       706496 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/0                                     14.2 ns         14.7 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/32                                     429 ns          349 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/1024                                 23601 ns        14734 ns
std::map<int, int>::ctor(iterator, iterator) (sorted sequence)/8192                                267753 ns       112155 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/0                                       434 ns          448 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/32                                      950 ns          963 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/1024                                  27205 ns        25344 ns
std::map<int, int>::insert(iterator, iterator) (all new keys)/8192                                 294248 ns       280713 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/0                                      435 ns          449 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/32                                     771 ns          706 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/1024                                 30841 ns        17495 ns
std::map<int, int>::insert(iterator, iterator) (half new keys)/8192                                468807 ns       285847 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/0                    449 ns          453 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/32                  1021 ns          932 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/1024               29796 ns        19518 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from same type)/8192              345688 ns       153966 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/0                     449 ns          450 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/32                   1026 ns          807 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024                31632 ns        15573 ns
std::map<int, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192               303024 ns       128946 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/0                            447 ns          452 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/32                           687 ns          710 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/1024                        8604 ns         8581 ns
std::map<int, int>::erase(iterator, iterator) (erase half the container)/8192                       65693 ns        67406 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/0                           15.0 ns         15.0 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/32                          2781 ns         1845 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/1024                      187999 ns       182103 ns
std::map<std::string, int>::ctor(iterator, iterator) (unsorted sequence)/8192                     2937242 ns      2934912 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/0                             15.0 ns         15.2 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/32                            1326 ns         2462 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/1024                         81778 ns        72193 ns
std::map<std::string, int>::ctor(iterator, iterator) (sorted sequence)/8192                       1177292 ns       669152 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/0                               439 ns          454 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/32                             2483 ns         2465 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/1024                         187614 ns       188072 ns
std::map<std::string, int>::insert(iterator, iterator) (all new keys)/8192                        1654675 ns      1706603 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/0                              437 ns          452 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/32                            1836 ns         1820 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/1024                        114885 ns       121865 ns
std::map<std::string, int>::insert(iterator, iterator) (half new keys)/8192                       1151960 ns      1197318 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/0            438 ns          455 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/32          1599 ns         1614 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/1024       95935 ns        82159 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from same type)/8192      776480 ns       941043 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/0             435 ns          462 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/32           1723 ns         1550 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/1024       107096 ns        92850 ns
std::map<std::string, int>::insert(iterator, iterator) (product_iterator from zip_view)/8192       893976 ns       775046 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/0                    436 ns          453 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/32                   775 ns          824 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/1024               20241 ns        20454 ns
std::map<std::string, int>::erase(iterator, iterator) (erase half the container)/8192              139038 ns       138032 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/0                                        14.8 ns         14.7 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/32                                        468 ns          426 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/1024                                    54289 ns        39028 ns
std::set<int>::ctor(iterator, iterator) (unsorted sequence)/8192                                   738438 ns       695720 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/0                                          14.7 ns         14.6 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/32                                          478 ns          391 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/1024                                      24017 ns        13905 ns
std::set<int>::ctor(iterator, iterator) (sorted sequence)/8192                                     267862 ns       111378 ns
std::set<int>::insert(iterator, iterator) (all new keys)/0                                            458 ns          450 ns
std::set<int>::insert(iterator, iterator) (all new keys)/32                                          1066 ns          956 ns
std::set<int>::insert(iterator, iterator) (all new keys)/1024                                       29190 ns        25212 ns
std::set<int>::insert(iterator, iterator) (all new keys)/8192                                      320441 ns       279602 ns
std::set<int>::insert(iterator, iterator) (half new keys)/0                                           454 ns          453 ns
std::set<int>::insert(iterator, iterator) (half new keys)/32                                          816 ns          709 ns
std::set<int>::insert(iterator, iterator) (half new keys)/1024                                      32072 ns        17074 ns
std::set<int>::insert(iterator, iterator) (half new keys)/8192                                     403386 ns       286202 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/0                                 451 ns          452 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/32                                710 ns          703 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/1024                             8261 ns         8499 ns
std::set<int>::erase(iterator, iterator) (erase half the container)/8192                            64466 ns        67343 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/0                                15.2 ns         15.0 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/32                               3069 ns         3005 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/1024                           189552 ns       180933 ns
std::set<std::string>::ctor(iterator, iterator) (unsorted sequence)/8192                          2887579 ns      2691678 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/0                                  15.1 ns         14.9 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/32                                 2611 ns         2514 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/1024                              91581 ns        78727 ns
std::set<std::string>::ctor(iterator, iterator) (sorted sequence)/8192                            1192640 ns      1158959 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/0                                    452 ns          457 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/32                                  2530 ns         2544 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/1024                              195352 ns       179614 ns
std::set<std::string>::insert(iterator, iterator) (all new keys)/8192                             1737890 ns      1749615 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/0                                   451 ns          454 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/32                                 1949 ns         1766 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/1024                             128853 ns       109467 ns
std::set<std::string>::insert(iterator, iterator) (half new keys)/8192                            1233077 ns      1177289 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/0                         450 ns          451 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/32                        809 ns          812 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/1024                    21736 ns        21922 ns
std::set<std::string>::erase(iterator, iterator) (erase half the container)/8192                   135884 ns       133228 ns

Fixes #154650

@philnik777 philnik777 changed the title optimize tree insert range unique [libc++] Optimize {map,set}::insert(InputIterator, InputIterator) Aug 21, 2025
@philnik777 philnik777 force-pushed the optimize_tree_insert_range_unique branch 2 times, most recently from 3b15ab7 to 7813206 Compare August 27, 2025 12:43
@ldionne ldionne marked this pull request as ready for review August 27, 2025 13:43
@ldionne ldionne requested a review from a team as a code owner August 27, 2025 13:43
@llvmbot llvmbot added the libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. label Aug 27, 2025
@llvmbot
Copy link
Member

llvmbot commented Aug 27, 2025

@llvm/pr-subscribers-libcxx

Author: Nikolas Klauser (philnik777)

Changes 
----------------------------------------------------------------------------------------------------------------------------
Benchmark                                                                                                old             new
----------------------------------------------------------------------------------------------------------------------------
std::map&lt;int, int&gt;::ctor(iterator, iterator) (unsorted sequence)/0                                   14.2 ns         14.8 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (unsorted sequence)/32                                   519 ns          404 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (unsorted sequence)/1024                               52460 ns        36242 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (unsorted sequence)/8192                              724222 ns       706496 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (sorted sequence)/0                                     14.2 ns         14.7 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (sorted sequence)/32                                     429 ns          349 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (sorted sequence)/1024                                 23601 ns        14734 ns
std::map&lt;int, int&gt;::ctor(iterator, iterator) (sorted sequence)/8192                                267753 ns       112155 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (all new keys)/0                                       434 ns          448 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (all new keys)/32                                      950 ns          963 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (all new keys)/1024                                  27205 ns        25344 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (all new keys)/8192                                 294248 ns       280713 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (half new keys)/0                                      435 ns          449 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (half new keys)/32                                     771 ns          706 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (half new keys)/1024                                 30841 ns        17495 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (half new keys)/8192                                468807 ns       285847 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from same type)/0                    449 ns          453 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from same type)/32                  1021 ns          932 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from same type)/1024               29796 ns        19518 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from same type)/8192              345688 ns       153966 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/0                     449 ns          450 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/32                   1026 ns          807 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/1024                31632 ns        15573 ns
std::map&lt;int, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/8192               303024 ns       128946 ns
std::map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/0                            447 ns          452 ns
std::map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/32                           687 ns          710 ns
std::map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/1024                        8604 ns         8581 ns
std::map&lt;int, int&gt;::erase(iterator, iterator) (erase half the container)/8192                       65693 ns        67406 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (unsorted sequence)/0                           15.0 ns         15.0 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (unsorted sequence)/32                          2781 ns         1845 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (unsorted sequence)/1024                      187999 ns       182103 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (unsorted sequence)/8192                     2937242 ns      2934912 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (sorted sequence)/0                             15.0 ns         15.2 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (sorted sequence)/32                            1326 ns         2462 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (sorted sequence)/1024                         81778 ns        72193 ns
std::map&lt;std::string, int&gt;::ctor(iterator, iterator) (sorted sequence)/8192                       1177292 ns       669152 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (all new keys)/0                               439 ns          454 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (all new keys)/32                             2483 ns         2465 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (all new keys)/1024                         187614 ns       188072 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (all new keys)/8192                        1654675 ns      1706603 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (half new keys)/0                              437 ns          452 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (half new keys)/32                            1836 ns         1820 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (half new keys)/1024                        114885 ns       121865 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (half new keys)/8192                       1151960 ns      1197318 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from same type)/0            438 ns          455 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from same type)/32          1599 ns         1614 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from same type)/1024       95935 ns        82159 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from same type)/8192      776480 ns       941043 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/0             435 ns          462 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/32           1723 ns         1550 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/1024       107096 ns        92850 ns
std::map&lt;std::string, int&gt;::insert(iterator, iterator) (product_iterator from zip_view)/8192       893976 ns       775046 ns
std::map&lt;std::string, int&gt;::erase(iterator, iterator) (erase half the container)/0                    436 ns          453 ns
std::map&lt;std::string, int&gt;::erase(iterator, iterator) (erase half the container)/32                   775 ns          824 ns
std::map&lt;std::string, int&gt;::erase(iterator, iterator) (erase half the container)/1024               20241 ns        20454 ns
std::map&lt;std::string, int&gt;::erase(iterator, iterator) (erase half the container)/8192              139038 ns       138032 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (unsorted sequence)/0                                        14.8 ns         14.7 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (unsorted sequence)/32                                        468 ns          426 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (unsorted sequence)/1024                                    54289 ns        39028 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (unsorted sequence)/8192                                   738438 ns       695720 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (sorted sequence)/0                                          14.7 ns         14.6 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (sorted sequence)/32                                          478 ns          391 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (sorted sequence)/1024                                      24017 ns        13905 ns
std::set&lt;int&gt;::ctor(iterator, iterator) (sorted sequence)/8192                                     267862 ns       111378 ns
std::set&lt;int&gt;::insert(iterator, iterator) (all new keys)/0                                            458 ns          450 ns
std::set&lt;int&gt;::insert(iterator, iterator) (all new keys)/32                                          1066 ns          956 ns
std::set&lt;int&gt;::insert(iterator, iterator) (all new keys)/1024                                       29190 ns        25212 ns
std::set&lt;int&gt;::insert(iterator, iterator) (all new keys)/8192                                      320441 ns       279602 ns
std::set&lt;int&gt;::insert(iterator, iterator) (half new keys)/0                                           454 ns          453 ns
std::set&lt;int&gt;::insert(iterator, iterator) (half new keys)/32                                          816 ns          709 ns
std::set&lt;int&gt;::insert(iterator, iterator) (half new keys)/1024                                      32072 ns        17074 ns
std::set&lt;int&gt;::insert(iterator, iterator) (half new keys)/8192                                     403386 ns       286202 ns
std::set&lt;int&gt;::erase(iterator, iterator) (erase half the container)/0                                 451 ns          452 ns
std::set&lt;int&gt;::erase(iterator, iterator) (erase half the container)/32                                710 ns          703 ns
std::set&lt;int&gt;::erase(iterator, iterator) (erase half the container)/1024                             8261 ns         8499 ns
std::set&lt;int&gt;::erase(iterator, iterator) (erase half the container)/8192                            64466 ns        67343 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (unsorted sequence)/0                                15.2 ns         15.0 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (unsorted sequence)/32                               3069 ns         3005 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (unsorted sequence)/1024                           189552 ns       180933 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (unsorted sequence)/8192                          2887579 ns      2691678 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (sorted sequence)/0                                  15.1 ns         14.9 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (sorted sequence)/32                                 2611 ns         2514 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (sorted sequence)/1024                              91581 ns        78727 ns
std::set&lt;std::string&gt;::ctor(iterator, iterator) (sorted sequence)/8192                            1192640 ns      1158959 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (all new keys)/0                                    452 ns          457 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (all new keys)/32                                  2530 ns         2544 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (all new keys)/1024                              195352 ns       179614 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (all new keys)/8192                             1737890 ns      1749615 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (half new keys)/0                                   451 ns          454 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (half new keys)/32                                 1949 ns         1766 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (half new keys)/1024                             128853 ns       109467 ns
std::set&lt;std::string&gt;::insert(iterator, iterator) (half new keys)/8192                            1233077 ns      1177289 ns
std::set&lt;std::string&gt;::erase(iterator, iterator) (erase half the container)/0                         450 ns          451 ns
std::set&lt;std::string&gt;::erase(iterator, iterator) (erase half the container)/32                        809 ns          812 ns
std::set&lt;std::string&gt;::erase(iterator, iterator) (erase half the container)/1024                    21736 ns        21922 ns
std::set&lt;std::string&gt;::erase(iterator, iterator) (erase half the container)/8192                   135884 ns       133228 ns

Fixes #154650

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

4 Files Affected:

  • (modified) libcxx/docs/ReleaseNotes/22.rst (+3-2)
  • (modified) libcxx/include/__tree (+52)
  • (modified) libcxx/include/map (+3-7)
  • (modified) libcxx/include/set (+3-7)
diff --git a/libcxx/docs/ReleaseNotes/22.rst b/libcxx/docs/ReleaseNotes/22.rst
index 5378655c66606..0f2cf1073bb38 100644
--- a/libcxx/docs/ReleaseNotes/22.rst
+++ b/libcxx/docs/ReleaseNotes/22.rst
@@ -53,9 +53,10 @@ Improvements and New Features
 - The performance of ``find(key)`` in ``map``, ``set``, ``multimap`` and ``multiset`` has been improved by up to 2.3x
 - Some reallocations are now avoided in `std::filesystem::path::lexically_relative`, resulting in a performance
   improvement of up to 1.7x.
-- The performance of the ``(iterator, iterator)`` constructors of ``multimap`` and ``multiset``
+- The performance of the ``(iterator, iterator)`` constructors of ``map``, ``set``, ``multimap`` and ``multiset``
   has been improved by up to 3x
-- The performance of ``insert(iterator, iterator)`` of ``multimap`` and ``multiset`` has been improved by up to 2.5x
+- The performance of ``insert(iterator, iterator)`` of ``map``, ``set``, ``multimap`` and ``multiset`` has been improved
+  by up to 2.5x
 - The performance of ``erase(iterator, iterator)`` in the unordered containers has been improved by up to 1.9x
 
 Deprecations and Removals
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 3ad2129ba9ddf..0ab79e1404afa 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -1025,6 +1025,58 @@ public:
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(__node_pointer __nd);
   _LIBCPP_HIDE_FROM_ABI iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
+  template <class _InIter, class _Sent>
+  _LIBCPP_HIDE_FROM_ABI void __insert_range_unique(_InIter __first, _Sent __last) {
+    if (__first == __last)
+      return;
+
+    if (__root() == nullptr) {
+      __insert_node_at(
+          __end_node(), __end_node()->__left_, static_cast<__node_base_pointer>(__construct_node(*__first).release()));
+      ++__first;
+    }
+
+    auto __max_node = static_cast<__node_pointer>(std::__tree_max(static_cast<__node_base_pointer>(__root())));
+
+    using __reference = decltype(*__first);
+
+    for (; __first != __last; ++__first) {
+      std::__try_key_extraction<key_type>(
+          [this, &__max_node](const key_type& __key, __reference&& __val) {
+            if (value_comp()(__max_node->__get_value(), __key)) { // __key > __max_node
+              __node_holder __nd = __construct_node(std::forward<__reference>(__val));
+              __insert_node_at(static_cast<__end_node_pointer>(__max_node),
+                               __max_node->__right_,
+                               static_cast<__node_base_pointer>(__nd.get()));
+              __max_node = __nd.release();
+            } else {
+              __end_node_pointer __parent;
+              __node_base_pointer& __child = __find_equal(__parent, __key);
+              if (__child == nullptr) {
+                __node_holder __nd = __construct_node(std::forward<__reference>(__val));
+                __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release()));
+              }
+            }
+          },
+          [this, &__max_node](__reference&& __val) {
+            __node_holder __nd = __construct_node(std::forward<__reference>(__val));
+            if (value_comp()(__max_node->__get_value(), __nd->__get_value())) { // __node > __max_node
+              __insert_node_at(static_cast<__end_node_pointer>(__max_node),
+                               __max_node->__right_,
+                               static_cast<__node_base_pointer>(__nd.get()));
+              __max_node = __nd.release();
+            } else {
+              __end_node_pointer __parent;
+              __node_base_pointer& __child = __find_equal(__parent, __nd->__get_value());
+              if (__child == nullptr) {
+                __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd.release()));
+              }
+            }
+          },
+          *__first);
+    }
+  }
+
   _LIBCPP_HIDE_FROM_ABI iterator __remove_node_pointer(__node_pointer) _NOEXCEPT;
 
 #if _LIBCPP_STD_VER >= 17
diff --git a/libcxx/include/map b/libcxx/include/map
index b53e1c4213487..8ba7719450f66 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -1089,18 +1089,14 @@ public:
 #  endif
 
   template <class _InputIterator>
-  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
-    for (const_iterator __e = cend(); __f != __l; ++__f)
-      insert(__e.__i_, *__f);
+  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {
+    __tree_.__insert_range_unique(__first, __last);
   }
 
 #  if _LIBCPP_STD_VER >= 23
   template <_ContainerCompatibleRange<value_type> _Range>
   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
-    const_iterator __end = cend();
-    for (auto&& __element : __range) {
-      insert(__end.__i_, std::forward<decltype(__element)>(__element));
-    }
+    __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range));
   }
 #  endif
 
diff --git a/libcxx/include/set b/libcxx/include/set
index b444e8357052a..6470894517fd8 100644
--- a/libcxx/include/set
+++ b/libcxx/include/set
@@ -742,18 +742,14 @@ public:
   }
 
   template <class _InputIterator>
-  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
-    for (const_iterator __e = cend(); __f != __l; ++__f)
-      __tree_.__emplace_hint_unique(__e, *__f);
+  _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {
+    __tree_.__insert_range_unique(__first, __last);
   }
 
 #  if _LIBCPP_STD_VER >= 23
   template <_ContainerCompatibleRange<value_type> _Range>
   _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
-    const_iterator __end = cend();
-    for (auto&& __element : __range) {
-      __tree_.__emplace_hint_unique(__end, std::forward<decltype(__element)>(__element));
-    }
+    __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range));
   }
 #  endif

ldionne
ldionne reviewed Aug 27, 2025
View reviewed changes
ldionne
ldionne reviewed Aug 28, 2025
View reviewed changes
@philnik777 philnik777 force-pushed the optimize_tree_insert_range_unique branch from 7813206 to 472f84e Compare August 29, 2025 08:45
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@ldionne ldionne ldionne left review comments

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

Successfully merging this pull request may close these issues.

[libc++] Optimize std::{map,set}::insert(Iterator, Iterator)
3 participants
@philnik777 @llvmbot @ldionne