Regression: Extent of compound struct datatypes

[dalcinl]

I think I've found a regression in Open MPI v4.1.0, cf mpi4py/mpi4py#29.

The extent of compound struct datatypes is being computed incorrectly. Use the attached file as a reproducer align.c.txt (sorry for the .txt extension, just a workaround for GitHub restrictions on attachments).

Try it yourself in your console as shown below. The last two lines show the mismatch. This looks like a regression, Open MPI v4.0.4 produces the expected output.

shell$ mv align.c.txt align.c
shell$ for i in `seq 0 5`; do mpicc -DCASE=$i align.c; ./a.out; done
c-sizeof=4  mpi-extent=4
c-sizeof=4  mpi-extent=4
c-sizeof=4  mpi-extent=4
c-sizeof=4  mpi-extent=4
c-sizeof=4  mpi-extent=3
c-sizeof=4  mpi-extent=2

[rhc54]

If 4.0.1 shows an error, and 4.0.4 has been fixed - I'm not sure what you are asking us to do about it? We already fixed it, yes?

[dalcinl]

If 4.0.1 shows an error

Sorry! I meant v4.1.0, I corrected the description.

[bosilca]

Actually I think that c-sizeof=4 mpi-extent=3 is the correct answer for the subarray case. My main argument to support this, is that unlike any other type creation the subarray creation adds soft markers in the datatype, and these soft markers change the computation of extent (as described in 5.1.6). More specifically:

1. subarray creation specifically adds the lb and ub markers on the generated datatype (as described in the MPI standard 5.1.3), which for your case with the MPI_CHAR datatype will be set at +1. Typemap of the type is then {lb_marker, 0}, {char, 0}, {ub_marker, 1} (when in all other cases is {char, 0}).
2. struct does not add markers nor adapts the extent to the predefined types alignment, so the typemap of the resulting type for case 4 is {lb_marker, 0}, {short, 0}, {char, 3}, {ub_marker, 3}. As an upper bound marker is present the extent of the datatype ignores the alignment rules (as if the struct was created packed in C).

For there reasons, I think that OMPI 4.1 and current master are correctly computing the bounds in your example.

[dalcinl]

@bosilca I don't agree with some of your interpretations of the standard. The consequence of your reasoning is fishy/unexpected/unintuitive behavior. BTW, your references to the MPI standard seems to be for the 2020 MPI-4 draft. I'm still in MPI-3.1, is there anything new in MPI-4 related to this matter?

1. It is true that the MPI standard provides a formula for subarrays that involve the lb/ub markers. That's a necessity of expressing the formula in a recursive way, but do this mean that the lb/ub markers have to be explicitly added to the datatype? How many do you add? One per dimension, as the formula implies? If yes, what's the point, if one at the end would be enough? Should't all that be considered an implementation detail? Is Open MPI explicitly using internal ub/lb markers within subarray datatypes? Compare with struct datatypes. Struct datatypes have to handle the padding $\epsilon$ to compute the final, actual datatype extent, but that extent is 'built-in' in the datatype, not an explicitly attached ub marker. IMHO, subarray datatypes should behave similarly (from an implementation point of view). Anyway, this is a sort of abstract discussion about definitions vs implementation. Let's move on.

2. Even if subarrays (or any other user-defined datatype) do have explicit ub/lb markers, I believe using them to define struct padding is wrong. In your point (2) you say that structs do not add markers. That's very true, there are no explicit markers added, but the struct constructor do have to determine the $\epsilon$ padding to define the proper ub value from which to compute the final extent.

Your comments made me realize what's the reasoning behind current Open MPI behavior. I'm afraid it is quite fishy. For example, try adding the following new case to my reproducer code:

  case 5:
    MPI_Type_create_resized(types[0], 0, (MPI_Aint)sizeof(short), &types[0]);
    break;

and next run it:

$ mpicc -DCASE=5 align.c; ./a.out
c-sizeof=4  mpi-extent=2

That's simply unpalatable.

[bosilca]

