[libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators #132665

winner245 · 2025-03-24T04:03:13Z

This patch optimizes std::fill, std::fill_n, std::ranges::fill, and std::ranges::fill_n for segmented iterators, achieving substantial performance improvements. Specifically, for deque<int> iterators, the performance improvements are above 10x for all these algorithms. The optimization also enables filling segmented memory of deque<int> to approach the performance of filling contiguous memory of vector<int>.

Benchmark results comparing the before and after implementations are provided below. For additional context, we’ve included vector<int> results, which remain unchanged, as this patch specifically targets segmented iterators and leaves non-segmented iterator behavior untouched.

Fixes two subtasks outlined in #102817.

`fill_n`

-----------------------------------------------------------------------------
Benchmark                                Before            After      Speedup
-----------------------------------------------------------------------------
std::fill_n(deque<int>)/32              11.4 ns          2.28 ns        5.0x
std::fill_n(deque<int>)/50              19.7 ns          3.40 ns        5.8x
std::fill_n(deque<int>)/1024             391 ns          37.3 ns       10.5x
std::fill_n(deque<int>)/8192            3174 ns           301 ns       10.5x
std::fill_n(deque<int>)/65536          26504 ns          2951 ns        9.0x
std::fill_n(deque<int>)/1048576       407960 ns         80658 ns        5.1x
rng::fill_n(deque<int>)/32              14.3 ns          2.15 ns        6.6x
rng::fill_n(deque<int>)/50              20.2 ns          3.22 ns        6.3x
rng::fill_n(deque<int>)/1024             381 ns          37.8 ns       10.1x
rng::fill_n(deque<int>)/8192            3101 ns           294 ns       10.5x
rng::fill_n(deque<int>)/65536          25098 ns          2926 ns        8.6x
rng::fill_n(deque<int>)/1048576       394342 ns         78874 ns        5.0x
std::fill_n(vector<int>)/32             1.76 ns          1.72 ns        1.0x
std::fill_n(vector<int>)/50             3.00 ns          2.73 ns        1.1x
std::fill_n(vector<int>)/1024           38.4 ns          37.9 ns        1.0x
std::fill_n(vector<int>)/8192            258 ns           252 ns        1.0x
std::fill_n(vector<int>)/65536          2993 ns          2889 ns        1.0x
std::fill_n(vector<int>)/1048576       80328 ns         80468 ns        1.0x
rng::fill_n(vector<int>)/32             1.99 ns          1.35 ns        1.5x
rng::fill_n(vector<int>)/50             2.66 ns          2.12 ns        1.3x
rng::fill_n(vector<int>)/1024           37.7 ns          35.8 ns        1.1x
rng::fill_n(vector<int>)/8192            253 ns           250 ns        1.0x
rng::fill_n(vector<int>)/65536          2922 ns          2930 ns        1.0x
rng::fill_n(vector<int>)/1048576       79739 ns         79742 ns        1.0x

`fill`

--------------------------------------------------------------------------
Benchmark                              Before            After     Speedup
--------------------------------------------------------------------------
std::fill(deque<int>)/32              13.7 ns          2.45 ns        5.6x
std::fill(deque<int>)/50              21.7 ns          4.57 ns        4.7x
std::fill(deque<int>)/1024             367 ns          38.5 ns        9.5x
std::fill(deque<int>)/8192            2896 ns           247 ns       11.7x
std::fill(deque<int>)/65536          23723 ns          2907 ns        8.2x
std::fill(deque<int>)/1048576       379043 ns         79885 ns        4.7x
rng::fill(deque<int>)/32              13.6 ns          2.70 ns        5.0x
rng::fill(deque<int>)/50              23.4 ns          3.94 ns        5.9x
rng::fill(deque<int>)/1024             377 ns          37.9 ns        9.9x
rng::fill(deque<int>)/8192            2914 ns           286 ns       10.2x
rng::fill(deque<int>)/65536          23612 ns          2939 ns        8.0x
rng::fill(deque<int>)/1048576       379841 ns         80079 ns        4.7x
std::fill(vector<int>)/32             1.99 ns          1.79 ns        1.1x
std::fill(vector<int>)/50             3.05 ns          3.06 ns        1.0x
std::fill(vector<int>)/1024           37.6 ns          38.0 ns        1.0x
std::fill(vector<int>)/8192            255 ns           257 ns        1.0x
std::fill(vector<int>)/65536          2966 ns          2981 ns        1.0x
std::fill(vector<int>)/1048576       78300 ns         80348 ns        1.0x
rng::fill(vector<int>)/32             1.77 ns          1.75 ns        1.0x
rng::fill(vector<int>)/50             4.85 ns          2.31 ns        2.1x
rng::fill(vector<int>)/1024           39.6 ns          36.1 ns        1.1x
rng::fill(vector<int>)/8192            238 ns           251 ns        0.9x
rng::fill(vector<int>)/65536          2941 ns          2918 ns        1.0x
rng::fill(vector<int>)/1048576       80497 ns         80442 ns        1.0x

llvmbot · 2025-03-24T17:45:19Z

@llvm/pr-subscribers-libcxx

Author: Peng Liu (winner245)

Changes

This patch optimizes std::fill, std::fill_n}, std::ranges::fill, and std::ranges::fill_n for segmented iterators, achieving substantial performance improvements. Specifically, for deque<int> iterators, the performance improvements are above 10x for all these algorithms. The optimization for segmented iterators is rather effective, as it enables filling segmented memory in deque<int> to match the performance of filling contiguous memory in vector<int>.

Below are the benchmark results comparing the before and after implementations. For reference purposes, we've also provided the benchmarks for vector<int>, though its performance remains unchanged, as this patch focuses solely on segmented iterators and does not modify contiguous memory handling.

Fixes two subtasks outlined in #102817.

`fill_n`

