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

[Duncan Exon Smith via llvm-dev]

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

> On Aug 17, 2016, at 14:03, Justin Bogner <mail at justinbogner.com> wrote:
> 
> +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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160818/ae81ea4a/attachment.html>