4 ms·
I agree this is one specific use case. Decreasing the vector size does have some upside: it makes the O(lognlognn) sorting network cheaper. For M1, performanc
by janwas 4y ago
I agree this is one specific use case.
Decreasing the vector size does have some upside: it makes the O(lognlognn) sorting network cheaper.
For M1, performance is not terrible, it seems mostly limited by the NEON instruction set (expensive to do masked stores and popcnt() comparison results).
How do you mean multiple partitions in parallel? One challenge is that subarrays vary in size. It could be interesting to do multiway partition (larger base for the logn, fewer passes over memory), but that seems hard to reconcile with the vectorized in-place approach. ips4o effectively does a 64 or 256-way partition, but that's also nontrivial to vectorize.
- moonchild 4y ago> makes the O(lognlognn) sorting network cheaper Good point. > subarrays vary in size Hmm. Haven't thought about this too much yet, but it seems to me that you'd probably still even win if you had to branch once you run out the common prefix to find a new subarray. Or maybe you try to find subarrays with similar sizes and mask out the last n stores (if your subarrays are too mismatched in general, then you hit the worst-case of quicksort _anyway_, so). > ips4o effectively does a 64 or 256-way partition, but that's also nontrivial to vectorize This is interesting. 64 and 256 are annoyingly large--mainly because you have to scatter to make any sense, and scatter-store is slow by comparison where it's even supported--but just 4 seems potentially feasible.
- janwas 4y agoAgree that scatter is expensive. We did actually have hopes for 4-way partition. Even ignoring the difficulties with doing that in-place, SIMD partition still seems to require one compressstore per partition. A quick prototype turned out to be half as fast as 2-way partition, which negates the gains from doing half as many passes (this depends on the ratio of compute to bandwidth, though).