Enabling `proc sort` on distributed arrays

[jabraham17]

Currently calling sort on a distributed array will result a warning that twoArrayRadix is not supported on distributed arrays

use BlockDist, Sort;
var a = blockDist.createArray(1..100, int);
sort(a); // warning: twoArrayRadix sort no longer handles distributed arrays. Please use TwoArrayDistributedRadixSort.twoArrayDistributedRadixSort instead (but note that it is not stable)
writeln(a);

The reason sort no longer handles distributed arrays is that previously any program that has use Sort would result in use BlockDist, and the support was removed as a easy fix for that.

We should enable sort on distributed arrays without requiring all programs that use Sort to use BlockDist

[bradcray]

We should enable sort on distributed arrays without requiring all programs that use Sort to use BlockDist

Maybe more to the point, a distributed Sort would either need to be independent of distribution (such that it could be used with BlockDist, CyclicDist, BlockCyclicDist, etc.) or to be implemented by moving the implementation into the distribution itself (as part of a dsi() or doi() method, say).

[mppf]

Maybe more to the point, a distributed Sort would either need to be independent of distribution (such that it could be used with BlockDist, CyclicDist, BlockCyclicDist, etc.) or to be implemented by moving the implementation into the distribution itself (as part of a dsi() or doi() method, say).

I find this direction surprising. I'm not sure I disagree exactly; it's just that the only case of distributed sorting that seems to make sense (to me anyway) is BlockDist. With something like CyclicDist, I am having trouble seeing how it could ever be efficient, since (I would imagine) it would necessarily involve comparing / shuffling adjacent elements, which would presumably produce a ton of communication. Maybe there is some way around it to make sorting a Cyclic distributed array reasonable, but does anybody care about it?

Suppose for the sake of argument that we had pretty good distributed sorting for Block. Would it be acceptable to implement distributed sorting for Cyclic by copying everything to a Block array? If not, wouldn't we be doing a big development effort for efficiently sorting Cyclic, that nobody cares about?

[lydia-duncan]

That's an interesting point. Trying to find a way it could work, I'm picturing something like a MergeSort that does the initial comparison by locale and then takes a local buffer of the elements for each locale that should be earliest to populate the final result, comparing until each temporary structure has been emptied. Maybe it does some background task to make sure the local buffer doesn't become a performance bottleneck or something. Happy to make a visual for how that would work if my description is not painting a good enough picture.

But I think the most important thing to consider is if a sorted cyclic array would be useful. And I think it could be. You could use the cyclic-ness of the array to evenly distribute tasks where earlier elements in the array are intended to be more important to perform first.

That said, I'd probably wait until a user requested it when prioritizing features to develop.

[mppf]

Cross-posting https://github.com/chapel-lang/chapel/issues/25561#issuecomment-2291582502 here:

... [interface sortable] could also help enable distributed sorting: #25713. This would allow the distributed sort implementation to be separate from Sort, while still being callable from Sort.

[bradcray]

With something like CyclicDist, I am having trouble seeing how it could ever be efficient, since (I would imagine) it would necessarily involve comparing / shuffling adjacent elements, which would presumably produce a ton of communication. Maybe there is some way around it to make sorting a Cyclic distributed array reasonable, but does anybody care about it?

This is why I mentioned doi*. Like, should we support sort on arrays only if they implement the doiSort interface, and just complain that it's not supported if they don't. It doesn't surprise me that Sort on Cyclic may not be a good fit, but are DR and Block really the only cases that would be? What about an irregular Block (user gets to pick where the cuts between blocks occur, but otherwise it's topologically equivalent to Block) or Block-Cyclic (which could be viewed as topologically equivalent to Block across a larger number of virtual processors)?

The #25561 mention also caught my eye since 'doi' is similar to a way of opting into an optional interface (and should be replaced by interfaces once they're ready for that).

[mppf]

Like, should we support sort on arrays only if they implement the doiSort interface, and just complain that it's not supported if they don't.

That sounds good to me. (We also won't want to have a different sort implementation for each array, so need to plan to reuse sort code somehow).

A nit I am calling out just to make sure it's clear to everyone: doiSort and doiSorted are different. dsiSorted is an iterator but doiSort would be something that sorts the array in-place. (And, we only have dsiSorted now, but it's already optional since it only exists for associative, so should arguably be named doiSorted as you have brought up elsewhere. Likewise, doiSort won't make sense for associative arrays since the elements are ordered by hash in the hashtable, so reordering them in the array is a bit nonsensical).