[libc++][ranges] Implement `ranges::partial_sort`.

Differential Revision: https://reviews.llvm.org/D128744

[libc++][ranges] Make range algorithms support proxy iterators

Also test all the range algorithms to verify the support.

Differential Revision: https://reviews.llvm.org/D129823

[libc++] Make _LIBCPP_DEBUG_RANDOMIZE_RANGE a function

Reviewed By: ldionne, Mordante, var-const, #libc

Spies: mgorny, libcxx-commits

Differential Revision: https://reviews.llvm.org/D128181

[libc++][ranges] Implement `ranges::sort`.

Differential Revision: https://reviews.llvm.org/D127557

[libc++] Granularize <iterator> includes

Reviewed By: ldionne, #libc

Spies: libcxx-commits, wenlei

Differential Revision: https://reviews.llvm.org/D127445

[libc++] Towards a simpler extern template story in libc++

The flexibility around extern template instantiation declarations in
libc++ result in a very complicated model, especially when support for

[libc++] Towards a simpler extern template story in libc++

The flexibility around extern template instantiation declarations in
libc++ result in a very complicated model, especially when support for
slightly different configurations (like the debug mode or assertions
in the dylib) are taken into account. That results in unexpected bugs
like http://llvm.org/PR50534 (and there have been multiple similar
bugs in the past, notably around the debug mode).

This patch gets rid of the _LIBCPP_DISABLE_EXTERN_TEMPLATE knob, which
I don't think is fundamental. Indeed, the motivation for that knob was to
avoid taking a dependency on the library, however that can be done better
by linking against the static library instead. And in fact, some parts of
the headers will always depend on things defined in the library, which
defeats the original goal of _LIBCPP_DISABLE_EXTERN_TEMPLATE.

Differential Revision: https://reviews.llvm.org/D103960

show more ...

[libc++] Make the Debug mode a configuration-time only option

The debug mode has been broken pretty much ever since it was shipped
because it was possible to enable the debug mode in user code witho

[libc++] Make the Debug mode a configuration-time only option

The debug mode has been broken pretty much ever since it was shipped
because it was possible to enable the debug mode in user code without
actually enabling it in the dylib, leading to ODR violations that
caused various kinds of failures.

This commit makes the debug mode a knob that is configured when
building the library and which can't be changed afterwards. This is
less flexible for users, however it will actually work as intended
and it will allow us, in the future, to add various kinds of checks
that do not assume the same ABI as the normal library. Furthermore,
this will make the debug mode more robust, which means that vendors
might be more tempted to support it properly, which hasn't been the
case with the current debug mode.

This patch shouldn't break any user code, except folks who are building
against a library that doesn't have the debug mode enabled and who try
to enable the debug mode in their code. Such users will get a compile-time
error explaining that this configuration isn't supported anymore.

In the future, we should further increase the granularity of the debug
mode checks so that we can cherry-pick which checks to enable, like we
do for unspecified behavior randomization.

Differential Revision: https://reviews.llvm.org/D122941

show more ...

[libc++] Remove unused __functional includes

Reviewed By: ldionne, #libc

Spies: arichardson, smeenai, libcxx-commits, arphaman

Differential Revision: https://reviews.llvm.org/D126098

[libc++] Use __libcpp_clz for a tighter __log2i function

While looking at D113413 I noticed that __log2i could perhaps be
improved to be both slightly smaller and faster.

projects/libcxx/benchmarks

[libc++] Use __libcpp_clz for a tighter __log2i function

While looking at D113413 I noticed that __log2i could perhaps be
improved to be both slightly smaller and faster.

projects/libcxx/benchmarks/sort.libcxx.out --benchmark_filter=BM_Sort_uint32_QuickSortAdversary*
suggests this is performance neutral, but it shaves a few bytes off the
benchmark binary, and even more off a Chromium build.

Differential revision: https://reviews.llvm.org/D125958

show more ...

[libcxx][NFC] Format sort.h

This is to simplify the changes made in D122780. This diff was generated using the command:

