Strong typing for local and global IDs

[clemensmanert]

Create a new own type for each kind of id, so they can not be mixed up any more.

[devreal]

Can you give an example for which IDs this is problematic?

[fmoessbauer]

This is required, as lbegin(dart_unit_t global_id) requires global unit ids. Hence, I renamed the function parameters too. IMO this is not a good solution as I already mentioned in the meeting, however otherwise we have to change the DART interface.

I know you have changed it in PR #133, however that was not a good one, as then the unit test failed. In fact, the bug was in the Array implementation and not in GlobMem. I stumbled upon this curiosity too.

[fuchsto]

@fmoessbauer Disregard that, I got it myself, can't quite remember why I implemented it this way, though.

EDIT: deleted my comment, you were too quick to answer and I can't seem to undelete it

[fuchsto]

@dash-project/developers

After all, I think @clemensmanert is right.
In C++ noone would give this a second thought and use phantom types or any other strong typing for
exactly this use case.
Documentation is not a solution. Any arcane interface can be documented, good interfaces don't need it.

I would introduce types in DART like:

typedef struct {
  dart_unit_t  id;
} dart_global_unit_t;

typedef struct {
  dart_unit_t  id;
} dart_local_unit_t;

... with some union-magic for convenient strong typing. This would work for DART (C99).

This would solve the situation in GlobMem where some methods expect global, some local unit ids.
We could just provide both:

pointer lbegin(dart_global_unit_t gunit) {
  // ...
}

pointer lbegin(dart_local_unit_t lunit) {
  // convert to global unit id and pass to dart_global_unit_t overload
}

[devreal]

To me it looks like this is only some (though maybe more prominent) form of documentation as well as long as we do not make sure that dart_unit_t itself is never used by the user in DASH. If implicit conversion has to happen we lose all semantic information at some point or another. Not sure what interfaces have to be changed for this to work. Or maybe I'm missing the point here?

[fuchsto]

You might: My intention is the opposite: the strong typing adds semantic information that I don't want to lose.
Let's use dart_group_addmember, where we communicated in code comments about is usage, as an example. It currently looks like this:

dart_ret_t dart_group_addmember(dart_group_t *g, dart_unit_t unitid);

As a user, I would be unsure whether unitid refers to the unit's global rank or its relative id in the current team. Both would make sense.

With strong typing, it would look like this:

dart_ret_t dart_group_addmember(dart_group_t *g, dart_global_unit_t unitid);

Passing dart_unit_t (which would still exist!) or dart_local_unit_t would fail due to a type mismatch.
There is no implicit conversion for struct types in C with reasonable compiler flags, even if the conversion would be trivial. Many excellent libraries use this method for strong typing.

Also, the compiler error would be really, really nice. Something along the lines of
"no function 'foo(dart_local_unit_t)' found, candidate is 'foo(dart_global_unit_t)'"

DASH users won't see these changes but DART is a library on its own with a public interface.
This is definitely relevant to users! If it wasn't, why would we put so much effort in dart-if.
I'm a user, too. I have needs.

[devreal]

Got it, thanks. I'm fine with changing the interface like that and not have implicit conversion (not possible in C anyway but could be possible in C++), even though it's a bit more coding effort (manually creating the struct from a dart_unit_t or using a macro to do it).

[fuchsto]

Right, but in C++ we can do even better and use phantom types like:

namespace dash {
  template <typename IdScope> struct unit_id { dart_unit_t id; }
  typedef unit_id<dash::scope::local>   local_unit_id;
  typedef unit_id<dash::scope::global> global_unit_id;
}

... and provide constructors or use brace initializers for convenient instantiation:

local_unit_id lu { 42 };

Ah yes, and conversion operators must be = delete, that's a crucial point indeed.

[devreal]

Thinking about this a little more it seems that it is only important to be able to differentiate global and local unit IDs based on the type. To make the change less intrusive, we could as well simply typedef dart_global_unit_t to dart_unit_t and create a special struct for dart_local_unit_t. Thus, the default would always be a global unit ID (as has been used already) and only team-local unit IDs have to be treated in a special way.