----------------------------------------------------------------------------
Benchmark                                Before           After      Speedup
----------------------------------------------------------------------------
std::fill_n(deque&lt;int&gt;)/32              12.9 ns         3.00 ns         4.3x
std::fill_n(deque&lt;int&gt;)/50              21.0 ns         4.07 ns         5.2x
std::fill_n(deque&lt;int&gt;)/1024             362 ns         39.4 ns         9.2x
std::fill_n(deque&lt;int&gt;)/8192            2945 ns          239 ns        12.3x
std::fill_n(deque&lt;int&gt;)/65536          23760 ns         2891 ns         8.2x
std::fill_n(deque&lt;int&gt;)/1048576       390518 ns        78182 ns         5.0x
rng::fill_n(deque&lt;int&gt;)/32              14.1 ns         3.16 ns         4.5x
rng::fill_n(deque&lt;int&gt;)/50              22.7 ns         4.06 ns         5.6x
rng::fill_n(deque&lt;int&gt;)/1024             382 ns         39.1 ns         9.8x
rng::fill_n(deque&lt;int&gt;)/8192            2984 ns          260 ns        11.5x
rng::fill_n(deque&lt;int&gt;)/65536          23809 ns         2875 ns         8.3x
rng::fill_n(deque&lt;int&gt;)/1048576       377297 ns        78241 ns         4.8x
std::fill_n(vector&lt;int&gt;)/32             1.97 ns         1.56 ns         1.3x
std::fill_n(vector&lt;int&gt;)/50             1.96 ns         2.03 ns         1.0x
std::fill_n(vector&lt;int&gt;)/1024           41.5 ns         43.0 ns         1.0x
std::fill_n(vector&lt;int&gt;)/8192            231 ns          245 ns         0.9x
std::fill_n(vector&lt;int&gt;)/65536          2946 ns         3092 ns         1.0x
std::fill_n(vector&lt;int&gt;)/1048576       73327 ns        78515 ns         0.9x
rng::fill_n(vector&lt;int&gt;)/32             1.81 ns         1.89 ns         1.0x
rng::fill_n(vector&lt;int&gt;)/50             2.68 ns         2.79 ns         1.0x
rng::fill_n(vector&lt;int&gt;)/1024           37.2 ns         37.9 ns         1.0x
rng::fill_n(vector&lt;int&gt;)/8192            251 ns          253 ns         1.0x
rng::fill_n(vector&lt;int&gt;)/65536          2876 ns         2919 ns         1.0x
rng::fill_n(vector&lt;int&gt;)/1048576       78037 ns        78382 ns         1.0x

`fill`

--------------------------------------------------------------------------
Benchmark                               Before          After      Speedup
--------------------------------------------------------------------------
std::fill(deque&lt;int&gt;)/32              13.9 ns         2.99 ns         4.6x
std::fill(deque&lt;int&gt;)/50              20.8 ns         4.38 ns         4.7x
std::fill(deque&lt;int&gt;)/1024             360 ns         36.8 ns         9.8x
std::fill(deque&lt;int&gt;)/8192            2931 ns          223 ns        13.1x
std::fill(deque&lt;int&gt;)/65536          23794 ns         2766 ns         8.6x
std::fill(deque&lt;int&gt;)/1048576       386669 ns        76049 ns         5.1x
rng::fill(deque&lt;int&gt;)/32              14.9 ns         3.87 ns         3.9x
rng::fill(deque&lt;int&gt;)/50              23.3 ns         4.82 ns         4.8x
rng::fill(deque&lt;int&gt;)/1024             376 ns         38.0 ns         9.9x
rng::fill(deque&lt;int&gt;)/8192            2969 ns          251 ns        11.8x
rng::fill(deque&lt;int&gt;)/65536          24008 ns         2827 ns         8.5x
rng::fill(deque&lt;int&gt;)/1048576       381733 ns        77591 ns         4.9x
std::fill(vector&lt;int&gt;)/32             1.81 ns         2.03 ns         0.9x
std::fill(vector&lt;int&gt;)/50             2.61 ns         2.64 ns         1.0x
std::fill(vector&lt;int&gt;)/1024           35.7 ns         36.7 ns         1.0x
std::fill(vector&lt;int&gt;)/8192            241 ns          243 ns         1.0x
std::fill(vector&lt;int&gt;)/65536          2766 ns         2849 ns         1.0x
std::fill(vector&lt;int&gt;)/1048576       76281 ns        77685 ns         1.0x
rng::fill(vector&lt;int&gt;)/32             1.73 ns         1.69 ns         1.0x
rng::fill(vector&lt;int&gt;)/50             2.27 ns         2.25 ns         1.0x
rng::fill(vector&lt;int&gt;)/1024           35.2 ns         35.4 ns         1.0x
rng::fill(vector&lt;int&gt;)/8192            246 ns          246 ns         1.0x
rng::fill(vector&lt;int&gt;)/65536          2843 ns         2900 ns         1.0x
rng::fill(vector&lt;int&gt;)/1048576       77900 ns        78126 ns         1.0x

Full diff: https://github.com/llvm/llvm-project/pull/132665.diff

8 Files Affected:

(modified) libcxx/include/CMakeLists.txt (+1)
(modified) libcxx/include/__algorithm/fill.h (+37-5)
(modified) libcxx/include/__algorithm/fill_n.h (+21-9)
(added) libcxx/include/__fwd/fill.h (+26)
(modified) libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp (+26)
(modified) libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp (+26)
(modified) libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp (+22)
(modified) libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp (+22)

diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt
index a021b9bb44d67..1ac582dcc1614 100644
--- a/libcxx/include/CMakeLists.txt
+++ b/libcxx/include/CMakeLists.txt
@@ -435,6 +435,7 @@ set(files
   __fwd/byte.h
   __fwd/complex.h
   __fwd/deque.h
+  __fwd/fill.h
   __fwd/format.h
   __fwd/fstream.h
   __fwd/functional.h
diff --git a/libcxx/include/__algorithm/fill.h b/libcxx/include/__algorithm/fill.h
index 1ce3eadb013d0..e519022f18084 100644
--- a/libcxx/include/__algorithm/fill.h
+++ b/libcxx/include/__algorithm/fill.h
@@ -10,8 +10,11 @@
 #define _LIBCPP___ALGORITHM_FILL_H
 
 #include <__algorithm/fill_n.h>
+#include <__algorithm/for_each_segment.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/segmented_iterator.h>
+#include <__type_traits/enable_if.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
@@ -21,23 +24,52 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 // fill isn't specialized for std::memset, because the compiler already optimizes the loop to a call to std::memset.
 
-template <class _ForwardIterator, class _Tp>
+template <class _ForwardIterator,
+          class _Sentinel,
+          class _Tp,
+          __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
-__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value, forward_iterator_tag) {
+__fill(_ForwardIterator __first, _Sentinel __last, const _Tp& __value) {
   for (; __first != __last; ++__first)
     *__first = __value;
 }
 
-template <class _RandomAccessIterator, class _Tp>
+template <class _OutIter, class _Tp>
+struct _FillSegment {
+  using _Traits _LIBCPP_NODEBUG = __segmented_iterator_traits<_OutIter>;
+
+  const _Tp& __value_;
+
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 explicit _FillSegment(const _Tp& __value) : __value_(__value) {}
+
+  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void
+  operator()(typename _Traits::__local_iterator __lfirst, typename _Traits::__local_iterator __llast) {
+    std::__fill(__lfirst, __llast, __value_);
+  }
+};
+
+template <class _RandomAccessIterator,
+          class _Tp,
+          __enable_if_t<__has_random_access_iterator_category<_RandomAccessIterator>::value &&
+                            !__is_segmented_iterator<_RandomAccessIterator>::value,
+                        int> = 0>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
-__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value, random_access_iterator_tag) {
+__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value) {
   std::fill_n(__first, __last - __first, __value);
 }
 
+template <class _SegmentedIterator,
+          class _Tp,
+          __enable_if_t<__is_segmented_iterator<_SegmentedIterator>::value, int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
+__fill(_SegmentedIterator __first, _SegmentedIterator __last, const _Tp& __value) {
+  std::__for_each_segment(__first, __last, _FillSegment<_SegmentedIterator, _Tp>(__value));
+}
+
 template <class _ForwardIterator, class _Tp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
 fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
-  std::__fill(__first, __last, __value, typename iterator_traits<_ForwardIterator>::iterator_category());
+  std::__fill(__first, __last, __value);
 }
 
 _LIBCPP_END_NAMESPACE_STD
diff --git a/libcxx/include/__algorithm/fill_n.h b/libcxx/include/__algorithm/fill_n.h
index 0da78e1f38c4c..c492ec882a483 100644
--- a/libcxx/include/__algorithm/fill_n.h
+++ b/libcxx/include/__algorithm/fill_n.h
@@ -12,7 +12,12 @@
 #include <__algorithm/min.h>
 #include <__config>
 #include <__fwd/bit_reference.h>
+#include <__fwd/fill.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/segmented_iterator.h>
 #include <__memory/pointer_traits.h>
+#include <__type_traits/enable_if.h>
 #include <__utility/convert_to_integral.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
@@ -26,9 +31,13 @@ _LIBCPP_BEGIN_NAMESPACE_STD
 
 // fill_n isn't specialized for std::memset, because the compiler already optimizes the loop to a call to std::memset.
 
-template <class _OutputIterator, class _Size, class _Tp>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
-__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value);
+template <class _OutIter, class _Size, class _Tp, __enable_if_t<!__is_segmented_iterator<_OutIter>::value, int> = 0>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutIter
+__fill_n(_OutIter __first, _Size __n, const _Tp& __value) {
+  for (; __n > 0; ++__first, (void)--__n)
+    *__first = __value;
+  return __first;
+}
 
 template <bool _FillVal, class _Cp>
 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
@@ -68,12 +77,15 @@ __fill_n(__bit_iterator<_Cp, false> __first, _Size __n, const bool& __value) {
   return __first + __n;
 }
 
-template <class _OutputIterator, class _Size, class _Tp>
-inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _OutputIterator
-__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value) {
-  for (; __n > 0; ++__first, (void)--__n)
-    *__first = __value;
-  return __first;
+template < class _OutIter,
+           class _Size,
+           class _Tp,
+           __enable_if_t<__is_segmented_iterator<_OutIter>::value && __has_forward_iterator_category<_OutIter>::value,
+                         int> = 0>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _OutIter __fill_n(_OutIter __first, _Size __n, const _Tp& __value) {
+  _OutIter __last = std::next(__first, __n);
+  std::fill(__first, __last, __value);
+  return __last;
 }
 
 template <class _OutputIterator, class _Size, class _Tp>
diff --git a/libcxx/include/__fwd/fill.h b/libcxx/include/__fwd/fill.h
new file mode 100644
index 0000000000000..628c552757201
--- /dev/null
+++ b/libcxx/include/__fwd/fill.h
@@ -0,0 +1,26 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___FWD_FILL_H
+#define _LIBCPP___FWD_FILL_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class _ForwardIterator, class _Tp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
+fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___FWD_FILL_H
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp
index 9b403db85ebf9..0b87f9038e618 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill.pass.cpp
@@ -17,6 +17,8 @@
 #include <array>
 #include <cassert>
 #include <cstddef>
+#include <deque>
+#include <ranges>
 #include <vector>
 
 #include "sized_allocator.h"
@@ -93,6 +95,27 @@ TEST_CONSTEXPR_CXX20 bool test_vector_bool(std::size_t N) {
   return true;
 }
 
+/*TEST_CONSTEXPR_CXX23*/ void
+test_segmented_iterator() { // TODO: Mark this test as TEST_CONSTEXPR_CXX23 when std::deque is constexpr
+  {                         // std::deque iterator
+    std::deque<int> in(20);
+    std::deque<int> expected(in.size(), 42);
+    std::fill(in.begin(), in.end(), 42);
+    assert(in == expected);
+  }
+
+#if TEST_STD_VER >= 20
+  { // join_view iterator
+    std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {0, 0}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}};
+    auto jv = std::ranges::join_view(v);
+    std::fill(jv.begin(), jv.end(), 42);
+    for (const auto& vec : v)
+      for (auto n : vec)
+        assert(n == 42);
+  }
+#endif
+}
+
 TEST_CONSTEXPR_CXX20 bool test() {
   types::for_each(types::forward_iterator_list<char*>(), Test<char>());
   types::for_each(types::forward_iterator_list<int*>(), Test<int>());
@@ -138,6 +161,9 @@ TEST_CONSTEXPR_CXX20 bool test() {
     }
   }
 