You don't get to choose when to add or not the markers. And we should not allow an implementation to choose either, because portability is key in MPI. Overall, the standard is pretty clear about the manipulation of extent and the lb and un markers, and when to take the epsilon in account. Fishy or not, the MPI forum is the place to submit proposals for improvement.

The only reason to have the markers is to be able to add padding to a datatype. But this padding is not only for adding empty space, but also for rewinding the datatype to allow composition. To give you an example, define a column in a row-major matrix, in a way that would allow the use of a count with the resulting datatype. Without the markers this would be impossible.

There is nothing fishy with your datatype, there is no requirement in MPI specifying that the extent has to be greater than the size (take a look at the column datatype from above to see why). What should always be greater or equal to the size is the true extent.

[hzhou]

Your comments made me realize what's the reasoning behind current Open MPI behavior. I'm afraid it is quite fishy. For example, try adding the following new case to my reproducer code:

  case 5:
    MPI_Type_create_resized(types[0], 0, (MPI_Aint)sizeof(short), &types[0]);
    break;

and next run it:

$ mpicc -DCASE=5 align.c; ./a.out
c-sizeof=4  mpi-extent=2

That's simply unpalatable.

I am having trouble understand this case. Can someone explain to me what's going on (regardless whether you think it is correct or not)?

[hzhou]

2\. struct does not add markers nor adapts the extent to the predefined types alignment, so the typemap of the resulting type for case 4 is `{lb_marker, 0}, {short, 0}, {char, 3}, {ub_marker, 3}`. As an upper bound marker is present the extent of the datatype ignores the alignment rules (as if the struct was created packed in C).

I think this argument is questionable. struct does adjust the extent according to the alignment requirement, otherwise, the early cases will be incorrect as well. Your argument is that in a struct, the existence of ub marker on the last type overrides the alignment requirement of all previous types. I don't think that is reasonable.

Also in my opinion, all datatypes have a lb and ub. The explicit ub_marker overrides the implicit ones, but other than that, it doesn't change any of the datatype behavior. So in the case of explicit ub_marker agrees with the implicit ub, I don't think it should have any different behavior.

You don't get to choose when to add or not the markers. And we should not allow an implementation to choose either, because portability is key in MPI. Overall, the standard is pretty clear about the manipulation of extent and the lb and un markers, and when to take the epsilon in account. Fishy or not, the MPI forum is the place to submit proposals for improvement.

I think this is a strawman. I don't think the fishy comment is on whether the 2nd type should have an explicit marker or not.

[ggouaillardet]

I respectfully invite @dalcinl to email mpi-comments@lists.mpi-forum.org and asks the MPI forum what the correct interpretation of the standard is.

Suggesting that Open MPI and MPICH reach a consensus on how to interpret the MPI standard is not the right way to move forward.

[bosilca]

I am having trouble understand this case. Can someone explain to me what's going on (regardless whether you think it is correct or not)?

I am not sure which part of the discussion you are pointing at in your comment.

[hzhou]

I am having trouble understand this case. Can someone explain to me what's going on (regardless whether you think it is correct or not)?

I am not sure which part of the discussion you are pointed at in your comment.

This one https://github.com/open-mpi/ompi/issues/8560#issuecomment-792238970

EDIT: to clarify, I was not pointing at any discussion for this question. I am just trying to understand what is going on in this case (case 5) that gives the results as shown.

[bosilca]

2\. struct does not add markers nor adapts the extent to the predefined types alignment, so the typemap of the resulting type for case 4 is `{lb_marker, 0}, {short, 0}, {char, 3}, {ub_marker, 3}`. As an upper bound marker is present the extent of the datatype ignores the alignment rules (as if the struct was created packed in C).

I think this argument is questionable. struct does adjust the extent according to the alignment requirement, otherwise, the early cases will be incorrect as well. Your argument is that in a struct, the existence of ub marker on the last type overrides the alignment requirement of all previous types. I don't think that is reasonable.

You might have misread my answer. Accounting for alignment is a different topic than adding the markers, these two concept are competing in the context of datatypes.

Also in my opinion, all datatypes have a lb and ub. The explicit ub_marker overrides the implicit ones, but other than that, it doesn't change any of the datatype behavior. So in the case of explicit ub_marker agrees with the implicit ub, I don't think it should have any different behavior.

