[libc++] Enable segmented iterator optimizations for join_view::iterator

[philnik]

Here are the benchmark results:

------------------------------------------------------------
Benchmark                                old             new
------------------------------------------------------------
BM_join_view_in_vectors/0           0.701 ns         3.47 ns
BM_join_view_in_vectors/1            16.6 ns         3.75 ns
BM_join_view_in_vectors/2            33.7 ns         5.66 ns
BM_join_view_in_vectors/64           1052 ns          172 ns
BM_join_view_in_vectors/512          8255 ns         1400 ns
BM_join_view_in_vectors/1024        16603 ns         2858 ns
BM_join_view_in_vectors/4000        64662 ns        12452 ns
BM_join_view_in_vectors/4096        66348 ns        12795 ns
BM_join_view_in_vectors/5500        89765 ns        17645 ns
BM_join_view_in_vectors/64000     1234386 ns       617878 ns
BM_join_view_in_vectors/65536     1269340 ns       600301 ns
BM_join_view_in_vectors/70000     1343142 ns       684041 ns
BM_join_view_out_vectors/0          0.699 ns        0.736 ns
BM_join_view_out_vectors/1           16.1 ns         3.79 ns
BM_join_view_out_vectors/2           31.6 ns         5.93 ns
BM_join_view_out_vectors/64           999 ns          161 ns
BM_join_view_out_vectors/512         7932 ns         1457 ns
BM_join_view_out_vectors/1024       15976 ns         2920 ns
BM_join_view_out_vectors/4000       62218 ns        13179 ns
BM_join_view_out_vectors/4096       63710 ns        13419 ns
BM_join_view_out_vectors/5500       85663 ns        18292 ns
BM_join_view_out_vectors/64000    1207589 ns       559316 ns
BM_join_view_out_vectors/65536    1242416 ns       590786 ns
BM_join_view_out_vectors/70000    1257713 ns       683171 ns
BM_join_view_deques/0                3.08 ns         16.1 ns
BM_join_view_deques/1                92.9 ns         19.4 ns
BM_join_view_deques/2                 195 ns         26.2 ns
BM_join_view_deques/64               5703 ns          251 ns
BM_join_view_deques/512             43109 ns         2188 ns
BM_join_view_deques/1024            88938 ns         5401 ns
BM_join_view_deques/4000           360749 ns        27811 ns
BM_join_view_deques/4096           371800 ns        28080 ns
BM_join_view_deques/5500           501057 ns        38059 ns
BM_join_view_deques/64000        10414050 ns      2155094 ns
BM_join_view_deques/65536        10813164 ns      2132998 ns
BM_join_view_deques/70000        11620544 ns      2395421 ns

[ldionne]

This is a neat optimization! I do have some requests for changes, but once those are addressed I think we're on the right track.

libcxx/include/__iterator/iterator_with_data.h

22

This is definitely more complicated, but we need to make this an actual iterator.

libcxx/include/__ranges/join_view.h

73–74

The reason why you're making this change is that otherwise, you can't specialize

template <class ???>
struct __segmented_iterator_traits<???>

Naively, one would want to write

template <class _View, bool _Const>
struct __segmented_iterator_traits<ranges::join_view<_View>::__iterator<_Const>>

but obviously that doesn't work because one cannot specialize on a dependent type, which __iterator is. Technically, it would be possible to use a enable_if that checks for a nested member of the type (e.g. __is_join_view_iterator), but that's not great and it introduces a SFINAE path whenever we instantiate these traits, which is bad for compile-times.

The other option is what you've done here: define the iterator and sentinel types outside of the class. I think that's much better, however it's an ABI break. Fortunately we don't care about this for now because we're still shipping ranges experimentally, but I think we should make this change for all of our existing (and upcoming) views right now to future-proof them.

CC @var-const @huixie90 @Mordante for awareness

276–277

Can this constructor be private? We don't want to expose non-standard APIs, and this iterator type is public, even though its name isn't public.

404–405

This would avoid forming a __segmented_iterator_traits<It> specialization when it would be nonsensical.

406

There's too much iterator-y stuff going on, let's be explicit about this.

429–431

Suggestion? I was thrown off by the *__iter.__inner_;, I thought you were dereferencing the iterator instead of the optional.

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.pass.cpp

124 ↗

