sorting routine for forward_list

David Kastrup
Wed Jul 3 14:46:00 GMT 2013


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

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

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.

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

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.

David Kastrup
-------------- next part --------------
A non-text attachment was scrubbed...
Type: text/x-c++src
Size: 9659 bytes
Desc: not available
URL: <>

More information about the Libstdc++ mailing list