This is a loose interpretation of the standard because the "implicit" bounds do not propagate, we have explicit rules on how to propagate the markers.

You don't get to choose when to add or not the markers. And we should not allow an implementation to choose either, because portability is key in MPI. Overall, the standard is pretty clear about the manipulation of extent and the lb and un markers, and when to take the epsilon in account. Fishy or not, the MPI forum is the place to submit proposals for improvement.

I think this is a strawman. I don't think the fishy comment is on whether the 2nd type should have an explicit marker or not.

According to the MPI standard there is always a marker on the subarray type. Dot.

[hzhou]

we have explicit rules on how to propagate the markers.

Could you point me to the text?

[bosilca]

I am having trouble understand this case. Can someone explain to me what's going on (regardless whether you think it is correct or not)?

I am not sure which part of the discussion you are pointed at in your comment.

This one #8560 (comment)

EDIT: to clarify, I was not pointing at any discussion for this question. I am just trying to understand what is going on in this case (case 5) that gives the results as shown.

Got it. Not much, the resize force the extent of the datatype to be 2 bytes, which being exactly the same as the size of the type does not change the perception of the datatype. It does however add the explicit marker, which is not used in this case. So the typemap is now {lb_marker, 0}, {short, 0}, {ub_marker, 2}. Thus, when the struct is used to create the final datatype, the marker propagates (MPI 4.0-rc section 5.1.6), so the resulting datatype has now an extent of 2 and a size of 4.

The datatype is legit, but weird and can certainly be misunderstood and mis used. As an example, a send with multiple counts of such a datatype, will send overlapping regions, while a receive would lead to non-deterministic communications (same issue as memcpy without overlapping regions, because MPI does not mandate the order in which each payload of a message is received).

[hzhou]

Thus, when the struct is used to create the final datatype, the marker propagates (MPI 4.0-rc section 5.1.6), so the resulting datatype has now an extent of 2 and a size of 4.

Thanks for the pointers. But I think we have different readings of the text. Could you quote the part that you based your conclusion upon?

[bosilca]

I think I already provided the pointers and examples. If you disagree with my interpretation, put forward yours and back it with pointers to the standard.

[hzhou]

Section 5.1.6 has an example of MPI_TYPE_CONTIGUOUS, which is understandable. I am not sure that example can be easily extended to MPI_TYPE_CREATE_STRUCT and if it does, how does it extends.

If you are quoting the statement on the formula below the mentioned example, that is just an interpretation of a given type map. What we are having in question here is how to determine the type map resulting from MPI_TYPE_CREATE_STRUCT, thus that formula is irrelevant.

If you are looking at other parts of the text, please point.

EDIT: just to clarify, the reason the MPI_TYPE_CONTIGUOUS example is understandable is because each component of the final datatype have explicit lb and ub and it doesn't have alignment issues.

[hzhou]

It does however add the explicit marker, which is not used in this case. So the typemap is now {lb_marker, 0}, {short, 0}, {ub_marker, 2}. Thus, when the struct is used to create the final datatype, the marker propagates

Seems you are saying the existence of a single ub_marker will always become the ub_marker of the entire stuct regardless all the other types inside (or order). That has to be counter-intuitive at least. I don't think there is text supporting this, but point me to it if there is.

[bosilca]

It does however add the explicit marker, which is not used in this case. So the typemap is now {lb_marker, 0}, {short, 0}, {ub_marker, 2}. Thus, when the struct is used to create the final datatype, the marker propagates

Seems you are saying the existence of a single ub_marker will always become the ub_marker of the entire stuct regardless all the other types inside (or order). That has to be counter-intuitive at least. I don't think there is text supporting this, but point me to it if there is.

Indeed, there is no way to remove a marker. I would found much more counterintuitive is if the markers would get removed at the implementors desire. We can argue about the interest, but 1) it is way better than the explicit MPI_LB and MPI_UB markers we had in the prior version of the MPI standard. Right now, the standard is clear, once you got a marker you keep it, until you reset it.

