Thank you for pointing out these interesting papers Mathias. On Tue Nov 11 2014 at 3:31:04 PM Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
I have personally seen cases where sorting speed is a bottleneck.
However, there are implementations that are still quite faster than this library (I have one that is at least 3.5 faster than std::sort), and
On 10/11/2014 13:53, Steven Ross wrote: that
fares better with small sizes.
I'd appreciate if you could point me to specific implementations and/or data, so I can run a direct comparison.
The implementation I have that I mentioned is based on these papers:
http://www.dia.eui.upm.es/asignatu/pro_par/articulos/AASort.pdf http://www.cse.uconn.edu/~zshi/course/cse5302/ref/chhugani08sorting.pdf http://olab.is.s.u-tokyo.ac.jp/~kamil.rocki/xiaochen_rocki_IA3_SC13.pdf
I did not test on other random distributions than uniform.
These are interesting applications of SIMD instructions with impressive results; they might be difficult to port but they look like something that people should seriously consider integrating into std::sort on systems that support the required instructions. On 10M evenly distributed random floats spread over all 32 bits available in the data type, I see a 243% speedup for float_sort vs std::sort. For smaller data ranges the speedup is greater. Will these approaches work well on larger data types, such as 64 or 128-bit integers, doubles, and strings? It appears that they might be harder to generalize. For the algorithm that was 3.5X as fast on evenly distributed random data, what is its worst-case performance? Some of those algorithms appeared to be O(N*N) in the worst case. Does it sort in-place, or require a copy of the memory? If you have an open-source portable version of one of these approaches, and it's as fast as advertised, it might make sense to add to boost.