P2642R2: LEWG 2023/06/14 presentation

[mhoemmen]

P2642 (padded mdspan layouts)

Use cases

1. Overaligned start of each contiguous segment of elements

   • aligned_accessor (P2897R0) only constrains .data()

   • Compile-time stride lets compilers prove overalignment of every row / column

   • Easier for compilers to vectorize; can skip loop prelude & postlude (less code)

2. Any submatrix of a row-major or column-major matrix

   • Layout of every contiguous submatrix of a layout_left or layout_right matrix

   • Layout of BLAS and LAPACK

   • Preserve stride-1 access in one dimension

Alternatives

• Just use layout_stride?

  • No compile-time strides

  • Function taking layout_stride mdspan must check {left, right}most stride at run time to guarantee contiguous access

• Hypothetical strided layout that permits any combination of compile- & run-time strides?

  • Common case of strided layouts: subview of existing layout_left or layout_right. Any run-time extent makes all strides to its left / right run-time values. The larger the rank, the less the overall benefit.

    • Example: submdspan of layout_left::mapping<extents<int, dynamic_extent, 5, 7, 11>> has all dynamic strides, even if subview's extents are known at compile time.

  • Fully compile-time extents and strides could support features of a specific computer architecture (e.g., specialized matrix-matrix multiply hardware). However, these hardware features are "atoms"; their input and output layouts are indivisible, so subviews aren't meaningful.

Why we allow padding_stride=0 (also at compile time)

Leftmost (for layout_left_padded; rightmost for layout_right_padded) extent is zero at compile time: extents<Integral, 0, ...>.

template<int Value>
using Int = integral_constant<int, Value>;

layout_left::mapping<extents<int, 0, 10>> mapping{};
mdspan m{nullptr, mapping};
auto m_sub = submdspan(m, tuple{Int<0>{}, Int<0>{}}, full_extent);

P2642?	m_sub.mapping()
Before	layout_stride::mapping<extents<int, 0, 10>>
After	layout_left_padded<0>::mapping<extents<int, 0, 10>>

Errata

• Consider renaming padding_stride template parameter, as it's not the "actual" compile-time padding stride

• .extents() returns by value, not by const reference

  • [mdspan.layout.reqmts] specifies that .extents() returns const extents_type&, but layout_{left,right}_padded::mapping::extents in P2642 returns extents_type.

  • layout_{left,right}_padded::mapping does not store the user's extents object

    • It stores the "padded extents"

    • Effectively a "layout_{left,right} of a bigger array"

  • Fix: Change to return const extents_type&; still return a new object, but rely on lifetime extension

• Specification of layout_left_padded<ps>::mapping(const layout_left_padded<ps>::mapping<OtherExtents>&) converting constructors and operator== may need adjustments, so that the spec as written can deduce the input padding_stride template argument.

  • Consider adding a public member to layout_{left,right}_padded::mapping so users can get the padding_stride template argument without needing to write a traits class

Implementation

PR 237 in https://github.com/kokkos/mdspan

Design suggestions from Tomasz Kamiński via reflector

layout_left::padded<ps>::mapping instead of layout_left_padded<ps>::mapping

The padding_stride template parameter must live outside the mapping.
Otherwise, it wouldn't be possible to construct the mapping from just
an extents object.

Layout mapping conversion customization point?

Current design: Explicit converting constructors

Current design includes converting constructors from less constrained to more constrained mappings, e.g., layout_left_padded to layout_left mapping. These constructors are conditionally explicit if there are nontrivial preconditions.

We did this because it matches existing conversions like layout_stride to layout_left.

Tomasz points out two disadvantages of the current approach.

1. Conditionally explicit mdspan constructor is also used to convert dynamic-extent to static-extent mdspan.

2. Adding additional layouts with the current approach would require modifying existing layout classes to add constructors.
   Also, users could not define conversions from custom layout mappings to Standard layout mappings.

Alternative: assume_layout customization point

Tomasz proposes an alternative design, where mdspan provides an assume_layout<Layout> customization point, that changes layout from more to less generic (e.g., strided -> padded -> left).

Advantages:

• Customizable for custom -> Standard layout mapping
• Avoids O(n^2) problem of adding new layout mappings

Disadvantages:

• Would we have to change the existing specification of mdspan's converting constructor?
• Use of explicit mdspan converting constructor is not common