llvm dev - Aug 2016 - 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 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

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>

+llvm-dev
> On 2016-Aug-18, at 08:02, Abe Skolnik <a.skolnik at samsung.com>
wrote:
> 
>> 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:
>> Another option is to privately split out lower-level versions of some
of the functions that avoid triggering the problematic callbacks (my current
plan).

On Thu, Aug 18, 2016 at 8:23 AM, Duncan P. N. Exon Smith via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> +llvm-dev
>
> > On 2016-Aug-18, at 08:02, Abe Skolnik <a.skolnik at samsung.com>
wrote:
> >
> >> 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.

>
> 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:
>
> >> Another option is to privately split out lower-level versions of
some
> of the functions that avoid triggering the problematic callbacks (my
> current plan).
>
>
> _______________________________________________
> 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/c7dc1136/attachment.html>

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:
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.  ;-)

> 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 [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