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 <
> 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
> >> 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:
> 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
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
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
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.