Jump to Table of Contents Collapse Sidebar

DxxxxR0
Structured bindings for std::extents

Draft Proposal,

This version:
http://wg21.link/Pxxxx
Author:
Bernhard Manfred Gruber <bernhardmgruber@gmail.com>
Audience:
LEWG
Project:
ISO/IEC JTC1/SC22/WG21 14882: Programming Language — C++
Source:
GitHub

Abstract

This paper proposes to add support for structured bindings to std::extents.

1. Motivation

[P0009r18] proposed std::mdspan, which was approved for C++23. It comes with the utility class template std::extents to describe the integral extents of a multidimensional index space. Practically, std::extents models an array of integrals, where some of the values can be specified at compile-time. However, std::extents behaves very little like an array. A notable missing feature are structured bindings, which would come in handy if the extents of the individual dimensions need to be extracted:

Before After
std::mdspan<double,
    std::extents<I, I1, I2, I3>, L, A> mdspan;
const auto& e = mdspan.extents();
for (I z = 0; z < e.extent(2); z++)
    for (I y = 0; y < e.extent(1); y++)
        for (I x = 0; x < e.extent(0); x++)
            mdspan[z, y, x] = 42.0;

const auto total =
    e.extent(0) * e.extent(1) * e.extent(2);
std::mdspan<double,
    std::extents<I, I1, I2, I3>, L, A> mdspan;
const auto& [depth, height, width] = mdspan.extents();
for (I z = 0; z < depth; z++)
    for (I y = 0; y < height; y++)
        for (I x = 0; x < width; x++)
            mdspan[z, y, x] = 42.0;
            
const auto total =
    width * height * depth;

Comparing before and after, the usability gain with structured bindings alone is marginal, but it allows us to use descriptive names for the extents to improve readability.

The proposed feature is increasingly useful when structured bindings can introduce a pack, as proposed in [P1061R4] and shown below:

With P1061
std::mdspan<double, std::extents<I, Is...>, L, A> mdspan;
const auto& [...es] = mdspan.extents();
for (const auto [...is] : std::views::cartesian_product(std::views::iota(0, es)...))
    mdspan[is...] = 42.0;

const auto total = (es * ...);

