code to sort otherwise-unsortable "ilist"s, e.g. symbol tables

Dear all,

The below has been tested quite thoroughly by now, including performance-testing by the way of using a modified compiler that triggers the below while compiling at least an old part of LLVM ["Function.cpp"] and sorting a symbol table with >7000 global variables.

Unfortunately, the optimization I have been working on for which I _thought_ I needed the ability to sort a symbol table is showing poor performance numbers [from the compiled code, not the compiler itself], so I think I probably won`t submit that, at least not in its present form -- maybe in a much-more-limited form that doesn`t need the sorting. However, I thought this sorting code might be useful to somebody else, so here it is for feedback.

Maybe somebody wants to add the needed glue code so e.g. "my_ilist.sort()" will call the below rather than invoking the relevant ancestor-class "sort()" and crashing? If so, then ditto for e.g. "my_ilist.sort(my_comparator)", please.

Regards,

Abe

===== snippet from altered "llvm/include/llvm/ADT/ilist.h" =====

===== context within "ilist.h": the 2nd "public:" section of "template<typename NodeTy, typename Traits=ilist_traits<NodeTy> > class iplist : public Traits" =====

   template <class Compare>
   void sort_without_temporary_list(Compare comp) {
     // The list is empty, vacuously sorted.
     if (empty())
       return;
     // The list has a single element, vacuously sorted.
     if (std::next(begin()) == end())
       return;

     iterator last_sorted{begin()};
     iterator just_after_last_sorted{std::next(last_sorted)};
     while (end() != just_after_last_sorted) {

       while ( (end() != just_after_last_sorted) && ! comp(*just_after_last_sorted, *last_sorted) ) {
         // advance the frontier by one element
         ++just_after_last_sorted;
         ++ last_sorted;
       } // this loop _must_ come _before_ the code to figure out how many elem.s to splice and where to splice them to [place-marker: NOTE 668]

       if (end() != just_after_last_sorted) { // check again in case advancing the frontier finished the job

         // first, find the insertion point for the first-past-the-frontier elem.
         iterator insertion_point{begin()};
         while ( ! comp(*just_after_last_sorted, *insertion_point) ) ++insertion_point;

         // set up some needed iterators
         const iterator just_after_insertion_point{std::next(insertion_point)};
         iterator prev_elem_checked_for_order_in_sublist_to_splice{ just_after_last_sorted};
         iterator just_after_last_elem_in_sublist_to_splice{std::next(just_after_last_sorted)};

         // try to make {the sublist to be spliced} as long as it can be while still being correct
         while ( (end() != just_after_last_elem_in_sublist_to_splice) && // ...
         /*...*/ ( ! comp(*just_after_insertion_point, *just_after_last_elem_in_sublist_to_splice) ) &&
         /*...*/ ! comp(*just_after_last_elem_in_sublist_to_splice, *prev_elem_checked_for_order_in_sublist_to_splice) ) {
           // extend the to-splice sublist by one element "to the right"
           ++prev_elem_checked_for_order_in_sublist_to_splice;
           ++just_after_last_elem_in_sublist_to_splice;
         }

         splice(insertion_point, *this, just_after_last_sorted, just_after_last_elem_in_sublist_to_splice);

         just_after_last_sorted = std::next(last_sorted); // refresh the iterator so it points to whatever is now just past the frontier
         // We don`t need to refresh the iterator "last_sorted" b/c this is a linked list...
         // and we definitely did not insert at the frontier [see NOTE 668].

       } // end if
     } // end while
   } // end of "sort_without_temporary_list(Compare comp)"
   void sort_without_temporary_list() { sort_without_temporary_list(op_less); }

+dexonsmith, since he completely changed the implementation of ilist to
a far more normal one about 15 minutes ago (in r278974)...

Abe Skolnik via llvm-dev <llvm-dev@lists.llvm.org> writes:

Thanks for submitting! I’ll likely fix the sort code eventually, so I may use this as a reference. Another option is to privately split out lower-level versions of some of the functions that avoid triggering the problematic callbacks (my current plan).

– dpnes

+llvm-dev

Thanks for submitting! I'll likely fix the sort code eventually, so I may use this as a reference.

You are welcome.

Should I clean it up to comply with style guidelines, forward-port to the latest trunk, and create a proper patch for official submission?

Regards,

Abe

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? (It's possible the current in-tree one doesn't either (I haven't bothered to understand it), but if we're going to fix it let's *fix* it.)

I'm also not convinced this is the right direction; using a single list makes it complicated. My inclination is to split out lower-level merge/sort operations that avoid the calls to transferNodesToList, as I mentioned before:

+llvm-dev

>
>> Thanks for submitting! I'll likely fix the sort code eventually, so I
may use this as a reference.
>
> You are welcome.
>
> Should I clean it up to comply with style guidelines, forward-port to
the latest trunk, and create a proper patch for official submission?
>
> Regards,
>
> Abe

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? (It's possible the current in-tree one doesn't either
(I haven't bothered to understand it), but if we're going to fix it let's
*fix* it.)

The one in-tree is a merge sort implementation, it should meet both
criteria.

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: https://en.wikipedia.org/wiki/Insertion_sort

Also, I found this helpful-seeming web site while searching for the Wikipedia links:

   http://bigocheatsheet.com/

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

I'm also not convinced this is the right direction; using a single list makes it complicated.

No _kidding_! :wink: It took a _lot_ of work to get intra-list sorting [1] working, [2] 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.

Regards,

Abe