(On Diff #476848)

I am worried about this test file becoming a mess if we start putting tests for all the segmented iterators here. Could we perhaps extract them to test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp instead, along with the deque tests?

[philnik]

Address comments

libcxx/include/__ranges/join_view.h

429–431

Unfortunately optional::or_else only available in C++23.

[huixie90]

libcxx/include/__iterator/iterator_with_data.h

44

this can be const?

46

do you need to && qualify this member? otherwise how can we know it can be only called once

79

this is a bit non-standard. Could you please briefly explain why we have a non-const operator*

81–82

questions: do we need iter_move and iter_swap?

[philnik]

Address comments

libcxx/include/__iterator/iterator_with_data.h

79

I'm not sure. Removed it.

81–82

I'm not sure. Added them for completeness.

[philnik]

Try to fix CI

[ldionne]

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp

126

Can you please make sure that we have a test that uses e.g. std::copy with a join_view_iterator that is *not* a segmented iterator?

[ldionne]

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp

126

Specifically, please mess up the constraint on purpose and see what fails. If nothing fails, we're missing coverage and we need to add it.

[philnik]

Try to fix CI

[philnik]

Rebased

libcxx/benchmarks/CMakeLists.txt

set(BENCHMARK_TESTS
     filesystem.bench.cpp
     format_to_n.bench.cpp
     format_to.bench.cpp
     format.bench.cpp
     formatted_size.bench.cpp
     formatter_float.bench.cpp
     formatter_int.bench.cpp
     function.bench.cpp
+    join_view.bench.cpp
     map.bench.cpp
     monotonic_buffer.bench.cpp
     ordered_set.bench.cpp
     std_format_spec_string_unicode.bench.cpp
     string.bench.cpp
     stringstream.bench.cpp
     to_chars.bench.cpp
     unordered_set_operations.bench.cpp

libcxx/benchmarks/join_view.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <deque>
+#include <ranges>
+
+#include "benchmark/benchmark.h"
+
+namespace {
+void run_sizes(auto benchmark) {
+  benchmark->Arg(0)
+      ->Arg(1)
+      ->Arg(2)
+      ->Arg(64)
+      ->Arg(512)
+      ->Arg(1024)
+      ->Arg(4000)
+      ->Arg(4096)
+      ->Arg(5500)
+      ->Arg(64000)
+      ->Arg(65536)
+      ->Arg(70000);
+}
+
+void BM_join_view_in_vectors(benchmark::State& state) {
+  auto size = state.range(0);
+  std::vector<std::vector<int>> input(size, std::vector<int>(32));
+  std::ranges::fill(input | std::views::join, 10);
+  std::vector<int> output;
+  output.resize(size * 32);
+
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(input);
+    benchmark::DoNotOptimize(output);
+    std::ranges::copy(input | std::views::join, output.begin());
+  }
+}
+BENCHMARK(BM_join_view_in_vectors)->Apply(run_sizes);
+
+void BM_join_view_out_vectors(benchmark::State& state) {
+  auto size = state.range(0);
+  std::vector<std::vector<int>> output(size, std::vector<int>(32));
+  std::vector<int> input;
+  input.resize(size * 32);
+  std::ranges::fill(input, 10);
+
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(output);
+    benchmark::DoNotOptimize(input);
+    std::ranges::copy(input, (output | std::views::join).begin());
+  }
+}
+BENCHMARK(BM_join_view_out_vectors)->Apply(run_sizes);
+
+void BM_join_view_deques(benchmark::State& state) {
+  auto size = state.range(0);
+  std::deque<std::deque<int>> deque(size, std::deque<int>(32));
+  std::ranges::fill(deque | std::views::join, 10);
+  std::vector<int> output;
+  output.resize(size * 32);
+
+  for (auto _ : state) {
+    benchmark::DoNotOptimize(deque);
+    benchmark::DoNotOptimize(output);
+    std::ranges::copy(deque | std::views::join, output.begin());
+  }
+}
+BENCHMARK(BM_join_view_deques)->Apply(run_sizes);
+} // namespace
+
+BENCHMARK_MAIN();

libcxx/docs/ReleaseNotes.rst

 -----------------------------
 - Declarations of ``std::c8rtomb()`` and ``std::mbrtoc8()`` from P0482R6 are
   now provided when implementations in the global namespace are provided by
   the C library.
 - Implemented ``<memory_resource>`` header from C++17
 - `D122780 <https://reviews.llvm.org/D122780>`_ Improved the performance of std::sort
 - The ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also optimized for
   ``std::deque<>::iterator``, which can lead to up to 20x performance improvements on certain algorithms.
+- The ``std`` and ``ranges`` versions of ``copy``, ``move``, ``copy_backward`` and ``move_backward`` are now also
+  optimized for ``join_view::iterator``, which can lead to up to 20x performance improvements on certain combinations of
+  iterators and algorithms.
 
 Deprecations and Removals
 -------------------------
 - ``unary_function`` and ``binary_function`` are no longer provided in C++17 and newer Standard modes.
   They can be re-enabled with ``_LIBCPP_ENABLE_CXX17_REMOVED_UNARY_BINARY_FUNCTION``.
 
 - Several incidental transitive includes have been removed from libc++. Those
   includes are removed based on the language version used. Incidental transitive

libcxx/include/CMakeLists.txt

set(files
   __iterator/indirectly_comparable.h
   __iterator/insert_iterator.h
   __iterator/istream_iterator.h
   __iterator/istreambuf_iterator.h
   __iterator/iter_move.h
   __iterator/iter_swap.h
   __iterator/iterator.h
   __iterator/iterator_traits.h
+  __iterator/iterator_with_data.h
   __iterator/mergeable.h
   __iterator/move_iterator.h
   __iterator/move_sentinel.h
   __iterator/next.h
   __iterator/ostream_iterator.h
   __iterator/ostreambuf_iterator.h
   __iterator/permutable.h
   __iterator/prev.h

libcxx/include/__iterator/iterator_with_data.h

+//===----------------------------------------------------------------------===//
+//
+// 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___ITERATOR_ITERATOR_WITH_DATA_H
+#define _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H
+
+#include <__compare/compare_three_way_result.h>
+#include <__compare/three_way_comparable.h>
+#include <__config>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/iter_swap.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/readable_traits.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER >= 20
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <forward_iterator _Iterator, class _Data>
+class __iterator_with_data {
+  _Iterator __iter_{};
+  _Data __data_{};
+
+public:
+  using value_type      = iter_value_t<_Iterator>;
+  using difference_type = iter_difference_t<_Iterator>;
+
+  _LIBCPP_HIDE_FROM_ABI __iterator_with_data() = default;
+
+  constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data(_Iterator __iter, _Data __data)
+      : __iter_(std::move(__iter)), __data_(std::move(__data)) {}
+
+  constexpr _LIBCPP_HIDE_FROM_ABI _Iterator __get_iter() const { return __iter_; }
+
+  constexpr _LIBCPP_HIDE_FROM_ABI _Data __get_data() && { return std::move(__data_); }
+
+  friend constexpr _LIBCPP_HIDE_FROM_ABI bool
+  operator==(const __iterator_with_data& __lhs, const __iterator_with_data& __rhs) {
+    return __lhs.__iter_ == __rhs.__iter_;
+  }
+
+  constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data& operator++() {
+    ++__iter_;
+    return *this;
+  }
+
+  constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data operator++(int) {
+    auto __tmp = *this;
+    __iter_++;
+    return __tmp;
+  }
+
+  constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data& operator--()
+    requires bidirectional_iterator<_Iterator>
+  {
+    --__iter_;
+    return *this;
+  }
+
+  constexpr _LIBCPP_HIDE_FROM_ABI __iterator_with_data operator--(int)
+    requires bidirectional_iterator<_Iterator>
+  {
+    auto __tmp = *this;
+    --__iter_;
+    return __tmp;
+  }
+
+  constexpr _LIBCPP_HIDE_FROM_ABI iter_reference_t<_Iterator> operator*() const { return *__iter_; }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr decltype(auto)
+  iter_move(const __iterator_with_data& __iter) noexcept(noexcept(ranges::iter_move(*__iter.__iter_))) {
+    return ranges::iter_move(*__iter.__iter_);
+  }
+
+  _LIBCPP_HIDE_FROM_ABI friend constexpr void
+  iter_swap(const __iterator_with_data& __lhs,
+            const __iterator_with_data& __rhs) noexcept(noexcept(ranges::iter_swap(*__lhs.__iter_, *__rhs.__iter_)))
+    requires indirectly_swappable<_Iterator>
+  {
+    return ranges::iter_swap(*__lhs.__data_, *__rhs.__iter_);
+  }
+};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 20
+
+#endif // _LIBCPP___ITERATOR_ITERATOR_WITH_DATA_H

libcxx/include/__ranges/join_view.h

 #include <__concepts/copyable.h>
 #include <__concepts/derived_from.h>
 #include <__concepts/equality_comparable.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iter_move.h>
 #include <__iterator/iter_swap.h>
 #include <__iterator/iterator_traits.h>
+#include <__iterator/iterator_with_data.h>
+#include <__iterator/segmented_iterator.h>
 #include <__ranges/access.h>
 #include <__ranges/all.h>
 #include <__ranges/concepts.h>
+#include <__ranges/empty.h>
 #include <__ranges/non_propagating_cache.h>
 #include <__ranges/range_adaptor.h>
 #include <__ranges/view_interface.h>
 #include <__type_traits/maybe_const.h>
 #include <__utility/forward.h>
 #include <optional>
 #include <type_traits>
 
using iterator_category = _If<
       _If<
         derived_from<_OuterC, forward_iterator_tag> && derived_from<_InnerC, forward_iterator_tag>,
         forward_iterator_tag,
         input_iterator_tag
       >
     >;
   };
 
