pon., 16 wrz 2024 o 22:07 Alfredo Correa napisał(a):

Hi Andrzej, (and all),

Thank you for taking the time to write your answer and the quick first-impressions

On Mon, Sep 16, 2024 at 7:17 AM Andrzej Krzemienski wrote:

...

śr., 26 kwi 2023 o 23:38 Alfredo Correa via Boost napisał(a):

...

The library is available here, https://gitlab.com/correaa/boost-multi.

Hi Alfredo,

Thank you for sharing your library. This has been more than a year now, and I am sorry for the delayed response. Thank you for reminding us of it in the slack channel. From this, I gather that the game is still afoot.

yes, it is. No problem about the delayed response.

...

I personally never needed to manipulate big multidimensional arrays, so I cannot immediately appreciate the usefulness of the library. I need a good introductory part. When I read the high-level description, I immediately think, "it is the same as std::mdspan". The docs say that it is different from the std::mdspan, but then I think, "no, it is the same as std::mdspan".

In my experience manipulating (big) multidimensional arrays boils down to 3 things:

1) manage allocations carefully, 2) resolve the tension between 1D access in a n-dimensional space. (Handle logic access but also fuse loops when performance demands it.) 3) good separation between value and reference semantics to avoid unnecessary copies when possible and ensure true value semantics when needed. Well-defined semantics in generic settings avoid the need for "defensive" copies.

Regarding the above statement "manipulating big multidimensional arrays boils down to 3 things [...]", it should go into the front matter of the docs. If I have read it first -- even though it doesn't tell me how the library manages allocations -- it already makes me confident that this library is a good match. The author knows the problem domain, the key points to be addressed. I also get a heads-up on what I will see in the further part of the docs and in the implementation.

None of this is directly tackled by std::mdspan. std::mdarray is newer, and I didn't have time to experiment with it. My understanding is that mdarray doesn't tackle these problems either, only 1) partially since it is going to be a container-adaptor (it will rely on an underlying container).

ok

...

From the comparison table, I gather that Multi offers both the container and the views (sort of references), and that std::mdspan is only a view. Am I right?

yes

...

The docs say that Multi provides value semantics, but I guess it is not a fair statement.

Multi provides value semantics that no other library provided so far IMO, and that is a fair statement.

...

I guess (and correct me if I got this wrong) that the container is value-semantic, but the views are not.

That is the nature of the views, that you want them *not* to have value

...

semantics.

I don't like to use the term "views" because it can mean many things, especially because the ranges and spans abuse the term. It means so many things that even the term "owning" views are used now, which is opposite to your definitions ("the nature of the views, that you want them *not* to have value semantics"). In my opinion, the current use of "view" has no well-defined reference semantics, no well-defined consistency propagation, and no well-defined lifetime. Individual elements can return anything, basically, l-values, e-values, or proxies. It seems that "view" nowadays means anything that is not strictly container-value but is related to it. For this reason, I stopped using the term view for my library. I tend to use more term subarrays and reference objects (not necessarily language references).

Ok, you make a good case for avoiding the term "view". But it leaves us without a good term to communicate. I meant something like std::string_view: you pass it by value, and "something" is copied (the pointer and the size), but you have the guarantee that the underlying sequence of characters is not copied. Is this what you call a subarray? But if so, I do not think that the term conveys the idea. A subarray sounds like a (deep) copy of a portion of the original array. Other candidates for a name: "span", "ref".

...

A fair comparison, should compare Multi's views to std::mdspan.

I touch on this on the section "Substitutability with standard vector and span". With respect to semantics mdspan is the same as span. In a few words "Multi's views" are proper references (as much as the language allows) and std::mdspan is a mix of things (that is lately accepted as good enough under the "view" wording).

Now, the Standard library has also a proposal in flight to add a container

...

for multi-dimensional arrays: std::mdarray: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p1684r2.html Could you also include it in your comparison? And I would expect that std::mdspan and std::mdarray are treated as one in this case.

