Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19

Subject: Re: [boost] [sort] Re: [review] Formal review period for Sort library begins today, November 10, and ends Wednesday, November 19
From: Steven Ross (spreadsort_at_[hidden])
Date: 2014-11-11 22:12:20

Thank you for pointing out these interesting papers Mathias.

On Tue Nov 11 2014 at 3:31:04 PM Mathias Gaunard <
mathias.gaunard_at_[hidden]> wrote:

> On 10/11/2014 13:53, Steven Ross 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
> 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.