Re: proposal Multi multidimensional array library

From: Alfredo Correa (alfredo.correa_at_[hidden])
Date: 2024-09-18 08:08:53

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/f5c99131a57892785862daa355586af818f2b712 )

pon., 16 wrz 2024 o 22:07 Alfredo Correa <alfredo.correa_at_[hidden]<mailto:alfredo.correa_at_[hidden]>> 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<int, N>, 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-correctness
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-vs-initialized-elements

Thank you very much for your help, I added you into the thanks section, I can remove it if you want.
Alfredo