[libc++] Optimize {map,set}::insert(InputIterator, InputIterator) (#154703)
```
----------------------------------------------------------------------------------------------------------------------------
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
Welcome to the LLVM project!
This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.
C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.
Other components include: the libc++ C++ standard library, the LLD linker, and more.
Consult the Getting Started with LLVM page for information on building and running LLVM.
For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.
Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.
The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.