Yes, I could to that, I can add mdarray in the same column as mdspan, and bump its specified requirement to C++26. (Multi is C++17) Take into mdarray is very recent I only had access to an experimental implementation of it.

...

I read that Multi's types have an STL-compatible interface (range).

yes, because it provides a iterators begin() and end() that are random access that access the multidimensional structure. The access can be recursive (A2D.begin(), A2D.end(), A2.begin()->begin(), etc) or flattened (A.elements().begin(), A.elements().end()).

I will add this explicitly early in the documentation.

...

But this is far from obvious what it means in the context of multi-dimensional arrays. The range/iterator interface was tailored for one-dimensional data structures. There is no obvious generalization to multiple dimensions.

There are two "canonical" generalizations to multiple dimensions, the library handles both is two different clear ways, recursive and flattened.

The first consists in regarding a multidimensional as *nested* 1D ranges, where the order of nesting corresponds to the indices ordering.

In this view given a multidimensional object A (dimensional larger than one), The A[0], A[1], A[2],... is a one dimensional sequence of ranges of lower dimension than A. If done right, all algorithms that work on 1D ranges should work on the range A.begin()... A.end().

If you write a function that is agnostic of the ultimate (true) dimension of A, you are writing dimension-generic code.

The second is to see the whole multidimensional object as a 1D range of all the "terminal" (zero-dimensional elements), that is an unravelled version of the array.

Both generalizations are useful, one is accessed through indices, or iterators, A[i] and A.begin(), A.end(). The interesting thing is that A itself is regarded as a 1D object for algorithms that expect that. For example std::ranges algorithms. The other generalization is accessed through the .elements() member. A.elements() gives all the elements across all dimensions are a linear range.

...

I wouldn't even expect a multi-dimensional array to give me an STL interface (whatever that means).

And yet it does. You know what it means now.

Imagine it, you have a multidimensional object and all the algorithms of STL and std::ranges and (if you wrote your generic functions carefully) all your functions that deal with 1D random access containers would work!

Yes, this makes sense. So you can observe an N-dimensional array as a long, flattened one-dimensional sequence (and this sequence is an STL sequence); and you can view an N-dimensional array as a (STL-compatible) sequence of (N-1)-dimensional arrays. I think the introduction should have it.

Maybe, you mean that the library offers a view where you can see the

...

entire multidimensional array as a long string of values? This would make sense, but if it is the case, I expect the introduction to say exactly this.

Presenting the multidimensional array as a long string is something that fundamentally breaks the abstraction of the multidimensional object, so I delayed referencing to it.

It is mentioned in the "comparison table" in the row "flattening of arrays".

I am going to add this distinction more prominently.

...

In the case of std::mdspan, it has been said that it has been tailored to efficiently represent both huge datasets as well as tiny 4x4 matrices. I am not sure if this is the case, but I request that the docs for Multi say what use case they have been designed and optimized for.

In this sense it is designed as std::vector, it is optimized for the large-n case number. It is not optimized (amortized) for insertions or push_backs because of the nature of multidimensional arrays and space and time efficiency constrains and to maintain symmetry among subdimensions.

Except for the fact that it wasn't programmed for compile-time dimensions (like mdspan was),

About this, does the implementation not miss on efficiency or correctness because of that? Fixed sizes or dimensions are the information that could be used in the implementation. By "correctness" I mean that you could stack a number of static_asserts that check things related to these constants). the small-n case shouldn't be bad either.

Also, there is no small-array optimization. Since the library is very good at interfacing with allocators, it gives the option for stack-based allocator for small array.

The other optimized case is on the dimensionality, in the sense that it is generic. Dimensionality is handled recursively.

...

Does the library only represent dense matrices, or can it also represent sparse data?

Who talked about "matrices"? :) (yes, I mistakenly wrote it once in the documentation)

