| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
(#134960)
Previously, the segmented iterator optimization for `std::for_each` was restricted to C++23 and later due to its dependency on `__movable_box`, which is not available in earlier standards. This patch eliminates that restriction, enabling consistent optimizations starting from C++11.
By backporting this enhancement, we improve performance across older standards and create opportunities to extend similar optimizations to other algorithms by forwarding their calls to `std::for_each`.
|
|
# Overview
As a disclaimer, this is my first PR to LLVM and while I've tried to
ensure I've followed the LLVM and libc++ contributing guidelines,
there's probably a good chance I missed something. If I have, just let
me know and I'll try to correct it as soon as I can.
This PR implements `std::ranges::iota` and
`std::ranges::out_value_result` outlined in
[P2440r1](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p2440r1.html).
As outlined in the paper above, I've:
- Implemented `out_value_result` and added to `<algorithm>`
- Added `out_value_result`, `iota_result`, and two overloads of `iota`
to `std::ranges` in `<numeric>`
- Updated the version macro `__cpp_lib_ranges_iota` in `<version>`
I've also added tests for `ranges::iota` and `ranges::out_value_result`.
Lastly, I added those structs to the appropriate module files.
Partially implements #105184
EDIT: Forgot to mention in the original post, thanks to @hawkinsw for
taking a look at a preliminary version of this PR!
# TODOs
- [x] Updating the range [status
doc](https://github.com/jamesETsmith/llvm-project/blob/main/libcxx/docs/Status/RangesMajorFeatures.csv)
- [x] Ensure all comments from https://reviews.llvm.org/D121436 are
addressed here
- [X] EDIT (I'll do this in a separate PR). ~~I'm open to implementing
the rest of P2440r1 (`ranges::shift_left` and `ranges::shift_right`) if
that's ok, I just wanted to get feedback on `ranges::iota` first~~
- [x] I've been having trouble building the modules locally and want to
make sure that's working properly
Closes: #134060
|
|
Drive-by changes:
- Consistently mark `std::__inplace_merge::__inplace_merge_impl`
`_LIBCPP_CONSTEXPR_SINCE_CXX26`.
- This function template is only called by other functions that becomes
constexpr since C++26, and it itself calls `std::__inplace_merge` that
is constexpr since C++26.
- Unblock related test coverage in constant evaluation for
`stable_partition`, `ranges::stable_sort`, `std::stable_sort`,
`std::stable_partition`, and `std::inplace_merge`.
|
|
Drive-by:
- Adds `constexpr_random.h` for pseudo-randomizing or shuffling in tests
for constant evaluation.
|
|
Drive-by: Enables test coverage for `ranges::stable_sort` with proxy
iterators, and changes "constexpr in" to "constexpr since" in comments
in `<algorithm>`.
|
|
(#129839)
|
|
Drive-by changes:
- Enables no-memory case for Clang.
- Enables `robust_re_difference_type.compile.pass.cpp` and
`robust_against_proxy_iterators_lifetime_bugs.pass.cpp` test coverage
for `std::stable_sort` in constant evaluation since C++26. The changes
were missing in the PR making `std::stable_sort` `constexpr`.
|
|
Implementing `constexpr std::stable_sort`. This is part of P2562R1,
tracked via issue #105360.
Closes #119394
Co-authored-by: A. Jiang <de34@live.cn>
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
|
|
This patch implements the forwarding to frozen C++03 headers as
discussed in
https://discourse.llvm.org/t/rfc-freezing-c-03-headers-in-libc. In the
RFC, we initially proposed selecting the right headers from the Clang
driver, however consensus seemed to steer towards handling this in the
library itself. This patch implements that direction.
At a high level, the changes basically amount to making each public
header look like this:
```
// inside <vector>
#ifdef _LIBCPP_CXX03_LANG
# include <__cxx03/vector>
#else
// normal <vector> content
#endif
```
In most cases, public headers are simple umbrella headers so there isn't
much code in the #else branch. In other cases, the #else branch contains
the actual implementation of the header.
|
|
Including The frozen C++03 headers results in a lot of formatting
changes in the main headers, so this splits these changes into a
separate commit instead.
This is part of
https://discourse.llvm.org/t/rfc-freezing-c-03-headers-in-libc.
|
|
|
|
This follows the pattern we use consistently for ranges algorithms.
This is a re-application of 24bc3244d4e which had been reverted in
f11abac65 due to unrelated failures.
|
|
modules (#107638)" (#110384)
This reverts 3 commits:
45a09d1811d5d6597385ef02ecf2d4b7320c37c5
24bc3244d4e221f4e6740f45e2bf15a1441a3076
bc6bd3bc1e99c7ec9e22dff23b4f4373fa02cae3
The GitHub pre-merge CI has been broken since this PR went in. This
change reverts it to see if I can get the pre-merge CI working again.
|
|
This follows the pattern we use consistently for ranges algorithms.
|
|
This patch adds a large number of missing includes in the libc++ headers
and the test suite. Those were found as part of the effort to move
towards a mostly monolithic top-level std module.
|
|
Implements [P1223R5][] completely.
Includes an implementation of `find_last`, `find_last_if`, and
`find_last_if_not`.
[P1223R5]: https://wg21.link/p1223r5
|
|
This is an intermediate step towards the PSTL dispatching mechanism
rework. It will make it a lot easier to track the upcoming front-end
changes. After the rework, there are basically no implementation details
in the front-end, so the definition of each algorithm will become much
simpler. Otherwise, it wouldn't make sense to define all the algorithms
in the same header.
|
|
headers (#83740)
This is a relatively low cost way of reducing the include sizes in older
language modes compared to the effect. For example, in C++14 mode the
include time of `<algorithm>` is reduced from 198ms to 127ms.
|
|
Originally, we used __libcpp_verbose_abort to handle assertion failures.
That function was declared from all public headers. Since we don't use
that mechanism anymore, we don't need to declare __libcpp_verbose_abort
from all public headers, and we can clean up a lot of unnecessary
includes.
This patch also moves the definition of the various assertion categories
to the <__assert> header, since we now rely on regular IWYU for these
assertion macros.
rdar://105510916
|
|
|
|
Notable things in this commit:
* refactors `__indirect_binary_left_foldable`, making it slightly
different (but equivalent) to _`indirect-binary-left-foldable`_, which
improves readability (a [patch to the Working Paper][patch] was made)
* omits `__cpo` namespace, since it is not required for implementing
niebloids (a cleanup should happen in 2024)
* puts tests ensuring invocable robustness and dangling correctness
inside the correctness testing to ensure that the algorithms' results
are still correct
[patch]: https://github.com/cplusplus/draft/pull/6734
|
|
Differential Revision: https://reviews.llvm.org/D159232
```
Running ./ranges_contains.libcxx.out
Run on (10 X 24.121 MHz CPU s)
CPU Caches:
L1 Data 64 KiB (x10)
L1 Instruction 128 KiB (x10)
L2 Unified 4096 KiB (x5)
Load Average: 3.37, 6.77, 5.27
--------------------------------------------------------------------
Benchmark Time CPU Iterations
--------------------------------------------------------------------
bm_contains_char/16 1.88 ns 1.87 ns 371607095
bm_contains_char/256 7.48 ns 7.47 ns 93292285
bm_contains_char/4096 99.7 ns 99.6 ns 7013185
bm_contains_char/65536 1296 ns 1294 ns 540436
bm_contains_char/1048576 23887 ns 23860 ns 29302
bm_contains_char/16777216 389420 ns 389095 ns 1796
bm_contains_int/16 7.14 ns 7.14 ns 97776288
bm_contains_int/256 90.4 ns 90.3 ns 7558089
bm_contains_int/4096 1294 ns 1290 ns 543052
bm_contains_int/65536 20482 ns 20443 ns 34334
bm_contains_int/1048576 328817 ns 327965 ns 2147
bm_contains_int/16777216 5246279 ns 5239361 ns 133
bm_contains_bool/16 2.19 ns 2.19 ns 322565780
bm_contains_bool/256 3.42 ns 3.41 ns 205025467
bm_contains_bool/4096 22.1 ns 22.1 ns 31780479
bm_contains_bool/65536 333 ns 332 ns 2106606
bm_contains_bool/1048576 5126 ns 5119 ns 135901
bm_contains_bool/16777216 81656 ns 81574 ns 8569
```
---------
Co-authored-by: Nathan Gauër <brioche@google.com>
|
|
Differential Revision: https://reviews.llvm.org/D157131
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
|
|
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D155025
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D155330
|
|
Reviewed By: #libc, var-const
Differential Revision: https://reviews.llvm.org/D150831
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits, mgrang
Differential Revision: https://reviews.llvm.org/D152860
|
|
See https://discourse.llvm.org/t/rfc-removing-the-legacy-debug-mode-from-libc/71026
Reviewed By: #libc, Mordante, ldionne
Differential Revision: https://reviews.llvm.org/D153672
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D152853
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D152581
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D151841
|
|
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D150128
|
|
Reviewed By: #libc, ldionne
Spies: ldionne, libcxx-commits
Differential Revision: https://reviews.llvm.org/D151573
|
|
Reviewed By: ldionne, #libc
Spies: pcwang-thead, libcxx-commits
Differential Revision: https://reviews.llvm.org/D151375
|
|
Reviewed By: ldionne, #libc
Spies: jloser, libcxx-commits
Differential Revision: https://reviews.llvm.org/D149706
|
|
|
|
This reverts commit b049fc0481bc387f57fd61da7239f85ef91096c1.
The wrong patch was landed.
|
|
Reviewed By: ldionne, #libc
Spies: jloser, libcxx-commits
Differential Revision: https://reviews.llvm.org/D149706
|
|
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D149615
|
|
This reverts commit cbd9e5454741ebe6b39521fe1a8ed4eed5c2c801.
The wrong patch was landed.
|
|
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D149615
|
|
This removes the need for a custom libc++ build to have a basic set of PSTL algorithms.
Reviewed By: ldionne, #libc
Spies: miyuki, libcxx-commits, arichardson
Differential Revision: https://reviews.llvm.org/D149624
|
|
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D149540
|
|
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D149539
|
|
Reviewed By: ldionne, #libc
Spies: libcxx-commits
Differential Revision: https://reviews.llvm.org/D149381
|
|
Reviewed By: ldionne, #libc
Spies: arichardson, libcxx-commits, miyuki
Differential Revision: https://reviews.llvm.org/D143161
|
|
algorithm's include of chrono causes include cycles:
```
algorithm -> chrono -> __chrono/convert_to_tm.h -> __chrono/statically_widen.h -> __format/concepts.h -> __format/format_parse_context.h -> string_view -> algorithm
algorithm -> chrono -> __chrono/convert_to_tm.h -> __chrono/statically_widen.h -> __format/concepts.h -> __format/format_parse_context.h -> string_view -> functional -> __functional/boyer_moore_searcher.h -> array -> algorithm
algorithm -> chrono -> __chrono/convert_to_tm.h -> __chrono/statically_widen.h -> __format/concepts.h -> __format/format_parse_context.h -> string_view -> functional -> __functional/boyer_moore_searcher.h -> unordered_map -> algorithm
algorithm -> chrono -> __chrono/convert_to_tm.h -> __chrono/statically_widen.h -> __format/concepts.h -> __format/format_parse_context.h -> string_view -> functional -> __functional/boyer_moore_searcher.h -> vector -> algorithm
```
This is a problem for clang modules after the std mega module is broken up, because it becomes a module cycle which is a hard error.
All of the includes in the `__chrono` and `__format` headers are being used and so can't be removed. algorithm's include of chrono is already removed in C++20, whereas the array, string_view, unordered_map, vector includes of algorithm aren't removed until C++23 (and it's 4x the includes that would need removing). Unconditionally remove the chrono include from algorithm in all versions, so that the module breakup can happen (the module has to apply to all C++ versions).
Reviewed By: Mordante, #libc
Differential Revision: https://reviews.llvm.org/D148405
|
|
We decided to go a different route. To make the switch easier, rip out the old integration first and build on a clean base.
Reviewed By: ldionne, #libc, #libc_abi
Spies: arichardson, libcxx-commits
Differential Revision: https://reviews.llvm.org/D148480
|
|
We changed the `abort` calls when trying to throw exceptions in `-fno-exceptions` mode to `__verbose_abort` calls, which removes the dependency in most files.
Reviewed By: ldionne, #libc
Spies: dim, emaste, mikhail.ramalho, smeenai, libcxx-commits
Differential Revision: https://reviews.llvm.org/D146076
|
