(j3.2006) an intrinsic for SORT()

[Bill Long]

> On Feb 6, 2018, at 8:14 AM, Clune, Thomas L. (GSFC-6101) <thomas.l.clune at nasa.gov> wrote:
> 
> My thought was that the standard would not specify the algorithm, as it is independent of the interface.    Performance is then a quality of implementation issue.   And since we?re only talking about intrinsics, we would not need to specify the behavior for ties that would otherwise give different results for different algorithms.
> 
> But providing an option to specify the algorithm would certainly be acceptable.   Of course then there needs to be another intrinsic to check on the availability of a given algorithm ?   Seems like overkill to me.   Provide an interface, require an implementation that conforms to the result must be ordered according to ?<=?  (with perhaps an option to order with ?>=?).       Users that need a faster algorithm than provided by the vendors can probably afford to spend the effort to link to the appropriate library.  Or even write it themselves - it?s not that hard to code these things.

I agree that a simple interface would be best. The algorithm can be chosen by the implementation. Indeed, it could reasonably differ based on the size of the input array.  Sort the list to small -> large values.  If you want the reversed list, it is A(N:1:-1).   As you note, if someone wants their own algorithm, it is easy enough to write it themselves.  This is a problem for which well-written user code would be performance competitive with a library routine.  So the rationale for the intrinsic is purely one of convenience. 

> 
> The next ?big? question is what about coarrays?   As with reductions, it would make a lot of sense to have the vendors enable sorting a distributed 1-d array.   The complication is then how to specify the distribution of the results.    Keeping the same distribution is friendly to the end user, but not so friendly to pivoting.    Probably could put CAF off until the next revision.
> 

Indeed, sorting distributed arrays has been commonly done ever since distributed-memory parallel systems have been available.  Certainly dating back to the T3D/T3E  days. 
Usually there are extra requirements on the output based on how the result is going to be used.  For example, if you want fast lookup, you probably want to make sure that all the values with the same K leftmost bits are on the same image. That can result in some images having more elements of the result than others.  Particularly, in the case where some values are repeated in the list, you probably want all of the equal values on the same image.  This has been a ?solved? problem for at least 20 years. And the code is not that hard to write.  It?s unclear if providing an intrinsic for this is worthwhile.  Certainly as a first pass,  we should look at only a single-image sort routine. 

Cheers,
Bill

> - Tom
> 
> 
> 
> 
> 
>> On Feb 5, 2018, at 5:47 PM, Bill Long <longb at cray.com> wrote:
>> 
>> 
>>> On Feb 5, 2018, at 3:48 PM, Steve Lionel <steve at stevelionel.com> wrote:
>>> 
>>> I could see the value in a proposal for a "quicksort" intrinsic that operated on intrinsic data types and rank-1 arrays only. 
>> 
>> Except that ?quicksort? is misnamed. OK, it?s better than Bubble sort.  But for sorting a long list of integers (representing, for example, genomic data), radix sort is often faster.  And it scales linearly both with the length of the list  and (inversely)  with the number of images.  At least in the versions I?m familiar with, the sorting part is mostly masked by the time it takes to read in the data.  You write the two operations intertwined to hide the cross-image  communication time. Or, alternatively, hide the READ time. 
>> 
>> We could easily add a crummy, non-performant quicksort and warn people it is only for convenience.  But that does not seem within our normal domain.  You can find a library routine that would do that. 
>> 
>> Cheers,
>> Bill
>> 
>> Bill Long                                                                       longb at cray.com
>> Principal Engineer, Fortran Technical Support &   voice:  651-605-9024
>> Bioinformatics Software Development                      fax:  651-605-9143
>> Cray Inc./ 2131 Lindau Lane/  Suite 1000/  Bloomington, MN  55425
>> 
>> 
>> _______________________________________________
>> J3 mailing list
>> J3 at mailman.j3-fortran.org
>> http://mailman.j3-fortran.org/mailman/listinfo/j3
> 
> _______________________________________________
> J3 mailing list
> J3 at mailman.j3-fortran.org
> http://mailman.j3-fortran.org/mailman/listinfo/j3

Bill Long                                                                       longb at cray.com
Principal Engineer, Fortran Technical Support &   voice:  651-605-9024
Bioinformatics Software Development                      fax:  651-605-9143
Cray Inc./ 2131 Lindau Lane/  Suite 1000/  Bloomington, MN  55425