<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div><div style="direction: inherit;">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). </div><div style="direction: inherit;"><br></div>-- dpnes</div><div><br>On Aug 17, 2016, at 14:03, Justin Bogner <<a href="mailto:mail@justinbogner.com">mail@justinbogner.com</a>> wrote:<br><br></div><blockquote type="cite"><div><span>+dexonsmith, since he completely changed the implementation of ilist to</span><br><span>a far more normal one about 15 minutes ago (in r278974)...</span><br><span></span><br><span>Abe Skolnik via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> writes:</span><br><blockquote type="cite"><span>Dear all,</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>The below has been tested quite thoroughly by now, including</span><br></blockquote><blockquote type="cite"><span>performance-testing by the way of using a modified compiler that</span><br></blockquote><blockquote type="cite"><span>triggers the below while compiling at least an old part of LLVM</span><br></blockquote><blockquote type="cite"><span>["Function.cpp"] and sorting a symbol table with >7000 global</span><br></blockquote><blockquote type="cite"><span>variables.</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>Unfortunately, the optimization I have been working on for which I</span><br></blockquote><blockquote type="cite"><span>_thought_ I needed the ability to sort a symbol table is showing poor</span><br></blockquote><blockquote type="cite"><span>performance numbers [from the compiled code, not the compiler itself],</span><br></blockquote><blockquote type="cite"><span>so I think I probably won`t submit that, at least not in its present</span><br></blockquote><blockquote type="cite"><span>form -- maybe in a much-more-limited form that doesn`t need the</span><br></blockquote><blockquote type="cite"><span>sorting. However, I thought this sorting code might be useful to</span><br></blockquote><blockquote type="cite"><span>somebody else, so here it is for feedback.</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>Maybe somebody wants to add the needed glue code so</span><br></blockquote><blockquote type="cite"><span>e.g. "my_ilist.sort()" will call the below rather than invoking the</span><br></blockquote><blockquote type="cite"><span>relevant ancestor-class "sort()" and crashing? If so, then ditto for</span><br></blockquote><blockquote type="cite"><span>e.g. "my_ilist.sort(my_comparator)", please.</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>Regards,</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>Abe</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>===== snippet from altered "llvm/include/llvm/ADT/ilist.h" =====</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span>===== context within "ilist.h": the 2nd "public:" section of</span><br></blockquote><blockquote type="cite"><span>"template<typename NodeTy, typename Traits=ilist_traits<NodeTy> ></span><br></blockquote><blockquote type="cite"><span>class iplist : public Traits" =====</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> template <class Compare></span><br></blockquote><blockquote type="cite"><span> void sort_without_temporary_list(Compare comp) {</span><br></blockquote><blockquote type="cite"><span> // The list is empty, vacuously sorted.</span><br></blockquote><blockquote type="cite"><span> if (empty())</span><br></blockquote><blockquote type="cite"><span> return;</span><br></blockquote><blockquote type="cite"><span> // The list has a single element, vacuously sorted.</span><br></blockquote><blockquote type="cite"><span> if (std::next(begin()) == end())</span><br></blockquote><blockquote type="cite"><span> return;</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> iterator last_sorted{begin()};</span><br></blockquote><blockquote type="cite"><span> iterator just_after_last_sorted{std::next(last_sorted)};</span><br></blockquote><blockquote type="cite"><span> while (end() != just_after_last_sorted) {</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> while ( (end() != just_after_last_sorted) && !</span><br></blockquote><blockquote type="cite"><span>comp(*just_after_last_sorted, *last_sorted) ) {</span><br></blockquote><blockquote type="cite"><span> // advance the frontier by one element</span><br></blockquote><blockquote type="cite"><span> ++just_after_last_sorted;</span><br></blockquote><blockquote type="cite"><span> ++ last_sorted;</span><br></blockquote><blockquote type="cite"><span> } // this loop _must_ come _before_ the code to figure out how</span><br></blockquote><blockquote type="cite"><span>many elem.s to splice and where to splice them to [place-marker: NOTE</span><br></blockquote><blockquote type="cite"><span>668]</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> if (end() != just_after_last_sorted) { // check again in case</span><br></blockquote><blockquote type="cite"><span>advancing the frontier finished the job</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> // first, find the insertion point for the first-past-the-frontier elem.</span><br></blockquote><blockquote type="cite"><span> iterator insertion_point{begin()};</span><br></blockquote><blockquote type="cite"><span> while ( ! comp(*just_after_last_sorted, *insertion_point) ) ++insertion_point;</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> // set up some needed iterators</span><br></blockquote><blockquote type="cite"><span> const iterator just_after_insertion_point{std::next(insertion_point)};</span><br></blockquote><blockquote type="cite"><span> iterator prev_elem_checked_for_order_in_sublist_to_splice{</span><br></blockquote><blockquote type="cite"><span>just_after_last_sorted};</span><br></blockquote><blockquote type="cite"><span> iterator</span><br></blockquote><blockquote type="cite"><span>just_after_last_elem_in_sublist_to_splice{std::next(just_after_last_sorted)};</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> // try to make {the sublist to be spliced} as long as it can be while still being correct</span><br></blockquote><blockquote type="cite"><span> while ( (end() != just_after_last_elem_in_sublist_to_splice) && // ...</span><br></blockquote><blockquote type="cite"><span> /*...*/ ( ! comp(*just_after_insertion_point,</span><br></blockquote><blockquote type="cite"><span>*just_after_last_elem_in_sublist_to_splice) ) &&</span><br></blockquote><blockquote type="cite"><span> /*...*/ ! comp(*just_after_last_elem_in_sublist_to_splice,</span><br></blockquote><blockquote type="cite"><span>*prev_elem_checked_for_order_in_sublist_to_splice) ) {</span><br></blockquote><blockquote type="cite"><span> // extend the to-splice sublist by one element "to the right"</span><br></blockquote><blockquote type="cite"><span> ++prev_elem_checked_for_order_in_sublist_to_splice;</span><br></blockquote><blockquote type="cite"><span> ++just_after_last_elem_in_sublist_to_splice;</span><br></blockquote><blockquote type="cite"><span> }</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> splice(insertion_point, *this, just_after_last_sorted,</span><br></blockquote><blockquote type="cite"><span>just_after_last_elem_in_sublist_to_splice);</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> just_after_last_sorted = std::next(last_sorted); // refresh</span><br></blockquote><blockquote type="cite"><span>the iterator so it points to whatever is now just past the frontier</span><br></blockquote><blockquote type="cite"><span> // We don`t need to refresh the iterator "last_sorted" b/c this is a linked list...</span><br></blockquote><blockquote type="cite"><span> // and we definitely did not insert at the frontier [see NOTE 668].</span><br></blockquote><blockquote type="cite"><span></span><br></blockquote><blockquote type="cite"><span> } // end if</span><br></blockquote><blockquote type="cite"><span> } // end while</span><br></blockquote><blockquote type="cite"><span> } // end of "sort_without_temporary_list(Compare comp)"</span><br></blockquote><blockquote type="cite"><span> void sort_without_temporary_list() { sort_without_temporary_list(op_less); }</span><br></blockquote><blockquote type="cite"><span>_______________________________________________</span><br></blockquote><blockquote type="cite"><span>LLVM Developers mailing list</span><br></blockquote><blockquote type="cite"><span><a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a></span><br></blockquote><blockquote type="cite"><span><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a></span><br></blockquote></div></blockquote></body></html>