P1684: Add questions and answers to proposal

Here are some questions and answers regarding mdarray's design,
that came out of an e-mail discussion to which we responded yesterday.

Why don't we use universal template parameters (P1985) to reduce verbosity?

One suggestion for mdarray was to accept concise
std::array-like expressions like mdarray<float, 3, 4, 5>,
as well as fully elaborated expressions like
mdarray<float, extents<size_t, 3, 4, 5>>.
This would depend on the "universal template parameters"
language feature proposed in P1985.
Besides that, it resembles how Kokkos::View
(the predecessor of mdspan) deduces "canonical" template arguments
from any reasonable order in which the user might list
the actual template arguments. For example,

• [mdspan.layout.policy.reqmts]
  could be used to identify the layout type,

• [mdspan.accessor.reqmts] could be used to identify accessor type,

• the contiguous container requirements to be used to identify the Container type, and

• whatever template argument is left would be the ElementType.

We did not take this approach for the following reasons.

1. It would not be consistent with mdspan,
   whose design was fixed in C++23.

2. It would have hindered writing generic interfaces that take mdarray.

3. It would proliferate instantiations and have a higher compile-time cost.

Consistency with mdspan

The first three template parameters of mdarray
are the same as the first three template parameters of mdspan.
This makes it clear that

a. mdarray and mdspan behave similarly with respect to their
ElementType, extents, and layout; and

b. their behavior differences relate particularly to their
last template parameter (mdarray has a container,
while mdspan has an accessor).

Given that mdspan is now in C++23,
changing mdspan would be practically impossible.

Regarding verbosity, the current mdspan template parameters design
was not what the mdspan authors had originally proposed.
The original mdspan proposal specified extents compactly,
e.g., mdspan<float*[3]*[5]*, ...> expressed
an mdspan of float with
extents<size_t, dynamic_extent, 3, dynamic_extent, 5, dynamic_extent>.
This would have required changing the C++ language itself
to accept syntax like float*[3]*[5]*, which in turn would have required
changing the definition of "incomplete type."
EWG rejected this as inadequately researched.

The mdspan authors later proposed reducing verbosity in ways
that would not affect the core language definition
(e.g., by abbreviating dynamic_extent with dyn),
but LEWG rejected those suggestions.

In practice, users often deal with mdspan's verbosity by creating
aliases whose names convey semantic information. matrix_view<float>
is a lot nicer than mdspan<float, dextents<size_t, 2>, layout_left>,
for example.

Writing generic interfaces taking mdarray

Suppose that I want to write a function do_something that takes
an mdarray of any ElementType, extents, and container type,
with overloads for layout_left and layout_right.
With the current mdarray design, it might look like this.

template<class Elt, class Ext, class C>
void do_something(const mdarray<Elt, Ext, layout_left, C>& a);

template<class Elt, class Ext, class C>
void do_something(const mdarray<Elt, Ext, layout_right, C>& a);

Now suppose that we want mdarray<Elt, 3, 4, 5>
to mean mdarray<Elt, extents<size_t, 3, 4, 5>>.
If mdarray is a class template and not an alias,
then the above interface would not accept mdarray<Elt, 3, 4, 5>.
One would need to use constraints to express overloads
for diffent layouts. This would make the interface more verbose,
obfuscated, and expensive to compile.
Here is an example of how to get the same effect as the above overloads
using the "universal template parameters" mdarray design.

template<template auto... Params>
  requires(
    is_same_v<typename mdarray<Params...>::layout_type, layout_left>
  )
void do_something(const mdarray<Params...>& a);

template<template auto... Params>
  requires(
    is_same_v<typename mdarray<Params...>::layout_type, layout_right>
  )
void do_something(const mdarray<Params...>& a);

Now suppose we want this interface
only to accept float as the ElementType.
With the current mdarray design,
this is easy both to implement and to read.

template<class Ext, class C>
void do_something(const mdarray<float, Ext, layout_left, C>& a);

template<class Elt, class Ext, class C>
void do_something(const mdarray<float, Ext, layout_right, C>& a);

With a universal template parameters mdarray design,
this adds both verbosity and compile-time cost.

template<template auto... Params>
  requires(
    is_same_v<typename mdarray<Params...>::value_type, float> &&
    is_same_v<typename mdarray<Params...>::layout_type, layout_left>
  )
void do_something(const mdarray<Params...>& a);

template<template auto... Params>
  requires(
    is_same_v<typename mdarray<Params...>::value_type, float> &&
    is_same_v<typename mdarray<Params...>::layout_type, layout_right>
  )
void do_something(const mdarray<Params...>& a);

Furthermore, this design makes it impossible
to define the function in a separate compilation unit.
One must write a "generic" yet fully constrained implementation
to catch all the ways that users might express the "same" mdarray.
For example, if I know that the ElementType is float,
the Extents are extents<size_t, 3, 4, 5>,
the Layout is layout_left,
and the Container is std::array<float, 60>,
the current mdarray design would let me declare

void do_something(const mdarray<float, extents<size_t, 3, 4, 5>,
  layout_left, std::array<float, 60>>& a);

