P2642R2 LEWG 2023/03/28 presentation

[mhoemmen]

P2642 (padded mdspan layouts)

Use cases

1. Overaligned start of each contiguous segment of elements

   • Explicit SIMD usually requires overalignment by SIMD width

   • "Pitched" allocations for coalesced memory access

   • Compilers more likely to vectorize and 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

• New 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. 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 result'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&; 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

[mhoemmen]

Feedback on Tomasz's questions

layout_left_padded vs. layout_left::padded

LEWG points out that the "topology" of layouts and layout mappings is that mappings live one level inside layouts. This matches the definition of a layout as a function from extents type to mapping type. Nesting a layout inside of another layout would break this.

Converting constructors vs. assume_layout

We don't foresee a strong need for a general layout mapping conversion customization point, for the following reasons.

• We don't expect to add many more layouts to the Standard.

• Existing layouts cover most use cases for strided layouts.

• submdspan (P2630) doesn't need explicit converting constructors for new layout mapping types, just an ADL-findable overload of submdspan_mapping.

• Other layouts, custom or future-Standard, would generally form their own self-contained "systems" -- e.g., slicing a space-filling curve layout won't result in a Standard layout.