+  template <input_range _View, bool _Const>
+    requires view<_View> && input_range<range_reference_t<_View>>
+  struct __join_view_iterator;
+
+  template <input_range _View, bool _Const>
+    requires view<_View> && input_range<range_reference_t<_View>>
+  struct __join_view_sentinel;
+
   template<input_range _View>
     requires view<_View> && input_range<range_reference_t<_View>>
   class join_view
     : public view_interface<join_view<_View>> {
   private:
     using _InnerRange = range_reference_t<_View>;
 
-    template<bool> struct __iterator;
-    template<bool> struct __sentinel;
+    template<bool _Const>
+    using __iterator = __join_view_iterator<_View, _Const>;
+
+    template<bool _Const>
+    using __sentinel = __join_view_sentinel<_View, _Const>;
+
+    template <input_range _View2, bool _Const2>
+      requires view<_View2> && input_range<range_reference_t<_View2>>
+    friend struct __join_view_iterator;
+
+    template <input_range _View2, bool _Const2>
+      requires view<_View2> && input_range<range_reference_t<_View2>>
+    friend struct __join_view_sentinel;
+
+    template <class>
+    friend struct std::__segmented_iterator_traits;
 
     static constexpr bool _UseCache = !is_reference_v<_InnerRange>;
     using _Cache = _If<_UseCache, __non_propagating_cache<remove_cvref_t<_InnerRange>>, __empty_cache>;
     _LIBCPP_NO_UNIQUE_ADDRESS _Cache __cache_;
     _LIBCPP_NO_UNIQUE_ADDRESS _View __base_ = _View();
 
   public:
     _LIBCPP_HIDE_FROM_ABI
constexpr auto end() const
                     common_range<_ConstInnerRange>) {
         return __iterator<true>{*this, ranges::end(__base_)};
       } else {
         return __sentinel<true>{*this};
       }
     }
   };
 
-  template<input_range _View>
+  template<input_range _View, bool _Const>
     requires view<_View> && input_range<range_reference_t<_View>>
