parallel arrays and sorting
Herhut, Stephan A
stephan.a.herhut at intel.com
Thu Apr 11 10:08:30 PDT 2013
Rick is travelling, so let me chime in.
An alternative would be to implement sorting of primitive types only. This brings back more choice in sort algorithms but limits use. For such a design, we considered a function as optional argument to sort that, given a value from the ParallelArray to be sorted, returns a key used for comparison, which again needs to be a primitive. This would at least enable sorting of objects by a field and, at some runtime cost, sorting of general data.
The tradeoff between these two approaches, and probably other designs, is hard to judge without knowing what sort is used for. So we decided to wait for some good use cases before deciding on a specific design.
Sorry, no answers only further questions.
From: es-discuss-bounces at mozilla.org [mailto:es-discuss-bounces at mozilla.org] On Behalf Of Norm Rubin
Sent: Monday, April 08, 2013 7:46 AM
To: es-discuss at mozilla.org
Subject: parallel arrays and sorting
In comparing ParallelArrays (rivertrail) to the cuda thrust library, I noticed that Sorting using parallelArrays looks like a missing primitive operation.
Sorting is special because the good (high performance) algorithm on a gpu is radix sort, while the good (high performance) algorithm on the cpu is parallel merge sort, The other way around radix sort of cpu, or parallel merge sort of a gpu is very slow and often worse than serial implementations
Sadly it is well past a jit to take the code for one flavor of sort and transform it into the other, while it would be pretty simple for a run-time to pick a good sort, if only it knew that a sort was going on. Run times would not be required to do so here since they can always pick a slow sort.
I know this is a slippery road, since once you add another prim, adding more prims becomes ever easier but sorting seems pretty important. And array already has a sort, so adding a version that works on ParallelArrays does not seem so bad.
What do you guys think?
This email message is for the sole use of the intended recipient(s) and may contain confidential information. Any unauthorized review, use, disclosure or distribution is prohibited. If you are not the intended recipient, please contact the sender by reply email and destroy all copies of the original message.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the es-discuss