[llvm-dev] code to sort otherwise-unsortable "ilist"s, e.g. symbol tables
Abe Skolnik via llvm-dev
llvm-dev at lists.llvm.org
Thu Aug 18 08:56:31 PDT 2016
On 08/18/2016 10:23 AM, Duncan P. N. Exon Smith wrote:
> IMO list sorts should be:
> - O(n lg n) complexity.
> - Stable.
> I haven't looked carefully enough at this to be sure it meets these criteria. Does it?
Stable if I did it right, but not O( n ⋅ log₂(n) ): insertion sort. For reference:
Also, I found this helpful-seeming web site while searching for the Wikipedia links:
> It's possible the current in-tree one doesn't either
Maybe. It uses a merge sort, which should be O( n ⋅ log₂(n) ), and _can_ be stable. Quoting
<https://en.wikipedia.org/wiki/Merge_sort>: "Most implementations produce a stable sort"
> if we're going to fix it let's *fix* it.
I _like_ that attitude. ;-)
> I'm also not convinced this is the right direction; using a single list makes it complicated.
No _kidding_! ;-) It took a _lot_ of work to get intra-list sorting  working,  rewritten
almost from scratch so it could quickly-enough handle a >7000-GV translation unit without
seeming like it`s stuck while sorting even with a fast CPU doing the compilation.
> My inclination is to split out lower-level merge/sort operations that avoid the calls to transferNodesToList, as I mentioned before
If you can fix the already-in-tree code so that the existing merge-sort code will work on
"iplist"s not only without crashing, but also _correctly_, then I`m all for it. I don`t care
much whether or not the code I recently emailed makes it into the tree. I wrote it for a
purpose, and that purpose now seems dead, so "that`s life" -- sometimes we write code just so
that, in the end, we can throw it away. I`ve been programming for enough years that I already
knew that before I started working on this. It was good practice and I probably learned something.
More information about the llvm-dev