-  template<bool _Const> struct join_view<_View>::__sentinel {
-    template<bool> friend struct __sentinel;
+  struct __join_view_sentinel {
+    template<input_range _View2, bool>
+      requires view<_View2> && input_range<range_reference_t<_View2>>
+    friend struct __join_view_sentinel;
 
   private:
-    using _Parent = __maybe_const<_Const, join_view>;
+    using _Parent = __maybe_const<_Const, join_view<_View>>;
     using _Base = __maybe_const<_Const, _View>;
     sentinel_t<_Base> __end_ = sentinel_t<_Base>();
 
   public:
     _LIBCPP_HIDE_FROM_ABI
-    __sentinel() = default;
+    __join_view_sentinel() = default;
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr explicit __sentinel(_Parent& __parent)
+    constexpr explicit __join_view_sentinel(_Parent& __parent)
       : __end_(ranges::end(__parent.__base_)) {}
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __sentinel(__sentinel<!_Const> __s)
+    constexpr __join_view_sentinel(__join_view_sentinel<_View, !_Const> __s)
       requires _Const && convertible_to<sentinel_t<_View>, sentinel_t<_Base>>
       : __end_(std::move(__s.__end_)) {}
 
     template<bool _OtherConst>
       requires sentinel_for<sentinel_t<_Base>, iterator_t<__maybe_const<_OtherConst, _View>>>
     _LIBCPP_HIDE_FROM_ABI
-    friend constexpr bool operator==(const __iterator<_OtherConst>& __x, const __sentinel& __y) {
+    friend constexpr bool operator==(const __join_view_iterator<_View, _OtherConst>& __x, const __join_view_sentinel& __y) {
       return __x.__outer_ == __y.__end_;
     }
   };
 
-  template<input_range _View>
+  template<input_range _View, bool _Const>
     requires view<_View> && input_range<range_reference_t<_View>>
-  template<bool _Const> struct join_view<_View>::__iterator
+  struct __join_view_iterator
     : public __join_view_iterator_category<__maybe_const<_Const, _View>> {
 
-    template<bool> friend struct __iterator;
+    template<input_range _View2, bool>
+      requires view<_View2> && input_range<range_reference_t<_View2>>
+    friend struct __join_view_iterator;
+
+    template <class>
+    friend struct std::__segmented_iterator_traits;
 
   private:
-    using _Parent = __maybe_const<_Const, join_view>;
+    using _Parent = __maybe_const<_Const, join_view<_View>>;
     using _Base = __maybe_const<_Const, _View>;
     using _Outer = iterator_t<_Base>;
     using _Inner = iterator_t<range_reference_t<_Base>>;
+    using _InnerRange = range_reference_t<_View>;
 
     static constexpr bool __ref_is_glvalue = is_reference_v<range_reference_t<_Base>>;
 
   public:
     _Outer __outer_ = _Outer();
 
   private:
     optional<_Inner> __inner_;
constexpr void __satisfy() {
         if (*__inner_ != ranges::end(__inner))
           return;
       }
 
       if constexpr (__ref_is_glvalue)
         __inner_.reset();
     }
 
+    _LIBCPP_HIDE_FROM_ABI constexpr __join_view_iterator(_Parent* __parent, _Outer __outer, _Inner __inner)
+      : __outer_(std::move(__outer)), __inner_(std::move(__inner)), __parent_(__parent) {}
+
   public:
     using iterator_concept = _If<
       __ref_is_glvalue && bidirectional_range<_Base> && bidirectional_range<range_reference_t<_Base>> &&
           common_range<range_reference_t<_Base>>,
       bidirectional_iterator_tag,
       _If<
         __ref_is_glvalue && forward_range<_Base> && forward_range<range_reference_t<_Base>>,
         forward_iterator_tag,
         input_iterator_tag
       >
     >;
 
     using value_type = range_value_t<range_reference_t<_Base>>;
 
     using difference_type = common_type_t<
       range_difference_t<_Base>, range_difference_t<range_reference_t<_Base>>>;
 
     _LIBCPP_HIDE_FROM_ABI
-    __iterator() requires default_initializable<_Outer> = default;
+    __join_view_iterator() requires default_initializable<_Outer> = default;
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __iterator(_Parent& __parent, _Outer __outer)
+    constexpr __join_view_iterator(_Parent& __parent, _Outer __outer)
       : __outer_(std::move(__outer))
       , __parent_(std::addressof(__parent)) {
       __satisfy();
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __iterator(__iterator<!_Const> __i)
+    constexpr __join_view_iterator(__join_view_iterator<_View, !_Const> __i)
       requires _Const &&
                convertible_to<iterator_t<_View>, _Outer> &&
                convertible_to<iterator_t<_InnerRange>, _Inner>
       : __outer_(std::move(__i.__outer_))
       , __inner_(std::move(__i.__inner_))
       , __parent_(__i.__parent_) {}
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr decltype(auto) operator*() const {
       return **__inner_;
     }
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr _Inner operator->() const
       requires __has_arrow<_Inner> && copyable<_Inner>
     {
       return *__inner_;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __iterator& operator++() {
+    constexpr __join_view_iterator& operator++() {
       auto&& __inner = [&]() -> auto&& {
         if constexpr (__ref_is_glvalue)
           return *__outer_;
         else
           return *__parent_->__cache_;
       }();
       if (++*__inner_ == ranges::end(__inner)) {
         ++__outer_;
         __satisfy();
       }
       return *this;
     }
 
     _LIBCPP_HIDE_FROM_ABI
     constexpr void operator++(int) {
       ++*this;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __iterator operator++(int)
+    constexpr __join_view_iterator operator++(int)
       requires __ref_is_glvalue &&
                forward_range<_Base> &&
                forward_range<range_reference_t<_Base>>
     {
       auto __tmp = *this;
       ++*this;
       return __tmp;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __iterator& operator--()
+    constexpr __join_view_iterator& operator--()
       requires __ref_is_glvalue &&
                bidirectional_range<_Base> &&
                bidirectional_range<range_reference_t<_Base>> &&
                common_range<range_reference_t<_Base>>
     {
       if (__outer_ == ranges::end(__parent_->__base_))
         __inner_ = ranges::end(*--__outer_);
 
       // Skip empty inner ranges when going backwards.
       while (*__inner_ == ranges::begin(*__outer_)) {
         __inner_ = ranges::end(*--__outer_);
       }
 
       --*__inner_;
       return *this;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    constexpr __iterator operator--(int)
+    constexpr __join_view_iterator operator--(int)
       requires __ref_is_glvalue &&
                bidirectional_range<_Base> &&
                bidirectional_range<range_reference_t<_Base>> &&
                common_range<range_reference_t<_Base>>
     {
       auto __tmp = *this;
       --*this;
       return __tmp;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    friend constexpr bool operator==(const __iterator& __x, const __iterator& __y)
+    friend constexpr bool operator==(const __join_view_iterator& __x, const __join_view_iterator& __y)
       requires __ref_is_glvalue &&
                equality_comparable<iterator_t<_Base>> &&
                equality_comparable<iterator_t<range_reference_t<_Base>>>
     {
       return __x.__outer_ == __y.__outer_ && __x.__inner_ == __y.__inner_;
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    friend constexpr decltype(auto) iter_move(const __iterator& __i)
+    friend constexpr decltype(auto) iter_move(const __join_view_iterator& __i)
       noexcept(noexcept(ranges::iter_move(*__i.__inner_)))
     {
       return ranges::iter_move(*__i.__inner_);
     }
 
     _LIBCPP_HIDE_FROM_ABI
-    friend constexpr void iter_swap(const __iterator& __x, const __iterator& __y)
+    friend constexpr void iter_swap(const __join_view_iterator& __x, const __join_view_iterator& __y)
       noexcept(noexcept(ranges::iter_swap(*__x.__inner_, *__y.__inner_)))
       requires indirectly_swappable<_Inner>
     {
       return ranges::iter_swap(*__x.__inner_, *__y.__inner_);
     }
   };
 
   template<class _Range>

 };
 } // namespace __join_view
 inline namespace __cpo {
   inline constexpr auto join = __join_view::__fn{};
 } // namespace __cpo
 } // namespace views
 } // namespace ranges
 
+template <class _View, bool _Const>
+  requires(ranges::common_range<typename ranges::__join_view_iterator<_View, _Const>::_Parent> &&
+           __is_cpp17_random_access_iterator<typename ranges::__join_view_iterator<_View, _Const>::_Outer>::value &&
+           __is_cpp17_random_access_iterator<typename ranges::__join_view_iterator<_View, _Const>::_Inner>::value)
+struct __segmented_iterator_traits<ranges::__join_view_iterator<_View, _Const>> {
+  using _JoinViewIterator = ranges::__join_view_iterator<_View, _Const>;
+
+  using __segment_iterator =
+      _LIBCPP_NODEBUG __iterator_with_data<typename _JoinViewIterator::_Outer, typename _JoinViewIterator::_Parent*>;
+  using __local_iterator = typename _JoinViewIterator::_Inner;
+
+  // TODO: Would it make sense to enable the optimization for other iterator types?
+
+  static constexpr _LIBCPP_HIDE_FROM_ABI __segment_iterator __segment(_JoinViewIterator __iter) {
+      if (ranges::empty(__iter.__parent_->__base_))
+        return {};
+      if (!__iter.__inner_.has_value())
+        return __segment_iterator(--__iter.__outer_, __iter.__parent_);
+      return __segment_iterator(__iter.__outer_, __iter.__parent_);
+  }
+
+  static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __local(_JoinViewIterator __iter) {
+      if (ranges::empty(__iter.__parent_->__base_))
+        return {};
+      if (!__iter.__inner_.has_value())
+        return ranges::end(*--__iter.__outer_);
+      return *__iter.__inner_;
+  }
+
+  static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __begin(__segment_iterator __iter) {
+      return ranges::begin(*__iter.__get_iter());
+  }
+
+  static constexpr _LIBCPP_HIDE_FROM_ABI __local_iterator __end(__segment_iterator __iter) {
+      return ranges::end(*__iter.__get_iter());
+  }
+
+  static constexpr _LIBCPP_HIDE_FROM_ABI _JoinViewIterator
+  __compose(__segment_iterator __seg_iter, __local_iterator __local_iter) {
+      return _JoinViewIterator(
+          std::move(__seg_iter).__get_data(), std::move(__seg_iter).__get_iter(), std::move(__local_iter));
+  }
+};
+
 #endif // _LIBCPP_STD_VER > 17
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___RANGES_JOIN_VIEW_H

libcxx/include/module.modulemap.in

module __iterator {
       module indirectly_comparable { private header "__iterator/indirectly_comparable.h" }
       module insert_iterator       { private header "__iterator/insert_iterator.h" }
       module istream_iterator      { private header "__iterator/istream_iterator.h" }
       module istreambuf_iterator   { private header "__iterator/istreambuf_iterator.h" }
       module iter_move             { private header "__iterator/iter_move.h" }
       module iter_swap             { private header "__iterator/iter_swap.h" }
       module iterator              { private header "__iterator/iterator.h" }
       module iterator_traits       { private header "__iterator/iterator_traits.h" }
+      module iterator_with_data    { private header "__iterator/iterator_with_data.h" }
       module mergeable {
         private header "__iterator/mergeable.h"
         export functional.__functional.ranges_operations
       }
       module move_iterator         { private header "__iterator/move_iterator.h" }
       module move_sentinel         { private header "__iterator/move_sentinel.h" }
       module next                  { private header "__iterator/next.h" }
       module ostream_iterator      { private header "__iterator/ostream_iterator.h" }

libcxx/test/libcxx/iterators/iterator_with_data.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+#include "test_macros.h"
+
+TEST_DIAGNOSTIC_PUSH
+TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header")
+#include <__iterator/iterator_with_data.h>
+TEST_DIAGNOSTIC_POP
+
+#include "test_iterators.h"
+
+static_assert(std::forward_iterator<std::__iterator_with_data<forward_iterator<int*>, int>>);
+static_assert(std::bidirectional_iterator<std::__iterator_with_data<bidirectional_iterator<int*>, int>>);
+static_assert(std::bidirectional_iterator<std::__iterator_with_data<random_access_iterator<int*>, int>>);
+static_assert(std::bidirectional_iterator<std::__iterator_with_data<contiguous_iterator<int*>, int>>);
+
+constexpr bool test() {
+  {
+    std::__iterator_with_data<forward_iterator<int*>, int> iter(forward_iterator<int*>(nullptr), 3);
+    assert(iter == iter);
+    assert(iter.__get_iter() == forward_iterator<int*>(nullptr));
+    assert(iter.__get_data() == 3);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+}

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__iterator/indirectly_comparable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/indirectly_comparable.h'}}
 #include <__iterator/insert_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/insert_iterator.h'}}
 #include <__iterator/istream_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/istream_iterator.h'}}
 #include <__iterator/istreambuf_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/istreambuf_iterator.h'}}
 #include <__iterator/iter_move.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iter_move.h'}}
 #include <__iterator/iter_swap.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iter_swap.h'}}
 #include <__iterator/iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator.h'}}
 #include <__iterator/iterator_traits.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator_traits.h'}}
+#include <__iterator/iterator_with_data.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/iterator_with_data.h'}}
 #include <__iterator/mergeable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/mergeable.h'}}
 #include <__iterator/move_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/move_iterator.h'}}
 #include <__iterator/move_sentinel.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/move_sentinel.h'}}
 #include <__iterator/next.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/next.h'}}
 #include <__iterator/ostream_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/ostream_iterator.h'}}
 #include <__iterator/ostreambuf_iterator.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/ostreambuf_iterator.h'}}
 #include <__iterator/permutable.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/permutable.h'}}
 #include <__iterator/prev.h> // expected-error@*:* {{use of private header from outside its module: '__iterator/prev.h'}}

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy.segmented.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14, c++17
 
 #include <algorithm>
+#include <array>
 #include <cassert>
 #include <concepts>
 #include <deque>
+#include <ranges>
 #include <vector>
 
+#include "test_iterators.h"
+#include "type_algorithms.h"
+
 template <class InContainer, class OutContainer>
 constexpr void test_containers() {
   using InIter  = typename InContainer::iterator;
   using OutIter = typename OutContainer::iterator;
 
   {
     InContainer in{1, 2, 3, 4};
     OutContainer out(4);
using OutIter = typename OutContainer::iterator;
     OutContainer out(4);
     std::same_as<std::ranges::in_out_result<InIter, OutIter>> auto ret = std::ranges::copy(in, out.begin());
     assert(std::ranges::equal(in, out));
     assert(ret.in == in.end());
     assert(ret.out == out.end());
   }
 }
 
+template <class Iter, class Sent>
+constexpr void test_join_view() {
+  auto to_subranges = std::views::transform([](auto& vec) {
+    return std::ranges::subrange(Iter(vec.data()), Sent(Iter(vec.data() + vec.size())));
+  });
+
+  { // segmented -> contiguous
+    std::vector<std::vector<int>> vectors = {};
+    auto range                            = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
+    std::array<int, 0> arr;
+
+    std::ranges::copy(subrange_vector | std::views::join, arr.begin());
+    assert(std::ranges::equal(arr, std::array<int, 0>{}));
+  }
+  { // segmented -> contiguous
+    std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};
+    auto range                            = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
+    std::array<int, 10> arr;
+
+    std::ranges::copy(subrange_vector | std::views::join, arr.begin());
+    assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+  }
+  { // contiguous -> segmented
+    std::vector<std::vector<int>> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}};
+    auto range                            = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
+    std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+
+    std::ranges::copy(arr, (subrange_vector | std::views::join).begin());
+    assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+  }
+  { // segmented -> segmented
+    std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};
+    auto range1                           = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range1.begin(), range1.end());
+    std::vector<std::vector<int>> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}};
+    auto range2                              = to_vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> to_subrange_vector(range2.begin(), range2.end());
+
+    std::ranges::copy(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).begin());
+    assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+  }
+}
+
 int main(int, char**) {
   if (!std::is_constant_evaluated()) {
     test_containers<std::deque<int>, std::deque<int>>();
     test_containers<std::deque<int>, std::vector<int>>();
     test_containers<std::vector<int>, std::deque<int>>();
     test_containers<std::vector<int>, std::vector<int>>();
   }
 
+  meta::for_each(meta::forward_iterator_list<int*>{}, []<class Iter> {
+    test_join_view<Iter, Iter>();
+    test_join_view<Iter, sentinel_wrapper<Iter>>();
+    test_join_view<Iter, sized_sentinel<Iter>>();
+  });
+
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_backward.pass.cpp

constexpr void test_containers() {
     auto range = std::ranges::subrange(In(in.begin()), Sent(In(in.end())));
     std::same_as<std::ranges::in_out_result<In, Out>> auto ret = std::ranges::copy_backward(range, Out(out.end()));
     assert(std::ranges::equal(in, out));
     assert(base(ret.in) == in.end());
     assert(base(ret.out) == out.begin());
   }
 }
 
