This patch changes the implementation of operator[], to follow similar
pattern as at, where we normalize argument types and forward to single
overload. The conversion now uses __mdspan::__index_type_cast, instead
of static_assert. This introduces asserts assuring that conversion is
is value preserving.
Finally, __is_multi_index is implemented as local lambda, avoiding
the need to create a local array with copies of the arguments.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__is_multi_index): Removed,
replaced with local lambda in mdspan::operator[].
(__mdspan::operator[]): Implement in terms of single overload
accepting index_type. Use __mdspan::__index_type_cast for type
conversion.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
This patch implements P3383R3: mdspan.at().
The mdspan::at cast only non-integral types to the index_type, before
performing the checks. This allows to detect negative value of arguments,
even if the index type is unsigned, and other values that would overflow
index_type.
libstdc++-v3/ChangeLog:
* include/std/mdspan (mdspan::at, mdspan::__index_int_t):
Define.
* testsuite/23_containers/mdspan/at.cc: New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
The submdspan feature broke compatibility with clang, due to a missing
'::template type'.
libstdc++-v3/ChangeLog:
* include/std/mdspan (submdspan): Fix missing '::template'.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Implements `submdspan` and `submdspan_mapping` for layout_left as
described in P3663 (Future proofing mdspan).
When computing the offset of the submdspan, one must check that the
lower bound of the slice range isn't out-of-range. There's a few
cases when the lower bound is never out-of-range:
- full_extent and exts.extent(k) != 0,
- collapsing slice types.
If those conditions are known to hold, no checks are generated.
Similarly, if all slices are full_extent, there's no need to call
mapping(0,...,0) for standardized mappings.
The implementation prepares to use the symmetry between layout_left and
layout_right and introduces concepts like a "layout side", i.e. left,
right or unknown/strided.
The tests use an iterator to replace nested for-loops. Which also makes
it easier to write the core test logic in a rank-independent manner.
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__is_submdspan_mapping_result)
(__mdspan::__submdspan_mapping_result, __mdspan::__fwd_prod)
(__mdspan::__acceptable_slice_type, __mdspan::__slice_begin)
(__mdspan::__suboffset, __mdspan::_LayoutSide, __mdspan::__mapping_side)
(__mdspan::_StridesTrait, __mdspan::__substrides_generic)
(__mdspan::__substrides_standardized, __mdspan::__substrides)
(__mdspan::__is_unit_stride_slice, __mdspan::_SliceKind)
(__mdspan::__make_slice_kind, __mdspan::__make_slice_kind_array)
(__mdspan::__is_block, __mdspan::__padded_block_begin_generic)
(__mdspan::__padded_block_begin, __mpdspan::_SubMdspanMapping)
(__mdspan::__submdspan_mapping_impl): Define.
(__mdspan::__dynamic_slice_extent, __mdspan::__static_slice_extent)
(__mdspan::__subextents): Move earlier in the file.
(layout_left::mapping::submdspan_mapping, __mdspan::__sliceable_mapping)
(__mdspan::__submapping, submdspan): Define.
* src/c++23/std.cc.in: Add submdspan.
* testsuite/23_containers/mdspan/submdspan/generic.cc: New test.
* testsuite/23_containers/mdspan/submdspan/selections/left.cc:
Instantiate selection tests for layout_left.
* testsuite/23_containers/mdspan/submdspan/selections/testcases.h: Generic
tests different selections.
* testsuite/23_containers/mdspan/submdspan/submdspan_mapping.cc: New test.
* testsuite/23_containers/mdspan/submdspan/submdspan_neg.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Splitting the tests for submdspan triggered a compiler warning. This
commit changes the implementation of __dynamic_extents. In particular,
how the span is created. Functionally, the two are equivalent.
libstdc++-v3/ChangeLog:
* include/std/mdspan (_ExtentsStorage::_M_dynamic_extents):
Create span from pointer + size, not begin and end iterators.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
We have __is_signed_integer and __is_unsigned_integer traits which
should have been updated by r16-2190-g4faa42ac0dee2c when making
__int128 an extended integer type (for PR libstdc++/96710). Currently
they check whether the type is a signed integer type or an unsigned
integer type, or a cv-qualified version of one of those. This doesn't
match the standard's definition, which does not include cv-qualified
types. This change ensures that signed __int128 and unsigned __int128
are included in those traits in strict -std modes, and it removes the
use of remove_cv_t so that they are not true for cv-qualified types.
This makes the traits match the meaning of "signed integer type" and
"unsigned integer type" in the standard ([basic.fundamental]).
We also have an __is_standard_integer trait, which is true if either
__is_signed_integer or __is_unsigned_integer is true, but that's also
not a match for the definition in the standard. The definitions of
"signed integer type" and "unsigned integer type" include both standard
and extended integer types, so only saying "standard" in the trait name
is misleading (even before this change, because in non-strict -std modes
the __GLIBCXX_TYPE_INT_N_0 .. __GLIBCXX_TYPE_INT_N_3 types were always
included in the trait, and they aren't standard integer types).
This change renames __is_standard_integer to the more accurate
__is_signed_or_unsigned_integer. Because the set of signed and
unsigned integer types is the same as the set of standard and extended
integer types, the trait could instead have been renamed to
__is_standard_or_extended_integer. I think it's clearer and more
self-explanatory to avoid "standard and extended" and name it for the
signed and unsigned integer types.
N.B. we don't want to call it just __is_integer_type because the integer
types includes cv-qualified types and also bool and the character types
char, wchar_t, char16_t etc.
The consequences of redefining and renaming these traits are small, and
only positive.
Apart from the uses in the __is_standard_integer trait, the only other
uses of __is_signed_integer and __is_unsigned_integer are in <format>
and those uses are unaffected by this change to add 128-bit integers to
the traits. In both uses the type argument is already cv-unqualified,
and there is already explicit handling for 128-bit integers where that
is required.
The existing uses of __is_standard_integer can simply be changed to use
the new name. This does change the behaviour of those uses of the trait,
because the __is_signed_or_unsigned_integer trait now includes
128-bit integers in strict modes. However, that is a desirable change
that fixes some bugs. Specifically, the [utility.intcmp] functions such
as std::cmp_less and the [numeric.sat.arith] functions such as
std::add_sat did not support 128-bit integers in strict modes. Since the
standard says they should be enabled for all signed and unsigned integer
types (or equivalently, for all standard and extended integer types),
those functions should all support __int128 and unsigned __int128. That
is fixed by this change. Additionally, the same changes in <charconv>,
<mdspan>, and <stdckdint.h> enable the use of 128-bit integers for those
APIs in strict modes.
Finally, this also make a drive-by fix to the enable_if constraints for
the integer overloads of std::from_chars. That used remove_cv_t and so
enabled the overload for lvalue arguments of type const char, which
won't work and should not be enabled.
libstdc++-v3/ChangeLog:
* include/bits/intcmp.h: Replace all uses of
__is_standard_integer with __is_signed_or_unsigned_integer.
* include/bits/max_size_type.h: Fix outdated comment.
* include/bits/sat_arith.h: Replace all uses of
__is_standard_integer with __is_signed_or_unsigned_integer.
* include/c_compatibility/stdckdint.h: Replace all uses of the
__cv_unqual_signed_or_unsigned_integer_type concept with
__is_signed_or_unsigned_integer.
(__cv_unqual_signed_or_unsigned_integer_type): Remove.
* include/ext/numeric_traits.h: Fix outdated comment.
* include/std/charconv (from_chars): Replace use of
__is_standard_integer with __is_signed_or_unsigned_integer.
Do not enable for cv-qualified char.
* include/std/mdspan: Likewise.
* include/std/type_traits (__is_unsigned_integer): Include
unsigned __int128 in type list.
(__is_signed_integer): Include signed __int128 in type list.
(__is_standard_integer): Rename to ...
(__is_signed_or_unsigned_integer): ... this.
* testsuite/23_containers/mdspan/extents/ctor_ints.cc: Test
with 128-bit integers.
* testsuite/23_containers/mdspan/submdspan/strided_slice.cc:
Likewise.
* testsuite/20_util/integer_comparisons/extended.cc: New test.
* testsuite/26_numerics/saturation/extended.cc: New test.
* testsuite/26_numerics/stdckdint/extended.cc: New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
LWG4272 proposes to add a condition for convertibility from
layout_stride::mapping to other mappings. New conversion requires
both that rank == 0 and that the extent types are convertible.
LWG4272 also proposes to add the same condition for conversion of
padded layouts, i.e. in addition to the condition on the padding
value, the extent types must be convertible.
libstdc++-v3/ChangeLog:
* include/std/mdspan (layout_left): Apply LWG4272.
(layout_right, layout_left_padded, layout_right_padded): Ditto.
* testsuite/23_containers/mdspan/layouts/ctors.cc: Add
test to check ctor uniformity at rank == 0. Update test
for new behavior.
* testsuite/23_containers/mdspan/layouts/padded.cc: Update test
for new behavior.
Co-authored-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Signed-off-by: Tomasz Kamiński <tkaminsk@redhat.com>
Implement submdspan_extents as described in P3663 and adds it to the std
module.
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/std/mdspan (submdspan_extents): New function.
* src/c++23/std.cc.in: Add submdspan_extents.
* testsuite/23_containers/mdspan/int_like.h: Add StructuralInt.
* testsuite/23_containers/mdspan/submdspan/submdspan_extents.cc: New test.
* testsuite/23_containers/mdspan/submdspan/submdspan_extents_neg.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Implements submdspan_canonicalize_slices as described in P3663 and adds
it to the std module.
There's one deviation from the standard. Doesn't (under all
circumstances) require:
0 <= begin[k] <= end[k] <= exts.extent(k)
where the k-th slice range is [begin[k], end[k]). Instead, it requires
that the k-th slice ranges is contained in the k-th extent interval. If
the slice range is empty, then that condition is always satisfied, even if
begin[k] == end[k] > exts.extent(k)
The deviation is that we enforce the above inequality through
preconditions. This is analogous to what the standard requires if
begin[k] is a constant wrapper.
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/std/mdspan (submdspan_canonicalize_slices): New
function.
* src/c++23/std.cc.in (submdspan_canonicalize_slices): Add.
* testsuite/23_containers/mdspan/submdspan/submdspan_canonicalize_slices.cc: New test.
* testsuite/23_containers/mdspan/submdspan/submdspan_canonicalize_slices_neg.cc: New test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
The changes needed for submdspan are:
* In submdspan related code the user-defined integer-like
types need to be copy- and move-constructable.
* The traits for writing tests that work with both left- and right,
possibly padded, layouts will also be useful for submdspan.
Therefore, this code is moved up and generalized.
* Move __offset further up in <mdspan> and fix some formatting
mistakes.
libstdc++-v3/ChangeLog:
* include/std/mdspan: Improve formatting and placement.
* testsuite/23_containers/mdspan/int_like.h: Optionally,
add move- and copy-ctors.
* testsuite/23_containers/mdspan/layouts/padded_traits.h: Move to...
* testsuite/23_containers/mdspan/layout_traits.h: ...here.
* testsuite/23_containers/mdspan/layouts/ctors.cc: Fix include.
* testsuite/23_containers/mdspan/layouts/mapping.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded_neg.cc: Ditto.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
These three changes are needed to make <mdspan> compatible with Clang:
- the type alias _Storage must occur before its first use.
- the friend declarations of function must match exactly, including
noexcept and constexpr.
- the 'template' in typename T::template type<double>.
libstdc++-v3/ChangeLog:
* include/std/mdspan (extents::_Storage): Move type alias before
its first use.
(__mdspan::__static_extents): Add missing noexcept and constexpr
to friend declaration in extents.
(__mdspan::__dynamic_extents): Ditto.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Implement the class submdspan_mapping_result and add it to the std
module.
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/std/mdspan (submdspan_mapping_result): New class.
* src/c++23/std.cc.in (submdspan_mapping_result): Add.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Add the class and updates the std module.
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/std/mdspan (full_extent_t): New class.
* src/c++23/std.cc.in (full_extent_t): Add.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
The improvement is that in __index_type_cast, we don't need to check at
runtime if we know that _IndexType is smaller than _OIndexType.
The cleanup is whitespace (overlength lines) in <mdspan>, grouping is_always_foo
and is_foo together, and de-uglifying a variable in test code.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__index_type_cast): Optimize by
skipping a __glibcxx_assert if it's know at compile-time.
(std::layout_left_padded, std::layout_righ_padded): Reorder
is_always_strided and is_unique member functions.
* testsuite/23_containers/mdspan/int_like.h: Rename _M_i to
value.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This commit adds the right padded layout as described in N5014, with
LWG4372 (dynamic padding value) and LWG4314 (move in operator()).
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/std/mdspan (_RightPaddedIndices): Traits for right
padded layouts.
(layout_right::mapping::mapping) New overload for right padded
layouts.
(layout_right_padded): Add implementation.
* src/c++23/std.cc.in (layout_right_padded): Add.
* testsuite/23_containers/mdspan/layouts/ctors.cc: Update
test for right padded layouts.
* testsuite/23_containers/mdspan/layouts/empty.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/mapping.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded_neg.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded_traits.h: Ditto.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This commit adds a new layout layout_left_padded as standardized in
N5014. It adds a purely internal feature testing macro padded_layouts
and registers layout_left_padded in the std module.
This commit implements LWG4372, because without it's not possible
to properly test padded layouts with a dynamic padding value. It also
implements LWG4314, for consistency with prior layouts.
The implementation uses a _PaddedStorage to deduplicate most of the code
shared between left- and right-padded layouts. It's implemented through
aggregation rather than inheritence, because of a bug related to
inheriting conditionally explicit ctors.
The tests are written such that the canonical version works for
layout_left_padded. A version for layout_right_padded is derived
essentially by reversing the order of the extents.
PR libstdc++/110352
libstdc++-v3/ChangeLog:
* include/bits/version.def (padded_layouts): Add new internal
feature testing macro.
* include/bits/version.h: Regenerate.
* include/std/mdspan (__fwd_prod): New overload.
(layout_left_padded): Add declaration and implementation.
(layout_right_padded): Add declaration only.
(layout_left::mapping::mapping): New overload for left
padded mappings.
(__index_type_cast): New function that performs a checked cast
to index_type.
(__is_left_padded_mapping): New concept.
(__is_right_padded_mapping): Ditto.
(__standardized_mapping): Recognize left and right padded
mappings.
(_LeftPaddedIndices): Traits for left padded details.
(_PaddedStorage): New class for implementing padded layouts.
* src/c++23/std.cc.in (layout_left_padded): Add.
* testsuite/23_containers/mdspan/layouts/class_mandate_neg.cc:
Refactor and add tests for layout_left_padded.
* testsuite/23_containers/mdspan/layouts/ctors.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/empty.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/mapping.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded_neg.cc: Ditto.
* testsuite/23_containers/mdspan/layouts/padded_traits.h: New
traits.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
For padded layouts we want to check that the product of the
padded stride with the remaining extents is representable.
Creating a second overload, allows passing in subspans of the
static extents and retains the ergonomics for the common case
of passing in all static extents.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__static_quotient): New overload.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
In libstdc++ the prefix _S is used for static members only. In <mdspan>
there's several type aliases that also used the prefix _S. They now use
a single leading underscore follow by a capital letter instead.
libstdc++-v3/ChangeLog:
* include/std/mdspan (_ExtentsStorage::_Base): New name for
_S_base.
(_ExtentsStorage::_Storage): New name for _S_storage.
(extents::_Storage): New name for _S_storage.
(layout_stride::mapping::_Strides): New name for
_S_stries_t.
* testsuite/23_containers/mdspan/class_mandate_neg.cc: Update
test to the new error message.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
In r16-2328-g29d53f6213e0a1 we fixed a bug related to user-defined
objects that can convert to an integers only via an rvalue reference.
The same commit also implemented LWG 4314 [1], but didn't mark it with
_GLIBCXX_RESOLVE_LIB_DEFECTS. This commit adds the missing markers.
[1]: https://cplusplus.github.io/LWG/issue4314
It also fixes one cases of trailing white-space near a ctor for
aligned_accessor.
libstdc++-v3/ChangeLog:
* include/std/mdspan (layout_left::mapping::operator()): Add
_GLIBCXX_RESOLVE_LIB_DEFECTS marker for 4314.
(layout_left::mapping::operator()): Ditto.
(layout_stride::mapping::operator()): Ditto.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This commit completes the implementation of P2897R7 by implementing and
testing the template class aligned_accessor.
PR libstdc++/120994
libstdc++-v3/ChangeLog:
* include/bits/version.def (aligned_accessor): Add.
* include/bits/version.h: Regenerate.
* include/std/mdspan (aligned_accessor): New class.
* src/c++23/std.cc.in (aligned_accessor): Add.
* testsuite/23_containers/mdspan/accessors/generic.cc: Add tests
for aligned_accessor.
* testsuite/23_containers/mdspan/accessors/aligned_neg.cc: New test.
* testsuite/23_containers/mdspan/version.cc: Add test for
__cpp_lib_aligned_accessor.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This commit implements the C++26 feature std::dims described in P2389R2.
It sets the feature testing macro to 202406 and adds tests.
Also fixes the test mdspan/version.cc
libstdc++-v3/ChangeLog:
* include/bits/version.def (mdspan): Set value for C++26.
* include/bits/version.h: Regenerate.
* include/std/mdspan (dims): Add.
* src/c++23/std.cc.in (dims): Add.
* testsuite/23_containers/mdspan/extents/misc.cc: Add tests.
* testsuite/23_containers/mdspan/version.cc: Update test.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Prior to this commit, the partial products of static extents in <mdspan>
was done in a loop that calls a function that computes the partial
product. The complexity is quadratic in the rank.
This commit removes the quadratic complexity.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__static_prod): Delete.
(__fwd_partial_prods): Compute at compile-time in O(rank), not
O(rank**2).
(__rev_partial_prods): Ditto.
(__size): Inline __static_prod.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This fixes an oversight in a previous commit that improved mdspan
related code. Because __size doesn't use __fwd_prod, __fwd_prod(__rank)
is not needed anymore. Hence, one can shrink the size of
__fwd_partial_prods.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__fwd_partial_prods): Reduce size of the
array by 1 element.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Using __int_traits avoids the need to include <limits> from <mdspan>.
This in turn should reduce the size of the pre-compiled <mdspan>.
Similar refactoring was carried out for PR92546. Unfortunately,
./gcc/xgcc -std=c++23 -P -E -x c++ - -include mdspan | wc -l
shows a decrease by 1(!) line. This is due to bits/max_size_type.h which
includes <limits>.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__valid_static_extent): Replace
numeric_limits with __int_traits.
(extents::_S_ctor_explicit): Ditto.
(extents::__static_quotient): Ditto.
(layout_stride::mapping::mapping): Ditto.
(mdspan::size): Ditto.
* testsuite/23_containers/mdspan/extents/class_mandates_neg.cc:
Update test with additional diagnostics.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
An interesting case to consider is:
bool same11(const std::extents<int, dyn, 2, 3>& e1,
const std::extents<int, dyn, dyn, 3>& e2)
{ return e1 == e2; }
Which has the following properties:
- There's no mismatching static extents, preventing any
short-circuiting.
- There's a comparison between dynamic and static extents.
- There's one trivial comparison: ... && 3 == 3.
Let E[i] denote the array of static extents, D[k] denote the array of
dynamic extents and k[i] be the index of the i-th extent in D.
(Naturally, k[i] is only meaningful if i is a dynamic extent).
The previous implementation results in assembly that's more or less a
literal translation of:
for (i = 0; i < 3; ++i)
e1 = E1[i] == -1 ? D1[k1[i]] : E1[i];
e2 = E2[i] == -1 ? D2[k2[i]] : E2[i];
if e1 != e2:
return false
return true;
While the proposed method results in assembly for
if(D1[0] == D2[0]) return false;
return 2 == D2[1];
i.e.
110: 8b 17 mov edx,DWORD PTR [rdi]
112: 31 c0 xor eax,eax
114: 39 16 cmp DWORD PTR [rsi],edx
116: 74 08 je 120 <same11+0x10>
118: c3 ret
119: 0f 1f 80 00 00 00 00 nop DWORD PTR [rax+0x0]
120: 83 7e 04 02 cmp DWORD PTR [rsi+0x4],0x2
124: 0f 94 c0 sete al
127: c3 ret
It has the following nice properties:
- It eliminated the indirection D[k[i]], because k[i] is known at
compile time. Saving us a comparison E[i] == -1 and conditionally
loading k[i].
- It eliminated the trivial condition 3 == 3.
The result is code that only loads the required values and performs
exactly the number of comparisons needed by the algorithm. It also
results in smaller object files. Therefore, this seems like a sensible
change. We've check several other examples, including fully statically
determined cases and high-rank examples. The example given above
illustrates the other cases well.
The constexpr condition:
if constexpr (!_S_is_compatible_extents<...>)
return false;
is no longer needed, because the optimizer correctly handles this case.
However, it's retained for clarity/certainty.
libstdc++-v3/ChangeLog:
* include/std/mdspan (extents::operator==): Replace loop with
pack expansion.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
In both fully static and dynamic extents the comparison
static_extent(i) == dynamic_extent
is known at compile time. As a result, extents::extent doesn't
need to perform the check at runtime.
An illustrative example is:
using E = std::extents<int, 3, 5, 7, 11, 13, 17>;
int required_span_size(const typename Layout::mapping<E>& m)
{ return m.required_span_size(); }
Prior to this commit the generated code (on -O2) is:
2a0: b9 01 00 00 00 mov ecx,0x1
2a5: 31 d2 xor edx,edx
2a7: 66 66 2e 0f 1f 84 00 data16 cs nop WORD PTR [rax+rax*1+0x0]
2ae: 00 00 00 00
2b2: 66 66 2e 0f 1f 84 00 data16 cs nop WORD PTR [rax+rax*1+0x0]
2b9: 00 00 00 00
2bd: 0f 1f 00 nop DWORD PTR [rax]
2c0: 48 8b 04 d5 00 00 00 mov rax,QWORD PTR [rdx*8+0x0]
2c7: 00
2c8: 48 83 f8 ff cmp rax,0xffffffffffffffff
2cc: 0f 84 00 00 00 00 je 2d2 <required_span_size_6d_static+0x32>
2d2: 83 e8 01 sub eax,0x1
2d5: 0f af 04 97 imul eax,DWORD PTR [rdi+rdx*4]
2d9: 48 83 c2 01 add rdx,0x1
2dd: 01 c1 add ecx,eax
2df: 48 83 fa 06 cmp rdx,0x6
2e3: 75 db jne 2c0 <required_span_size_6d_static+0x20>
2e5: 89 c8 mov eax,ecx
2e7: c3 ret
which is a scalar loop, and notably includes the check
308: 48 83 f8 ff cmp rax,0xffffffffffffffff
to assert that the static extent is indeed not -1. Note, that on -O3 the
optimizer eliminates the comparison; and generates a sequence of scalar
operations: lea, shl, add and mov. The aim of this commit is to
eliminate this comparison also for -O2. With the optimization applied we
get:
2e0: f3 0f 6f 0f movdqu xmm1,XMMWORD PTR [rdi]
2e4: 66 0f 6f 15 00 00 00 movdqa xmm2,XMMWORD PTR [rip+0x0]
2eb: 00
2ec: 8b 57 10 mov edx,DWORD PTR [rdi+0x10]
2ef: 66 0f 6f c1 movdqa xmm0,xmm1
2f3: 66 0f 73 d1 20 psrlq xmm1,0x20
2f8: 66 0f f4 c2 pmuludq xmm0,xmm2
2fc: 66 0f 73 d2 20 psrlq xmm2,0x20
301: 8d 14 52 lea edx,[rdx+rdx*2]
304: 66 0f f4 ca pmuludq xmm1,xmm2
308: 66 0f 70 c0 08 pshufd xmm0,xmm0,0x8
30d: 66 0f 70 c9 08 pshufd xmm1,xmm1,0x8
312: 66 0f 62 c1 punpckldq xmm0,xmm1
316: 66 0f 6f c8 movdqa xmm1,xmm0
31a: 66 0f 73 d9 08 psrldq xmm1,0x8
31f: 66 0f fe c1 paddd xmm0,xmm1
323: 66 0f 6f c8 movdqa xmm1,xmm0
327: 66 0f 73 d9 04 psrldq xmm1,0x4
32c: 66 0f fe c1 paddd xmm0,xmm1
330: 66 0f 7e c0 movd eax,xmm0
334: 8d 54 90 01 lea edx,[rax+rdx*4+0x1]
338: 8b 47 14 mov eax,DWORD PTR [rdi+0x14]
33b: c1 e0 04 shl eax,0x4
33e: 01 d0 add eax,edx
340: c3 ret
Which shows eliminating the trivial comparison, unlocks a new set of
optimizations, i.e. SIMD-vectorization. In particular, the loop has been
vectorized by loading the first four constants from aligned memory; the
first four strides from non-aligned memory, then computes the product
and reduction. It interleaves the above with computing 1 + 12*S[4] +
16*S[5] (as scalar operations) and then finishes the reduction.
A similar effect can be observed for fully dynamic extents.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__all_static): New function.
(__mdspan::_StaticExtents::_S_is_dyn): Inline and eliminate.
(__mdspan::_ExtentsStorage::_S_is_dynamic): New method.
(__mdspan::_ExtentsStorage::_M_extent): Use _S_is_dynamic.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
One previous commit optimized fully dynamic extents; and another
refactored __size such that __fwd_prod is valid for __r = 0, ..., rank
(exclusive).
Therefore, by noticing that __rev_prod (and __fwd_prod) never accesses
the first (or last) extent, one can avoid pre-computing partial products
of static extents in those cases, if all other extents are dynamic.
We check that the size of the reference object file decreases further
and the .rodata sections for
__fwd_prod<dyn, ..., dyn, 11>
__rev_prod<3, dyn, ..., dyn>
are absent.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__fwd_prods): Relax condition for fully-dynamic
extents to cover (dyn, ..., dyn, X).
(__rev_partial_prods): Analogous for (X, dyn, ..., dyn).
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
In mdspan related code, for extents with no static extents, i.e. only
dynamic extents, the following simplifications can be made:
- The array of dynamic extents has size rank.
- The two arrays dynamic-index and dynamic-index-inv become
trivial, e.g. k[i] == i.
- All elements of the arrays __{fwd,rev}_partial_prods are 1.
This commits eliminates the arrays for dynamic-index, dynamic-index-inv
and __{fwd,rev}_partial_prods. It also removes the indirection k[i] == i
from the source code, which isn't as relevant because the optimizer is
(often) capable of eliminating the indirection.
To check if it's working we look at:
using E2 = std::extents<int, dyn, dyn, dyn, dyn>;
int stride_left_E2(const std::layout_left::mapping<E2>& m, size_t r)
{ return m.stride(r); }
which generates the following
0000000000000190 <stride_left_E2>:
190: 48 c1 e6 02 shl rsi,0x2
194: 74 22 je 1b8 <stride_left_E2+0x28>
196: 48 01 fe add rsi,rdi
199: b8 01 00 00 00 mov eax,0x1
19e: 66 90 xchg ax,ax
1a0: 48 63 17 movsxd rdx,DWORD PTR [rdi]
1a3: 48 83 c7 04 add rdi,0x4
1a7: 48 0f af c2 imul rax,rdx
1ab: 48 39 fe cmp rsi,rdi
1ae: 75 f0 jne 1a0 <stride_left_E2+0x10>
1b0: c3 ret
1b1: 0f 1f 80 00 00 00 00 nop DWORD PTR [rax+0x0]
1b8: b8 01 00 00 00 mov eax,0x1
1bd: c3 ret
We see that:
- There's no code to load the partial product of static extents.
- There's no indirection D[k[i]], it's just D[i] (as before).
On a test file which computes both mapping::stride(r) and
mapping::required_span_size, we check for static storage with
objdump -h
we don't see the NTTP _Extents, anything (anymore) related to
_StaticExtents, __fwd_partial_prods or __rev_partial_prods. We also
check that the size of the reference object file (described three
commits prior) reduced by a few percent from 41.9kB to 39.4kB.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__all_dynamic): New function.
(__mdspan::_StaticExtents::_S_dynamic_index): Convert to method.
(__mdspan::_StaticExtents::_S_dynamic_index_inv): Ditto.
(__mdspan::_StaticExtents): New specialization for fully dynamic
extents.
(__mdspan::__fwd_prod): New constexpr if branch to avoid
instantiating __fwd_partial_prods.
(__mdspan::__rev_prod): Ditto.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
The methods layout_{left,right}::mapping::stride are defined
as
\prod_{i = 0}^r E[i]
\prod_{i = r+1}^n E[i]
This is computed as the product of a precomputed static product and the
product of the required dynamic extents.
Disassembly shows that even for low-rank extents, i.e. rank == 1 and
rank == 2, with at least one dynamic extent, the generated code loads
two values; and then runs the loop over at most one element, e.g. for
stride_left_d5 defined below the generated code is:
220: 48 8b 04 f5 00 00 00 mov rax,QWORD PTR [rsi*8+0x0]
227: 00
228: 31 d2 xor edx,edx
22a: 48 85 c0 test rax,rax
22d: 74 23 je 252 <stride_left_d5+0x32>
22f: 48 8b 0c f5 00 00 00 mov rcx,QWORD PTR [rsi*8+0x0]
236: 00
237: 48 c1 e1 02 shl rcx,0x2
23b: 74 13 je 250 <stride_left_d5+0x30>
23d: 48 01 f9 add rcx,rdi
240: 48 63 17 movsxd rdx,DWORD PTR [rdi]
243: 48 83 c7 04 add rdi,0x4
247: 48 0f af c2 imul rax,rdx
24b: 48 39 f9 cmp rcx,rdi
24e: 75 f0 jne 240 <stride_left_d5+0x20>
250: 89 c2 mov edx,eax
252: 89 d0 mov eax,edx
254: c3 ret
If there's no dynamic extents, it simply loads the precomputed product
of static extents.
For rank == 1 the answer is the constant `1`; for rank == 2 it's either 1 or
extents.extent(k), with k == 0 for layout_left and k == 1 for
layout_right.
Consider,
using Ed = std::extents<int, dyn>;
int stride_left_d(const std::layout_left::mapping<Ed>& m, size_t r)
{ return m.stride(r); }
using E3d = std::extents<int, 3, dyn>;
int stride_left_3d(const std::layout_left::mapping<E3d>& m, size_t r)
{ return m.stride(r); }
using Ed5 = std::extents<int, dyn, 5>;
int stride_left_d5(const std::layout_left::mapping<Ed5>& m, size_t r)
{ return m.stride(r); }
The optimized code for these three cases is:
0000000000000060 <stride_left_d>:
60: b8 01 00 00 00 mov eax,0x1
65: c3 ret
0000000000000090 <stride_left_3d>:
90: 48 83 fe 01 cmp rsi,0x1
94: 19 c0 sbb eax,eax
96: 83 e0 fe and eax,0xfffffffe
99: 83 c0 03 add eax,0x3
9c: c3 ret
00000000000000a0 <stride_left_d5>:
a0: b8 01 00 00 00 mov eax,0x1
a5: 48 85 f6 test rsi,rsi
a8: 74 02 je ac <stride_left_d5+0xc>
aa: 8b 07 mov eax,DWORD PTR [rdi]
ac: c3 ret
For rank == 1 it simply returns 1 (as expected). For rank == 2, it
either implements a branchless formula, or conditionally loads one
value. In all cases involving a dynamic extent this seems like it's
always doing clearly less work, both in terms of computation and loads.
In cases not involving a dynamic extent, it replaces loading one value
with a branchless sequence of four instructions.
This commit also refactors __size to no use any of the precomputed
arrays. This prevents instantiating __{fwd,rev}_partial_prods for
low-rank extents. This results in a further size reduction of a
reference object file (described two commits prior) by 9% from 46.0kB to
41.9kB.
In a prior commit we optimized __size to produce better object code by
precomputing the static products. This refactor enables the optimizer to
generate the same optimized code.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__fwd_prod): Optimize
for rank <= 2.
(__mdspan::__rev_prod): Ditto.
(__mdspan::__size): Refactor to use a pre-computed product, not
a partial product.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
In mdspan related code involving static extents, often the IndexType is
part of the template parameters, even though it's not needed.
This commit extracts the parts of _ExtentsStorage not related to
IndexType into a separate class _StaticExtents.
It also prefers passing the array of static extents, instead of the
whole extents object where possible.
The size of an object file compiled with -O2 that instantiates
Layout::mapping<extents<IndexType, Indices...>::stride
Layout::mapping<extents<IndexType, Indices...>::required_span_size
for the product of
- eight IndexTypes
- three Layouts,
- nine choices of Indices...
decreases by 19% from 69.2kB to 55.8kB.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::_StaticExtents): Extract non IndexType
related code from _ExtentsStorage.
(__mdspan::_ExtentsStorage): Use _StaticExtents.
(__mdspan::__static_extents): Return reference to NTTP of _StaticExtents.
(__mdspan::__contains_zero): New overload.
(__mdspan::__exts_prod, __mdspan::__static_quotient): Use span to avoid
copying __sta_exts.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Previously, the default ctor of mdspan was never noexcept, even if all
members of mdspan were nothrow default constructible.
This commit makes mdspan conditionally nothrow default constructible.
A similar strengthening happens in libc++.
libstdc++-v3/ChangeLog:
* include/std/mdspan (mdspan::mdspan): Make default ctor
conditionally noexcept.
* testsuite/23_containers/mdspan/mdspan.cc: Add tests.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
The mdspan::is_{,always}_{unique,strided,exhaustive} methods only call
their counterparts in mdspan::mapping_type. The standard specifies that
the methods of mdspan::mapping_type are noexcept, but doesn't specify if
the methods of mdspan are noexcept.
Libc++ strengthened the exception guarantee for these mdspan methods.
This commit conditionally strengthens these methods for libstdc++.
libstdc++-v3/ChangeLog:
* include/std/mdspan (mdspan::is_always_unique): Make
conditionally noexcept.
(mdspan::is_always_exhaustive): Ditto.
(mdspan::is_always_strided): Ditto.
(mdspan::is_unique): Ditto.
(mdspan::is_exhaustive): Ditto.
(mdspan::is_strided): Ditto.
* testsuite/23_containers/mdspan/layout_like.h: Make noexcept
configurable. Add ThrowingLayout.
* testsuite/23_containers/mdspan/mdspan.cc: Add tests for
noexcept.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
The second bug report in PR121061 is that the conversion of custom
OtherIndexType to IndexType is incorrectly not done via r-value
references.
This commit fixes the forwarding issue, adds a custom IndexType called
RValueInt, which only allows conversion to int via r-value reference.
PR libstdc++/121061
libstdc++-v3/ChangeLog:
* include/std/mdspan (extents::extents): Perform conversion to
index_type of an r-value reference.
(layout_left::mapping::operator()): Ditto.
(layout_right::mapping::operator()): Ditto.
(layout_stride::mapping::operator()): Ditto.
* testsuite/23_containers/mdspan/extents/custom_integer.cc: Add
tests for RValueInt and MutatingInt.
* testsuite/23_containers/mdspan/int_like.h (RValueInt): Add.
* testsuite/23_containers/mdspan/layouts/mapping.cc: Test with
RValueInt.
* testsuite/23_containers/mdspan/mdspan.cc: Ditto.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
PR121061 consists of two bugs for mdspan related code. This commit fixes
the first one. Namely, when passing custom IndexType as an array or
span, the conversion to int must be const. Prior to this commit the
constraint incorrectly also allowed non-const conversion. This commit
updates all related constraints to check
__valid_index_type<const OtherIndexType&, index_type>
in those cases. Also adds a MutatingInt to int_like.h which only
supports non-const conversion to int and updates the tests.
PR libstdc++/121061
libstdc++-v3/ChangeLog:
* include/std/mdspan (extents::extents): Fix constraint to
prevent non-const conversion to index_type.
(layout_stride::mapping::mapping): Ditto.
(mdspan::mdspan): Ditto.
(mdspan::operator[]): Ditto.
* testsuite/23_containers/mdspan/extents/custom_integer.cc: Add
test for MutatingInt.
* testsuite/23_containers/mdspan/int_like.h (MutatingInt): Add.
* testsuite/23_containers/mdspan/layouts/mapping.cc: Add test for
MutatingInt.
* testsuite/23_containers/mdspan/layouts/stride.cc: Ditto.
* testsuite/23_containers/mdspan/mdspan.cc: Ditto.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This fixes:
include/c++/16.0.0/mdspan:1182:33: error: use 'template' keyword to treat 'mapping' as a dependent template name
1182 | const typename _OLayout::mapping<_OExtents>&>
| ^
include/c++/16.0.0/mdspan:1185:31: error: use 'template' keyword to treat 'mapping' as a dependent template name
1185 | const typename _OLayout::mapping<_OExtents>&, mapping_type>
| ^
libstdc++-v3/ChangeLog:
* include/std/mdspan (mdspan): Add template keyword for
dependent name.
This implements P3029R1. In P3029R1, the CTAD for span is refined to
permit deducing the extent of the span from an integral constant, e.g.
span((T*) ptr, integral_constant<size_t, 5>{});
is deduced as span<T, 5>. Similarly, in
auto exts = extents(integral_constant<int, 2>);
auto md = mdspan((T*) ptr, integral_constant<int, 2>);
exts and md have types extents<size_t, 2> and mdspan<double,
extents<size_t, 2>>, respectively.
PR libstdc++/120914
libstdc++-v3/ChangeLog:
* include/std/span (span): Update CTAD to enable
integral constants [P3029R1].
* include/std/mdspan (extents): ditto.
(mdspan): ditto.
* testsuite/23_containers/span/deduction.cc: Test deduction
guide.
* testsuite/23_containers/mdspan/extents/misc.cc: ditto.
* testsuite/23_containers/mdspan/mdspan.cc: ditto.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Implements the class mdspan as described in N4950, i.e. without P3029.
It also adds tests for mdspan. This commit completes the implementation
of P0009, i.e. the C++23 part <mdspan>.
PR libstdc++/107761
libstdc++-v3/ChangeLog:
* include/std/mdspan (mdspan): New class.
* src/c++23/std.cc.in (mdspan): Add.
* testsuite/23_containers/mdspan/class_mandate_neg.cc: New test.
* testsuite/23_containers/mdspan/mdspan.cc: New test.
* testsuite/23_containers/mdspan/layout_like.h: Add class
LayoutLike which models a user-defined layout.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
The current code uses __mdspan::__fwd_prod(__exts, __rank) to express
computing the size of an extent. This commit adds an function __mdspan::
__size(__exts) to express the idea more directly.
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mdspan::__size): New function.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Previously the prerequisite of the extents ctors that
static_extent(i) == dynamic_extent || extent(i) == other.extent(i).
was not checked. This commit adds the __glibcxx_assert and test them.
libstdc++-v3/ChangeLog:
* include/std/mdspan (extents): Check prerequisite of the ctor that
static_extent(i) == dynamic_extent || extent(i) == other.extent(i).
* testsuite/23_containers/mdspan/extents/class_mandates_neg.cc:
Test the implemented prerequisite.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
Previously, the prerequisite that the arguments passed to operator() are
a multi-dimensional index (of extents()) was not checked.
Both mapping::operator() and mdspan::operator[] have the same
prerequisite. Since, mdspan must check the prerequisite for user-defined
layout mappings, the preference is to check in mdspan.
Because out-of-bounds accesses are very common it's nevertheless useful
to check the prerequisite in mapping::operator(). This is relevant for
cases where the layout mappings are used without mdspan. This commit
checks the prerequisites via _GLIBCXX_DEBUG_ASSERTs and adds the required
tests.
More discussion in the email chain starting at:
https://gcc.gnu.org/pipermail/libstdc++/2025-July/062265.html
libstdc++-v3/ChangeLog:
* include/std/mdspan: Check prerequisites of
layout_*::operator() with _GLIBCXX_DEBUG_ASSERTs.
* testsuite/23_containers/mdspan/layouts/debug/out_of_bounds_neg.cc:
Add tests for prerequisites.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Signed-off-by: Luc Grosheintz <luc.grosheintz@gmail.com>
This is needed to fix an error with Clang 19:
include/c++/16.0.0/mdspan:512:30: error: use 'template' keyword to treat 'mapping' as a dependent template name
512 | is_same_v<typename _Layout::mapping<typename _Mapping::extents_type>,
| ^
libstdc++-v3/ChangeLog:
* include/std/mdspan (__mapping_of): Add template keyword.
Tomasz Kamiński