LEWG Kona 11/2023 Padded Layouts Review

[crtrott]

Padded Layouts

• Proposes two new layouts: layout_left_padded and layout_right_padded
• Similar to layout_left and layout_right but store one stride, allowing padding of the leftmost or rightmost dimension

Compare memory storage of layout_left and layout_left_padded:

int data[] = {0, 1, 2, 3, 4, 5};
mdspan<int, dextents<int,2>, layout_left>
  m(data,extents(3,2));

for(int col=0; col<m.extents(0); col++) {
  for(int row =0; row<m.extents(1); row++) 
    std::cout << m[col,row] << " ";
  std::cout << std::endl;
}
// prints:
//  0 3
//. 1 4
//  2 5

// Want colums to be aligned to cache lines - i.e. pad with dummy values 
int data[] = {0, 1, 2, 999, 3, 4, 5, 999};
mdspan<int, dextents<int,2>, layout_left_padded<4>>
  m(data,extents(3,2));

for(int col=0; col<m.extents(0); col++) {
  for(int row =0; row<m.extents(1); row++) 
    std::cout << m[col,row] << " ";
  std::cout << std::endl;
}
// prints:
//  0 3
//. 1 4
//  2 5

• Layouts take padding parameter: layout_left_padded<PaddingValue>
• The padding stride (i.e. stride(1) for layout_left_padded or stride(extents_type::rank()-1) for layout_right_padded) is the next larger multiple of PaddingValue for the corresponding extent.

using map_t = layout_left_padded<4>::mapping<dextents<int, 2>>;
map_t m(3,2); // => m.stride(1) == 4
map_t m(4,2); // => m.stride(1) == 4
map_t m(5,2); // => m.stride(1) == 8

• PaddingValue can be static or dynamic (std::dynamic_extent)
  • if it is dynamic, provide the stride as an argument to the constructor

Use cases:

• alignment of rows/columns/subtensors to cache lines/page boundaries etc.
• more efficient support for very common subsets of submdspan for layout_left, layout_right
  • i.e. don't have to fall back to layout_stride but preserve the stride-1 compile time knowledge for a lot of common cases
  • Extremely common in linear algebra: these layouts were originally part of the linalg proposal
• Note: these layouts are what was actually the default layouts for the mdspan predecessor Kokkos::View

Impact on existing elements in C++23/26 draft

• Also provides converting constructors in layout_left and layout_right
  • for rank > 1 has precondition checks that stride(0) == extents().extent(0) etc.
  • for rank < 2 can convert layout_left_padded to layout_right etc.
• Modifies C++26 submdspan

  mdspan<int, dextents<int, 3>, layout_left> m(ptr, 6, 3, 3);
  auto m_sub = submdspan(m, pair{1,3}, pair{2,3}, 0);
  // Previous: decltype(m_sub) => mdspan<int, dextents<int, 2>, layout_stride>
  // Now: decltype(m_sub) => mdspan<int, dextents<int, 2>, layout_left_padded<dynamic_extent>>

[mhoemmen]

LEWG review 2023/11/09:

1. Remove the new feature test macro, and instead, bump the existing submdspan macro __cpp_lib_submdspan
2. Stray semicolon somewhere in the class declaration
3. Constructor defined inline, so we can strike it from the wording below the class.