Coder Social home page Coder Social logo

array_ref's Introduction

ISO C++ Proposals and Supporting Material for mdspan

Proposals

Rendering Bikeshed

You can use the bikeshed API online; for instance, using curl you can do

curl https://api.csswg.org/bikeshed/ -F [email protected] -F force=1 > P0332.html

or you can install bikeshed locally. See https://github.com/tabatkins/bikeshed for more details.

array_ref's People

Contributors

brycelelbach avatar crtrott avatar dsunder avatar hcedwar avatar jlperla avatar keryell avatar mbianco avatar mhoemmen avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

array_ref's Issues

Notes on proposal

notes for the r3 branch

  • Need some examples of use, like a note showing hot to instantiate and accessing an element of the array_erf?
  • Have separate sessions for Properties, Mapping, and Layout (the layout is just a class with a subclass of type mapping. I think in the previous version this was a little hidden, but with the format of the standard, people should be able to follow. Maybe put the layout before the mapping. I don't know if people would be puzzled more by the forward definition or the delayed one.
  • is_layout could be implemented as
#include <type_traits>                                                                                                                                                                                      

template <typename T...>                                                                                                                                                                                    
using void_t = void;                                                                                                                                                                                        


struct my_layout {                                                                                                                                                                                          
    template <typename DType, DType...>                                                                                                                                                                     
    struct mapping {                                                                                                                                                                                        
        using is_mapping = std::true_type;                                                                                                                                                                  
    };                                                                                                                                                                                                      

};                                                                                                                                                                                                          


template <typename T, typename Dummy=void>                                                                                                                                                                  
struct is_layout : std::false_type {};                                                                                                                                                                      

template <typename T>                                                                                                                                                                                       
struct is_layout<T, void_t<typename T::template mapping<int> > > : std::true_type {};                                                                                                                       

int main() {                                                                                                                                                                                                
    static_assert(is_layout<my_layout>::value, "");                                                                                                                                                         
    static_assert(!is_layout<int>::value, "");                                                                                                                                                              

}                                                                                                                                                                                                           
  • The "standard layouts" section should be renamed, I think, into "provided layouts", or "standard provided layouts".
  • Name "domain, codomains, mapping types" into "Types"?

Possible issue with proposed template specialization resolution changes for relaxed array types

Section 5 of the current draft has the following text:

For consistent template specialization resolution of explicit and implicit dimensions the std::extent of an array type declaration must match a template specialization with extent parameters.

template < typename A >
struct array_traits {
  static constexpr unsigned rank = std::rank<A>::value ;
  static constexpr size_t extent_0 = std::extent<A,0>::value ;
  static constexpr size_t extent_1 = std::extent<A,1>::value ;
  static constexpr size_t extent_2 = std::extent<A,2>::value ;
  // etc.
};

template< size_t N0 , size_t N1 , size_t N2 >
struct array_traits< int[N0][N1][N2] > {
  static constexpr size_t rank = 3 ;
  static constexpr size_t extent_0 = N0 ;
  static constexpr size_t extent_1 = N1 ;
  static constexpr size_t extent_2 = N2 ;
};

array_traits< int[1][2][3] > // matches the partial specialization
array_traits< int[ ][ ][ ] > // matches the partial specialization

I'm interpreting this as meaning that the two instantiations at the end of the code snippet, array_traits<int[1][2][3]> and array_traits<int[][][]>, should both match the partial template specialization struct array_traits<int[N0][N1][N2]>.

I believe there are two problems related to this.

Problem A

It is my assumption that if we want the above to work, then we would also want the same behavior for one-dimension arrays.

Unfortunately, the proposed change would NOT be backwards compatible with prior versions of the C++ standard; this would change how one-dimension arrays are matched in templates. The current behavior is as follows:

template <typename T>
struct A       { static constexpr unsigned spec_picked = 0; };

template <typename T>
struct A<T[ ]> { static constexpr unsigned spec_picked = 1; };

template <typename T, unsigned N>
struct A<T[N]> { static constexpr unsigned spec_picked = 2; };

static_assert(0 == A<int   >::spec_picked, "A<int> failed");
static_assert(1 == A<int[ ]>::spec_picked, "A<int[ ]> failed");
static_assert(2 == A<int[3]>::spec_picked, "A<int[3]> failed");

The proposed change would instead give us:

static_assert(0 == A<int   >::spec_picked, "A<int> failed");
static_assert(2 == A<int[ ]>::spec_picked, "A<int[ ]> failed");
static_assert(2 == A<int[3]>::spec_picked, "A<int[3]> failed");

This would presumably be problematic, because it would prevent template metaprogrammers from distinguishing between array types with implicit dimensions and array types with explicit dimensions.

Problem B

If the proposed change was implemented as it is currently written, it is unclear to me what the values of the non-type template parameters would be when they happen to match an implicit dimension. Here's the test case I started writing when I began attempting an implementation in Clang:

template <typename T>
struct A
{
    static constexpr bool specialized = false;
};

template <unsigned N0, unsigned N1, unsigned N2>
struct A<int[N0][N1][N2]>
{
    static constexpr bool specialized = true;
    static constexpr unsigned extent_0 = N0;
    static constexpr unsigned extent_1 = N1;
    static constexpr unsigned extent_2 = N2;
};

int main()
{
    typedef A<int[1][2][3]> a0;

    static_assert(a0::specialized == true);
    static_assert(a0::extent_0 == 1);
    static_assert(a0::extent_1 == 2);
    static_assert(a0::extent_2 == 3);

    typedef A<int[][][]>    a1;

    static_assert(a1::specialized == true);
    static_assert(a1::extent_0 == /* ??? */);
    static_assert(a1::extent_1 == /* ??? */);
    static_assert(a1::extent_2 == /* ??? */);
}

Would the values of N0, N1 and N2 (and extent_0, extent_1 and extent_2) be 0 for the a1 type?

Summary

I am concerned that I am somehow misinterpreting the quoted section of the proposal. If I'm not, I think we need to change this, although it may make it more difficult to implement our proposal - because you'd need to have a large number of partial specializations to match all the possible permutations of implicit/explicit dimensions. E.g.

array_traits<T[  ][  ][  ]>
array_traits<T[N0][  ][  ]>
array_traits<T[  ][N0][  ]>
/* etc, you get the idea */

P0332 confusing statement in one section, and do we need more conversion examples?

Proposed: [dcl.array] 11.3.4 Arrays, p3

There is a thing which starts with "In addition" which is confusing. How is it "in addition" if we just said "any" bound can be omitted. Maybe it should be more something like: "If only the first of the constant expressions that specify the bounds of the arrays is omitted, the incomplete array type may be used: "​

Also do we want to have a more complete example catalogue for matching? Though all the other ones are probably not ambiguous.

Otherwise this looks much better than before. I would be convinced ;-)