In this example, we trade readability for generality. Destructuring the extents into a pack allows us to expand the extents again into a series of iota views, which we can turn into the index space for mdspan using a cartesian_product. Notice, that the implementation is also rank agnostic, and for std::layout_right (std::mdspan's default) iterates contiguously through memory.

2. Design space

2.1. Handling static extents

When destructuring std::extents we can deal with the compile-time/static extents in two ways:

Option A is arguably simpler and may be less surprising. The structured bindings just represent what the extents(i) member function would return. Option B retains the compile-time nature of static extents at the cost of imposing a mix of integers and std::integral_constants upon users.

Regarding optimization potential, option A should rarely be a problem since structured bindings refer to a concrete instance of std::extents in scope, which is thus visible to the compiler. Using constant propagation, the compiler can likely determine the compile-time value that the structured bindings refer to. In the provided example below, g++ 12.2 successfully unrolls the nested loops and transforms them into vector instructions.

It’s worthwhile to point out that std::integral_constant has a non-explicit conversion operator to its value_type, so it will be demoted automatically to a runtime value where needed (e.g. in all examples above).

2.2. Modification

Modifications of the values stored inside a std::extents should not be allowed, since it is neither possible in case of a static extent nor does it follow the design of std::extents::extent(rank_type) -> index_type, which returns by value.

3. Implementation Option A (demote static extents to runtime values)

One possible implementation is to use the tuple interface and delegate to std::extents::extent(rank_type):

namespace std {
template <size_t I, typename IndexType, size_t... Extents>
    constexpr IndexType get(const extents<IndexType, Extents...>& e) noexcept {
        return e.extent(I);
    }
}

template <typename IndexType, std::size_t... Extents>
struct std::tuple_size<std::extents<IndexType, Extents...>>
    : std::integral_constant<std::size_t, sizeof...(Extents)> {};

template <std::size_t I, typename IndexType, std::size_t... Extents>
struct std::tuple_element<I, std::extents<IndexType, Extents...>> {
    using type = IndexType;
};
An example of such an implementation using the Kokkos reference implementation of std::mdspan on Godbolt is provided here: https://godbolt.org/z/zo5Wb6TMG.

4. Implementation Option B (retaining static extents)

One possible implementation is to use the tuple interface and query the extents type whether a specific extent is static or not. Depending on this information, either the runtime extent via std::extents::extent(I) or a std::integral_constant of the appropriate index type and static extent is returned:

namespace std {
    template <size_t I, typename IndexType, size_t... Extents>
    constexpr auto get(const extents<IndexType, Extents...>& e) noexcept {
        if constexpr (extents<IndexType, Extents...>::static_extent(I) == dynamic_extent)
            return e.extent(I);
        else
            return integral_constant<IndexType,
                static_cast<IndexType>(
                    extents<IndexType, Extents...>::static_extent(I))>{};
    }
}

template <typename IndexType, std::size_t... Extents>
struct std::tuple_size<std::extents<IndexType, Extents...>>
    : std::integral_constant<std::size_t, sizeof...(Extents)> {};

template <std::size_t I, typename IndexType, std::size_t... Extents>
struct std::tuple_element<I, std::extents<IndexType, Extents...>> {
    using type = decltype(std::get<I>(std::extents<IndexType, Extents...>{}));
};

An example of such an implementation using the Kokkos reference implementation of std::mdspan on Godbolt is provided here: https://godbolt.org/z/841PeWM18.

5. Polls

The author would like to seek guidance on whether structured bindings for std::extents are perceived as useful and whether to continue with this proposal. And if yes, whether implementation Option A or Option B is preferred.

6. Wording

TODO

Add the following to [mdspan.extents.overview] after the deduction guide for std::extents:
// [mdspan.extents.tuple], tuple interface
template<class T> struct tuple_size;
template<size_t I, class T> struct tuple_element;
template <class IndexType, size_t... Extents>
  struct tuple_size<extents<IndexType, Extents...>>;
template <size_t I, class IndexType, size_t... Extents>
  struct tuple_element<I, extents<IndexType, Extents...>>;
template <size_t I, class IndexType, size_t... Extents>
  constexpr IndexType get(const extents<IndexType, Extents...>& e) noexcept;

Add a new section after [mdspan.extents.dextents]:

24.7.3.3.7 Tuple interface [mdspan.extents.tuple]

template <class IndexType, size_t... Extents>
  struct tuple_size<extents<IndexType, Extents...>> : integral_constant<size_t, sizeof...(Extents)> { };
template <size_t I, class IndexType, size_t... Extents>
  struct tuple_element<I, extents<IndexType, Extents...>> {
    using type = IndexType;
  };

Mandates: I < sizeof...(Extents) is true.

template <size_t I, class IndexType, size_t... Extents>
  constexpr IndexType get(const extents<IndexType, Extents...>& e) noexcept;

Mandates: I < sizeof...(Extents) is true.

Returns: e.extent(I)

6.1. Feature-test macro

Add the following macro definition to 17.3.2 [version.syn], Header <version> synopsis, with the value selected by the editor to reflect the date of adoption of this paper:

#define __cpp_lib_extents_structured_bindings 20XXXXL // also in <mdspan>

7. Acknowledgements

I would like to thank Mark Hoemmen and Christan Trott for encouraging me to write this proposal, Mark Hoemmen for suggesting implementation B, and Michael Hava for reviewing.

References

Informative References

[P0009r18]
Christian Trott; et al. MDSPAN. 2022-07-13. URL: https://wg21.link/P0009r18
[P1061R4]
Barry Revzin; Jonathan Wakely. Structured Bindings can introduce a Pack. 2023-02-14. URL: https://wg21.link/P1061R4