Sorting issues

[aprokop]

In general, we have multiple issues/challenges associated with sort. The goal of this discussion is to gather all of them together in one place.

Interface

The current interface gets a view of values, sorts it and returns a permutation. There are several issues with this:

• There is no simple sort algorithm without computing a permutation
  In situations where we don't need permutation, we get a penalty.
• The interface is not aligned with any other standard
  The best standard to align with is probably Thrust, which provides sort, stable_sort, sort_by_key, stable_sort_by_key

General performance issues

• There is no single sort that is the fastest in all cases
  BinSort beats std::sort for larger number of values in Serial and OpenMP, but only for some problems. In others, std::sort may be 3x faster.

Issues with Kokkos::BinSort

• BinSort does not work well with duplicated entries
  It gets progressively slower with increased percentage of duplicates. In the worst case, it takes forever.
• BinSort does not work with custom types (e.g., Kokkos::Pair)
• BinSort is slower than std::sort in some situations
• BinSort is always slower than Thrust::sort_by_key
• BinSort does not provide sort_by_key
  Which is OK when we only want permutation indices, but not OK when we want other values as that requires two calls to sort.

Attempts so far

• Sort performance benchmark Add sort benchmark #278
• Attempt of the new interface Introduce sort and sortByKey #460
  Ran into the performance penalty of lacking sort_by_key in Kokkos

[aprokop]

We should try using Thrust whenever available, even for host side sorting. This should be possible, but I'm not sure if Thrust has to be configured first to allow for that.

[aprokop]

Two PRs in Kokkos improved Kokkos::BinSort for host-side: kokkos/kokkos#5890, kokkos/kokkos#5892.
Also, Kokkos has a radix sort implementation in progress: kokkos/kokkos#5507.

[aprokop]

Did a lightning talk at Kokkos User Group Meeting on 12/12/2023. Opened kokkos/kokkos#6668.