Preparation for Oulu

  1. Drop extensibility section
  2. Preferred syntax discussion in a separate and referenced paper.
  3. Mention no requirements on property pack ordering
  4. Concept spec for layout extensibility.
  5. Bounds checking - does it throw? Would perturb 'constexpr'
  6. Drop layout_order for first generation
  7. subarray bounds checking if input array_ref has bounds checking
  8. separate papers for specification and motivation+examples

Static extents and subviews. Is the design complete?

Right now it says "Non-trivial subviews of regular views will often have view_layout_stride." Certainly true, but is this necessary or a good thing?

Aren't static strides also possible and require similar optimization to static extents? Think of view< int[3][4][2]> array and then subview(array, std::extents::all, 3, std::extents::all) (i.e. the matlab equivalent of array(:,3,:). Shouldn't the compiler be able to use at least one static stride?

This also relates to having a std::all for the subview list of indices, because otherwise there would be no way for the slice to know if it has cut down on one of the extents. i.e. in the above subview(array, std::pair(0,2), 3, std::pair(0,1)) can only use static extents through some even more improbable compile time magic of realizing that [0,2] is the whole of the first dimension, etc.


I could be wrong, but I think that this means view_layout_stride would need to be more general and allow a list of possibly static extents? I just fear that this part needs more design. Would the current design allow a: view_layout_stride which is something like template<typename Strides...> struct view_layout{...}; with a magic stride of 0 as dynamic? I think this is an important issue to get right before subview(...) is proposed. Could the layout struct itself manage static strides, or could this change the underlying design of view itself?

An even easier example is view<3,3> array; and subview(array, 1, all) should be contiguous and the compiler should know that it is statically of size 2.

Premailing Checklist

  • Update P0019 to reflect Albuquerque notes - Dan
    The paper had already been updated in November, and it doesn't need to include property ontology
  • Complete P0900 paper to discuss property ontology - David
  • Update P0546 to reference property ontology - Dan
  • Update P0860 to reference property ontology - Dan
  • Update P0856 to reference property ontology - David
  • Update P0009 to reflects Albuquerque meeting notes - Dan
  • Review P00332 for strength and clarity - Dan
  • Proofread for grammar and wording

Unworkable constructor

The following constructor:

explicit constexpr array_ref(pointer p, Properties const&... props) noexcept;

is unworkable as not all properties are construction properties, only perhaps some of them.
In Kokkos we have constructor properties vs. array_ref properties, which have some overlap.

Question about the implementation

Thanks Carter for the updated version,