```
clang-format include/__algorithm/sort.h -i
```

Reviewed By: #libc, ldi

[libcxx][NFC] Format sort.h

This is to simplify the changes made in D122780. This diff was generated using the command:

```
clang-format include/__algorithm/sort.h -i
```

Reviewed By: #libc, ldionne

Differential Revision: https://reviews.llvm.org/D122858

show more ...

Introduce branchless sorting functions for sort3, sort4 and sort5.

We are introducing branchless variants for sort3, sort4 and sort5.
These sorting functions have been generated using Reinforcement

Introduce branchless sorting functions for sort3, sort4 and sort5.

We are introducing branchless variants for sort3, sort4 and sort5.
These sorting functions have been generated using Reinforcement
Learning and aim to replace __sort3, __sort4 and __sort5 variants
for integral types.

The libc++ benchmarks were run on isolated machines for Skylake, ARM and
AMD architectures and achieve statistically significant improvement in
sorting random integers on test cases from sort1 to sort262144 for
uint32 and uint64.

A full performance overview for Intel Skylake, AMD and Arm can be
found here: https://bit.ly/3AtesYf

Reviewed By: ldionne, #libc, philnik

Spies: daniel.mankowitz, mgrang, Quuxplusone, andreamichi, philnik, libcxx-commits, nilayvaish, kristof.beyls

Differential Revision: https://reviews.llvm.org/D118029

show more ...

[libc++] Revert "Protect users from relying on detail headers" & related changes

This commit reverts 5aaefa51 (and also partly 7f285f48e77 and b6d75682f9,
which were related to the original commit).

[libc++] Revert "Protect users from relying on detail headers" & related changes

This commit reverts 5aaefa51 (and also partly 7f285f48e77 and b6d75682f9,
which were related to the original commit). As landed, 5aaefa51 had
unintended consequences on some downstream bots and didn't have proper
coverage upstream due to a few subtle things. Implementing this is
something we should do in libc++, however we'll first need to address
a few issues listed in https://reviews.llvm.org/D106124#3349710.

Differential Revision: https://reviews.llvm.org/D120683

show more ...

[libcxx][modules] protects users from relying on detail headers

libc++ has started splicing standard library headers into much more
fine-grained content for maintainability. It's very likely that ou

[libcxx][modules] protects users from relying on detail headers