The point is that the term 'matrices' (and 'tensors') carry semantic meaning, such as algebraic operations, related to liner algebra (and geometry). If someone wants to implement matrices using Multi they are welcomed, and of course, as you said, using multi::array from Multi is an obvious candidate to implement dense matrices.

From the intro paragraph: "The library's primary concern is with the storage and logic structure of data; it doesn't make algebraic or geometric assumptions about the arrays and their elements. In this sense, it is instead a building block to implement algorithms to represent mathematical operations, specifically on numeric data. Although most of the examples use numeric elements for conciseness, the library is designed to hold general types (e.g. non-numeric, non-trivial types, like std::string, other containers or, in general, user-defined value-types.)"

Ok, so I unnecessarily involved the tem "matrix", but I think the notion of dense vs sparse representation still applies here. But I also gather from the other parts that the container only handles the dense representation.

...

The term "stride-based". It is not clear to me what it means.

It referees to the main data structure layout that the library supports. Ultimately, it says that the data of any Multi object is arranged as base + i1*stride1 + i2*stride2 + i3*stride3 + ...

Sorry, I still don't get it. I also do notunderstand if there are any other possible representations, not stride-based.

mdspan/mdarray gives (completely?) general layouts, but at the price of no-iterators, and fewer complexity guarantees.

If there is a better name for it, please let me know.

I wouldn't know, and maybe "stride-based" is a good one, but you may need to explain it; unless you are certain that whoever needs a multi-dimensional matrix already knows what "stride-based" means. (Maybe it is the case.)

...

I cannot see from the introduction if this library will throw exceptions.

It does not. It embraces the basic exception guarantee in general.

Operations that allocate may throw exceptions from the allocator, which is provided by other libraries.

Ok, so on GPUs that may not support exceptions, you can provide a non-throwing allocator, and you have no-exceptions guarantee. Is that right?

Logical errors when using the library result in UB or assertions when possible.

I understand that these logical errors boil down to unsatisfied preconditions, right? If so, I would recommend using this term: if preconditions of this library function are not satisfied, it results in undefined behavior, which this library attempts to reflect via assertions.

I will make this clear in the documentation.

...

The comparison between Multi and std::mdspan in the row "const-propagation semantics" is unfair. I guess you are comparing Multi's container with a view.

Not in particular, I am comparing all aspect of Multi. All aspect of Multi should propagate constness (modulo bugs).

...

A view is not expected to propagate constness.

(it seems that nothing is expected from "views" after all, so everything is allowed)

Multi subarrays, and iterators propagate constness, IMO in a way that ranges should have propagated constness. I choose to propagate constness because it makes const useful.

Ok, maybe if I dig deeper, I will understand it better. Regards, &rzej;

...

So this is the very initial feedback, I hope it helps.

It helps a lot actually, I appreciate your time and effort. I will proceed to improve the documentation based on your comments.

Thank you, Alfredo