In the implementation there is a decoupling between layout types and offsets. This would make extendability a little complex since a user should define a tag-type plus an implementation as partial specialization of a (std::) library template. And you still need to model some offset concept.
What I would prefer is to have the layout-offset to model the offset concept so that the extendability does not have to pass through a specialization. The user just have to implement a template class with a give interface. What's the rationale behind the current implementation?

I think this would make even easier to produce a generic affine layout in which the order of the strides are specified at compile time, so that layout_left and layout_right could be simple alias templates of this generic class (I should provide an implementation, shouldn't I?). We are using something similar in our library, a stripped example of implementation can be found in https://github.com/crosetto/examples_cpp/blob/master/Code/Solution/storage_info_sol.hpp#L30 in which the layout map specifies the permutation to apply to the indices in order to get the offsets.

Does any of this make sense to anybody?

"one-line" change to clang still causes acceptance of incorrect code

The "one-line" change to clang (as far as I can tell) that we referenced in the [][] paper is this one (in commit b7b9efb) on the clang github). There are still substantial things that don't work even with that change, though; for instance:

#include <cstdlib>
#include <iostream>

// This *SHOULDN'T* work
void test(int[][][5][][]) {
  cout << "called foo(int[][][5][][])" << endl;
}

int main(int argc, char** argv)
{
  test(*(int(*)[][][5][][])&i);
}

Creating generic views of a static number of dimensions?

Will this interface allow us to create a view with a static number of dimensions? Maybe with some metafunction? This has come up frequently when I write generic libraries. i.e.

template<int N> auto myfunction()
{
view< double[][][]...? > array(...); //Want to generate based on parameter N
//...
}

Using '0' as the "magic value" of dynamic

This makes complete sense.My only question is whether there will be any ugly interactions if zero length arrays are made standard in C or C++? (I believe GCC supports them).

In particular, this may come up if we are forced to go with the alternative in section 6, so that there is a metafunction to create the view_dimension object: view<int, view_dimension<0,3>> == std::view<int, <int[][3]> but also view<int, view_dimension<0,3>> == view<int[0][3]>???

It may be reasonable to just say we will reject all arrays with a zero dimension in the interface?

contiguity and iterators

At the Jacksonville (March 2016) meeting the LEWG discussion included desire for iterators. Performant iterators can be implemented if-and-only-if the referenced array is contiguous and the order of iteration is layout dependent. A strategy:

array_ref {
  static constexpr bool is_always_contiguous ;
  constexpr bool is_contiguous() const noexcept ;
  using iterator = pointer ; // typical, not required
  iterator begin() const noexcept ; // requires is_contiguous()
  iterator end() const noexcept ; // requires is_contiguous()
}

User defined layout?

I have some concerns about “user defined layouts”, if they are possible (I thought they were). A layout, right now is just a tag to select the view_offset. A user then would need to implement the view_offset, and then it's interface should be in the proposal (a C++ Concept). It may be necessary to have different interfaces for different types of layouts, for instance for regular and not regular.

Make the complexity of extent types a little more clear

I think that non-specialist readers comparing this to the array_view proposal are going to have a little trouble understanding why we need all these types for the extents. An extra paragraph may help. Something like the following, perhaps in Section 3:

"Beyond the speedups due to optimal algorithms with better cache locality possible with flexible storage layout, the main feature to achieve zero-overhead abstraction is (potentially) static extents and strides.

For example, with C-style storage layout, a compiler can optimize access to a double[0][3] array by knowing that the first stride is a static 3. To enable these sorts of optimizations, we need to allow for constexpr extents in the type, and use them where appropriate in operator(). So,
view< int[][3] > array( buffer , L );
static_assert(std::is_same<decltype(array.extent(1)), ?????>::value, "Static type"); //TODO, wasn't sure how to show the differences.
constexpr const std::size_t extent_1 = array.extent(1);

For strided layouts, this is also important. For example, a slide of an entire column in the above array give a strided_layout, where the stride is statically known to be 3.

Some notes on the proposal

Hello,
This is a review of the current HEAD (6abdf1d) of the P0009 proposal text.

General

  1. The following can be said for the gsl::span as well but I think some justification needs to be in place: How will queries interact with containers or codebases that use std::size_t?
  2. Should there be a const_mdspan class to indicate that this is a view that doesn't modify the codomain data?
  3. Add using declarations for const_reference and const_pointer?
  4. Maybe provide template deduction guides.
  5. The co-domain space definition may need to be restricted a bit so that it cannot be interepreted that its elements may be pointers. (They could be with the exception of member-function pointers though).
  6. Should there be an additional section describing the allowance of for an mdspan with dynamic number of dimensions for a future addition?