+  if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED when std::deque is made constexpr
+    test_segmented_iterator();
+
   return true;
 }
 
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp
index 4dda8714d2cfa..3d397bc6c9f06 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/fill_n.pass.cpp
@@ -17,6 +17,8 @@
 #include <array>
 #include <cassert>
 #include <cstddef>
+#include <deque>
+#include <ranges>
 #include <vector>
 
 #include "sized_allocator.h"
@@ -176,6 +178,27 @@ TEST_CONSTEXPR_CXX20 void test_struct_array() {
   }
 }
 
+/*TEST_CONSTEXPR_CXX23*/ void
+test_segmented_iterator() { // TODO: Mark this test as TEST_CONSTEXPR_CXX23 when std::deque is constexpr
+  {                         // std::deque iterator
+    std::deque<int> in(20);
+    std::deque<int> expected(in.size(), 42);
+    std::fill_n(in.begin(), in.size(), 42);
+    assert(in == expected);
+  }
+
+#if TEST_STD_VER >= 20
+  { // join_view iterator
+    std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {0, 0}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}};
+    auto jv = std::ranges::join_view(v);
+    std::fill_n(jv.begin(), std::distance(jv.begin(), jv.end()), 42);
+    for (const auto& vec : v)
+      for (auto n : vec)
+        assert(n == 42);
+  }
+#endif
+}
+
 TEST_CONSTEXPR_CXX20 bool test() {
   types::for_each(types::forward_iterator_list<char*>(), Test<char>());
   types::for_each(types::forward_iterator_list<int*>(), Test<int>());
@@ -225,6 +248,9 @@ TEST_CONSTEXPR_CXX20 bool test() {
     }
   }
 
+  if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED when std::deque is made constexpr
+    test_segmented_iterator();
+
   return true;
 }
 
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp
index 61a659fb0028c..e610fd3c3cb06 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill.pass.cpp
@@ -18,6 +18,7 @@
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
 #include <string>
 #include <vector>
@@ -128,6 +129,24 @@ constexpr bool test_vector_bool(std::size_t N) {
 }
 #endif
 
+/*TEST_CONSTEXPR_CXX23*/ void
+test_segmented_range() { // TODO: Mark this test as TEST_CONSTEXPR_CXX23 when std::deque is constexpr
+  {                      // std::deque
+    std::deque<int> in(20);
+    std::deque<int> expected(in.size(), 42);
+    std::ranges::fill(in, 42);
+    assert(in == expected);
+  }
+  { // join_view
+    std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {0, 0}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}};
+    auto jv = std::ranges::join_view(v);
+    std::ranges::fill(jv, 42);
+    for (const auto& vec : v)
+      for (auto n : vec)
+        assert(n == 42);
+  }
+}
+
 constexpr bool test() {
   test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();
   test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();
@@ -227,6 +246,9 @@ constexpr bool test() {
   }
 #endif
 
+  if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED when std::deque is made constexpr
+    test_segmented_range();
+
   return true;
 }
 
diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp
index 2d6e24a03e0b3..2c7b0fe091c04 100644
--- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/ranges.fill_n.pass.cpp
@@ -16,6 +16,7 @@
 #include <algorithm>
 #include <array>
 #include <cassert>
+#include <deque>
 #include <ranges>
 #include <string>
 #include <vector>
@@ -101,6 +102,24 @@ constexpr bool test_vector_bool(std::size_t N) {
 }
 #endif
 
+/*TEST_CONSTEXPR_CXX23*/ void
+test_segmented_range() { // TODO: Mark this test as TEST_CONSTEXPR_CXX23 when std::deque is constexpr
+  {                      // std::deque
+    std::deque<int> in(20);
+    std::deque<int> expected(in.size(), 42);
+    std::ranges::fill_n(std::ranges::begin(in), std::ranges::size(in), 42);
+    assert(in == expected);
+  }
+  { // join_view
+    std::vector<std::vector<int>> v{{1, 2}, {1, 2, 3}, {0, 0}, {3, 4, 5}, {6}, {7, 8, 9, 6}, {0, 1, 2, 3, 0, 1, 2}};
+    auto jv = std::ranges::join_view(v);
+    std::ranges::fill_n(std::ranges::begin(jv), std::ranges::distance(jv), 42);
+    for (const auto& vec : v)
+      for (auto n : vec)
+        assert(n == 42);
+  }
+}
+
 constexpr bool test() {
   test_iterators<cpp17_output_iterator<int*>, sentinel_wrapper<cpp17_output_iterator<int*>>>();
   test_iterators<cpp20_output_iterator<int*>, sentinel_wrapper<cpp20_output_iterator<int*>>>();
@@ -175,6 +194,9 @@ constexpr bool test() {
   }
 #endif
 
+  if (!TEST_IS_CONSTANT_EVALUATED) // TODO: Use TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED when std::deque is made constexpr
+    test_segmented_range();
+
   return true;
 }

libcxx/include/__algorithm/fill_fill_n_common.h

ldionne

LGTM with a minor change. Thanks for the optimization!

libcxx/include/__algorithm/fill_n.h

ldionne · 2025-08-01T15:58:41Z

Removing from the LLVM 21 release since this missed the branch point. I'll merge this when CI is done running and this will make LLVM 22 though.

libcxx/include/__algorithm/fill.h

github-actions · 2025-10-15T11:11:06Z

✅ With the latest revision this PR passed the C/C++ code formatter.

Michael137 · 2025-10-16T06:43:36Z

There's weird lldb-api test failure....

Example 1