+template <class Iter, class Sent>
+constexpr void test_join_view() {
+  auto to_subranges = std::views::transform([](auto& vec) {
+          return std::ranges::subrange(Iter(vec.begin()), Sent(Iter(vec.end())));
+        });
+
+  { // segmented -> contiguous
+    std::vector<std::vector<int>> vectors = {};
+    auto range = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
+    std::array<int, 0> arr;
+
+    std::ranges::copy_backward(subrange_vector | std::views::join, arr.end());
+    assert(std::ranges::equal(arr, std::array<int, 0>{}));
+  }
+  { // segmented -> contiguous
+    std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};
+    auto range = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
+    std::array<int, 10> arr;
+
+    std::ranges::copy_backward(subrange_vector | std::views::join, arr.end());
+    assert(std::ranges::equal(arr, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+  }
+  { // contiguous -> segmented
+    std::vector<std::vector<int>> vectors = {{0, 0, 0, 0}, {0, 0}, {0, 0, 0, 0}, {}};
+    auto range = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range.begin(), range.end());
+    std::array arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+
+    std::ranges::copy_backward(arr, (subrange_vector | std::views::join).end());
+    assert(std::ranges::equal(subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+  }
+  { // segmented -> segmented
+    std::vector<std::vector<int>> vectors = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10}, {}};
+    auto range1 = vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> subrange_vector(range1.begin(), range1.end());
+    std::vector<std::vector<int>> to_vectors = {{0, 0, 0, 0}, {0, 0, 0, 0}, {}, {0, 0}};
+    auto range2 = to_vectors | to_subranges;
+    std::vector<std::ranges::subrange<Iter, Sent>> to_subrange_vector(range2.begin(), range2.end());
+
+    std::ranges::copy_backward(subrange_vector | std::views::join, (to_subrange_vector | std::views::join).end());
+    assert(std::ranges::equal(to_subrange_vector | std::views::join, std::array{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
+  }
+}
+
+template <class>
+constexpr bool is_proxy_iterator = false;
+
+template <class Iter>
+constexpr bool is_proxy_iterator<ProxyIterator<Iter>> = true;
+
 template <template <class> class InIter, template <class> class OutIter>
 constexpr void test_sentinels() {
   test_iterators<InIter<int*>, OutIter<int*>, InIter<int*>>();
   test_iterators<InIter<int*>, OutIter<int*>, sentinel_wrapper<InIter<int*>>>();
   test_iterators<InIter<int*>, OutIter<int*>, sized_sentinel<InIter<int*>>>();
 
-  if (!std::is_constant_evaluated()) {
-    if constexpr (!std::is_same_v<InIter<int*>, contiguous_iterator<int*>> &&
-                  !std::is_same_v<OutIter<int*>, contiguous_iterator<int*>> &&
-                  !std::is_same_v<InIter<int*>, ContiguousProxyIterator<int*>> &&
-                  !std::is_same_v<OutIter<int*>, ContiguousProxyIterator<int*>>) {
+    if (!std::is_constant_evaluated()) {
       test_containers<std::deque<int>,
                       std::deque<int>,
                       InIter<std::deque<int>::iterator>,
                       OutIter<std::deque<int>::iterator>>();
       test_containers<std::deque<int>,
                       std::vector<int>,
                       InIter<std::deque<int>::iterator>,
                       OutIter<std::vector<int>::iterator>>();
       test_containers<std::vector<int>,
                       std::deque<int>,
                       InIter<std::vector<int>::iterator>,
                       OutIter<std::deque<int>::iterator>>();
       test_containers<std::vector<int>,
                       std::vector<int>,
                       InIter<std::vector<int>::iterator>,
                       OutIter<std::vector<int>::iterator>>();
     }
+    if constexpr (!is_proxy_iterator<InIter<int*>>)
+      test_join_view<InIter<std::vector<int>::iterator>, InIter<std::vector<int>::iterator>>();
   }
 }
 
 template <template <class> class Out>
 constexpr void test_in_iterators() {
   test_sentinels<bidirectional_iterator, Out>();
   test_sentinels<random_access_iterator, Out>();
   test_sentinels<contiguous_iterator, Out>();