[Ipopt-tickets] [Ipopt] #234: Bad idea of "std::list<TripletEntry>.sort" in "IpTripletToCSRConverter"

[Ipopt]

#234: Bad idea of "std::list<TripletEntry>.sort" in "IpTripletToCSRConverter"
-------------------------+------------------------
Reporter:  galago        |      Owner:  ipopt-team
    Type:  enhancement   |     Status:  new
Priority:  high          |  Component:  Ipopt
 Version:  3.11          |   Severity:  critical
Keywords:  CSRConverter  |
-------------------------+------------------------
 I am using IPOPT to solve a large scale NLP. When I tried to employ
 PARDISO as my linear solver, its initialization became very slow.
 By Hotspots analysis (shown in the image below), I found that
 “TripletToCSRConverter::InitializeConverter” consumes almost half of my
 optimazation time(30.86 secs of 78.24 secs).
 '''The function “std::list<TripletEntry> entry_list.sort(…)” takes 30 secs
 to finish its job when sorting an array with the length of 860,040.'''
 ----
 I thought “std::list<>.sort” can be replaced by a better implementation.
 Then I commented the original code and wrote a class called MatSorter.

 {{{
         // Create a list with all triplet entries
         //-- std::list<TripletEntry> entry_list(nonzeros);
         //-- std::list<TripletEntry>::iterator list_iterator =
 entry_list.begin();
         //-- for (Index i = 0; i < nonzeros; i++) {
         //--    list_iterator->Set(airn[i], ajcn[i], i);
         //--    list_iterator++;
         //-- }
         //-- DBG_ASSERT(list_iterator == entry_list.end());

         /** Patch #3, 2014-5-6 by Jeffrey Fung, Zhejiang University */
         class MatSorter {               // sort to standard CSC format
                 int *ia, *ja;
         public:
                 MatSorter(int *i, int *j): ia(i), ja(j) {}
                 bool operator () (int i, int j) const {
                         return ia[i] < ia[j] || (ia[i] == ia[j] && ja[i] <
 ja[j]);
                 }
         };

 }}}

 Form the data required and sort an index array “idx_sort[]” which
 functions as “PosTriplet”.

 {{{
 for (k = 0; k < nonzeros; k++) {
                 if (airn[k] > ajcn[k]) {                        // Upper
 triangular of matrix
                         ia_tri[k] = ajcn[k];
                         ja_tri[k] = airn[k];
                 }
                 else {
                         ia_tri[k] = airn[k];
                         ja_tri[k] = ajcn[k];
                 }
                 idx_sort[k] = k;
         }
         // Quick sort algorithm for large arrays
         std::sort(idx_sort, idx_sort + nonzeros, MatSorter(ia_tri,
 ja_tri));

 }}}

 After the modification I performed the same Hotspots analysis. '''Sorting
 time is reduced from 30 secs to 1.14 secs. It was almost of 27X speedup
 for the function “InitializeConverter” and “std::sort()” just consumed
 1.07 secs.'''
 Detailed time summary is shown in the images below.
 I wonder if my experience could contribute to your next build.
 The modified file “IpTripletToCSRConverter.cpp” is also attached.

--
Ticket URL: <https://projects.coin-or.org/Ipopt/ticket/234>
Ipopt <http://projects.coin-or.org/Ipopt>
Interior-point optimizer for nonlinear programs.