| commit | d9bc548facf3929b45a68d0d8ae44778afe66d8f | [log] [tgz] |
|---|---|---|
| author | Nikolas Klauser <nikolasklauser@berlin.de> | Fri Aug 15 08:59:39 2025 +0200 |
| committer | GitHub <noreply@github.com> | Fri Aug 15 08:59:39 2025 +0200 |
| tree | e3820ce8b5506a65a5b4857038148338a3b286d0 | |
| parent | cbbf303ff51b61315f82b0f87bb52db2bedf2b78 [diff] |
[libc++] Optimize __tree::find and __tree::__erase_unique (#152370) 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 ```
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.