In conclusion one should be careful with creating the datatypes, calls to resize should be used to correctly define the boundaries.

[hzhou]

Indeed, there is no way to remove a marker. I would found much more counterintuitive is if the markers would get removed at the implementors desire.

I see your emphasis on "removing" the marker now.

Well, first I would like to emphasize the text that lb_marker and ub_marker are two additional conceptual datatypes, i.e, they don't really exist, or they exist just for the convenience of explanation or understanding. As conceptually goes, they always exist.

Regardless of the conceptual or not, did the text say anything that we can't add ub_marker? As far as I read that section, an implementation can always add explicit ub_marker to all datatypes. So in the case 5, we are not ignorantly removing the explicit ub_marker, we are removing the ub_marker when there is another entry of type ub_marker with a higher displacement -- exactly as the text says.

[bosilca]

If you are quoting the statement on the formula below the mentioned example, that is just an interpretation of a given type map. What we are having in question here is how to determine the type map resulting from MPI_TYPE_CREATE_STRUCT, thus that formula is irrelevant.

This is no interpretation, this is the formula describing how the markers must be propagated. And this clearly states that if any of the types has a marker, the ub of the type is directly inherited from the marker, without applying to alignment rule (aka. there is no epsilon on the marker case).

[hzhou]

If you are quoting the statement on the formula below the mentioned example, that is just an interpretation of a given type map. What we are having in question here is how to determine the type map resulting from MPI_TYPE_CREATE_STRUCT, thus that formula is irrelevant.

This is no interpretation, this is the formula describing how the markers must be propagated. And this clearly states that if any of the types has a marker, the ub of the type is directly inherited from the marker, without applying to alignment rule (aka. there is no epsilon on the marker case).

That is a formula that --

1. given an explicit typemap
2. how to determine lb(Typemap)
3. how to determine ub(Typemap)

There is nothing in it has anything to do with how the typemap is derived. There is no propagation.

[bosilca]

Indeed, there is no way to remove a marker. I would found much more counterintuitive is if the markers would get removed at the implementors desire.

I see your emphasis on "removing" the marker now.

Well, first I would like to emphasize the text that lb_marker and ub_marker are two additional conceptual datatypes, i.e, they don't really exist, or they exist just for the convenience of explanation or understanding.

While we agree on the fact that they do not have a physical representation, the markers are used for more than convenience of explanation or understanding. They are used to add gaps at the beginning and the end of datatypes, and to define how a count impacts the memory layout of a datatype.

[bosilca]

If you are quoting the statement on the formula below the mentioned example, that is just an interpretation of a given type map. What we are having in question here is how to determine the type map resulting from MPI_TYPE_CREATE_STRUCT, thus that formula is irrelevant.

This is no interpretation, this is the formula describing how the markers must be propagated. And this clearly states that if any of the types has a marker, the ub of the type is directly inherited from the marker, without applying to alignment rule (aka. there is no epsilon on the marker case).

That is a formula that --

1. given an explicit typemap
2. how to determine lb(Typemap)
3. how to determine ub(Typemap)

There is nothing in it has anything to do with how the typemap is derived. There is no propagation.

And how would you get one of these markers inside the type ?

[hzhou]

In my understanding, all datatypes have this conceptual lb_marker and ub_marker to begin with.

[hzhou]

And whether or not the implementation produces or use a typemap with or without explicit markers is the implementation detail, as long as they don't result in the wrong lb ub determination.

[ggouaillardet]

Regardless of the conceptual or not, did the text say anything that we can't add ub_marker? As far as I read that section, an implementation can always add explicit ub_marker to all datatypes.

Are you then saying that MPI_Type_dup(MPI_INT, &type) and MPI_Type_create_resized(MPI_INT, 0, 4, &type) generate an equivalent type?

[dalcinl]

And how would you get one of these markers inside the type ?

That formula with markers inside the type can be traced back to at least MPI-1.1, at the time we had MPI_{LB|UB}, and they could be explicitly inserted anywhere within the list of types used to feed the struct constructor. Those how wrote MPI-2 and added the resize call did not changed the text much, they just moved it around. No surprises that now the thing is darn confusing. I agree with @hzhou's interpretation/proposal/suggestion, simply because IMHO it is the common sense and useful behavior.