in a header, and define the function in a separate source file.
However, the universal template parameters design
would require a fully constrained, yet generic declaration
and definition in a header file.

template<template auto... Params>
  requires(
    is_same_v<typename mdarray<Params...>::value_type, float> &&
    is_same_v<typename mdarray<Params...>::extents_type,
      extents<size_t, 3, 4, 5>> &&
    is_same_v<typename mdarray<Params...>::layout_type, layout_left> &&
    is_same_v<typename mdarray<Params...>::container_type,
      std::array<float, 60>>
  )
void do_something(const mdarray<Params...>& a);

Reducing instantiations and compile-time cost

We already mentioned above how a universal template parameters
mdarray design would add compile-time cost to interfaces taking mdarray,
by forcing use of requires constraints instead of simple overloads.
Just using mdarray would likely also increase build cost.
First, if users could supply template arguments in different orders,
then mdarray would need more deduction and error checking
to find the "canonical" template parameters.
Second, accepting mdarray<float, 3, 4, 5>
as well as mdarray<float, extents<size_t, 3, 4, 5>>
would take more deduction effort.
For instance, the current mdarray design only needs to check
that the second template argument is an extents specialization.
Third, with the universal template parameters design,
it would become more likely that users would instantiate
different specializations of mdarray with exactly the same behavior,
that nevertheless would count as different types
in terms of compilation, generation of debug symbols, and linking.
The current mdarray design avoids this redundancy.

Why is std::vector the default container type?

In the current mdarray proposal,
the default container type is always std::vector.
Users must spell out std::array explicitly
if they want that as the container type.
There's no extents-based automatic selection of the container type.
We have encountered the following objections to this design.

1. mdarray could use std::array as the default container type
   if all the extents are known at compile time,
   and use std::vector otherwise.

2. std::vector is a poor default, because it takes extra space
   to store the capacity as well as the size,
   even though mdarray is not resizable.

We had originally proposed (1), but LEWG explicitly rejected this.
This design would have obfuscated the cost of moves
and the invariants of a moved-from mdarray.

Regarding (2), first, LEWG's resolution of (1) means that
users who mix compile-time and run-time extents
would need to choose the container type themselves anyway.
(It's important to note that some users
want $O(1)$ move behavior and control of allocation,
even if all the extents are known at compile time. For example,
some users may want to allocate a 3 x 3 array with cudaMallocManaged,
where moves don't reallocate.)
Such users would have the opportunity to use a custom container
that supports dynamic allocation without resizing.
This "ideal" default container type,
which does not currently exist in the Standard,
has the following properties.

a. Its constructor accepts a run-time size,
and an optional allocator.

b. Its size is fixed after construction.

This is dynarray, which was proposed as
N3662 ("C++ Dynamic Arrays"),
but was voted out of C++14 into a Technical Specification.
Writing a new proposal that reintroduces dynarray,
with updated wording, would likely be a much more expensive
and time-consuming WG21 exercise than proposing mdarray
as a container adapter.

Second, there is a good reason to use std::vector
as the container type.
P1684R5 (re)introduces the ability to move the container
out of an mdarray, via the extract_container member function.
This enables reusing a container as storage
for multiple mdarray in a sequential "chain,"
rather than asking users to reuse storage via a custom allocator
(which would add complication and run-time cost).
Container reuse justifies using std::vector as mdarray's container,
because the vector could grow to fit differently sized mdarray,
without necessarily requiring reallocation on each growth.

Why isn't mdarray a container instead of a container adapter?

We considered a container design, but ultimately decided on the
current container adapter design. This section explains our reasons
for retaining the container adapter design.

First, just making mdarray manage the allocation itself
wouldn't make mdarray a "container."
The Standard Library's container requirements all include iterators.
This would require us to define multidimensional iterators.
For general layouts, multidimensional iterators
are nearly impossible to make performant
without fanciful compiler support.
(Consider that we permit nonunique layouts, for example.)
Ignoring nonunique layouts and just returning an iterator
to the underlying storage already poses problems.
For instance, should std::copy of a rank-2 layout_left
to a rank-2 layout_right mdarray perform a transpose?
More generally, should mdarray iterators encode
some canonical iteration order, even if that iteration order
is not the most performant for the mdarray's layout?
Do nonunique layouts mean that nonconst iterators
should have a different order (only over the "unique elements")
than const iterators (over the full domain)?
These questions pose potential performance traps for unwary users.
As a result, we have elected not to provide iterators
for either mdspan or mdarray.
This means that mdarray cannot be a container.

Second, a multidimensional array container whose default allocation and
cost-of-move behavior depend only on the extents,
really should be two containers,
just like std::array and std::vector are two containers.
However, this would prevent use of custom containers,
and would make it harder to write generic interfaces using mdarray.

Third, it would likely be much more time consuming
to write the wording and finish WG21 review
of a new container than a new container adapter.

The issue provides the proposed questions and answers for the P1684 mdarray design, but it does not name a target file or test. Locate the P1684 proposal document, add the supplied material in the appropriate section, and verify that its Markdown, code examples, and links render correctly.