llvm-project

Author	SHA1	Message	Date
Timothy Choi	d282452e4c	[libc++] Avoid string reallocation in `std::filesystem::path::lexically_relative` (#152964 ) Improves runtime by around 20 to 40%. (1.3x to 1.7x) ``` Benchmark Time CPU Time Old Time New CPU Old CPU New ------------------------------------------------------------------------------------------------------------------------------------------------ BM_LexicallyRelative/small_path/2 -0.2111 -0.2082 229 181 228 180 BM_LexicallyRelative/small_path/4 -0.2579 -0.2550 455 338 452 337 BM_LexicallyRelative/small_path/8 -0.2643 -0.2616 844 621 838 619 BM_LexicallyRelative/small_path/16 -0.2582 -0.2556 1562 1158 1551 1155 BM_LexicallyRelative/small_path/32 -0.2518 -0.2496 3023 2262 3004 2254 BM_LexicallyRelative/small_path/64 -0.2806 -0.2775 6344 4564 6295 4549 BM_LexicallyRelative/small_path/128 -0.2165 -0.2137 11762 9216 11683 9186 BM_LexicallyRelative/small_path/256 -0.2672 -0.2645 24499 17953 24324 17891 BM_LexicallyRelative/large_path/2 -0.3268 -0.3236 426 287 422 285 BM_LexicallyRelative/large_path/4 -0.3274 -0.3248 734 494 729 492 BM_LexicallyRelative/large_path/8 -0.3586 -0.3560 1409 904 1399 901 BM_LexicallyRelative/large_path/16 -0.3978 -0.3951 2764 1665 2743 1659 BM_LexicallyRelative/large_path/32 -0.3934 -0.3908 5323 3229 5283 3218 BM_LexicallyRelative/large_path/64 -0.3629 -0.3605 10340 6587 10265 6564 BM_LexicallyRelative/large_path/128 -0.3450 -0.3423 19379 12694 19233 12649 BM_LexicallyRelative/large_path/256 -0.3097 -0.3054 36293 25052 35943 24965 ``` --------- Co-authored-by: Nikolas Klauser <nikolasklauser@berlin.de>	2025-08-20 16:58:21 +02:00
William Tran-Viet	1c51886920	[libc++] Implement P3168R2: Give optional range support (#149441 ) Resolves #105430 - Implement all required pieces of P3168R2 - Leverage existing `wrap_iter` and `bounded_iter` classes to implement the `optional` regular and hardened iterator type, respectively - Update documentation to match	2025-08-18 18:04:45 +03:00
Nikolas Klauser	d9bc548fac	[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 ```	2025-08-15 08:59:39 +02:00
Nikolas Klauser	cbbf303ff5	[libc++] Optimize __hash_table copy constructors and assignment (#151951 ) ``` ---------------------------------------------------------------------------------------------------------------------- Benchmark old new ---------------------------------------------------------------------------------------------------------------------- std::unordered_set<int>::ctor(const&)/0 15.4 ns 14.6 ns std::unordered_set<int>::ctor(const&)/32 686 ns 322 ns std::unordered_set<int>::ctor(const&)/1024 35839 ns 21490 ns std::unordered_set<int>::ctor(const&)/8192 385790 ns 280270 ns std::unordered_set<int>::operator=(const&) (into cleared Container)/0 15.1 ns 15.9 ns std::unordered_set<int>::operator=(const&) (into cleared Container)/32 1077 ns 333 ns std::unordered_set<int>::operator=(const&) (into cleared Container)/1024 31296 ns 9984 ns std::unordered_set<int>::operator=(const&) (into cleared Container)/8192 266776 ns 109418 ns std::unordered_set<int>::operator=(const&) (into partially populated Container)/0 15.1 ns 16.3 ns std::unordered_set<int>::operator=(const&) (into partially populated Container)/32 962 ns 320 ns std::unordered_set<int>::operator=(const&) (into partially populated Container)/1024 31713 ns 10128 ns std::unordered_set<int>::operator=(const&) (into partially populated Container)/8192 266113 ns 108525 ns std::unordered_set<int>::operator=(const&) (into populated Container)/0 0.990 ns 2.03 ns std::unordered_set<int>::operator=(const&) (into populated Container)/32 963 ns 263 ns std::unordered_set<int>::operator=(const&) (into populated Container)/1024 27600 ns 7793 ns std::unordered_set<int>::operator=(const&) (into populated Container)/8192 235295 ns 66248 ns std::unordered_set<std::string>::ctor(const&)/0 16.0 ns 15.0 ns std::unordered_set<std::string>::ctor(const&)/32 2950 ns 1277 ns std::unordered_set<std::string>::ctor(const&)/1024 246935 ns 73762 ns std::unordered_set<std::string>::ctor(const&)/8192 3310895 ns 2468608 ns std::unordered_set<std::string>::operator=(const&) (into cleared Container)/0 16.1 ns 15.8 ns std::unordered_set<std::string>::operator=(const&) (into cleared Container)/32 5856 ns 1039 ns std::unordered_set<std::string>::operator=(const&) (into cleared Container)/1024 170436 ns 74836 ns std::unordered_set<std::string>::operator=(const&) (into cleared Container)/8192 1574235 ns 1096891 ns std::unordered_set<std::string>::operator=(const&) (into partially populated Container)/0 16.0 ns 16.3 ns std::unordered_set<std::string>::operator=(const&) (into partially populated Container)/32 5571 ns 1064 ns std::unordered_set<std::string>::operator=(const&) (into partially populated Container)/1024 199220 ns 75462 ns std::unordered_set<std::string>::operator=(const&) (into partially populated Container)/8192 1552465 ns 1116094 ns std::unordered_set<std::string>::operator=(const&) (into populated Container)/0 1.70 ns 2.14 ns std::unordered_set<std::string>::operator=(const&) (into populated Container)/32 2562 ns 645 ns std::unordered_set<std::string>::operator=(const&) (into populated Container)/1024 228608 ns 39100 ns std::unordered_set<std::string>::operator=(const&) (into populated Container)/8192 2013723 ns 390401 ns ``` Fixes #77657	2025-08-15 08:57:33 +02:00
Nikolas Klauser	1cac2be874	[libc++] Optimize copy construction and assignment of __tree (#151304 ) ``` ---------------------------------------------------------------------------------------------------------- Benchmark old new ---------------------------------------------------------------------------------------------------------- std::map<int, int>::ctor(const&)/0 15.5 ns 14.9 ns std::map<int, int>::ctor(const&)/32 474 ns 321 ns std::map<int, int>::ctor(const&)/1024 24591 ns 11101 ns std::map<int, int>::ctor(const&)/8192 236153 ns 98868 ns std::map<std::string, int>::ctor(const&)/0 15.2 ns 14.9 ns std::map<std::string, int>::ctor(const&)/32 2673 ns 2340 ns std::map<std::string, int>::ctor(const&)/1024 115354 ns 86088 ns std::map<std::string, int>::ctor(const&)/8192 1298510 ns 626876 ns std::map<int, int>::operator=(const&) (into cleared Container)/0 16.5 ns 16.1 ns std::map<int, int>::operator=(const&) (into cleared Container)/32 548 ns 323 ns std::map<int, int>::operator=(const&) (into cleared Container)/1024 28418 ns 11026 ns std::map<int, int>::operator=(const&) (into cleared Container)/8192 281827 ns 97113 ns std::map<int, int>::operator=(const&) (into populated Container)/0 2.42 ns 1.85 ns std::map<int, int>::operator=(const&) (into populated Container)/32 369 ns 73.0 ns std::map<int, int>::operator=(const&) (into populated Container)/1024 24078 ns 2322 ns std::map<int, int>::operator=(const&) (into populated Container)/8192 266537 ns 22963 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/0 16.6 ns 16.2 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/32 2614 ns 1622 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/1024 116826 ns 63281 ns std::map<std::string, int>::operator=(const&) (into cleared Container)/8192 1316655 ns 649177 ns std::map<std::string, int>::operator=(const&) (into populated Container)/0 2.42 ns 1.89 ns std::map<std::string, int>::operator=(const&) (into populated Container)/32 1264 ns 581 ns std::map<std::string, int>::operator=(const&) (into populated Container)/1024 238826 ns 39943 ns std::map<std::string, int>::operator=(const&) (into populated Container)/8192 2412327 ns 379456 ns ``` Fixes #77658 Fixes #62571	2025-08-05 09:49:40 +02:00
Hui	d344c383e2	[libc++][ranges] implement `std::ranges::zip_transform_view` (#79605 ) Fixes #104977 Fixes #105035 --------- Co-authored-by: Louis Dionne <ldionne.2@gmail.com> Co-authored-by: A. Jiang <de34@live.cn>	2025-07-20 09:13:59 +01:00
Louis Dionne	167c695cec	[libc++] Add and empty skeleton for LLVM 22 release notes (#149535 )	2025-07-19 14:32:54 +01:00

7 Commits