Transform input to RadixSort in-place?

[kevkrist]

Hi! I'm wondering if there's a simple way to do some transformations on the input data before feeding it into RadixSort? The context is, I would like to apply a predicate to the input data before sorting without having to write the compacted data back to global memory before invoking device-side radix sort. I'm sure I could chase code to figure out how to do this, but I want to check if there is a simple answer first. Thanks!

[elstehle]

Thank you for your question, @kevkrist. This is currently not supported yet. I'm about to start working on adding support for partial sorting and top-k. This issue is the one you want to keep an eye on for tracking progress. Likely, the approach will be based on a partition-based (radix) sort. I think your request is closely related to partial sorting. I'll keep your feature request in the back of my had while designing our approach and will see if we can enable it with the new interface for partial sorting.

[elstehle]

My understanding is that @kevkrist is trying to implement something along the lines of:
Sort all items, except the ones that have a value of >5.

	0	1	2	3	4	5	6	7	8	9
items	7	2	5	9	3	10	6	1	8	4
flags	x			x		x	x		x
sorted	1	2	3	4	5

It does relate to partial sorting in the sense that during the first sorting pass you discard (i.e., don't write out) the items that are out of the range that you are interested in. In this case, the size of the range of items to "discard" corresponds to the number of x-flagged items. That's where it deviates from a normal partial sort - but since a partial sort can support not writing out such items, I was planning to accommodate such feature request.

Please correct me if your request was different, @kevkrist.

[kevkrist]

@pauleonix You lost me on your interpretation of 'compacted' -- I simply mean 'apply predicate to some values and write out only items whose corresponding values pass the predicate', which is maybe what you mean, since a 'fancy' input iterator that skipped over items whose corresponding values failed the predicate would seem to do the trick.

[kevkrist]

@elstehle Yes that is correct! Thank you and sorry if I wasn't clear.

[pauleonix]

@kevkrist Ah, ok, so fused partition and sort. I followed "do some transformations" too closely (assuming sth that can be achieved using a transform iterator). "Stream compaction" would have been a better fitting keyword than "transformations". Partitioning came to mind as well due to "apply a predicate", but I would have never interpreted it as both partitioning and then sorting. Props to @elstehle for getting it right just from that text.

I would say that it is still quite different to top-k and partial sort in that those need to work through all elements while this algorithm would rather be a masked sort (sort_if?). Doing the stream-compaction in-place with a single kernel is possible using decoupled look-back, but fusing that with sort doesn't sound like it would avoid a lot of memory traffic because the stream-compaction is parallelized according to the big initial range while the following sort naturally has less parallelism.

But maybe Dr Top-k and co hold some surprises that I'm not aware of.

[pauleonix]

I think @brycelelbach is working on a parallel filter_view which is somewhat related. I.e. with an out-of place sort as I mentioned above and that filter view as input one would get what you want (no idea if it is particularly fast though as I have no idea if/how that view solves the problem of the smaller amount of parallelism in the ouput).