Some early studies of the constraints with the MULTI container library

Hi @BobSteagall and @hatcat ,

I have been testing your reference implementation to use my https://gitlab.com/correaa/boost-multi as a storage engine.

MULTI is a general purpose container of dynamic arrays for arbitrary dimension, focuses only on dense strided memory layouts. One of the principles of the library is that dimensionality of anything wuth dimension D can be seen also as something of dimension D - 1 of elements of higher dimension; therefore allowing generic programming in multiple dimensions. It also is agnostic to linear algebra applications.

So, in some aspect is more general than the LA proposal engines (arbitrary dimensionality) and is some aspects it is less ambitious (no linear algebra, no fancy or sparse storage strategies). The good thing is that I believe the storage and view engine concept should also be independent of the LA operations, so the intersection of the two projects is the case of D = 2 (and perhaps D = 1).

With this in mind, I added this simple test to verify the constraints and already I find some incompatibilities out of the box (I am using the branch r7z)

#include "test_common.hpp"

#include "linear_algebra/matrix.hpp"

using namespace STD_LA;
using namespace STD_LA::detail;
using namespace MDSPAN_NS;

#include "alf/boost/multi/include/multi/array.hpp"

TEST(MULTI_ENGINE, InitialCheck)
{
    namespace multi = boost::multi;
    STD_LA::matrix< multi::array<double, 2> > v;
}

I get out the box these 3 initial errors which I think can help both improve my library and also the LA proposal, see my comments interleaved:

/home/correaa/prj/wg21/tests/test_multi.cpp: In member function ‘virtual void MULTI_ENGINE_DefaultCtor_Test::TestBody()’:
/home/correaa/prj/wg21/tests/test_multi.cpp:25:49: error: template constraint failure for ‘template<class ET, class COT>  requires (copyable<ET>) && (default_initializable<ET>) && (readable_matrix_engine<ET>) class std::experimental::math::matrix’
   25 |         STD_LA::matrix< multi::array<double, 2> > v;
      |                                                 ^
/home/correaa/prj/wg21/tests/test_multi.cpp:25:49: note: constraints not satisfied
In file included from /home/correaa/prj/wg21/include/matrix:144,
                 from /home/correaa/prj/wg21/tests/test_common.hpp:10,
                 from /home/correaa/prj/wg21/tests/test_multi.cpp:1:
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp: In substitution of ‘template<class ET, class COT>  requires (copyable<ET>) && (default_initializable<ET>) && (readable_matrix_engine<ET>) class std::experimental::math::matrix [with ET = boost::multi::array<double, 2>; COT = void]’:
/home/correaa/prj/wg21/tests/test_multi.cpp:25:42:   required from here
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp:590:9:   required for the satisfaction of ‘readable_engine_fundamentals<ET>’ [with ET = boost::multi::array<double, 2, std::allocator<double> >]
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp:743:9:   required for the satisfaction of ‘readable_matrix_engine<ET>’ [with ET = boost::multi::array<double, 2, std::allocator<double> >]
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp:591:5:   in requirements with ‘const ET& eng’ [with ET = boost::multi::array<double, 2, std::allocator<double> >]
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp:597:18: note: nested requirement ‘is_convertible_v<typename ET::reference, typename ET::element_type>’ is not satisfied
  597 |         requires std::is_convertible_v<typename ET::reference, typename ET::element_type>;
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ok, my arrays have M2D::reference and M2D::element_type typedefs but you expect a different meaning from them. We have a common meaning for element_type which is the type of the elements, e.g. scalar. However in my library, reference is an object of lower dimension, not necessarily a scalar.

multi::array<double, 2> A({10, 5});
// multi::array<double, 2>::element_type is double
// multi::array<double, 2>::reference is not double&, it is multi::basic_array<double, 1, double*>, a reference-like object of dimension 1.

The logic behind this is that I want to view A as a 1D container of arrays of dimension 1D from the point of view of access and iteration.

For example

multi::array<double, 2>::reference A3 = A[3];
assert( A3.size() == 5 )

My suggestion is that reference is renamed to element_ref or element_reference in the proposal, which I can also add to my library (I already use element_ref, element_cref, element_ptr and element_const_ptr.

(My logic also applies to value_type, multi::array<double, 2>::value_type is precisely multi::array<double, 1>, just to give another example. This is consistent because multi::array<double, 2>::reference is convertible to multi::array<double, 2>::value_type)

As far as I see, the engine concept doesn't need to support subviews of views of lower dimension, that is fine, but a clear meaning of "reference" would be helpful.

...
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp:598:18: note: nested requirement ‘is_convertible_v<typename ET::const_reference, typename ET::element_type>’ is not satisfied
  598 |         requires std::is_convertible_v<typename ET::const_reference, typename ET::element_type>;
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Same argument for const_reference, I suggest to rename it to element_const_reference or element_cref.

...
/home/correaa/prj/wg21/include/linear_algebra/engine_support.hpp:600:23: note: the required expression ‘eng.capacity()’ is invalid
  600 |         { eng.capacity() } -> same_as<typename ET::size_type>;
      |           ~~~~~~~~~~~~^~
cc1plus: note: set ‘-fconcepts-diagnostics-depth=’ to at least 2 for more detail
make[2]: *** [tests/CMakeFiles/la_test.dir/build.make:238: tests/CMakeFiles/la_test.dir/test_multi.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:959: tests/CMakeFiles/la_test.dir/all] Error 2

Due to constraints and tradeoffs that occur in multiple dimensions (in general) I do not support space reservation. Therefore the concept of capacity, separated from sizes or the number of elements is non-existent. Of course I could add a trivial capacity function but that will send the message that my library supports space reservation.

More importantly, how does it concern to a LA library if the storage engine supports capacity or space reservation in general? I understand that resizing may be supported to perform inplace changes in the extensions of the matrices but I think in that case, "resizing" alone is the required operation.

Incidentally, in my library I call it .reextent({nx, ny, ... }), I don't use the word .resize because I don't provide amortized operations like std::vector does and I don't want to give the impression I do. The only virtue of reextent is doing element preservation.

Ok, that is what I have for now. Let me know if you want to talk about this points, I am available in Slack too.

To illustrate the reference/element problem I have the following code test:

using NDArrays = std::tuple<
    multi::array<double, 1>,
    multi::array<double, 2>,
    multi::array<double, 3>
>;

BOOST_AUTO_TEST_CASE_TEMPLATE(convertibles, NDArray, NDArrays)
{
    static_assert( std::is_convertible_v<typename NDArray::      reference, typename NDArray::value_type> );
    static_assert( std::is_convertible_v<typename NDArray::const_reference, typename NDArray::value_type> );

    static_assert( std::is_same_v<typename NDArray::element_type, typename multi::array<double, 1>::value_type>);
    static_assert( std::is_same_v<typename NDArray::element_ref , typename multi::array<double, 1>::reference >);

    using NDRef = typename NDArray::ref;

    static_assert( std::is_convertible_v<NDRef, NDArray> );

    static_assert( std::is_convertible_v<typename NDRef::      reference, typename NDRef::value_type> );
    static_assert( std::is_convertible_v<typename NDRef::const_reference, typename NDRef::value_type> );

    static_assert( std::is_same_v<typename NDRef::element_type, typename multi::array<double, 1>::value_type> );
    static_assert( std::is_same_v<typename NDRef::element_ref , typename multi::array<double, 1>::reference > );
}

also available here: https://gitlab.com/correaa/boost-multi/-/blob/master/test/concepts.cpp

BobSteagall / wg21

Some early studies of the constraints with the MULTI container library #74