[fuchsto]

Then we would have another interface / behavior the user has to learn and keep in mind.
To anyone who is not involved in DART code, it would be annoying that there are two different styles to specify a unit id, and they would be mixed up all the time.
Having to "treat FOO in a special way because reasons" is a symptom of a bad interface.

[devreal]

Out of curiosity, I started implementing typed unit IDs for the DASH part. Please see https://github.com/dash-project/dash/compare/feat-143-unitids

Some things I noticed:

1. I do not allow for implicit construction from a dart_unit_t (and related) to prevent type errors from going unnoticed. However, without implicit conversion the initialization of a global_unit_t and local_unit_t cannot be written like:

global_unit_t unit = 0;

but has to be:

global_unit_t unit{0};

2. I started adding typed unit IDs to the GlobMem interface, which already triggered adaptations in some places. There are some explicit conversions required though, which hopefully can be deleted later on.
3. From my understanding, there were some places that used local unit IDs where global IDs would be required, e.g., GlobIter::find, local_range, min_element. Please review.
4. We are using C++11, which does not support multi-statement constexpr functions, which allow some work to potentially be shifted to compile-time. With C++14, all operators on the typed unit ID could be implemented as constexpr. However, this should not be critical in our case.

Overall, I think this is a viable route to go. Once the conversion in DASH is done, it will be much easier to introduce typed unit IDs in DART as it only requires adaptation of the unit_id struct. Please review the implementation so far. If there are no objections, I will continue converting the remaining classes (364 places using dart_unit_t left).

[fmoessbauer]

Hi, at a first glance, I noticed the following points:

• dash::myid() and dash::size() should never be used internally. Better use team.global_id(). Please correct me if I am wrong with this opinion.
• I recommend naming the unit scope as tobi has written above, because it is refers to a scope. See here

The rest of your changes looks great to me.

[devreal]

dash::myid() and dash::size() should never be used internally. Better use team.global_id(). Please correct me if I am wrong with this opinion.

The implementation of team.global_id() was actually a copy of team.dart_id() as it returned the DART team ID so I deliberately deleted it. I also do not see why a team should provide the global ID of a unit if this aspect is already handled by a global function. Maybe I do not see what is wrong with dash::myid() though.

I recommend naming the unit scope as tobi has written above, because it is refers to a scope. See here

Not sure I understand this part. Do mean dash::scope::local? Should this ever be used by a user directly? Are there other scopes already?

[fuerlinger]

The implementation of team.global_id() was actually a copy of team.dart_id() as it returned the DART team ID so I deliberately deleted it. I also do not see why a team should provide the global ID of a unit if th is aspect is already handled by a global function. Maybe I do not see what is wrong with dash::myid() though.

I think what Felix means is that in DASH library code dash::myid() and dash::size() is likely incorrect / not what you want, since most constructs in DASH have a team (possibly different from dash::Team::All() associated with them. Library code should always use team.myid() or team.size() for the correct team that forms the context for the algorihtm/container. Felix, fell free to correct me if this is not what you were getting at.

[devreal]

In the cases where I replaced team.myid() with dash::myid(), the respective library call GlobMem::lbegin() expects a global ID, not a team-local ID, which makes sense since DART global pointer hold global IDs (afaik). We could provide an overload that also takes a local_unitid and performs a translation.

The question is whether teams should provide the global ID of the current unit. IMO, this is not a clean solution as teams should only be concerned with team-local IDs (and the translation to and from global IDs).

[fuerlinger]

Agreed, providing separate global IDs seems redundant to me. The global ID is simply the ID in dash::Team::All() which is always readily available as dash::myid()

[fmoessbauer]

The point ist that I am not happy with dash::myid() at all because its name does not imply to which team it is related. However I understand that for new DASH users (which do not use teams) dash::myid() it is useful. For example MPI does not provide something similar. There you always have to specify to which communicator the id is related. Just my two cents.

To the dash::scope::local point: I am ok with your solution, but I thought I would be good to have the scope name in the type. However this is never exposed to the user, so ignore my comment from above ;)

