[llvm-dev] code to sort otherwise-unsortable "ilist"s, e.g. symbol tables

[Justin Bogner via llvm-dev]

+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 at lists.llvm.org> writes:
> 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); }
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev