Is it possible to sort with custom type?

[mclarsen]

Say I have a type that contains two values like Vec<int,2> that represent edges. I want to sort them according to there indices so all of the same edges are next to each other after the sort. Is this possible?

[rhornung67]

I believe you can do that by providing a custom comparator. There is also a capability to sort key-value pairs based on the keys. https://raja.readthedocs.io/en/develop/sphinx/user_guide/feature/sort.html Please let us know if you need more information.

[mclarsen]

Its unclear how to provide a custom comparison operation in the examples or the documentation. If I give it a function like I would to std::sort:

  bool operator()(const Vec2Id &lhs, const Vec2Id &rhs) {
    return the comparison;
  }

I hit a static assert saying:

RAJA/policy/cuda/sort.hpp(235): error: static assertion failed with "sort<cuda_exec> is only implemented for RAJA::operators::less or RAJA::operators::greater"

If I provide a template specialization of the operators::less for my Vec2Id type then it complains about radix sort stuff:

agent/agent_radix_sort_onesweep.cuh(119): error: class "cub::Traits<Vec<int32_t, 2>>" has no member "UnsignedBits"

I am thinking that the only sort implementation is for scalar types (e.g., radix sort), but I wanted to check to see if I was missing something. Any advice would be appreciated.

[rhornung67]

Ah. I seem to recall that cub sorts, which RAJA uses internally, only support scalar built-in types. @MrBurmark is this, correct?

[MrBurmark]

General operators are supported for non-gpu backends. But the gpu backends like cuda are limited to what their library supports. For cuda only scalars are supported by the cub radix sort algorithms. You may be able to use a key-value pairs sort instead which sorts a range of keys and reorders the range of values to match. I would recommend splitting the pairs into an array of keys and an array of values but you could make strided ranges go hit the first of each pair, then the second of each pair I suppose. Or if you want to be sneaky you might be able to reinterpret the pairs as a single scalar of a larger type that is supported, reinterpret_cast<int64*>(vec<int32, 2>*).

[mclarsen]

I think i can work around it by performing some sort of hash of the values (since the values might not be able to be represented in 64 bits). Then have a check that does a deep inspection once I have grouped the values.

[rhornung67]

If you get something like that to work, we would very much appreciate you sharing it so we can add it as an example to the user guide.

[mclarsen]

Sure. I will code something up and get permission to share it.