[rkowalewski]

This seems to be a discussion about our programming conventions. What @fmoessbauer and @fuerlinger meant is that we should not use short-hand statements in our library. While dash::myid() is always the global unit id, it results in better readability to explicitly use the associated context (at least for me). Apart from that, short-hand statements may still change in future while dash::Team::All() should be stable.

An additional comment to the code changes. We explicitly loose the context information if one extracts the native dart_id. However, for this purpose we still have to add type safety for dart_unit_t with some union magic as @fuchsto already mentioned.

[devreal]

So just to make sure I understand this right: your argument is that I should use dash::Team::All().myid() instead of dash::myid()? The issue there is that dash::Team::All().myid() also returns a local_unitid while dash::myid() returns a global_unitid. We would need to introduce a template parameter to dash::Team to control this type (which would be fine with me if this is requested).

As soon as DASH is fully aware of the typed unit IDs a user cannot pass dart_unit_t to any DASH functionality without explicit conversion. As I mentioned above, the adaptation of the DART API can be done easily then, although the C interface will be less comfortable to use imo.

[devreal]

Come to think about it, the return type of dash::Team::All().myid() should be dash::global_unit_t anyway. I will change it accordingly.

I would also propose to implement dash::myid in terms of dash::Team::All().myid() to dedup this functionality.

[fmoessbauer]

I am not sure how you are going to implement that. dash::Team::All returns a reference to a dash team and team.myid() should always return a relative id. This is also supports my idea of team.global_id()

[fuchsto]

@devreal Thank you so much for putting your time into this.
I will digest your implementation and the discussions and add my remarks here.

[devreal]

@fmoessbauer I was a bit too fast on that, it's not easily possible to implement this using a template (since dash::Team::* would become dash::Team<>::* across the code base). However, I still think that team.global_id() is bad design because a specific team couldn't care less about the global unit ID.

If we still want to encapsulate the accessor for the global unit ID inside dash::Team we could have a static function along with the other accessors for invariants like All() and Null():

  /**
   * The invariant unit ID in \c dash::Team::All().
   */
  inline static global_unit_t GlobalUnitID()
  {
    return global_unit_t(Team::_team_all.myid());
  }

Not sure whether this provides any benefit over the dash::myid() shortcut though.

[fuchsto]

@devreal I aggree, for several reasons.

Briefly put, from the perspective of a specific team, there is no "global". You have to "step outside" of the team's reference frame to view the global scope.

A static method looks very intuitive to me to express this because developers simply cannot obtain the global position from a team instance, they have to consolidate the type dash::Team which has no execution context. Nice one.

[fmoessbauer]

Ok, you convinced me. I did not even thought about a static method. IMO the static method is the best solution. Thanks for putting time into this and the enlightening discussion.

[devreal]

I just finished converting most of the places where dart_unit_t was used to using typed unit IDs.

The usage of global_unit_t is quite rare. However, in many places the default Team::All() team is used if no team is explicitly specified, thus requiring the otherwise legal use of dash::myid() to be converted to local_unit_t. I'm also not quite happy about the fact that dash::Team::All().myid() returns local_unit_t while dash::myid() returns global_unit_t since it is not entirely consistent and might lead to confusion. However, I don't see a better way of doing this at the moment.

Overall, the conversion was rather tedious (changing things here breaks things there, changing things there breaks things somewhere else and always having to rebuild most of the code) and a bigger effort than expected originally so I hope I didn't change any semantics. Please check and let me know what you think, I'm happy to adjust the details.

There are about 60 places left where left where dart_unit_t is still in use but they are either minor or legacy code or not straightforward fixable for me.

[fuchsto]

@devreal
Currently reviewing your changes in PR #186

Need to clarify semantics for myself first, but apart from that, the PR should include documentation.
I will add documentation in branch feat-143-unitids and assign you, @fmoessbauer and @fuerlinger for review.

[fuchsto]

