diff options
Diffstat (limited to 'libcxx')
23 files changed, 416 insertions, 82 deletions
diff --git a/libcxx/docs/ReleaseNotes/22.rst b/libcxx/docs/ReleaseNotes/22.rst index b5dcfc7..8d023a1 100644 --- a/libcxx/docs/ReleaseNotes/22.rst +++ b/libcxx/docs/ReleaseNotes/22.rst @@ -41,6 +41,7 @@ Implemented Papers - P2321R2: ``zip`` (`Github <https://llvm.org/PR105169>`__) (The paper is partially implemented. ``zip_transform_view`` is implemented in this release) - P3044R2: sub-``string_view`` from ``string`` (`Github <https://llvm.org/PR148140>`__) +- P3223R2: Making ``std::istream::ignore`` less surprising (`Github <https://llvm.org/PR148178>`__) - P3168R2: Give ``std::optional`` Range Support (`Github <https://llvm.org/PR105430>`__) Improvements and New Features @@ -64,6 +65,8 @@ Improvements and New Features - Multiple internal types have been refactored to use ``[[no_unique_address]]``, resulting in faster compile times and reduced debug information. +- The performance of ``std::find`` has been improved by up to 2x for integral types + Deprecations and Removals ------------------------- diff --git a/libcxx/docs/Status/Cxx2cPapers.csv b/libcxx/docs/Status/Cxx2cPapers.csv index 9e1678f..4e0918b 100644 --- a/libcxx/docs/Status/Cxx2cPapers.csv +++ b/libcxx/docs/Status/Cxx2cPapers.csv @@ -151,7 +151,7 @@ "`P3111R8 <https://wg21.link/P3111R8>`__","Atomic Reduction Operations","2025-06 (Sofia)","","","`#148174 <https://github.com/llvm/llvm-project/issues/148174>`__","" "`P3060R3 <https://wg21.link/P3060R3>`__","Add ``std::views::indices(n)``","2025-06 (Sofia)","","","`#148175 <https://github.com/llvm/llvm-project/issues/148175>`__","" "`P2319R5 <https://wg21.link/P2319R5>`__","Prevent ``path`` presentation problems","2025-06 (Sofia)","","","`#148177 <https://github.com/llvm/llvm-project/issues/148177>`__","" -"`P3223R2 <https://wg21.link/P3223R2>`__","Making ``std::istream::ignore`` less surprising","2025-06 (Sofia)","","","`#148178 <https://github.com/llvm/llvm-project/issues/148178>`__","" +"`P3223R2 <https://wg21.link/P3223R2>`__","Making ``std::istream::ignore`` less surprising","2025-06 (Sofia)","|Complete|","22","`#148178 <https://github.com/llvm/llvm-project/issues/148178>`__","" "`P2781R9 <https://wg21.link/P2781R9>`__","``std::constant_wrapper``","2025-06 (Sofia)","","","`#148179 <https://github.com/llvm/llvm-project/issues/148179>`__","" "`P3697R1 <https://wg21.link/P3697R1>`__","Minor additions to C++26 standard library hardening","2025-06 (Sofia)","","","`#148180 <https://github.com/llvm/llvm-project/issues/148180>`__","" "`P3552R3 <https://wg21.link/P3552R3>`__","Add a Coroutine Task Type","2025-06 (Sofia)","","","`#148182 <https://github.com/llvm/llvm-project/issues/148182>`__","" diff --git a/libcxx/docs/TestingLibcxx.rst b/libcxx/docs/TestingLibcxx.rst index 2277910..6171629 100644 --- a/libcxx/docs/TestingLibcxx.rst +++ b/libcxx/docs/TestingLibcxx.rst @@ -482,7 +482,7 @@ when running the benchmarks. For example, .. code-block:: bash - $ libcxx/utils/libcxx-lit <build> libcxx/test/benchmarks/string.bench.cpp --show-all --param optimization=speed + $ libcxx/utils/libcxx-lit <build> libcxx/test/benchmarks/containers/string.bench.cpp --show-all --param optimization=speed Note that benchmarks are only dry-run when run via the ``check-cxx`` target since we only want to make sure they don't rot. Do not rely on the results of benchmarks @@ -504,7 +504,7 @@ more benchmarks, as usual: .. code-block:: bash $ cmake -S runtimes -B <build> [...] - $ libcxx/utils/libcxx-lit <build> libcxx/test/benchmarks/string.bench.cpp --param optimization=speed + $ libcxx/utils/libcxx-lit <build> libcxx/test/benchmarks/containers/string.bench.cpp --param optimization=speed Then, get the consolidated benchmark output for that run using ``consolidate-benchmarks``: diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h index 8c8cb58..5f32ae8 100644 --- a/libcxx/include/__algorithm/find.h +++ b/libcxx/include/__algorithm/find.h @@ -12,6 +12,7 @@ #include <__algorithm/find_segment_if.h> #include <__algorithm/min.h> +#include <__algorithm/simd_utils.h> #include <__algorithm/unwrap_iter.h> #include <__bit/countr.h> #include <__bit/invert_if.h> @@ -44,39 +45,102 @@ _LIBCPP_BEGIN_NAMESPACE_STD // generic implementation template <class _Iter, class _Sent, class _Tp, class _Proj> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter -__find(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) { +__find_loop(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) { for (; __first != __last; ++__first) if (std::__invoke(__proj, *__first) == __value) break; return __first; } -// trivially equality comparable implementations -template <class _Tp, - class _Up, - class _Proj, - __enable_if_t<__is_identity<_Proj>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value && - sizeof(_Tp) == 1, - int> = 0> -_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __find(_Tp* __first, _Tp* __last, const _Up& __value, _Proj&) { - if (auto __ret = std::__constexpr_memchr(__first, __value, __last - __first)) - return __ret; - return __last; +template <class _Iter, class _Sent, class _Tp, class _Proj> +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter +__find(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) { + return std::__find_loop(std::move(__first), std::move(__last), __value, __proj); } -#if _LIBCPP_HAS_WIDE_CHARACTERS -template <class _Tp, - class _Up, - class _Proj, - __enable_if_t<__is_identity<_Proj>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value && - sizeof(_Tp) == sizeof(wchar_t) && _LIBCPP_ALIGNOF(_Tp) >= _LIBCPP_ALIGNOF(wchar_t), - int> = 0> +#if _LIBCPP_VECTORIZE_ALGORITHMS +template <class _Tp, class _Up> +[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI +_LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __find_vectorized(_Tp* __first, _Tp* __last, _Up __value) { + if (!__libcpp_is_constant_evaluated()) { + constexpr size_t __unroll_count = 4; + constexpr size_t __vec_size = __native_vector_size<_Tp>; + using __vec = __simd_vector<_Tp, __vec_size>; + + auto __orig_first = __first; + + auto __values = static_cast<__simd_vector<_Up, __vec_size>>(__value); // broadcast the value + while (static_cast<size_t>(__last - __first) >= __unroll_count * __vec_size) [[__unlikely__]] { + __vec __lhs[__unroll_count]; + + for (size_t __i = 0; __i != __unroll_count; ++__i) + __lhs[__i] = std::__load_vector<__vec>(__first + __i * __vec_size); + + for (size_t __i = 0; __i != __unroll_count; ++__i) { + if (auto __cmp_res = __lhs[__i] == __values; std::__any_of(__cmp_res)) { + auto __offset = __i * __vec_size + std::__find_first_set(__cmp_res); + return __first + __offset; + } + } + + __first += __unroll_count * __vec_size; + } + + // check the remaining 0-3 vectors + while (static_cast<size_t>(__last - __first) >= __vec_size) { + if (auto __cmp_res = std::__load_vector<__vec>(__first) == __values; std::__any_of(__cmp_res)) { + return __first + std::__find_first_set(__cmp_res); + } + __first += __vec_size; + } + + if (__last - __first == 0) + return __first; + + // Check if we can load elements in front of the current pointer. If that's the case load a vector at + // (last - vector_size) to check the remaining elements + if (static_cast<size_t>(__first - __orig_first) >= __vec_size) { + __first = __last - __vec_size; + return __first + std::__find_first_set(std::__load_vector<__vec>(__first) == __values); + } + } + + __identity __proj; + return std::__find_loop(__first, __last, __value, __proj); +} +#endif + +#ifndef _LIBCPP_CXX03_LANG +// trivially equality comparable implementations +template < + class _Tp, + class _Up, + class _Proj, + __enable_if_t<__is_identity<_Proj>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __find(_Tp* __first, _Tp* __last, const _Up& __value, _Proj&) { - if (auto __ret = std::__constexpr_wmemchr(__first, __value, __last - __first)) - return __ret; - return __last; + if constexpr (sizeof(_Tp) == 1) { + if (auto __ret = std::__constexpr_memchr(__first, __value, __last - __first)) + return __ret; + return __last; + } +# if _LIBCPP_HAS_WIDE_CHARACTERS + else if constexpr (sizeof(_Tp) == sizeof(wchar_t) && _LIBCPP_ALIGNOF(_Tp) >= _LIBCPP_ALIGNOF(wchar_t)) { + if (auto __ret = std::__constexpr_wmemchr(__first, __value, __last - __first)) + return __ret; + return __last; + } +# endif +# if _LIBCPP_VECTORIZE_ALGORITHMS + else if constexpr (is_integral<_Tp>::value) { + return std::__find_vectorized(__first, __last, __value); + } +# endif + else { + __identity __proj; + return std::__find_loop(__first, __last, __value, __proj); + } } -#endif // _LIBCPP_HAS_WIDE_CHARACTERS +#endif // TODO: This should also be possible to get right with different signedness // cast integral types to allow vectorization diff --git a/libcxx/include/__algorithm/simd_utils.h b/libcxx/include/__algorithm/simd_utils.h index 96b074c..aaeb8a8 100644 --- a/libcxx/include/__algorithm/simd_utils.h +++ b/libcxx/include/__algorithm/simd_utils.h @@ -115,6 +115,11 @@ template <class _VecT, class _Iter> } template <class _Tp, size_t _Np> +[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __any_of(__simd_vector<_Tp, _Np> __vec) noexcept { + return __builtin_reduce_or(__builtin_convertvector(__vec, __simd_vector<bool, _Np>)); +} + +template <class _Tp, size_t _Np> [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __all_of(__simd_vector<_Tp, _Np> __vec) noexcept { return __builtin_reduce_and(__builtin_convertvector(__vec, __simd_vector<bool, _Np>)); } diff --git a/libcxx/include/__flat_map/flat_map.h b/libcxx/include/__flat_map/flat_map.h index 31ba9bc..7bb235b 100644 --- a/libcxx/include/__flat_map/flat_map.h +++ b/libcxx/include/__flat_map/flat_map.h @@ -29,7 +29,6 @@ #include <__flat_map/key_value_iterator.h> #include <__flat_map/sorted_unique.h> #include <__flat_map/utils.h> -#include <__functional/invoke.h> #include <__functional/is_transparent.h> #include <__functional/operations.h> #include <__fwd/memory.h> @@ -48,7 +47,6 @@ #include <__ranges/container_compatible_range.h> #include <__ranges/drop_view.h> #include <__ranges/from_range.h> -#include <__ranges/ref_view.h> #include <__ranges/size.h> #include <__ranges/subrange.h> #include <__ranges/zip_view.h> diff --git a/libcxx/include/__flat_map/flat_multimap.h b/libcxx/include/__flat_map/flat_multimap.h index abaacf9..96d9454 100644 --- a/libcxx/include/__flat_map/flat_multimap.h +++ b/libcxx/include/__flat_map/flat_multimap.h @@ -22,7 +22,6 @@ #include <__algorithm/upper_bound.h> #include <__assert> #include <__compare/synth_three_way.h> -#include <__concepts/convertible_to.h> #include <__concepts/swappable.h> #include <__config> #include <__cstddef/byte.h> @@ -30,7 +29,6 @@ #include <__flat_map/key_value_iterator.h> #include <__flat_map/sorted_equivalent.h> #include <__flat_map/utils.h> -#include <__functional/invoke.h> #include <__functional/is_transparent.h> #include <__functional/operations.h> #include <__fwd/vector.h> @@ -47,7 +45,6 @@ #include <__ranges/container_compatible_range.h> #include <__ranges/drop_view.h> #include <__ranges/from_range.h> -#include <__ranges/ref_view.h> #include <__ranges/size.h> #include <__ranges/subrange.h> #include <__ranges/zip_view.h> @@ -57,14 +54,12 @@ #include <__type_traits/is_allocator.h> #include <__type_traits/is_nothrow_constructible.h> #include <__type_traits/is_same.h> -#include <__type_traits/maybe_const.h> #include <__utility/exception_guard.h> #include <__utility/move.h> #include <__utility/pair.h> #include <__utility/scope_guard.h> #include <__vector/vector.h> #include <initializer_list> -#include <stdexcept> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header diff --git a/libcxx/include/__flat_map/key_value_iterator.h b/libcxx/include/__flat_map/key_value_iterator.h index d04a23d..795651a 100644 --- a/libcxx/include/__flat_map/key_value_iterator.h +++ b/libcxx/include/__flat_map/key_value_iterator.h @@ -20,7 +20,6 @@ #include <__type_traits/conditional.h> #include <__utility/forward.h> #include <__utility/move.h> -#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header diff --git a/libcxx/include/__flat_set/flat_multiset.h b/libcxx/include/__flat_set/flat_multiset.h index 65f4161..b1a4917 100644 --- a/libcxx/include/__flat_set/flat_multiset.h +++ b/libcxx/include/__flat_set/flat_multiset.h @@ -13,54 +13,40 @@ #include <__algorithm/equal_range.h> #include <__algorithm/lexicographical_compare_three_way.h> #include <__algorithm/lower_bound.h> -#include <__algorithm/min.h> #include <__algorithm/ranges_equal.h> #include <__algorithm/ranges_inplace_merge.h> #include <__algorithm/ranges_is_sorted.h> #include <__algorithm/ranges_sort.h> -#include <__algorithm/ranges_unique.h> #include <__algorithm/remove_if.h> #include <__algorithm/upper_bound.h> #include <__assert> #include <__compare/synth_three_way.h> -#include <__concepts/convertible_to.h> #include <__concepts/swappable.h> #include <__config> -#include <__cstddef/byte.h> -#include <__cstddef/ptrdiff_t.h> -#include <__flat_map/key_value_iterator.h> #include <__flat_map/sorted_equivalent.h> #include <__flat_set/ra_iterator.h> #include <__flat_set/utils.h> -#include <__functional/invoke.h> #include <__functional/is_transparent.h> #include <__functional/operations.h> #include <__fwd/vector.h> #include <__iterator/concepts.h> -#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/prev.h> -#include <__iterator/ranges_iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__memory/allocator_traits.h> #include <__memory/uses_allocator.h> #include <__memory/uses_allocator_construction.h> -#include <__ranges/access.h> #include <__ranges/concepts.h> #include <__ranges/container_compatible_range.h> #include <__ranges/drop_view.h> #include <__ranges/from_range.h> -#include <__ranges/ref_view.h> #include <__ranges/size.h> #include <__ranges/subrange.h> -#include <__ranges/zip_view.h> -#include <__type_traits/conjunction.h> #include <__type_traits/container_traits.h> #include <__type_traits/invoke.h> #include <__type_traits/is_allocator.h> #include <__type_traits/is_nothrow_constructible.h> #include <__type_traits/is_same.h> -#include <__type_traits/maybe_const.h> #include <__utility/as_const.h> #include <__utility/exception_guard.h> #include <__utility/move.h> diff --git a/libcxx/include/__flat_set/flat_set.h b/libcxx/include/__flat_set/flat_set.h index cc788bd..5fa1f2d 100644 --- a/libcxx/include/__flat_set/flat_set.h +++ b/libcxx/include/__flat_set/flat_set.h @@ -12,7 +12,6 @@ #include <__algorithm/lexicographical_compare_three_way.h> #include <__algorithm/lower_bound.h> -#include <__algorithm/min.h> #include <__algorithm/ranges_adjacent_find.h> #include <__algorithm/ranges_equal.h> #include <__algorithm/ranges_inplace_merge.h> @@ -24,20 +23,16 @@ #include <__compare/synth_three_way.h> #include <__concepts/swappable.h> #include <__config> -#include <__cstddef/ptrdiff_t.h> #include <__flat_map/sorted_unique.h> #include <__flat_set/ra_iterator.h> #include <__flat_set/utils.h> -#include <__functional/invoke.h> #include <__functional/is_transparent.h> #include <__functional/operations.h> #include <__fwd/vector.h> #include <__iterator/concepts.h> -#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> #include <__iterator/prev.h> -#include <__iterator/ranges_iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__memory/allocator_traits.h> #include <__memory/uses_allocator.h> @@ -47,10 +42,7 @@ #include <__ranges/container_compatible_range.h> #include <__ranges/drop_view.h> #include <__ranges/from_range.h> -#include <__ranges/ref_view.h> #include <__ranges/size.h> -#include <__ranges/subrange.h> -#include <__type_traits/conjunction.h> #include <__type_traits/container_traits.h> #include <__type_traits/invoke.h> #include <__type_traits/is_allocator.h> diff --git a/libcxx/include/__utility/default_three_way_comparator.h b/libcxx/include/__utility/default_three_way_comparator.h index 438ab55..92cdce6 100644 --- a/libcxx/include/__utility/default_three_way_comparator.h +++ b/libcxx/include/__utility/default_three_way_comparator.h @@ -40,13 +40,13 @@ struct __default_three_way_comparator<_LHS, } }; -#if _LIBCPP_STD_VER >= 20 && __has_builtin(__builtin_lt_synthesises_from_spaceship) +#if _LIBCPP_STD_VER >= 20 && __has_builtin(__builtin_lt_synthesizes_from_spaceship) template <class _LHS, class _RHS> struct __default_three_way_comparator< _LHS, _RHS, __enable_if_t<!(is_arithmetic<_LHS>::value && is_arithmetic<_RHS>::value) && - __builtin_lt_synthesises_from_spaceship(const _LHS&, const _RHS&)>> { + __builtin_lt_synthesizes_from_spaceship(const _LHS&, const _RHS&)>> { _LIBCPP_HIDE_FROM_ABI static int operator()(const _LHS& __lhs, const _RHS& __rhs) { auto __res = __lhs <=> __rhs; if (__res < 0) diff --git a/libcxx/include/istream b/libcxx/include/istream index 93def61..7f15521 100644 --- a/libcxx/include/istream +++ b/libcxx/include/istream @@ -70,6 +70,7 @@ public: basic_istream& getline(char_type* s, streamsize n, char_type delim); basic_istream& ignore(streamsize n = 1, int_type delim = traits_type::eof()); + basic_istream& ignore(streamsize n, char_type delim); // Since C++26, implemented as a DR int_type peek(); basic_istream& read (char_type* s, streamsize n); streamsize readsome(char_type* s, streamsize n); @@ -172,6 +173,7 @@ template <class Stream, class T> # include <__type_traits/conjunction.h> # include <__type_traits/enable_if.h> # include <__type_traits/is_base_of.h> +# include <__type_traits/is_same.h> # include <__type_traits/make_unsigned.h> # include <__utility/declval.h> # include <__utility/forward.h> @@ -292,6 +294,10 @@ public: basic_istream& getline(char_type* __s, streamsize __n, char_type __dlm); basic_istream& ignore(streamsize __n = 1, int_type __dlm = traits_type::eof()); + template <class _Tp = char_type, __enable_if_t<is_same<_Tp, char>::value, int> = 0> + _LIBCPP_HIDE_FROM_ABI basic_istream& ignore(streamsize __n, char_type __delim) { + return ignore(__n, traits_type::to_int_type(__delim)); + } int_type peek(); basic_istream& read(char_type* __s, streamsize __n); streamsize readsome(char_type* __s, streamsize __n); diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index dc19333..93d43f8 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1225,6 +1225,7 @@ module std [system] { header "deque" export * export std.iterator.reverse_iterator + export std.algorithm.simd_utils // This is a workaround for https://llvm.org/PR120108. } module exception { @@ -1847,7 +1848,10 @@ module std [system] { module ranges { module access { header "__ranges/access.h" } - module all { header "__ranges/all.h" } + module all { + header "__ranges/all.h" + export std.ranges.ref_view + } module as_rvalue_view { header "__ranges/as_rvalue_view.h" } module chunk_by_view { header "__ranges/chunk_by_view.h" @@ -2235,6 +2239,7 @@ module std [system] { header "vector" export std.iterator.reverse_iterator export * + export std.algorithm.simd_utils // This is a workaround for https://llvm.org/PR120108. } // Experimental C++ Standard Library interfaces diff --git a/libcxx/include/string b/libcxx/include/string index 729a420..cfd6861 100644 --- a/libcxx/include/string +++ b/libcxx/include/string @@ -2552,7 +2552,7 @@ _LIBCPP_STRING_V1_EXTERN_TEMPLATE_LIST(_LIBCPP_DECLARE, wchar_t) # endif # undef _LIBCPP_DECLARE -# if _LIBCPP_STD_VER <= 17 || !__has_builtin(__builtin_lt_synthesises_from_spaceship) +# if _LIBCPP_STD_VER <= 17 || !__has_builtin(__builtin_lt_synthesizes_from_spaceship) template <class _CharT, class _Traits, class _Alloc> struct __default_three_way_comparator<basic_string<_CharT, _Traits, _Alloc>, basic_string<_CharT, _Traits, _Alloc> > { using __string_t _LIBCPP_NODEBUG = basic_string<_CharT, _Traits, _Alloc>; diff --git a/libcxx/test/benchmarks/algorithms/nonmodifying/find.bench.cpp b/libcxx/test/benchmarks/algorithms/nonmodifying/find.bench.cpp index b2ead1c..afea31f 100644 --- a/libcxx/test/benchmarks/algorithms/nonmodifying/find.bench.cpp +++ b/libcxx/test/benchmarks/algorithms/nonmodifying/find.bench.cpp @@ -51,6 +51,7 @@ int main(int argc, char** argv) { // find bm.template operator()<std::vector<char>>("std::find(vector<char>) (" + comment + ")", std_find); bm.template operator()<std::vector<int>>("std::find(vector<int>) (" + comment + ")", std_find); + bm.template operator()<std::vector<long long>>("std::find(vector<long long>) (" + comment + ")", std_find); bm.template operator()<std::deque<int>>("std::find(deque<int>) (" + comment + ")", std_find); bm.template operator()<std::list<int>>("std::find(list<int>) (" + comment + ")", std_find); diff --git a/libcxx/test/libcxx/utilities/utility/has_default_three_way.compile.pass.cpp b/libcxx/test/libcxx/utilities/utility/has_default_three_way.compile.pass.cpp index 42b4855..625b194 100644 --- a/libcxx/test/libcxx/utilities/utility/has_default_three_way.compile.pass.cpp +++ b/libcxx/test/libcxx/utilities/utility/has_default_three_way.compile.pass.cpp @@ -18,7 +18,7 @@ static_assert(std::__has_default_three_way_comparator<long, int>::value); static_assert(std::__has_default_three_way_comparator<long, long>::value); static_assert(std::__has_default_three_way_comparator<std::string, std::string>::value); -#if __has_builtin(__builtin_lt_synthesises_from_spaceship) +#if __has_builtin(__builtin_lt_synthesizes_from_spaceship) static_assert(std::__has_default_three_way_comparator<const std::string&, const std::string&>::value); static_assert(std::__has_default_three_way_comparator<const std::string&, const std::string_view&>::value); static_assert(std::__has_default_three_way_comparator<std::string, std::string_view>::value); diff --git a/libcxx/test/std/containers/sequences/vector/common.h b/libcxx/test/std/containers/sequences/vector/common.h index 4af6559..34453f8 100644 --- a/libcxx/test/std/containers/sequences/vector/common.h +++ b/libcxx/test/std/containers/sequences/vector/common.h @@ -214,10 +214,10 @@ struct throwing_iterator { }; inline void check_new_delete_called() { - assert(globalMemCounter.new_called == globalMemCounter.delete_called); - assert(globalMemCounter.new_array_called == globalMemCounter.delete_array_called); - assert(globalMemCounter.aligned_new_called == globalMemCounter.aligned_delete_called); - assert(globalMemCounter.aligned_new_array_called == globalMemCounter.aligned_delete_array_called); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.new_called == globalMemCounter.delete_called); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.new_array_called == globalMemCounter.delete_array_called); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.aligned_new_called == globalMemCounter.aligned_delete_called); + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.aligned_new_array_called == globalMemCounter.aligned_delete_array_called); } template <class T, typename Alloc> diff --git a/libcxx/test/std/input.output/filesystems/class.path/path.member/path.append.pass.cpp b/libcxx/test/std/input.output/filesystems/class.path/path.member/path.append.pass.cpp index 3442019..b3d96c2 100644 --- a/libcxx/test/std/input.output/filesystems/class.path/path.member/path.append.pass.cpp +++ b/libcxx/test/std/input.output/filesystems/class.path/path.member/path.append.pass.cpp @@ -12,6 +12,11 @@ // These tests require locale for non-char paths // UNSUPPORTED: no-localization +// In MinGW mode, with optimizations enabled with a DLL, the number of counted +// allocations mismatches, as some ctor/dtor calls are generated in the +// calling code, and some are called from the DLL. +// ADDITIONAL_COMPILE_FLAGS: -DALLOW_MISMATCHING_LIBRRARY_INTERNAL_ALLOCATIONS + // <filesystem> // class path diff --git a/libcxx/test/std/input.output/filesystems/class.path/path.member/path.concat.pass.cpp b/libcxx/test/std/input.output/filesystems/class.path/path.member/path.concat.pass.cpp index 5596de7..570d303 100644 --- a/libcxx/test/std/input.output/filesystems/class.path/path.member/path.concat.pass.cpp +++ b/libcxx/test/std/input.output/filesystems/class.path/path.member/path.concat.pass.cpp @@ -12,6 +12,11 @@ // These tests require locale for non-char paths // UNSUPPORTED: no-localization +// In MinGW mode, with optimizations enabled with a DLL, the number of counted +// allocations mismatches, as some ctor/dtor calls are generated in the +// calling code, and some are called from the DLL. +// ADDITIONAL_COMPILE_FLAGS: -DALLOW_MISMATCHING_LIBRRARY_INTERNAL_ALLOCATIONS + // <filesystem> // class path diff --git a/libcxx/test/std/input.output/iostream.format/input.streams/istream.unformatted/ignore.char_type.pass.cpp b/libcxx/test/std/input.output/iostream.format/input.streams/istream.unformatted/ignore.char_type.pass.cpp new file mode 100644 index 0000000..d0d174c --- /dev/null +++ b/libcxx/test/std/input.output/iostream.format/input.streams/istream.unformatted/ignore.char_type.pass.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// Requires 396145d in the built library. +// XFAIL: using-built-library-before-llvm-9 +// XFAIL: FROZEN-CXX03-HEADERS-FIXME + +// <istream> + +// basic_istream& ignore(streamsize n, char_type delim); + +#include <cassert> +#include <sstream> +#include <string> + +#include "test_macros.h" + +int main(int, char**) { + std::istringstream in("\xF0\x9F\xA4\xA1 Clown Face"); + in.ignore(100, '\xA1'); // Ignore up to '\xA1' delimiter, + // previously might have ignored to EOF. + + assert(in.gcount() == 4); // 4 bytes were ignored. + assert(in.peek() == ' '); // Next character is a space. + + std::string str; // Read the next word. + in >> str; + assert(str == "Clown"); + + // Parameter value "-1L" doesn't cause ambiguity with the char_type overload. + in.ignore(100, -1L); // Ignore up to EOF, which is the default behavior. + assert(in.eof()); // Stream should be at EOF now. + assert(in.gcount() == 5); + + return 0; +} diff --git a/libcxx/test/support/count_new.h b/libcxx/test/support/count_new.h index c8169d3..f175bc2 100644 --- a/libcxx/test/support/count_new.h +++ b/libcxx/test/support/count_new.h @@ -626,7 +626,11 @@ struct RequireAllocationGuard { void requireExactly(std::size_t N) { m_req_alloc = N; m_exactly = true; } ~RequireAllocationGuard() { +#ifdef ALLOW_MISMATCHING_LIBRRARY_INTERNAL_ALLOCATIONS + ASSERT_WITH_LIBRARY_INTERNAL_ALLOCATIONS(globalMemCounter.checkOutstandingNewEq(static_cast<int>(m_outstanding_new_on_init))); +#else assert(globalMemCounter.checkOutstandingNewEq(static_cast<int>(m_outstanding_new_on_init))); +#endif std::size_t Expect = m_new_count_on_init + m_req_alloc; assert(globalMemCounter.checkNewCalledEq(static_cast<int>(Expect)) || (!m_exactly && globalMemCounter.checkNewCalledGreaterThan(static_cast<int>(Expect)))); diff --git a/libcxx/utils/find-rerun-candidates b/libcxx/utils/find-rerun-candidates new file mode 100755 index 0000000..5ac2644 --- /dev/null +++ b/libcxx/utils/find-rerun-candidates @@ -0,0 +1,242 @@ +#!/usr/bin/env python3 + +import argparse +import datetime +import functools +import os +import pathlib +import re +import statistics +import subprocess +import sys + +import git +import pandas +import tqdm + +@functools.total_ordering +class Commit: + """ + This class represents a commit inside a given Git repository. + """ + + def __init__(self, git_repo, sha): + self._git_repo = git_repo + self._sha = sha + + def __eq__(self, other): + """ + Return whether two commits refer to the same commit. + + This doesn't take into account the content of the Git tree at those commits, only the + 'identity' of the commits themselves. + """ + return self.fullrev == other.fullrev + + def __lt__(self, other): + """ + Return whether a commit is an ancestor of another commit in the Git repository. + """ + # Is self._sha an ancestor of other._sha? + res = subprocess.run(['git', '-C', self._git_repo, 'merge-base', '--is-ancestor', self._sha, other._sha]) + if res.returncode not in (0, 1): + raise RuntimeError(f'Error when trying to obtain the commit order for {self._sha} and {other._sha}') + return res.returncode == 0 + + def __hash__(self): + """ + Return the full revision for this commit. + """ + return hash(self.fullrev) + + @functools.cache + def show(self, include_diff=False): + """ + Return the commit information equivalent to `git show` associated to this commit. + """ + cmd = ['git', '-C', self._git_repo, 'show', self._sha] + if not include_diff: + cmd.append('--no-patch') + return subprocess.check_output(cmd, text=True) + + @functools.cached_property + def shortrev(self): + """ + Return the shortened version of the given SHA. + """ + return subprocess.check_output(['git', '-C', self._git_repo, 'rev-parse', '--short', self._sha], text=True).strip() + + @functools.cached_property + def fullrev(self): + """ + Return the full SHA associated to this commit. + """ + return subprocess.check_output(['git', '-C', self._git_repo, 'rev-parse', self._sha], text=True).strip() + + @functools.cached_property + def commit_date(self): + """ + Return the date of the commit as a `datetime.datetime` object. + """ + repo = git.Repo(self._git_repo) + return datetime.datetime.fromtimestamp(repo.commit(self._sha).committed_date) + + def prefetch(self): + """ + Prefetch cached properties associated to this commit object. + + This makes it possible to control when time is spent recovering that information from Git for + e.g. better reporting to the user. + """ + self.commit_date + self.fullrev + self.shortrev + self.show() + + def __str__(self): + return self._sha + +def directory_path(string): + if os.path.isdir(string): + return pathlib.Path(string) + else: + raise NotADirectoryError(string) + +def parse_lnt(lines, aggregate=statistics.median): + """ + Parse lines in LNT format and return a list of dictionnaries of the form: + + [ + { + 'benchmark': <benchmark1>, + <metric1>: [float], + <metric2>: [float], + 'data_points': int, + ... + }, + { + 'benchmark': <benchmark2>, + <metric1>: [float], + <metric2>: [float], + 'data_points': int, + ... + }, + ... + ] + + If a metric has multiple values associated to it, they are aggregated into a single + value using the provided aggregation function. + """ + results = {} + for line in lines: + line = line.strip() + if not line: + continue + + (identifier, value) = line.split(' ') + (benchmark, metric) = identifier.split('.') + if benchmark not in results: + results[benchmark] = {'benchmark': benchmark} + + entry = results[benchmark] + if metric not in entry: + entry[metric] = [] + entry[metric].append(float(value)) + + for (bm, entry) in results.items(): + metrics = [key for key in entry if isinstance(entry[key], list)] + min_data_points = min(len(entry[metric]) for metric in metrics) + for metric in metrics: + entry[metric] = aggregate(entry[metric]) + entry['data_points'] = min_data_points + + return list(results.values()) + +def sorted_revlist(git_repo, commits): + """ + Return the list of commits sorted by their chronological order (from oldest to newest) in the + provided Git repository. Items earlier in the list are older than items later in the list. + """ + revlist_cmd = ['git', '-C', git_repo, 'rev-list', '--no-walk'] + list(commits) + revlist = subprocess.check_output(revlist_cmd, text=True).strip().splitlines() + return list(reversed(revlist)) + +def main(argv): + parser = argparse.ArgumentParser( + prog='find-rerun-candidates', + description='Find benchmarking data points that are good candidates for additional runs, to reduce noise.') + parser.add_argument('directory', type=directory_path, + help='Path to a valid directory containing benchmark data in LNT format, each file being named <commit>.lnt. ' + 'This is also the format generated by the `benchmark-historical` utility.') + parser.add_argument('--metric', type=str, default='execution_time', + help='The metric to analyze. LNT data may contain multiple metrics (e.g. code size, execution time, etc) -- ' + 'this option allows selecting which metric is analyzed for rerun candidates. The default is "execution_time".') + parser.add_argument('--filter', type=str, required=False, + help='An optional regular expression used to filter the benchmarks included in the analysis. ' + 'Only benchmarks whose names match the regular expression will be analyzed.') + parser.add_argument('--outlier-threshold', metavar='FLOAT', type=float, default=0.1, + help='Relative difference from the previous points for considering a data point as an outlier. This threshold is ' + 'expressed as a floating point number, e.g. 0.25 will detect points that differ by more than 25%% from their ' + 'previous result.') + parser.add_argument('--data-points-threshold', type=int, required=False, + help='Number of data points above which an outlier is not considered an outlier. If an outlier has more than ' + 'that number of data points yet its relative difference is above the threshold, it is not considered an ' + 'outlier. This can be used to re-run noisy data points until we have at least N samples, at which point ' + 'we consider the data to be accurate, even if the result is beyond the threshold. By default, there is ' + 'no limit on the number of data points.') + parser.add_argument('--git-repo', type=directory_path, default=pathlib.Path(os.getcwd()), + help='Path to the git repository to use for ordering commits in time. ' + 'By default, the current working directory is used.') + args = parser.parse_args(argv) + + # Extract benchmark data from the directory. + data = {} + files = [f for f in args.directory.glob('*.lnt')] + for file in tqdm.tqdm(files, desc='Parsing LNT files'): + rows = parse_lnt(file.read_text().splitlines()) + (commit, _) = os.path.splitext(os.path.basename(file)) + commit = Commit(args.git_repo, commit) + data[commit] = rows + + # Obtain commit information which is then cached throughout the program. Do this + # eagerly so we can provide a progress bar. + for commit in tqdm.tqdm(data.keys(), desc='Prefetching Git information'): + commit.prefetch() + + # Create a dataframe from the raw data and add some columns to it: + # - 'commit' represents the Commit object associated to the results in that row + # - `revlist_order` represents the order of the commit within the Git repository. + revlist = sorted_revlist(args.git_repo, [c.fullrev for c in data.keys()]) + data = pandas.DataFrame([row | {'commit': c} for (c, rows) in data.items() for row in rows]) + data = data.join(pandas.DataFrame([{'revlist_order': revlist.index(c.fullrev)} for c in data['commit']])) + + # Filter the benchmarks if needed. + if args.filter is not None: + keeplist = [b for b in data['benchmark'] if re.search(args.filter, b) is not None] + data = data[data['benchmark'].isin(keeplist)] + + # Detect outliers by selecting all benchmarks whose change percentage is beyond the threshold. + # If we have a max number of points, also take that into account. + if args.data_points_threshold is not None: + print(f'Generating outliers with more than {args.outlier_threshold * 100}% relative difference and less than {args.data_points_threshold} data points') + else: + print(f'Generating outliers with more than {args.outlier_threshold * 100}% relative difference') + + overall = set() + for (benchmark, series) in data.sort_values(by='revlist_order').groupby('benchmark'): + pct_change = series[args.metric].pct_change() + outliers = series[pct_change.abs() > args.outlier_threshold] + if args.data_points_threshold is not None: + outliers = outliers[outliers['data_points'] < args.data_points_threshold] + outliers = set(outliers['commit']) + overall |= outliers + if len(outliers) > 0: + print(f'{benchmark}: {" ".join(c.shortrev for c in outliers)}') + + if len(overall) > 0: + print(f'Summary: {" ".join(c.shortrev for c in overall)}') + else: + print(f'No outliers') + +if __name__ == '__main__': + main(sys.argv[1:]) diff --git a/libcxx/utils/visualize-historical b/libcxx/utils/visualize-historical index ef28e8b..114c7e8 100755 --- a/libcxx/utils/visualize-historical +++ b/libcxx/utils/visualize-historical @@ -213,13 +213,6 @@ def main(argv): 'Since the chart is interactive, it generally makes most sense to include all the benchmarks ' 'and to then filter them in the browser, but in some cases producing a chart with a reduced ' 'number of data series is useful.') - parser.add_argument('--find-outliers', metavar='FLOAT', type=float, required=False, - help='Instead of building a chart, detect commits that show a large spike (more than the given relative threshold) ' - 'with the previous result and print those to standard output. This can be used to generate a list of ' - 'potential outliers that we might want to re-generate the data for. The threshold is expressed as a ' - 'floating point number, e.g. 0.25 will detect points that differ by more than 25%% from their previous ' - 'result. This option respects --filter, i.e. only benchmarks that match the filter will be analyzed for ' - 'outliers.') parser.add_argument('--subtitle', type=str, required=False, help='Optional subtitle for the chart. This can be used to help identify the contents of the chart.') parser.add_argument('--git-repo', type=directory_path, default=pathlib.Path(os.getcwd()), @@ -258,16 +251,6 @@ def main(argv): keeplist = [b for b in data['benchmark'] if re.search(args.filter, b) is not None] data = data[data['benchmark'].isin(keeplist)] - # If requested, perform a basic pass to detect outliers. - # Note that we consider a commit to be an outlier if any of the benchmarks for that commit is an outlier. - if args.find_outliers is not None: - threshold = args.find_outliers - outliers = set() - for (benchmark, series) in data.sort_values(by='revlist_order').groupby('benchmark'): - outliers |= set(series[series[args.metric].pct_change() > threshold]['commit']) - print(f'Outliers (more than {threshold * 100}%): {" ".join(c.shortrev for c in outliers)}') - return - # Plot the data for all the required benchmarks. figure = create_plot(data, args.metric, subtitle=args.subtitle) do_open = args.output is None or args.open |