2025-10-15T14:11:22.1682762Z FAIL: lldb-api :: commands/expression/import-std-module/array/TestArrayFromStdModule.py (386 of 1311)
2025-10-15T14:11:22.1685275Z ******************** TEST 'lldb-api :: commands/expression/import-std-module/array/TestArrayFromStdModule.py' FAILED ********************
2025-10-15T14:11:22.1690783Z Script:
2025-10-15T14:11:22.1733631Z --
2025-10-15T14:11:22.1748819Z /usr/bin/python3.10 /home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/dotest.py -u CXXFLAGS -u CFLAGS --env LLVM_LIBS_DIR=/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./lib --env LLVM_INCLUDE_DIR=/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/include --env LLVM_TOOLS_DIR=/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin --libcxx-include-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/include/c++/v1 --libcxx-include-target-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/include/x86_64-pc-linux-gnu/c++/v1 --libcxx-library-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./lib/x86_64-pc-linux-gnu --arch x86_64 --build-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/lldb-test-build.noindex --lldb-module-cache-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin/lldb --compiler /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin/clang --dsymutil /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin/dsymutil --make /usr/bin/gmake --llvm-tools-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin --lldb-obj-root /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/tools/lldb --lldb-libs-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./lib --cmake-build-type Release --category libc++ /home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/commands/expression/import-std-module/array -p TestArrayFromStdModule.py
2025-10-15T14:11:22.1782392Z --
2025-10-15T14:11:22.1782806Z Exit Code: 1
2025-10-15T14:11:22.1783018Z 
2025-10-15T14:11:22.1783168Z Command Output (stdout):
2025-10-15T14:11:22.1783524Z --
2025-10-15T14:11:22.1784525Z lldb version 22.0.0git (https://github.com/llvm/llvm-project revision 3a44bb8cd476316ee7fa3673cb1d1769b7f8df1a)
2025-10-15T14:11:22.1785503Z   clang revision 3a44bb8cd476316ee7fa3673cb1d1769b7f8df1a
2025-10-15T14:11:22.1786073Z   llvm revision 3a44bb8cd476316ee7fa3673cb1d1769b7f8df1a
2025-10-15T14:11:22.1786848Z Skipping the following test categories: ['msvcstl', 'dsym', 'gmodules', 'debugserver', 'objc']
2025-10-15T14:11:22.1787554Z 
2025-10-15T14:11:22.1787665Z --
2025-10-15T14:11:22.1787958Z Command Output (stderr):
2025-10-15T14:11:22.1788303Z --
2025-10-15T14:11:22.1790024Z UNSUPPORTED: LLDB (/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang-x86_64) :: test_dsym (TestArrayFromStdModule.TestCase) (test case does not fall in any category of interest for this run) 
2025-10-15T14:11:22.1792485Z FAIL: LLDB (/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang-x86_64) :: test_dwarf (TestArrayFromStdModule.TestCase)
2025-10-15T14:11:22.1794388Z FAIL: LLDB (/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang-x86_64) :: test_dwo (TestArrayFromStdModule.TestCase)
2025-10-15T14:11:22.1795529Z ======================================================================
2025-10-15T14:11:22.1796012Z FAIL: test_dwarf (TestArrayFromStdModule.TestCase)
2025-10-15T14:11:22.1796546Z ----------------------------------------------------------------------
2025-10-15T14:11:22.1797068Z Traceback (most recent call last):
2025-10-15T14:11:22.1798424Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 1804, in test_method
2025-10-15T14:11:22.1799484Z     return attrvalue(self)
2025-10-15T14:11:22.1801300Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-15T14:11:22.1802353Z     return func(*args, **kwargs)
2025-10-15T14:11:22.1803361Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-15T14:11:22.1804421Z     return func(*args, **kwargs)
2025-10-15T14:11:22.1805621Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/commands/expression/import-std-module/array/TestArrayFromStdModule.py", line 45, in test
2025-10-15T14:11:22.1806993Z     self.expect_expr("a.front()", result_type=value_type, result_value="3")
2025-10-15T14:11:22.1808423Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 2572, in expect_expr
2025-10-15T14:11:22.1809623Z     value_check.check_value(self, eval_result, str(eval_result))
2025-10-15T14:11:22.1810964Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 313, in check_value
2025-10-15T14:11:22.1812185Z     test_base.assertEqual(self.expect_value, val.GetValue(), this_error_msg)
2025-10-15T14:11:22.1812996Z AssertionError: '3' != None : $2 = <invalid type>
2025-10-15T14:11:22.1813491Z Checking SBValue: $2 = <invalid type>
2025-10-15T14:11:22.1814291Z Config=x86_64-/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang
2025-10-15T14:11:22.1815087Z ======================================================================
2025-10-15T14:11:22.1815603Z FAIL: test_dwo (TestArrayFromStdModule.TestCase)
2025-10-15T14:11:22.1816095Z ----------------------------------------------------------------------
2025-10-15T14:11:22.1816692Z Traceback (most recent call last):
2025-10-15T14:11:22.1817627Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 1804, in test_method
2025-10-15T14:11:22.1818498Z     return attrvalue(self)
2025-10-15T14:11:22.1819308Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-15T14:11:22.1820371Z     return func(*args, **kwargs)
2025-10-15T14:11:22.1821383Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-15T14:11:22.1822320Z     return func(*args, **kwargs)
2025-10-15T14:11:22.1824058Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/commands/expression/import-std-module/array/TestArrayFromStdModule.py", line 45, in test
2025-10-15T14:11:22.1825362Z     self.expect_expr("a.front()", result_type=value_type, result_value="3")
2025-10-15T14:11:22.1826552Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 2572, in expect_expr
2025-10-15T14:11:22.1827748Z     value_check.check_value(self, eval_result, str(eval_result))
2025-10-15T14:11:22.1828783Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 313, in check_value
2025-10-15T14:11:22.1830084Z     test_base.assertEqual(self.expect_value, val.GetValue(), this_error_msg)
2025-10-15T14:11:22.1830698Z AssertionError: '3' != None : $2 = <invalid type>
2025-10-15T14:11:22.1831148Z Checking SBValue: $2 = <invalid type>
2025-10-15T14:11:22.1831920Z Config=x86_64-/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang
2025-10-15T14:11:22.1833084Z ----------------------------------------------------------------------
2025-10-15T14:11:22.1833739Z Ran 3 tests in 7.151s
2025-10-15T14:11:22.1833944Z 
2025-10-15T14:11:22.1834088Z FAILED (failures=2, skipped=1)
2025-10-15T14:11:22.1834465Z Failures per category:
2025-10-15T14:11:22.1834770Z libc++ - 2
2025-10-15T14:11:22.1835035Z dwarf - 1
2025-10-15T14:11:22.1835291Z expression - 2
2025-10-15T14:11:22.1835573Z std-module - 2
2025-10-15T14:11:22.1835842Z dwo - 1
2025-10-15T14:11:22.1835991Z 
2025-10-15T14:11:22.1836094Z --

Example 2

2025-10-16T03:01:38.2970672Z FAIL: lldb-api :: commands/expression/import-std-module/array/TestArrayFromStdModule.py (386 of 1313)
2025-10-16T03:01:38.2972722Z ******************** TEST 'lldb-api :: commands/expression/import-std-module/array/TestArrayFromStdModule.py' FAILED ********************
2025-10-16T03:01:38.2989498Z Script:
2025-10-16T03:01:38.2989801Z --
2025-10-16T03:01:38.3003607Z /usr/bin/python3.10 /home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/dotest.py -u CXXFLAGS -u CFLAGS --env LLVM_LIBS_DIR=/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./lib --env LLVM_INCLUDE_DIR=/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/include --env LLVM_TOOLS_DIR=/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin --libcxx-include-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/include/c++/v1 --libcxx-include-target-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/include/x86_64-pc-linux-gnu/c++/v1 --libcxx-library-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./lib/x86_64-pc-linux-gnu --arch x86_64 --build-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/lldb-test-build.noindex --lldb-module-cache-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/lldb-test-build.noindex/module-cache-lldb/lldb-api --clang-module-cache-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/lldb-test-build.noindex/module-cache-clang/lldb-api --executable /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin/lldb --compiler /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin/clang --dsymutil /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin/dsymutil --make /usr/bin/gmake --llvm-tools-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./bin --lldb-obj-root /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/tools/lldb --lldb-libs-dir /home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/./lib --cmake-build-type Release --category libc++ /home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/commands/expression/import-std-module/array -p TestArrayFromStdModule.py
2025-10-16T03:01:38.3017432Z --
2025-10-16T03:01:38.3017680Z Exit Code: 1
2025-10-16T03:01:38.3017866Z 
2025-10-16T03:01:38.3018007Z Command Output (stdout):
2025-10-16T03:01:38.3018346Z --
2025-10-16T03:01:38.3022235Z lldb version 22.0.0git (https://github.com/llvm/llvm-project revision f1c4c1bd541468cd2be0f04ed66c5252c9b13fbd)
2025-10-16T03:01:38.3023236Z   clang revision f1c4c1bd541468cd2be0f04ed66c5252c9b13fbd
2025-10-16T03:01:38.3023838Z   llvm revision f1c4c1bd541468cd2be0f04ed66c5252c9b13fbd
2025-10-16T03:01:38.3024899Z Skipping the following test categories: ['msvcstl', 'dsym', 'gmodules', 'debugserver', 'objc']
2025-10-16T03:01:38.3025486Z 
2025-10-16T03:01:38.3025598Z --
2025-10-16T03:01:38.3025955Z Command Output (stderr):
2025-10-16T03:01:38.3026306Z --
2025-10-16T03:01:38.3027768Z UNSUPPORTED: LLDB (/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang-x86_64) :: test_dsym (TestArrayFromStdModule.TestCase) (test case does not fall in any category of interest for this run) 
2025-10-16T03:01:38.3030256Z FAIL: LLDB (/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang-x86_64) :: test_dwarf (TestArrayFromStdModule.TestCase)
2025-10-16T03:01:38.3032548Z FAIL: LLDB (/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang-x86_64) :: test_dwo (TestArrayFromStdModule.TestCase)
2025-10-16T03:01:38.3033739Z ======================================================================
2025-10-16T03:01:38.3034287Z FAIL: test_dwarf (TestArrayFromStdModule.TestCase)
2025-10-16T03:01:38.3034860Z ----------------------------------------------------------------------
2025-10-16T03:01:38.3035398Z Traceback (most recent call last):
2025-10-16T03:01:38.3036457Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 1804, in test_method
2025-10-16T03:01:38.3037509Z     return attrvalue(self)
2025-10-16T03:01:38.3038492Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-16T03:01:38.3039730Z     return func(*args, **kwargs)
2025-10-16T03:01:38.3042111Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-16T03:01:38.3043170Z     return func(*args, **kwargs)
2025-10-16T03:01:38.3044383Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/commands/expression/import-std-module/array/TestArrayFromStdModule.py", line 45, in test
2025-10-16T03:01:38.3045826Z     self.expect_expr("a.front()", result_type=value_type, result_value="3")
2025-10-16T03:01:38.3047059Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 2572, in expect_expr
2025-10-16T03:01:38.3048509Z     value_check.check_value(self, eval_result, str(eval_result))
2025-10-16T03:01:38.3050117Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 313, in check_value
2025-10-16T03:01:38.3051412Z     test_base.assertEqual(self.expect_value, val.GetValue(), this_error_msg)
2025-10-16T03:01:38.3052192Z AssertionError: '3' != None : $2 = <invalid type>
2025-10-16T03:01:38.3052716Z Checking SBValue: $2 = <invalid type>
2025-10-16T03:01:38.3053561Z Config=x86_64-/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang
2025-10-16T03:01:38.3054407Z ======================================================================
2025-10-16T03:01:38.3054948Z FAIL: test_dwo (TestArrayFromStdModule.TestCase)
2025-10-16T03:01:38.3055508Z ----------------------------------------------------------------------
2025-10-16T03:01:38.3056052Z Traceback (most recent call last):
2025-10-16T03:01:38.3057067Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 1804, in test_method
2025-10-16T03:01:38.3058135Z     return attrvalue(self)
2025-10-16T03:01:38.3059319Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-16T03:01:38.3060372Z     return func(*args, **kwargs)
2025-10-16T03:01:38.3061447Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/decorators.py", line 156, in wrapper
2025-10-16T03:01:38.3062828Z     return func(*args, **kwargs)
2025-10-16T03:01:38.3064032Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/test/API/commands/expression/import-std-module/array/TestArrayFromStdModule.py", line 45, in test
2025-10-16T03:01:38.3065504Z     self.expect_expr("a.front()", result_type=value_type, result_value="3")
2025-10-16T03:01:38.3066725Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 2572, in expect_expr
2025-10-16T03:01:38.3067912Z     value_check.check_value(self, eval_result, str(eval_result))
2025-10-16T03:01:38.3069278Z   File "/home/gha/actions-runner/_work/llvm-project/llvm-project/lldb/packages/Python/lldbsuite/test/lldbtest.py", line 313, in check_value
2025-10-16T03:01:38.3070461Z     test_base.assertEqual(self.expect_value, val.GetValue(), this_error_msg)
2025-10-16T03:01:38.3071365Z AssertionError: '3' != None : $2 = <invalid type>
2025-10-16T03:01:38.3071879Z Checking SBValue: $2 = <invalid type>
2025-10-16T03:01:38.3072791Z Config=x86_64-/home/gha/actions-runner/_work/llvm-project/llvm-project/build/bootstrapping-build/bin/clang
2025-10-16T03:01:38.3073681Z ----------------------------------------------------------------------
2025-10-16T03:01:38.3074193Z Ran 3 tests in 7.287s
2025-10-16T03:01:38.3074417Z 
2025-10-16T03:01:38.3074566Z FAILED (failures=2, skipped=1)
2025-10-16T03:01:38.3074959Z Failures per category:
2025-10-16T03:01:38.3075281Z libc++ - 2
2025-10-16T03:01:38.3075553Z dwarf - 1
2025-10-16T03:01:38.3075844Z expression - 2
2025-10-16T03:01:38.3076136Z std-module - 2
2025-10-16T03:01:38.3076391Z dwo - 1
2025-10-16T03:01:38.3076525Z 
2025-10-16T03:01:38.3076613Z --

@Michael137 Do you have any idea?

Looks like the same issue as: #149477

We'll have to skip the tests like we did in f5022bd until we fix it properly

llvm-ci · 2025-10-17T01:15:29Z

LLVM Buildbot has detected a new failure on builder sanitizer-x86_64-linux-fast running on sanitizer-buildbot3 while building libcxx at step 2 "annotate".

Full details are available at: https://lab.llvm.org/buildbot/#/builders/169/builds/16076

Here is the relevant piece of the build log for the reference

Step 2 (annotate) failure: 'python ../sanitizer_buildbot/sanitizers/zorg/buildbot/builders/sanitizers/buildbot_selector.py' (failure)
...
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using lld-link: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/lld-link
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using ld64.lld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/ld64.lld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using wasm-ld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/wasm-ld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using ld.lld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/ld.lld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using lld-link: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/lld-link
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using ld64.lld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/ld64.lld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using wasm-ld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/wasm-ld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/main.py:74: note: The test suite configuration requested an individual test timeout of 0 seconds but a timeout of 900 seconds was requested on the command line. Forcing timeout to be 900 seconds.
-- Testing: 92728 tests, 64 workers --
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.
FAIL: LLVM :: ExecutionEngine/JITLink/x86-64/MachO_weak_references.s (71993 of 92728)
******************** TEST 'LLVM :: ExecutionEngine/JITLink/x86-64/MachO_weak_references.s' FAILED ********************
Exit Code: -6

Command Output (stdout):
--
# RUN: at line 1
rm -rf /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp && mkdir -p /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp
# executed command: rm -rf /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp
# note: command had no output on stdout or stderr
# executed command: mkdir -p /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp
# note: command had no output on stdout or stderr
# RUN: at line 2
/home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-mc -triple=x86_64-apple-macosx10.9 -filetype=obj -o /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s
# executed command: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-mc -triple=x86_64-apple-macosx10.9 -filetype=obj -o /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s
# note: command had no output on stdout or stderr
# RUN: at line 3
/home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-present -abs bar=0x1 -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# executed command: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-present -abs bar=0x1 -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# note: command had no output on stdout or stderr
# RUN: at line 4
/home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-absent -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# executed command: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-absent -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# .---command stderr------------
# | libc++abi: Pure virtual function called!
# `-----------------------------
# error: command failed with exit status: -6

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
Slowest Tests:
--------------------------------------------------------------------------
191.07s: LLVM :: CodeGen/AMDGPU/sched-group-barrier-pipeline-solver.mir
152.47s: Clang :: Driver/fsanitize.c
109.90s: Clang :: Preprocessor/riscv-target-features.c
88.68s: LLVM :: CodeGen/AMDGPU/amdgcn.bitcast.1024bit.ll
87.43s: Clang :: OpenMP/target_update_codegen.cpp
Step 10 (stage2/asan_ubsan check) failure: stage2/asan_ubsan check (failure)
...
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using lld-link: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/lld-link
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using ld64.lld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/ld64.lld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using wasm-ld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/wasm-ld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using ld.lld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/ld.lld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using lld-link: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/lld-link
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using ld64.lld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/ld64.lld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/llvm/config.py:531: note: using wasm-ld: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/wasm-ld
llvm-lit: /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/utils/lit/lit/main.py:74: note: The test suite configuration requested an individual test timeout of 0 seconds but a timeout of 900 seconds was requested on the command line. Forcing timeout to be 900 seconds.
-- Testing: 92728 tests, 64 workers --
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.
FAIL: LLVM :: ExecutionEngine/JITLink/x86-64/MachO_weak_references.s (71993 of 92728)
******************** TEST 'LLVM :: ExecutionEngine/JITLink/x86-64/MachO_weak_references.s' FAILED ********************
Exit Code: -6

Command Output (stdout):
--
# RUN: at line 1
rm -rf /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp && mkdir -p /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp
# executed command: rm -rf /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp
# note: command had no output on stdout or stderr
# executed command: mkdir -p /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp
# note: command had no output on stdout or stderr
# RUN: at line 2
/home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-mc -triple=x86_64-apple-macosx10.9 -filetype=obj -o /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s
# executed command: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-mc -triple=x86_64-apple-macosx10.9 -filetype=obj -o /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o /home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s
# note: command had no output on stdout or stderr
# RUN: at line 3
/home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-present -abs bar=0x1 -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# executed command: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-present -abs bar=0x1 -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# note: command had no output on stdout or stderr
# RUN: at line 4
/home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-absent -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# executed command: /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/bin/llvm-jitlink -noexec -check-name=jitlink-check-bar-absent -check=/home/b/sanitizer-x86_64-linux-fast/build/llvm-project/llvm/test/ExecutionEngine/JITLink/x86-64/MachO_weak_references.s /home/b/sanitizer-x86_64-linux-fast/build/llvm_build_asan_ubsan/test/ExecutionEngine/JITLink/x86-64/Output/MachO_weak_references.s.tmp/macho_weak_refs.o
# .---command stderr------------
# | libc++abi: Pure virtual function called!
# `-----------------------------
# error: command failed with exit status: -6

--

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90..
Slowest Tests:
--------------------------------------------------------------------------
191.07s: LLVM :: CodeGen/AMDGPU/sched-group-barrier-pipeline-solver.mir
152.47s: Clang :: Driver/fsanitize.c
109.90s: Clang :: Preprocessor/riscv-target-features.c
88.68s: LLVM :: CodeGen/AMDGPU/amdgcn.bitcast.1024bit.ll
87.43s: Clang :: OpenMP/target_update_codegen.cpp

ldionne · 2025-10-17T16:31:13Z

Thanks for merging this @frederick-vs-ja !

winner245 force-pushed the segmented-fill branch 2 times, most recently from 892e5b2 to bb949d4 Compare March 24, 2025 17:43

winner245 added libc++ libc++ C++ Standard Library. Not GNU libstdc++. Not libc++abi. performance labels Mar 24, 2025

winner245 force-pushed the segmented-fill branch 6 times, most recently from 9d18306 to d89bca5 Compare March 25, 2025 01:11

philnik777 reviewed Mar 25, 2025

View reviewed changes

libcxx/include/__algorithm/fill_fill_n_common.h Outdated Show resolved Hide resolved

winner245 marked this pull request as ready for review March 25, 2025 18:06

winner245 requested a review from a team as a code owner March 25, 2025 18:06

winner245 mentioned this pull request Mar 26, 2025

[libc++] P3372R3: constexpr deque #128656

Open

winner245 mentioned this pull request Apr 5, 2025

[libc++] Optimize ranges::{for_each, for_each_n} for segmented iterators #132896

Merged

winner245 force-pushed the segmented-fill branch from d89bca5 to b3a4fd9 Compare June 15, 2025 01:45

winner245 changed the title ~~[libc++] Optimize {std,ranges}::{fill,fill_n} for segmented iterators~~ [libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators Jun 15, 2025

winner245 force-pushed the segmented-fill branch 4 times, most recently from 2df2a8f to 5616913 Compare June 15, 2025 11:40

ldionne approved these changes Jun 24, 2025

View reviewed changes

libcxx/include/__algorithm/fill_n.h Outdated Show resolved Hide resolved

winner245 force-pushed the segmented-fill branch 2 times, most recently from b426e8d to f780dcc Compare June 25, 2025 17:37

winner245 added 2 commits June 28, 2025 14:37

Optimize {std,ranges}::{fill,fill_n} for segmented iterators

4d64875

Improve readability of SFINAE for std::__fill_n

f128d8a

winner245 force-pushed the segmented-fill branch from f780dcc to f128d8a Compare June 28, 2025 18:38

Merge branch 'main' into segmented-fill

8cffb9c

ldionne added this to the LLVM 21.x Release milestone Jul 15, 2025

github-project-automation bot added this to LLVM Release Status Jul 15, 2025

github-project-automation bot moved this to Needs Triage in LLVM Release Status Jul 15, 2025

ldionne approved these changes Jul 15, 2025

View reviewed changes

github-project-automation bot moved this from Needs Triage to Needs Merge in LLVM Release Status Jul 15, 2025

tru moved this from Needs Merge to Done in LLVM Release Status Jul 17, 2025

ldionne added 2 commits August 1, 2025 11:55

Merge branch 'main' into segmented-fill

28495c9

Move release note to LLVM 22 release

c748b85

ldionne removed this from the LLVM 21.x Release milestone Aug 1, 2025

ldionne added the pending-ci Merging the PR is only pending completion of CI label Aug 1, 2025

frederick-vs-ja reviewed Aug 8, 2025

View reviewed changes

libcxx/include/__algorithm/fill.h Outdated Show resolved Hide resolved

frederick-vs-ja added 3 commits October 15, 2025 19:08

Merge branch 'main' into segmented-fill

a6194f9

Update to use __is_segmented_iterator_v

c4ee5fa

Update to use __is_segmented_iterator_v, take 2

cb6e3a7

frederick-vs-ja added 2 commits October 15, 2025 20:10

Update to use __is_segmented_iterator_v, take 3

de5e1dd

Fix the wrong fix about __is_segmented_iterator_v

15be57e

This comment was marked as resolved.

Sign in to view

frederick-vs-ja added 3 commits October 16, 2025 09:06

Merge branch 'main' into segmented-fill

3a083ed

clang-format

8074c26

clang-format, take 2

076f7b4

This comment was marked as resolved.

Sign in to view

Merge branch 'main' into segmented-fill

d1496e5

frederick-vs-ja merged commit d0cee69 into llvm:main Oct 16, 2025
79 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

[libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators #132665

[libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators #132665

Uh oh!

winner245 commented Mar 24, 2025 •

edited

Loading

Uh oh!

llvmbot commented Mar 24, 2025

`fill_n`

`fill`

Uh oh!

Uh oh!

ldionne left a comment

Uh oh!

Uh oh!

ldionne commented Aug 1, 2025

Uh oh!

Uh oh!

github-actions bot commented Oct 15, 2025 •

edited

Loading

Uh oh!

This comment was marked as resolved.

Michael137 commented Oct 16, 2025

Uh oh!

This comment was marked as resolved.

Uh oh!

llvm-ci commented Oct 17, 2025

Uh oh!

ldionne commented Oct 17, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

[libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators #132665

[libc++] Optimize std::{,ranges}::{fill,fill_n} for segmented iterators #132665

Uh oh!

Conversation

winner245 commented Mar 24, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

fill_n

fill

Uh oh!

llvmbot commented Mar 24, 2025

fill_n

fill

Uh oh!

Uh oh!

ldionne left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ldionne commented Aug 1, 2025

Uh oh!

Uh oh!

github-actions bot commented Oct 15, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

This comment was marked as resolved.

Michael137 commented Oct 16, 2025

Uh oh!

This comment was marked as resolved.

Uh oh!

llvm-ci commented Oct 17, 2025

Uh oh!

ldionne commented Oct 17, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

winner245 commented Mar 24, 2025 •

edited

Loading

`fill_n`

`fill`

`fill_n`

`fill`

github-actions bot commented Oct 15, 2025 •

edited

Loading