Suppose I have the following struct

struct {
  int    a[5][3];
  double b;
}

and I want to create a datatype to communicate a[0][0], a[1][0], and b. I would expect to create a struct datatype out of a subarray datatype with sizes=[5,3],subsizes[2,1],substarts=[0,0],order=C for the a slot and MPI_DOUBLE for the b slot, and of course following the alignment rules of the compiler. But with all the mess in the MPI spec, plus the various interpretations of each development team, it is unlikely such simple approach would be portable.

[hzhou]

Regardless of the conceptual or not, did the text say anything that we can't add ub_marker? As far as I read that section, an implementation can always add explicit ub_marker to all datatypes.

Are you then saying that MPI_Type_dup(MPI_INT, &type) and MPI_Type_create_resized(MPI_INT, 0, 4, &type) generate an equivalent type?

Assuming sizeof(int) is 4, I would say they should generate equivalent type -- equivalent as far as the user can tell.

[ggouaillardet]

So let's have a look at chapter 4.1.6 of MPI 3.1, and look at the formula at page 105.

consider the following code

#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[]) {
    MPI_Init(&argc, &argv);
    MPI_Datatype d, type;
    int bl[2] = {1, 1};
    MPI_Aint offsets[2] = {0, 0};
    MPI_Aint lb, ub;
    MPI_Datatype types[2] = {MPI_DOUBLE, MPI_INT};
    MPI_Type_dup(MPI_INT, &d);
    types[1] = d;
    MPI_Type_create_struct(2, bl, offsets, types, &type);
    MPI_Type_get_extent(type, &lb, &ub);
    printf("extent {(double, 0), (dup(int), 0)} = %ld\n", ub);
    return 0;
}

and let's hope we can both agree to assume sizeof(double) == 8 and sizeof(int) == 4.

type has the following type map

{ (MPI_DOUBLE, 0), (MPI_INT, 0) }

since no entry has type `ub_marker`, the upper bound is given by line 25

max((0+8), (0+4)) + eps

`eps` is zero here, so `ub(type)` is `8`.

Now let's slightly update the code as follow