Hi again Andrzej, Here it is my response. Thank you again for your clarifications. This time I actually did changes in the text, (list of changes for reference https://gitlab.com/correaa/boost-multi/-/commit/f5c99131a57892785862daa35558... ) pon., 16 wrz 2024 o 22:07 Alfredo Correa mailto:alfredo.correa@gmail.com> napisał(a): 1) manage allocations carefully, 2) resolve the tension between 1D access in a n-dimensional space. (Handle logic access but also fuse loops when performance demands it.) 3) good separation between value and reference semantics to avoid unnecessary copies when possible and ensure true value semantics when needed. Well-defined semantics in generic settings avoid the need for "defensive" copies. Regarding the above statement "manipulating big multidimensional arrays boils down to 3 things [...]", it should go into the front matter of the docs. If I have read it first -- even though it doesn't tell me how the library manages allocations -- it already makes me confident that this library is a good match. The author knows the problem domain, the key points to be addressed. I also get a heads-up on what I will see in the further part of the docs and in the implementation. Great, I changed the intro and now it has the following modified bullets I don't like to use the term "views" because it can mean many things, especially because the ranges and spans abuse the term. It means so many things that even the term "owning" views are used now, which is opposite to your definitions ("the nature of the views, that you want them *not* to have value semantics"). In my opinion, the current use of "view" has no well-defined reference semantics, no well-defined consistency propagation, and no well-defined lifetime. Individual elements can return anything, basically, l-values, e-values, or proxies. It seems that "view" nowadays means anything that is not strictly container-value but is related to it. For this reason, I stopped using the term view for my library. I tend to use more term subarrays and reference objects (not necessarily language references). Ok, you make a good case for avoiding the term "view". But it leaves us without a good term to communicate. I agree, we are running out-of-words. I meant something like std::string_view: you pass it by value, and "something" is copied (the pointer and the size), but you have the guarantee that the underlying sequence of characters is not copied. Is this what you call a subarray? yes But if so, I do not think that the term conveys the idea. A subarray sounds like a (deep) copy of a portion of the original array. Ok, a deep copy would make another array (or array-value) in my vocabulary, generally of lower dimensionality. I use the term subarray because it conveys that is a subset of another set and they values are still linked to it (reference). Other candidates for a name: "span", "ref". “Span” is already used (for whatever spans are) and “ref” is not a word. Perhaps I can use the composite word subarray-reference to be more specific. I think I am going to use the words “array-value” and “subarray-reference” to emphasize this. In the documentation of the classes I now say: “A subarray-reference is part (or a whole) of another larger array. It is important to understand that `subarray`s have referential semantics, their elements are not independent of the values of the larger arrays they are part of. The elements and structure of a `subarray` can be copies into a new array-value (type `array`, see later) to recover value semantics. …” A fair comparison, should compare Multi's views to std::mdspan. I touch on this on the section "Substitutability with standard vector and span". With respect to semantics mdspan is the same as span. In a few words "Multi's views" are proper references (as much as the language allows) and std::mdspan is a mix of things (that is lately accepted as good enough under the "view" wording). Now, the Standard library has also a proposal in flight to add a container for multi-dimensional arrays: std::mdarray: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p1684r2.html Could you also include it in your comparison? And I would expect that std::mdspan and std::mdarray are treated as one in this case. Yes, I could to that, I can add mdarray in the same column as mdspan, and bump its specified requirement to C++26. (Multi is C++17) Take into mdarray is very recent I only had access to an experimental implementation of it. I modified the table to add the information I could gather about mdarray. Take into account that I have been genereous with mdarray and gave it the benefit of the doubt since I don’t know the details. Note that by the author of the mdarray and mdspan implementations, they are separate libraries in principle: “In order for the two proposals to be independent I will keep that apart for now (unless LEWG tells me otherwise) and write a follow up paper which simply adds an overload to submdspanwhich does the above to forward to the overload taking an mdspan.” https://stackoverflow.com/a/74020681/225186 Yes, this makes sense. So you can observe an N-dimensional array as a long, flattened one-dimensional sequence (and this sequence is an STL sequence); and you can view an N-dimensional array as a (STL-compatible) sequence of (N-1)-dimensional arrays. I think the introduction should have it. Thank you, I rephrased further the bullets at the start: “Features of this library that aim to facilitate the manipulation of multidimensional arrays include: * Value semantics of multidimensional array containers and well-defined referential semantics to avoid unnecessary copies if possible. * Availability of different access patterns to the elements in the multidimensional structure, as nested sequences or as a single sequence of elements. A D-dimensional array can be interpreted either as an (STL-compatible) sequence of (D-1)-dimensional subarrays or as a flattened one-dimensional (STL-compatible) sequence of elements, assuring interoperability with legacy and modern libraries (e.g., STL, ranges, Thrust --CUDA and AMD GPUs--, Boost). * Careful memory management and allocation to exploit modern memory spaces, including GPU memory, mapped memory, and fancy pointers.” Except for the fact that it wasn't programmed for compile-time dimensions (like mdspan was), About this, does the implementation not miss on efficiency or correctness because of that? Fixed sizes or dimensions are the information that could be used in the implementation. By "correctness" I mean that you could stack a number of static_asserts that check things related to these constants). Yes, it *could* be used to increase correctness but at the expense of complicated code. IMO there is no performance gain in making arbitrary dimensions constexpr, remember that the internal representation is with “strides”, strides are calculated from sizes, if even one is runtime, almost the whole stride information results in runtime values. The only optimal case is when compile-time dimensions are at the start or at the end of the indexing. When it is at the end one could have multi::array< std::array, D – 1>, but I digress. To be fair with the compilers, they can take advantage of knowing at compile type the dimensions of the multi::array already; I have examples in compiler explorer in which the known compile-time values are propagated all the way to the element access calculation point. I guess I can make the assertions “more constexpr”, perhaps using GCC extensions to catch more compile-time mistakes. BTW, multi::arrays can be used in constexpr contexts in C++2? as long as the allocation doesn’t “escape”. Ok, so I unnecessarily involved the tem "matrix", but I think the notion of dense vs sparse representation still applies here. But I also gather from the other parts that the container only handles the dense representation. Yes, it is the dense in the sense that all elements exist in memory at once, subarrays obtained from subblocks are not contiguous necessarily. The term "stride-based". It is not clear to me what it means. It referees to the main data structure layout that the library supports. Ultimately, it says that the data of any Multi object is arranged as base + i1*stride1 + i2*stride2 + i3*stride3 + ... Sorry, I still don't get it. I also do notunderstand if there are any other possible representations, not stride-based. Yes, there are other possible (dense) layouts, such as block or zig-zag, or Hilbert. See fig 4 here: https://dl.acm.org/doi/10.1145/3555353 As in any data structure, it is a compromise, in these layouts random access requires more computation but neighbor elements in the array are statistically closer in memory. The don’t generalize very well in more that 2 dimensions. mdspan/mdarray gives (completely?) general layouts, but at the price of no-iterators, and fewer complexity guarantees. If there is a better name for it, please let me know. I wouldn't know, and maybe "stride-based" is a good one, but you may need to explain it; unless you are certain that whoever needs a multi-dimensional matrix already knows what "stride-based" means. (Maybe it is the case.) Yes, I think the person that knows will know and the person that doesn’t will interpret the array internal structure as a black box. Ok, so on GPUs that may not support exceptions, you can provide a non-throwing allocator, and you have no-exceptions guarantee. Is that right? YES Logical errors when using the library result in UB or assertions when possible. I understand that these logical errors boil down to unsatisfied preconditions, right? If so, I would recommend using this term: if preconditions of this library function are not satisfied, it results in undefined behavior, which this library attempts to reflect via assertions. Yes. Do you want that in the introduction? Ok, I added it: “The library does not throw exceptions, but it provides basic guarantees (such as no memory-leaks) in theie presence (e.g. thrown from allocators). Indexing and other logical errors results in undefined behavior, which this library attempts to reflect via assertions.” Multi subarrays, and iterators propagate constness, IMO in a way that ranges should have propagated constness. I choose to propagate constness because it makes const useful. Ok, maybe if I dig deeper, I will understand it better. Yes, please feel free to try your “const-correctness” in Godbolt. Take a look at https://www.youtube.com/watch?v=qv29fo9sUjY This section https://gitlab.com/correaa/boost-multi/-/blob/master/README.md#const-correct... And this example: https://godbolt.org/z/sWj7KrcM1 (notice that some std::ranges can be allowed to write elements inside the `print` function) BTW, if you still have the energy I would like to know your opinion on this section: https://gitlab.com/correaa/boost-multi/-/blob/master/README.md#uninitialized... Thank you very much for your help, I added you into the thanks section, I can remove it if you want. Alfredo