sorting routine for forward_list

[Jonathan Wakely]

On 3 July 2013 15:46, David Kastrup wrote:
>
> Hi,
>
> I've dug through some old C code of mine, rewrote it to fit to
> forward_list, documented it somewhat and test-drove it.  When compared
> to the standard stdlibc++ installation on a current Ubuntu system,

As you presumably figured out to email this list, it's called
libstdc++ not stdlibc++ :-)

> sorting a large file:
>
> dak@lola:~/src/mergesort$ wc /home/dak/Downloads/tex.web
>   24981  125152 1030597 /home/dak/Downloads/tex.web
>
> when compiled with -O was roughly 40% faster than using the stock
> sorting routine which is suitably impressive given that it only uses
> public interfaces.  Admittedly, I don't know the compiler options used
> for Ubuntu's stdlibc++ but I'd hope they'd include optimization.

All the relevant code is in templates, so isn't in libstdc++.so
anyway, the templates are instantiated in your program and so your
optimisations are what matter.

Your algorithm requires the list size, which isn't stored for a
std::forward_list.  Including the time to count the list in the
timings brings it down to 30-35% faster in some quick tests I did, but
that's still significant.


> Of course, the actual advantage may depend a lot on the actual computer
> and architecture, but the algorithm has good coherence in memory access
> patterns.

I haven't looked at the actual sort routine (sorting algorithms are
not my speciality,) but using a comparison object that counts
invocations shows the number of  comparisons is of the same order of
magnitude as the current std::forward_list::sort() implementation,
which is good (the standard says there will be approximately N log(N)
comparisons.)  Do you know its worst-case performance?

> It's "old school": there is not really much that could be done better
> given the public interfaces of forward_list.  Sort order is stable.
> Only list pointers are changed, elements are not moved or exchanged, so
> iterators remain valid.
>
> Turning it into a list-internal workhorse could give it a slight speed
> boost, and that's pretty much required when using it on stuff like the
> normal doubly-linked list since it does not make sense to maintain
> correct backward links while sorting those: backward links can much more
> efficiently be reconstituted afterwards in a single pass.

N.B. You'd need to reconstitute those links if an exception is thrown
by the comparison functor, but that shouldn't be a problem.  The
standard places no requirements on the order of the elements if an
exception is thrown.

> The question is who could be bothered with the task of processing this
> contribution in a manner that will actually lead to its inclusion in
> stdlibc++.
>
> I have signed assignment papers for various GNU software already, so
> going through with that procedure for GCC or libstdc++ would not be a
> problem, given an actual interest.

Great, because that's sometimes the hardest part :-)