```c
#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[]) {
    MPI_Init(&argc, &argv);
    MPI_Datatype r, type;
    int bl[2] = {1, 1};
    MPI_Aint offsets[2] = {0, 0};
    MPI_Aint lb, ub;
    MPI_Datatype types[2] = {MPI_DOUBLE, MPI_INT};
    MPI_Type_create_resized(MPI_INT,0, 4, &r);
    types[1] = r;
    MPI_Type_create_struct(2, bl, offsets, types, &type);
    MPI_Type_get_extent(type, &lb, &ub);
    printf("extent {(double, 0), (resized(int,0,4), 0)} = %ld\n", ub);
    return 0;
}

Now type has the following type map

{ (MPI_DOUBLE, 0), (MPI_INT, 0), (ub, 4) }

since there is at least one entry has type ub_marker, type is now given by line 27

max(4)

so ub(type) is 4

If you can spot one or more errors in my interpretation of the standard, please point me to at least one and quote the relevant part of the standard I did not follow.

[hzhou]

Now type has the following type map

{ (MPI_DOUBLE, 0), (MPI_INT, 0), (ub, 4) }

This is the part we disagree with. I don't think the text has anything saying that a ub_mark of one of the constituents can become the ub_mark in the resulting derived datatype directly. In my understanding, the resulting type map is --

{ (MPI_DOUBLE, 0), (MPI_INT, 0), (ub, 8) }

, which is the same as

{ (MPI_DOUBLE, 0), (MPI_INT, 0) }

PS: maybe this type map illustrates my understanding more clearly --

{ (MPI_DOUBLE, 0), (ub, 8), (MPI_INT, 0), (ub, 4) }

They are all equivalent. The ub_mark is just conceptually there for explanations.

[ggouaillardet]

I literally applied the formula at page 94 (MPI_Type_create_struct()), and ended up with

{ (MPI_DOUBLE, 0), (MPI_INT, 0), (ub,4) }

Feel free to prove me wrong by quoting one or more relevant parts of the standard:

• did I fail to ignore (ub, 4) ?
• did I fail to add (ub, 8) somewhere ?
• any other mistake(2) ?

[hzhou]

I literally applied the formula at page 94 (MPI_Type_create_struct()), and ended up with

{ (MPI_DOUBLE, 0), (MPI_INT, 0), (ub,4) }

Thanks for bringing in new facts. Now, on page 94, there is nothing about ub_marker, is there? So where is your (ub, 4) based on?

[ggouaillardet]

MPI_Type_create_resized(MPI_INT, 0, 4, type) generates type with the following type map

{ (MPI_INT, 0), (ub, 4) }

Page 94 says nothing about ub_marker (nor lb_marker fwiw) indeed. That is why my interpretation is ub should be treated just like any other type in the formula (e.g. it cannot be ignored) and this is what I literally did.

[hzhou]

Page 94 says nothing about ub_marker (nor lb_marker fwiw) indeed. That is why my interpretation is ub should be treated just like any other type in the formula (e.g. it cannot be ignored) and this is what I literally did.

So let's acknowledge at this point on, we are both talking about our interpretation. What is the semantics of

{ (MPI_INT, 0), (ub, 4) }

? My interpretation is that means MPI_Type_extent(dt) should return ub of 4 and just that. So the type map of MPI_DOUBLE can be viewed as

{ (MPI_DOUBLE, 0), (ub, 8) }

, unless of course, the user overwrites it with another ub.

There is no text explicitly saying this either, but I believe this interpretation does not contradict any text and fits (my) intuition, fits the semantics of MPI_Type_resize (re-size), and fits the intention of emphasizing ub_marker as conceptual entities.

[ggouaillardet]

page 106 105, lines 20-21 and 25-26 explicitly consider the case a given type map does not have any ub_marker (nor lb_marker fwiw) so I see this as an implicit contradiction with your interpretation that a MPI implementation is free to add ub (or lb) entries to predefined datatypes.

If this fails to convince you, then let's agree to have a honest disagreement on how to interpret MPI the standard.

I hope we can agree that two (allegedly) correct interpretations of the MPI standard is an issue, and the MPI Forum is the right body to address that and provide authoritative guidance.

[hzhou]

I believe you are referring to the formula on page 105. which is a formula on a given type map. You can have a typemap as

{ (MPI_DOUBLE, 0) }

or a typemap as

{ (MPI_DOUBLE, 0), (lb, 0), (ub, 8)}

or a typemap as

{ (MPI_DOUBLE, 0), (ub, 8) }

, and each of these typemaps can be applied with the referenced formula. And they are equivalent. The purpose of the formula in the text is to explain how this conceptual ub_marker supposed to work (i.e. used in calculating lb and ub), nothing else. The clause you mentioned is important for the understanding of lb_marker and ub_marker, but does not imply anything else.

I think at this point we clearly understand each other, that is good enough.

[ggouaillardet]

I stand corrected on the page number, I meant page 105.

[bosilca]

The 2 forms are not equivalent, otherwise 1) the standard would have added lb and ub markers in all examples talking about how to interpret the type map, and 2) the standard would not have make these markers appear explicitly in the equations describing the ub and lb of a datatype, and 3) the standard would have avoided talking about the markers as conditionals in sentences such as "An entry of type ub_marker can be deleted if there is another entry of type ub_marker with a higher displacement; an entry of type lb_marker can be deleted if there is another entry of type lb_marker with a lower displacement."

@dalcinl you seem to interpret MPI_TYPE_CREATE_STRUCT as creating some kind of equivalent to an struct created by a C compiler. This is not the case, it just creates a non-homogeneous type with bytes-level displacements for each element. To further clarify this, the standard explicitly states: "In principle, a compiler may define an additional alignment rule for structures, e.g., to use at least 4 or 8 byte alignment, although the content may have a max_i{k_i} alignment less than this structure alignment. To maintain portability, users should always resize structure derived datatype handles if used in an array of structures, see the Example in Section 19.1.15."