Section 3.2

  1. msspan -> mdspan
  2. Should operator() be defined such that it works with std::tuple and std::array? (The constructor would be nice too).
  3. Maybe add rank_static?
  4. Why is the parameter of the extent member functions int, since it is required it to be >=0?
  5. std::extent integral constants are std::size_t. Shouldn't the rank() return type be std::size_t as well?
  6. Similarly shouldn't the extent member functions return std::size_t so that it is compatible with std::extent?
  7. Should the extent, static_extent and stride be implemented such that they can in addition take the index as a template parameter like: template <std::size_t I> constexpr const size_type &extent(), or this functionallity will be just left to std::extent? Having static access will be necessary for compile-time algorithms.
  8. "Extensions to access properties may cause reference to become a proxy type". This is very useful, can it be elaborated a bit more so that implementations do not lock out of such a feature?
  9. Shouldn't Section 3.2.2 have the remaining using declarations?
  10. Consider changing the name of static_extent. Maybe make it private and introduce a static constexpr bool is_static_extent<I> member function. This will resolve the ambiguity of expressions like "A statically declared extent of dynamic_extent denotes that the extent is dynamic".
  11. "If 0 <= r < rank() the extent of coordinate r. If rank() <= r then extent(r) == 1" requires a run-time check. Should an alternative mechanism be proposed or just say If rank() <= r then extent(r) is undefined?
  12. Should size() be renamed to element_count() or similar?
  13. The size() algorithm should be a non-recursive compile time one.
  14. What does the span() function return if is_always_contigous != true?
  15. Why should rank_dynamic() <= sizeof...(DynamicExtents) and not rank_dynamic() == sizeof...(DynamicExtents)?
  16. V::static_extent(r) == V::static_extent(r) -> V::static_extent(r) == U::static_extent(r)
  17. static constexpr bool is_always_unique: what is the meaning of always?
  18. The mapping observers can be very specific to the layout and I am not sure they should be exposed by mdspan. For example the stride member function may not be appropriate for user-defined layouts (let's say a symmetric matrix, where the stride depends on the indices)
  19. I am not certain that public exposure is needed for required_span_size.
  20. size_type is used in 3.2.7 but not defined anywhere.

Section 3.3

  1. The preferred mechanism for declaring rank and static extents is amazing.
  2. The DynamicExtents constructor should be disabled for an all-static extents.

Section 3.4

  1. What about static slice specifiers?

Section 3.5

  1. size_type is used in 3.5.2 but not defined anywhere.
  2. In 3.5.2, extent in the layout reference interface returns an index_type, but in the description a size_type
  3. Previous comments about compile time flavour of relevant member functions applies here too.

Best Regards,
Nasos

`Middle' implicit dimensions?

As far as I can tell, the interface will allow implicit dimensions in order, double[][3] or double[][], but cannot support double[3][][3] or double[3][] due to the nature of C arrays (even if we aren't really using them internally).

Is there any good reason to avoid these sorts of implicit vs. explicit setups (I believe Eigen and others support either ordering with Matrix<double, 3, Dynamic> MatrixXd, etc. in http://eigen.tuxfamily.org/dox/group__TutorialMatrixClass.html). Is this a major limitation in the interface? In particular, if we are intending to have a fortran storage ordered array, one more natural version is double[3][]?

Add short comparison to array_view?

This is C++ standard politics outside of my paygrade, but I think we need to reiterate that the posted array_view does not fulfil essential needs, and this is a replacement which addresses all of the issues.

Maybe something like:

The essential issue with array_view in N4512 "Multidimensional bounds, offset and array_view, revision 7" is that it does not fulfill C++'s "zero-overhead abstraction'' requirement (for both dynamic and static extents), and does not provide a zero-overhead abstraction to different memory layouts which are essential for library interoperability with a variety of C++ (e.g. Eigen) and other languages (e.g. Fortran and Matlab's C++ interface). Were it to be accepted, another library would be necessary to provide "direct mapping to the hardware'' for views of arrays. Many of the issues are discussed in more detail in N4355, N4300, and N4222.

Unlike N4512, this proposal leaves the layout more general to allow padding and different orderings essential for performance, and keeps all constexpr extents, which allows the compiler to optimize operator(), and allows interoperability with libraries using compile-time extents.


...Part of this is the name. If we think that array_view is the best choice, then we could say something like:

The name view is chosen to differentiate from array_view, but a change to array_view could be considered later.

Dynamic extent and "magic value" of zero

For the preferred array_ref data type syntax

using A_t = array_ref< int[][][3] > ;

there is no "magic value" required to specify a dynamic range.
Assuming that we cannot persuade EWG to relax the array type declaration for an incomplete object type the backup syntax

using A_t = array_ref< int , array_property::dimension< ... > > ;

needs a "magic value" to specify dynamic vs. static dimensions.
The "magic value" of zero is compact in contrast to some namespaced constexpr value.

using A_t = array_ref< int , array_properties::dimension<0,0,3> > ;

A native array type declaration is not allowed to have zero for a array bounds expression, so there is no conflict.
A default constructed array_ref has consistent and expected extent values for both preferred and dimension syntax.

A_t A ;
assert( A.extent(0) == 0 );
assert( A.extent(1) == 0 );
assert( A.extent(2) == 3 );

One potential concern is that a non-default construction of an array_ref can replace "magic zero" dimensions with dynamic dimension values where if zero were actually a static array bounds expression (which is incompatible with the standard array type declaration) then the extent could not replace the "static zero."

reference_K

I've been trying to use the reference_K implementation since I need the subarray support in there. When I use g++ to compile the test cases, everything work fine. But when I use clang++ to compile them, I get build errors like this:


../include/array_ref:222:44: error: template name refers to non-type template 'dimension_typed<unsigned long, 0, 20, 30, 40>::extent'
      return ( i < I ? Dimension::template extent<I>::value : 1 ) *
                                           ^
../include/array_ref:261:32: note: in instantiation of function template specialization 'std::experimental::array_property::layout_right::mapping<std::experimental::array_property::dimension_typed<unsigned
      long, 0, 20, 30, 40> >::get_stride<0>' requested here
    { return mapping::template get_stride<0>(i); }
                               ^
../include/array_ref:635:20: note: in instantiation of member function 'std::experimental::array_property::layout_right::mapping<std::experimental::array_property::dimension_typed<unsigned long, 0, 20, 30,
      40> >::stride' requested here
    { return m_map.stride(i); }
                   ^

Could this be because the support of C++11 not complete in clang? I tried clang version 3.8.

P0546r0: subspan extent preconditions

On 8/12/17, 5:42 AM, "Bjorn Reese" [email protected] wrote:

I have experimented with P0546R0 for an incremental parser and came
across a minor issue.

The incremental parser finds the next token in the input and updates its
current position using a subspan(). When reaching the end, the span
becomes empty. The empty subspan is not allowed by the pre-conditions of
P0546R0. This problem is easily solved by changing the pre-conditions
from

   offset < size()
   offset + count < size()

into

   offset <= size()
   offset + count <= size()

`operator()` implementation with (some) static extents

I just wanted to do a sanity check that the implementation of operator() is able to handle fixed extents for optimization.

Stating the obvious simplest example:

view<int[][]> dynamic_test = ...; //Set both extents to 2, and fill in with 2x2
view<int[2][2]> static_test = ...; //Fill in the 2x2 data.
dynamic_test(1,1); //Compiler has to lookup both strides in memory, etc.
static_test(1,1); //Compiler could generate code using both constexpr strides

Of course, when finding the offsets/strides in dynamic_test, there isn't much that can be done. But one of the strides is constexpr and 2 in the static example, gives plenty of opportunity for optimization.

I think it would be useful in the document to give a simple example saying how operator() could implement this generically. It may just come down to clever organization with constexpr.

If there is no tricky way to do it generically, is it going to require a combinatorial number of overloads of operator() to use the constexpr version where available and a dynamic lookup of strides? (i.e. a concept that checks a whether each index is static or not). The number of overloads required may also interact with storage ordering. I think that view<int[][2], view_layout_right> and view<int[][2], view_layout_left> have different optimization possibilities for the 2 constexpr stride.

Sorry if I missed the steps or description in the current setup. Feel free to completely ignore this if I am off base or missing something simple.

Make the existence of a reference implementation clearer

I think it is valuable to point out that there is a partially complete reference implementation, give the URL, etc. My guess is that one major pushback from the microsoft folks will be that this is entirely unproven.

This could go on its own paragraph at the bottom of section 1, with emphasized text to make sure noone misses it.

Add paragraph explaining why extents are tricky here?

I think that a paragraph explaining why extents are tricky is useful. Maybe something like:

The complexity in implementing extents is that the type depends on whether the extent was given statically or dynamically. As discussed before, this is essential to ensure a zero-overhead penalty for the abstraction. For example, consider view< int[ ][3][3] > array_1 vs. view< int[ ][ ][ ] > array_2. Calling array_1.extent(1) returns a constexpr const std::size_t, while array_2.extent(1) returns a const std::size_t. This static information is essential for the compiler to generate an efficient operator() or for interfacing libraries such as Eigen to query an underlying static extent to enable SIMD optimizations based on the known extent length, etc.

Range paper on proxy iterators

See http://open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0022r0.html

Sounds like this problem is basically solved for the range. If we knew about this earlier, it may have been possible to add in in iterators to the current design. This stuff is above my head, but it sounds like:

  • The ValueType and ReferenceType would end up being view with potentially strided layout for ours (in general), potentially with the static extents depending on where the iterator is.
  • Then an iter_swap is necessary to be defined. I think this would basically just copy the data between the slices of the view referenced, and I see no problem with it.
  • I don't know what iter_move means with these sorts of setups, but I suspect that isn't an issue particular to this setup (e.g., what does iter_move look like with std::array<int,10> right now?

P0900 Concerns - insufficiently vetted by Kokkos team

P0900 was generated quickly from some initial discussions. This proposal has not received sufficient vetting with the rest of the Kokkos / ISO-C++ team (@hcedwar, @crtrott, @dsunder, @mhoemmen). However, the 2018-03-Jacksonville pre-meeting deadline is too soon to allow sufficient vetting and this topic is too important to not submit a paper.

Decision: Revise abstract to note that this is initial exploration of this design. If the paper is taken up by LEWG at 2018-03-Jacksonville then the objective is to prompt discussion and collect perspectives of the available experts for a subsequent revision to (1) include more stakeholders and (2) make a concrete proposal.

bikeshed processing

@dhollman : Need to add instructions for bikeshed processing / viewing / converting so that paper source files can be verified before commits & merges. Github doesn't have an automatic viewing feature for .bs like its does for .md and .rst

P0900: Per Property Assignability combined with "default property mode"

In order to get through the "pass it into a generic context" and everybody can convert into everybody quandary we could propose that every property has a default mode. If a span with a property A and a mode alpha is trying to get to assigned to a span which doesn't have property A than assignability is determined by the compatibility of mode alpha with the default mode of A. Thus for example the default mode of atomic_access could be false and the property could define that assigning atomic_access with true to a span with false is not allowed. Thus we have a pretty straight forward non-exponential mechanism to distinguish between properties where it is safe to just ignore the property then passing a span to a function and properties, such as atomic, where it may not be safe to do so. The beauty of this approach is that each property itself is responsibility to define the validity of a decay. One requirement of the default mode of a property would be that it does not have any effect on the span, i.e. it is the same as not defining it.

Summary of ABQ comments on `span`

I'm going through the comments on span from Albuquerque to both understand where span stands relative to incorporation into the IS (and as it relates to P0546, P0856, and P0860) and to make sure we haven't made the same mistakes in mdspan. I'll enumerate summaries of the issues here (some with bulleted responses about how we've treated that in mdspan)

Comments from a thread titled "Questions raised while trying to implement " on the lib-ext reflector:

  • The comparison operators should work with differing extents, particularly if the extent of one of them is dynamic
    • mdspan doesn't define comparison operators, not even operator== (could this be a problem/inconsistency for some people? Probably it's okay to just tell people to convert to span first, especially with the potential for deduction guides on the conversion operators)
  • The comparison operators should be able to compare spans of unequal extents, since std::equal and std::lexigraphical_compare do this
  • span<int> and span<long> should be comparable
  • The comparison operators take their parameters by const reference rather than by value, even though the paper itself recommends passing span by value
    • We should change the free function subspan to take an mdspan by value for the same reason
  • Contiguous iterators and contiguous containers: span currently has (or had?) a constructor that takes a ContiguousContainer (i.e., a Container whose iterators meet the requirements of contiguous iterators [27.2.1]). This isn't implementable via SFINAE (or any other compile-time technique) since contiguous iterator is a runtime property.
    • mdspan doesn't have this constructor. It doesn't look like we're using the term "contiguous" in any contexts that would imply the need for SFINAE, but we should double-check this
  • If the size of the span (in bytes) is larger than numeric_limits<ptrdiff_t>::max() (e.g., as could be the case if sizeof(value_type) is much larger than 1), then as_bytes() and as_writable_bytes() could introduce undefined behavior.
    • This applies to us also. We should consider using size_t here instead. (Also, seems like a good motivation for the T[][][] syntax, so that we don't have to use -1 for a magic extent value)
    • A later note says that LEWG has already discussed this and decided to stick with ptrdiff_t, so maybe we shouldn't change anything.
  • No reason for the nullptr_t constructor, since it's the same as the default constructor
    • Not sure I agree with this one. Implicit convertibility from a nullptr_t is a reasonable trait to have. Either way, we omitted discussion/description of this constructor in the paper, even though it's in the wording.

Other Pre-meeting comments

  • span<int, 42>.subspan<0>() shouldn't return a span<dynamic_extent>
    • This is another artifact of the dynamic_extent magic number. It doesn't look like we have that problem because our subspan extents are always given as normal function arguments rather than template arguments (though this seems like a bit of a shortcoming since it means we can't have a subspan with static extents other than the entirety of the parent's extent for a given rank)
  • all iterator functions shoudl be constexpr
    • mdspan is not iterable (?!?) so this doesn't apply.
  • Shouldn't have both length and size

Small Group discussion comments

  • Lots of discussion about constructors taking shared_ptr/unique_ptr (presumably the array partial specializations)
  • Something indecipherable about propagating noexcept (presumably relating to comparison operators?)
  • The static version should work with std::get, since it is like std::array (though then it would have to participate in structured binding?)
    • Probably not that applicable to mdspan. If you really need this, just convert to a span

Full group discussion

  • Maybe considering switching back to array_view, now that the term view does not imply immutable (presumably with some change to string_view?)
  • Poll to remove unique_ptr and shared_ptr constructors: 6-8-0-0-0
  • Poll to remove nullptr_t constructor: 4-5-3-0-0
  • Poll to remove span(pointer, pointer) constructor: 0-0-2-10-0

Other notes (not from span discussion, but encountered while working on it):

  • On the conversion constructors and assignment operators:
template< typename UType , typename ... UProperties >
constexpr mdspan( mdspan< UType , UProperties ... > const & ) noexcept;
template< typename UType , typename ... UProperties >
mdspan & operator = ( mdspan< UType , UProperties ... > const & ) noexcept;

One of the requirements is that "V::static_extent(r) == U::static_extent(r) or V::static_extent(r) == std::dynamic_extent for 0 < r < V::rank()". This should probably also include the possibility that U::static_extent(r) == std::dynamic_extent.

  • mdspan defines the constraints here in terms of std::is_assignable<U::pointer, V::pointer>, but span defines it in terms of accessing a U::value_type through a V::pointer meeting the rules for well-defined object access defined in [basic.lval]/8. Are these definitions exactly equivalent?

Static queries on extents

Saw your comment on the latest commit that the answer to this is that they will optimize away. Great news.

A few questions to verify:
a) For statically given extents, we would still be able to call array.extent(0) at compile time if it was static?
b) is there a metafunction we can call to determine if a particular extent is static? This was a little easier before.

Non regular layouts?

There is another point I'm trying to understand. A 2D tiled array can be seen as a 4D array in which two dimensions indicate the tile and other two indicate indices within the tile. So if we regard this array as 4D the layout will be regular, possibly bijective. If we consider it as a tiled-2D array, the strides are a little more complicated. Given R and S to be the number os tiles in I and J, then a mapping to 2D to 4D would be (i,j) -> (i/R, j/S, i%R, j%S) This is still bijective but would no have uniform striding ( offset(i,j) - offset(i,j+1) depends on i and j).

I guess this proposal is about regular layouts, in the sense that the user will use a 4D array if a tiled array is needed, is this right?

I'm mentioning this since in my work we use to let the user using a simple abstraction of the data, but then the algorithms can exploit the actual low level layout. We do it explicitly, since we know that there are two levels of abstraction (a view of a view). In general, however, the problem can be more complex: how do I decide when it's time to go "physical"? So, a specific library build on top of the views, would provide the necessary abstractions (e.g., view_offsets that are not regular)

Comments on the paper.

I have some comments.

I would define basic concepts first and then show the interfaces that provide those concepts. For instance I would define what a layout is and what a regular layout is. In this way the reader is already equipped with the basics.
Specifically I would clarify that view_layout_left refers to the fact that the minimum stride is the first, and they decrease monotonically. view_layout_right is the other way around. What about the view_layout_stride (view my next issue)?

In the code the view_layout_right and the default share the same code. Do we need to be more explicit? I do not understand when the proposal says that the "implementation is allowed to pad". How does this happen? I pass a pointer and a view, is the implementation setting my base pointer somewhere else? Is the padding too big to make the indices to go out of bound?

I think that a very useful case is when the user creates a view_layout_right out of another view_layout_right|left with smaller dimensions, in which case the padding happens automatically. I think this is how I would use the library to control alignment.

Alternative type specification for simple cases, to complete with array_view?

I don't have strong feelings on this, but I imagine one pushback will be the array_view folks saying that:
array_view<int, 3> is a lot easier than view< int[ ][ ][ ] > array?

As discussed, a metafunction is possible to make this sort of thing possible. Could we have:
view<int, 3> == view< int[ ][ ][ ] > array?
Or maybe using a type alias with that metafunction, implicit_view<int, 3> == view< int[ ][ ][ ] >?

Even if this is dropped, it might be worth pointing this out. Maybe clearer at the bottom of section 7?

Overuse of specializations?

I’m quite new to the standard committee, but I have the feeling that an API that changes based on template arguments would make people unwilling to accept it. I talk about the _x appended on member function names. Also this will force using several macros in the implementation. I kind of understand the statement that writing .template function<#> is annoying, but it would simplify code that uses the views to produce other libraries. For instance, right now one would use switch to select the proper method out of a template argument. It was already quite hard to convince people that having operator[] for rank 1 views was not a bad idea.

P0332 implies array incompleteness is no longer "local"

After working on a patch to clang for P0332 (pull request with patch coming soon), the biggest issue I see with this proposal is that array incompleteness is no longer "local" (I don't have a better word for this, but it will become clear what I mean pretty soon). That is, you only have to look at the outermost extent to determine the completeness of an array type. Because of this, we can always say that an array type is:

  • complete, T[N], and we don't care about the extents of T (if any) as long as T is a complete type. Thus we only have to store information about [N] with the type and we can treat everything else recursively.
  • incomplete, T[], and we don't care about the extents of T (if any) as long as T is a complete type.

Note that in both cases, we only have to examine one "layer" of the completeness of T, and zero layers of the extents.

Now consider the state of affairs under P0332. Given a type T[N],

  • the type is complete if T is not an array type.
  • if T is an array type of the form U[M], we have to (recursively) examine the completeness of U.
  • if T is an array of the form U[], we know that T[N] is an incomplete type, but we still have to expand the definition of incomplete type to include N (in addition to the extents, if any, of U)

This would lead to some structural changes in the way array types are described in clang. It's not a deal-breaker by any means, but it's emblematic of why this is not a trivial change.

Implications of relaxed array types for function overload resolution

Hi all,

So, in testing the proposed relaxed array type constraints on a patched version of the Clang compiler, I ran into some potential issues with how the relaxed array type constraints interact with function overload resolution. The core of the issue is that the current C++ standard doesn't require recursive array-to-pointer decay. I'm not sure if such a feature is even a good idea, but I thought I'd mention it.

Here's what my test case looks like:

typedef int array_1d_imp[ ];
typedef int array_1d_exp[3];

void test_1d_imp(array_1d_imp a) { a[0] = 1; }
void test_1d_exp(array_1d_exp a) { a[0] = 1; }

typedef int array_2d_imp_imp[ ][ ];
typedef int array_2d_imp_exp[ ][3];
typedef int array_2d_exp_imp[3][ ];
typedef int array_2d_exp_exp[3][3];

void test_2d_imp_imp(array_2d_imp_imp a) { a[0][0] = 1; } // fails: a is an incomplete type
void test_2d_imp_exp(array_2d_imp_exp a) { a[0][0] = 1; }
void test_2d_exp_imp(array_2d_exp_imp a) { a[0][0] = 1; } // fails: a is an incomplete type
void test_2d_exp_exp(array_2d_exp_exp a) { a[0][0] = 1; }

int main()
{
    {
        int a_imp[ ] = { 1, 2, 3 }; 
        int a_exp[3] = { 1, 2, 3 }; 

        test_1d_imp(a_imp);
        test_1d_exp(a_imp);

        test_1d_imp(a_exp);
        test_1d_exp(a_exp);

        int* ap;

        test_1d_imp(ap);
        test_1d_exp(ap);
    }

    {
        int a_imp_exp[ ][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; 
        int a_exp_exp[3][3] = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; 

        test_2d_imp_imp(a_imp_exp); // fails: no conversion from int [3][3] to int (*)[]
        test_2d_imp_exp(a_imp_exp);
        test_2d_exp_imp(a_imp_exp); // fails: no conversion from int [3][3] to int (*)[]
        test_2d_exp_exp(a_imp_exp);

        test_2d_imp_imp(a_exp_exp); // fails: no conversion from int [3][3] to int (*)[]
        test_2d_imp_exp(a_exp_exp);
        test_2d_exp_imp(a_exp_exp); // fails: no conversion from int [3][3] to int (*)[]
        test_2d_exp_exp(a_exp_exp);

        int** ap;

        test_2d_imp_imp(ap); // fails: no conversion from int ** to int (*)[]
        test_2d_imp_exp(ap); // fails: no conversion from int ** to int (*)[3]
        test_2d_exp_imp(ap); // fails: no conversion from int ** to int (*)[]
        test_2d_exp_exp(ap); // fails: no conversion from int ** to int (*)[3]
    }
}

The first thing to note is that while the functions test_2d_imp_imp and test_2d_exp_imp will fail to compile in this example because they attempt to use an incomplete type (e.g. a relaxed array), they will NOT fail to compile if the array type is not used in the function body (e.g. if the function was a no-op instead of a[0][0] = 1, they compile). This is important because you may want to pass in a relaxed array type to a function to specify array extents. E.g. the following might be a valid use-case:

size_t dim = get_dimension(1, int[ ][3][ ]);

If get_dimension doesn't use the incomplete array type, and just extracts information from it via TMP, this /should/ be fine. However, the current function overload rules would prevent this from working, as you can see in the above test case.

Personally, I am fine with how this currently functions, even though I found it a bit non-intuitive at first glance. If we /did/ propose some change to array-to-pointer rules/function overload resolution, it would mean that the relaxation of array type declarators would no longer be a trivial change (for the Clang compiler, the change is currently a one-line patch; I suspect the same will be true for at least GCC).

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.