sorting routine for forward_list

David Kastrup dak@gnu.org
Wed Jul 3 14:46:00 GMT 2013


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

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

-- 
David Kastrup
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stlsort.cc
Type: text/x-c++src
Size: 9659 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20130703/131c1efa/attachment.bin>


More information about the Libstdc++ mailing list