libc++ has started splicing standard library headers into much more
fine-grained content for maintainability. It's very likely that outdated
and naive tooling (some of which is outside of LLVM's scope) will
suggest users include things such as <__ranges/access.h> instead of
<ranges>, and Hyrum's law suggests that users will eventually begin to
rely on this without the help of tooling. As such, this commit
intends to protect users from themselves, by making it a hard error for
anyone outside of the standard library to include libc++ detail headers.

Differential Revision: https://reviews.llvm.org/D106124

show more ...

[libc++] Normalize all our '#pragma GCC system_header', and regression-test.

Now we'll notice if a header forgets to include this magic phrase.

Differential Revision: https://reviews.llvm.org/D1188

[libc++] Normalize all our '#pragma GCC system_header', and regression-test.

Now we'll notice if a header forgets to include this magic phrase.

Differential Revision: https://reviews.llvm.org/D118800

show more ...

[libc++] Alphabetize header #includes. NFCI.

The NFC part of D116809. We still want to enforce this in CI,
but the mechanism for that is still to-be-determined.

Differential Revision: https://revie

[libc++] Alphabetize header #includes. NFCI.

The NFC part of D116809. We still want to enforce this in CI,
but the mechanism for that is still to-be-determined.

Differential Revision: https://reviews.llvm.org/D116809

show more ...

[libc++] Cast to the right `difference_type` in various algorithms

Differential Revision: https://reviews.llvm.org/D113868

[libc++] Minor fixups in the new introsort code.

Differential Revision: https://reviews.llvm.org/D114133

[libc++] Unspecified behavior randomization in libc++

This effort is dedicated to deflake the tests of the users which depend
on the unspecified behavior of algorithms and containers. This also
migh

[libc++] Unspecified behavior randomization in libc++

This effort is dedicated to deflake the tests of the users which depend
on the unspecified behavior of algorithms and containers. This also
might help updating the sorting algorithm in libcxx which has the
quadratic worst case in the future or at least create a new one under
flag.

For detailed design, please see the design doc I provide in the patch.

Differential Revision: https://reviews.llvm.org/D96946

show more ...

[libc++] Add introsort to avoid O(n^2) behavior

This commit adds a benchmark that tests std::sort on an adversarial inputs,
and uses introsort in std::sort to avoid O(n^2) behavior on adversarial
in

[libc++] Add introsort to avoid O(n^2) behavior

This commit adds a benchmark that tests std::sort on an adversarial inputs,
and uses introsort in std::sort to avoid O(n^2) behavior on adversarial
inputs.

Inputs where partitions are unbalanced even after 2 log(n) pivots have
been selected, the algorithm switches to heap sort to avoid the
possibility of spending O(n^2) time on sorting the input.
Benchmark results show that the intro sort implementation does
significantly better.

Benchmarking results before this change. Time represents the sorting
time required per element:

----------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
----------------------------------------------------------------------------------------------------------
BM_Sort_uint32_QuickSortAdversary_1 3.75 ns 3.74 ns 187432960
BM_Sort_uint32_QuickSortAdversary_4 3.05 ns 3.05 ns 231211008
BM_Sort_uint32_QuickSortAdversary_16 2.45 ns 2.45 ns 288096256
BM_Sort_uint32_QuickSortAdversary_64 32.8 ns 32.8 ns 21495808
BM_Sort_uint32_QuickSortAdversary_256 132 ns 132 ns 5505024
BM_Sort_uint32_QuickSortAdversary_1024 498 ns 497 ns 1572864
BM_Sort_uint32_QuickSortAdversary_16384 3846 ns 3845 ns 262144
BM_Sort_uint32_QuickSortAdversary_262144 61431 ns 61400 ns 262144
BM_Sort_uint64_QuickSortAdversary_1 3.93 ns 3.92 ns 181141504
BM_Sort_uint64_QuickSortAdversary_4 3.10 ns 3.09 ns 222560256
BM_Sort_uint64_QuickSortAdversary_16 2.50 ns 2.50 ns 283639808
BM_Sort_uint64_QuickSortAdversary_64 33.2 ns 33.2 ns 21757952
BM_Sort_uint64_QuickSortAdversary_256 132 ns 132 ns 5505024
BM_Sort_uint64_QuickSortAdversary_1024 478 ns 477 ns 1572864
BM_Sort_uint64_QuickSortAdversary_16384 3932 ns 3930 ns 262144
BM_Sort_uint64_QuickSortAdversary_262144 61646 ns 61615 ns 262144

Benchmarking results after this change:

----------------------------------------------------------------------------------------------------------
Benchmark Time CPU Iterations
----------------------------------------------------------------------------------------------------------
BM_Sort_uint32_QuickSortAdversary_1 6.31 ns 6.30 ns 107741184
BM_Sort_uint32_QuickSortAdversary_4 4.51 ns 4.50 ns 158859264
BM_Sort_uint32_QuickSortAdversary_16 3.00 ns 3.00 ns 223608832
BM_Sort_uint32_QuickSortAdversary_64 44.8 ns 44.8 ns 15990784
BM_Sort_uint32_QuickSortAdversary_256 69.0 ns 68.9 ns 9961472
BM_Sort_uint32_QuickSortAdversary_1024 118 ns 118 ns 6029312
BM_Sort_uint32_QuickSortAdversary_16384 175 ns 175 ns 4194304
BM_Sort_uint32_QuickSortAdversary_262144 210 ns 210 ns 3407872
BM_Sort_uint64_QuickSortAdversary_1 6.75 ns 6.73 ns 103809024
BM_Sort_uint64_QuickSortAdversary_4 4.53 ns 4.53 ns 160432128
BM_Sort_uint64_QuickSortAdversary_16 2.98 ns 2.97 ns 234356736
BM_Sort_uint64_QuickSortAdversary_64 44.3 ns 44.3 ns 15990784
BM_Sort_uint64_QuickSortAdversary_256 69.2 ns 69.2 ns 10223616
BM_Sort_uint64_QuickSortAdversary_1024 119 ns 119 ns 6029312
BM_Sort_uint64_QuickSortAdversary_16384 173 ns 173 ns 4194304
BM_Sort_uint64_QuickSortAdversary_262144 212 ns 212 ns 3407872

Differential Revision: https://reviews.llvm.org/D113413

show more ...

[libc++] Add an option to disable wide character support in libc++

Some embedded platforms do not wish to support the C library functionality
for handling wchar_t because they have no use for it. It

[libc++] Add an option to disable wide character support in libc++

Some embedded platforms do not wish to support the C library functionality
for handling wchar_t because they have no use for it. It makes sense for
libc++ to work properly on those platforms, so this commit adds a carve-out
of functionality for wchar_t.

Unfortunately, unlike some other carve-outs (e.g. random device), this
patch touches several parts of the library. However, despite the wide
impact of this patch, I still think it is important to support this
configuration since it makes it much simpler to port libc++ to some
embedded platforms.

Differential Revision: https://reviews.llvm.org/D111265

show more ...

[libc++][NFC] Remove useless _LIBCPP_PUSH_MACROS

Only files that actually use min/max are required to do this dance.

Differential Revision: https://reviews.llvm.org/D108778

[libc++] Eliminate needless `add_lvalue_reference` from <algorithm> helpers. NFCI.

When `_Compare` is a function parameter already (so it's not `void`
and it's not an abominable function type), `add

[libc++] Eliminate needless `add_lvalue_reference` from <algorithm> helpers. NFCI.

When `_Compare` is a function parameter already (so it's not `void`
and it's not an abominable function type), `add_lvalue_reference_t<_Compare>`
is simply a synonym for `_Compare&`. We don't need to pull in `<type_traits>`
and instantiate a template trait to figure that out.

Differential Revision: https://reviews.llvm.org/D108400

show more ...

[libcxx][modularisation] moves <utility> content out of <type_traits>

Moves:

* `std::move`, `std::forward`, `std::declval`, and `std::swap` into
`__utility/${FUNCTION_NAME}`.
* `std::swap_ranges`

[libcxx][modularisation] moves <utility> content out of <type_traits>

Moves:

* `std::move`, `std::forward`, `std::declval`, and `std::swap` into
`__utility/${FUNCTION_NAME}`.
* `std::swap_ranges` and `std::iter_swap` into
`__algorithm/${FUNCTION_NAME}`

Differential Revision: https://reviews.llvm.org/D103734

show more ...

[libcxx] Move all algorithms into their own headers

This is a fairly mechanical change, it just moves each algorithm into
its own header. This is intended to be a NFC.

This commit re-applies 7ed7d4

[libcxx] Move all algorithms into their own headers

This is a fairly mechanical change, it just moves each algorithm into
its own header. This is intended to be a NFC.

This commit re-applies 7ed7d4ccb899, which was reverted in 692d7166f771
because the Modules build got broken. The modules build has now been
fixed, so we're re-committing this.

Differential Revision: https://reviews.llvm.org/D103583

Attribution note
----------------
I'm only committing this. This commit is a mix of D103583, D103330 and
D104171 authored by:

Co-authored-by: Christopher Di Bella <[email protected]>
Co-authored-by: zoecarver <[email protected]>

show more ...

[libcxx][gardening] Move all algorithms into their own headers.

This is a fairly mechanical change, it just moves each algorithm into its own header. This is a NFC.

Note: during this change, I burn

[libcxx][gardening] Move all algorithms into their own headers.

This is a fairly mechanical change, it just moves each algorithm into its own header. This is a NFC.

Note: during this change, I burned down all the includes, so this follows "include only and exactly what you use."

Differential Revision: https://reviews.llvm.org/D103583

show more ...