See my comments in PR #186:

Currently there is a conversion operator to dart_unit_t and a conversion constructor from dart_unit_t.

In effect, this allows use cases we intended to prohibit in the first place:

dash::local_unit_t  l_uid { 12 };
dash::global_unit_t g_uid { 12 };
l_uid = g_uid; // works, but shouldn't even compile

Added test suite UnitIdTest for further test of unit id semantics.

[devreal]

I added documentation and deleted mixed-type comparison and assignment operators.

[fuchsto]

As the usage of local vs. global unit ids is discussed repeatedly for several use cases, I propose the following rules:

If a context depends on a specific team, such as a class instance that is initialized with
a team reference, all unit ids in this context are relative to the team by default.

Example:

dash::Confabulation<int> cfb(1024, team);
// confabulation: \kən-ˌfa-byə-ˈlā-shən\
// noun: disturbance of memory (psych.)
auto disturbance = cfb.at_unit(dash::local_unit_t { 3 });

auto mmap = dash::MemoryMap::AtUnit(dash::global_unit_t { 3 });

For static methods and C interfaces, unit ids in parameters are global if the function does not
depend on a specific team and local otherwise.

dart_ret_t ret = dart_confabulation_at(cfb, team, dart_local_unit_t { 3 });
dart_ret_t ret = dart_memory_map_at(dart_global_unit_t { 3 });

Ceterum censeo: I still don't like the term "local" for teams.
A "local" team can span several compute nodes and it therefore sounds misleading to me.

In the DART topology module, I use relative_id and global_id.

Any objections?

@dash-project/developers let's decide this now as long as the bulk-redesign is not completed, yet.

[fmoessbauer]

I totally agree on @fuchsto's proposal. So in short this means

• Change the (public) interface of dash::GlobMem to use relative / local ids
• Rename local_unit_t to relative_unit_t (can be simply done using sed)

[devreal]

I agree that the term local_unit_t is not very intuitive. However, with relative_unit_t it's not clear either -- it's relative to what? How about team_unit_t and global_unit_t? (Renaming them in the end is straightforwarding, Eclipse ftw :)

For the lbegin|lend case: I think the reason this function actually takes a global unit ID is that the DART global pointer takes a global unit ID, thus avoiding a translation through DART. With the typed unit IDs, we could offer an overload, which does a translation for [local|relative|team]_unit_t and uses the global ID otherwise. Of course we don't want to do this for all member functions taking a unit ID but in this case it's simply more efficient.

[fuchsto]

A unit id that is relative to Team::All() is global, and the relative_unit_t for units in Team::All() is equivalent to global_unit_t, so it's semantically stable. Even if the "wrong" type is used, it would still be correct.

Using team_unit_t and global_unit_t would imply that these are different concepts, that is, it reads like a global unit id is unrelated to a team.

Also, Eclipse?! Oh boy, you are just too lazy to invest half a year in a vim configuration!

[devreal]

I am back from China and managed to implement typed unit IDs in DART during the conference breaks. This change was even more invasive since we cannot define operations on structs in C.

The DASH unit types are now derived from the DART unit types, hence we could get rid of the scope enum entirely.

Please note that there are a handfull todos for @fuchsto (see TODO[TF]) in places where I would have needed too much guess to fix the mismatch of unit IDs so I only fixed it in a way that makes the compiler happy, tests are likely to fail at this point.

I have not applied the renaming discussed earlier, yet.

[fuchsto]

@devreal Naahiiice, thank you, much appreciated!

Updated branch feat-143-unitids to development via rebase. Some unit tests fail now, presumably due to the now-enforced local/global semantics of unit ids. Will take care of that.

[fuchsto]

@devreal On second and third thoughts, I follow your suggestion to rename relative unit ID types to

dart_team_unit_t = dash::team_unit_t (instead of *local_unit_id)

You're right, dart_relative_unit_t would be less intuitive for users that are not familiar with the "historical" naming scheme.
Will run an sed on source files once integration tests pass.

[fuchsto]

Fixed in #186