sorting routine for forward_list
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.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 9659 bytes
Desc: not available
More information about the Libstdc++