- PPL-devel - BUGSENG Mailman

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: fix performance bug in compute_generator().
by Marco Poletti 16 Sep '10

16 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: d91c33b33dbc8b59332d279550366ed55ae9ae38 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d91c33b33dbc… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 21:08:27 2010 +0200 MIP_Problem: fix performance bug in compute_generator(). --- src/MIP_Problem.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index a619ce4..33ead88 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1768,7 +1768,7 @@ PPL::MIP_Problem::compute_generator() const { // Finally, build the generator. Linear_Expression expr; for (dimension_type i = external_space_dim; i-- > 0; ) - expr += num[i] * Variable(i); + add_mul_assign(expr, num[i], Variable(i)); MIP_Problem& x = const_cast<MIP_Problem&>(*this); x.last_generator = point(expr, lcm);

1 0

[GIT] ppl/ppl(sparse_matrices): ppl_c_implementation_common: fix performance bug in ppl_Linear_Expression_add_to_coefficient.
by Marco Poletti 16 Sep '10

16 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: ba9f6c92b49afbbfc37d864f59fff70df90f6536 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ba9f6c92b49a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 21:07:58 2010 +0200 ppl_c_implementation_common: fix performance bug in ppl_Linear_Expression_add_to_coefficient. --- interfaces/C/ppl_c_implementation_common.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index 3380207..b95451a 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -536,7 +536,7 @@ ppl_Linear_Expression_add_to_coefficient(ppl_Linear_Expression_t le, ppl_const_Coefficient_t n) try { Linear_Expression& lle = *to_nonconst(le); const Coefficient& nn = *to_const(n); - lle += nn * Variable(var); + add_mul_assign(lle, nn, Variable(var)); return 0; } CATCH_ALL

1 0

[GIT] ppl/ppl(master): MIP_Problem: fix performance bug in compute_generator().
by Marco Poletti 16 Sep '10

16 Sep '10

Module: ppl/ppl Branch: master Commit: d91c33b33dbc8b59332d279550366ed55ae9ae38 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d91c33b33dbc… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 21:08:27 2010 +0200 MIP_Problem: fix performance bug in compute_generator(). --- src/MIP_Problem.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index a619ce4..33ead88 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1768,7 +1768,7 @@ PPL::MIP_Problem::compute_generator() const { // Finally, build the generator. Linear_Expression expr; for (dimension_type i = external_space_dim; i-- > 0; ) - expr += num[i] * Variable(i); + add_mul_assign(expr, num[i], Variable(i)); MIP_Problem& x = const_cast<MIP_Problem&>(*this); x.last_generator = point(expr, lcm);

1 0

[GIT] ppl/ppl(master): ppl_c_implementation_common: fix performance bug in ppl_Linear_Expression_add_to_coefficient.
by Marco Poletti 16 Sep '10

16 Sep '10

Module: ppl/ppl Branch: master Commit: ba9f6c92b49afbbfc37d864f59fff70df90f6536 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ba9f6c92b49a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 21:07:58 2010 +0200 ppl_c_implementation_common: fix performance bug in ppl_Linear_Expression_add_to_coefficient. --- interfaces/C/ppl_c_implementation_common.cc | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/interfaces/C/ppl_c_implementation_common.cc b/interfaces/C/ppl_c_implementation_common.cc index 3380207..b95451a 100644 --- a/interfaces/C/ppl_c_implementation_common.cc +++ b/interfaces/C/ppl_c_implementation_common.cc @@ -536,7 +536,7 @@ ppl_Linear_Expression_add_to_coefficient(ppl_Linear_Expression_t le, ppl_const_Coefficient_t n) try { Linear_Expression& lle = *to_nonconst(le); const Coefficient& nn = *to_const(n); - lle += nn * Variable(var); + add_mul_assign(lle, nn, Variable(var)); return 0; } CATCH_ALL

1 0

[GIT] ppl/ppl(MPI): New commits
by Roberto Bagnara 16 Sep '10

16 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=410bc1bd0738… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 17:49:42 2010 +0200 Distributed_Sparse_Matrix: fix bug in exiting_index_reducer_functor, affecting performance. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=845523ef9403… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Sep 16 11:37:56 2010 +0200 Distributed_Sparse_Matrix: print the number of pivot operations in the destructor. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=389d8c2fc3b5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 21:28:11 2010 +0200 Revert "Distributed_Sparse_Matrix: use a dynamicly-allocated array instead of a vector for the reduce operation in float_entering_index." This reverts commit 4d5f95afb8b9a662e3b6f2160a15a49c971a2972. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=73999983bdc2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 19:31:58 2010 +0200 Distributed_Sparse_Matrix: optimize exact_entering_index(), exploiting the local copies of working_cost. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=4d5f95afb8b9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 19:14:28 2010 +0200 Distributed_Sparse_Matrix: use a dynamicly-allocated array instead of a vector for the reduce operation in float_entering_index. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d03f80ce8f87… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 18:32:42 2010 +0200 Distributed_Sparse_Matrix: optimize float_entering_index(), exploiting the local copies of working_cost. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=0fc1afaecf71… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 17:57:01 2010 +0200 Distributed_Sparse_Matrix: store the working_cost in worker nodes, add a set_working_cost() operation and update the nodes' working_cost in get_exiting_and_pivot(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46e1b9016642… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 17:04:49 2010 +0200 Distributed_Sparse_Matrix: optimize exact_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d264fd25c3eb… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 16:43:27 2010 +0200 Distributed_Sparse_Matrix: optimize float_entering_index() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9a06a4a19080… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 16:37:56 2010 +0200 Distributed_Sparse_Matrix: optimize compute_working_cost() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=fe9a6af26af0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 16:36:52 2010 +0200 Sparse_Row: optimize linear_combine() for the case (coeff1 == 1). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7eecade09567… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 16:36:23 2010 +0200 Sparse_Row: avoid creating stored zeroes in combine_needs_second(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=87f29dca86f2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 16:13:30 2010 +0200 Distributed_Sparse_Matrix: optimize compute_working_cost__common() for sparse working_cost rows. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=307394ac54c4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Tue Sep 14 16:03:53 2010 +0200 MIP_Problem: some little optimizations to exploit sparse workin_cost rows.

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 15 Sep '10

15 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ff67a6bed878… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 19:12:40 2010 +0200 MIP_Problem: remove useless reset() from linear_conbine(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c4547fd8dd86… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 19:12:08 2010 +0200 Sparse_Row: optimize the linear_combine() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e4cdaa38008b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 19:11:39 2010 +0200 Sparse_Row: don't create stored zeroes in combine_needs_second(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=241a4a6fcb61… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:42:33 2010 +0200 Sparse_Row: document that linear_combine() parameters must not be 0. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c8d497ffeae2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:38:44 2010 +0200 MIP_Problem: use Row::linear_combine() in linear_combine(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=9a2ab566f2c5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:38:14 2010 +0200 Sparse_Row: add a linear_combine() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e752bae13ff6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 18:37:58 2010 +0200 Dense_Row: add a linear_combine() method.

1 0

[GIT] ppl/ppl(sparse_matrices): New commits
by Roberto Bagnara 15 Sep '10

15 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=41c1b88df329… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:49:08 2010 +0200 MIP_Problem: remove some optimizations meant for dense matrices when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=eed6e5900dac… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:27:20 2010 +0200 PIP_Tree: remove useless code. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f9c4de14d8ad… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:25:23 2010 +0200 PIP_Tree: remove unnecessary temporary variables. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b423bf3864d7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:17:49 2010 +0200 Row, Matrix: avoid inclusion of unnecessary files. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ccad0ef8e489… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:17:01 2010 +0200 tests/Sparse_Matrix: run the tests only when using sparse matrices. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=46143fc9a592… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 17:10:52 2010 +0200 CO_Tree: run tests only when using sparse matrices, avoiding compiler errors. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=432dd51be380… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 16:43:54 2010 +0200 PIP_Tree: use Row and Matrix, simplifying code. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=e37b5f946405… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 16:16:32 2010 +0200 PIP_Problem: use Row and Matrix, simplifying code. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=15f178d464a4… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 16:15:55 2010 +0200 CO_Tree.defs.hh: include CO_Tree.types.hh. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=7994e8aef25d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:50:55 2010 +0200 Declare typedefs for Row and Matrix, and use them in MIP_Problem. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=abc0e90fa8ef… Merge: df7a6c989c0c19ed661e1a0af488096f98fc8d0b 10c6e068e1bffe92c73954fbc1e4943756d7fdb8 Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:39:50 2010 +0200 Merge remote branch 'origin/master' into sparse_matrices Conflicts: src/MIP_Problem.cc URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=df7a6c989c0c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:34:23 2010 +0200 tests/Sparse_Matrix/sparserow1: don't trigger assertions in Sparse_Row::lower_bound(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=129497d5d417… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 14:26:23 2010 +0200 PIP_Tree: return if there are no candidates, in find_lexico_minimum_column(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=10c6e068e1bf… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 13:44:59 2010 +0200 PIP_Problem: declare iterators used in for loops in the loop header. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4a0a65c926d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 13:44:35 2010 +0200 PIP_Tree: declare iterators used in for loops in the loop header. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3b1e87b5e0f0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 12:22:53 2010 +0200 MIP_Problem: remove non-necessary temporary variables. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cc8ee2d086c6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 12:09:48 2010 +0200 MIP_Problem: remove out-dated comment. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b3cff936b2c9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 12:05:58 2010 +0200 MIP_Problem: declare iterators used in for loops in the loop header. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1df9606a9a7c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:54:12 2010 +0200 Make PPL_DIRTY_TEMP_COEFFICIENT work outside the PPL namespace, too.

1 0

[GIT] ppl/ppl(master): New commits
by Roberto Bagnara 15 Sep '10

15 Sep '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=10c6e068e1bf… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 13:44:59 2010 +0200 PIP_Problem: declare iterators used in for loops in the loop header. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=a4a0a65c926d… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 13:44:35 2010 +0200 PIP_Tree: declare iterators used in for loops in the loop header. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=3b1e87b5e0f0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 12:22:53 2010 +0200 MIP_Problem: remove non-necessary temporary variables. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cc8ee2d086c6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 12:09:48 2010 +0200 MIP_Problem: remove out-dated comment. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=b3cff936b2c9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 12:05:58 2010 +0200 MIP_Problem: declare iterators used in for loops in the loop header. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1df9606a9a7c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:54:12 2010 +0200 Make PPL_DIRTY_TEMP_COEFFICIENT work outside the PPL namespace, too.

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: add comment.
by Marco Poletti 15 Sep '10

15 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 02cc3ed26b0cebcc016573421b0a525e76ae8d1d URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=02cc3ed26b0c… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:44:24 2010 +0200 MIP_Problem: add comment. --- src/MIP_Problem.cc | 1 + 1 files changed, 1 insertions(+), 0 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index b27e021..27c3c61 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1754,6 +1754,7 @@ PPL::MIP_Problem::erase_artificials(const dimension_type begin_artificials, { // This block is equivalent to: // working_cost[new_last_column] = working_cost.get(old_last_column); + // But it avoids storing zeroes. Coefficient_traits::const_reference old_cost = working_cost.get(old_last_column);

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: optimize further steepest_edge_exact_entering_index() for sparse working_cost rows.
by Marco Poletti 15 Sep '10

15 Sep '10

Module: ppl/ppl Branch: sparse_matrices Commit: 856f1052f1a7a81f6ca924ca6e692900552017ad URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=856f1052f1a7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Wed Sep 15 11:41:44 2010 +0200 MIP_Problem: optimize further steepest_edge_exact_entering_index() for sparse working_cost rows. --- src/MIP_Problem.cc | 54 ++++++++++++++++++++++++++++++++++----------------- 1 files changed, 36 insertions(+), 18 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 58c2112..b27e021 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1204,25 +1204,43 @@ PPL::MIP_Problem::steepest_edge_exact_entering_index() const { k = columns.rbegin(); std::vector<std::pair<dimension_type, Coefficient> >::reverse_iterator k_end = columns.rend(); + working_cost_type::const_iterator itr = working_cost.end(); for ( ; k != k_end; ++k) { - Coefficient_traits::const_reference cost_j = working_cost[k->first]; - // We cannot compute the (exact) square root of abs(\Delta x_j). - // The workaround is to compute the square of `cost[j]'. - challenger_num = cost_j * cost_j; - // Initialization during the first loop. - if (entering_index == 0) { - std::swap(current_num, challenger_num); - std::swap(current_den, k->second); - entering_index = k->first; - continue; - } - challenger_value = challenger_num * current_den; - current_value = current_num * k->second; - // Update the values, if the challenger wins. - if (challenger_value > current_value) { - std::swap(current_num, challenger_num); - std::swap(current_den, k->second); - entering_index = k->first; + itr = working_cost.lower_bound(itr, k->first); + if (itr != working_cost.end() && itr.index() == k->first) { + // We cannot compute the (exact) square root of abs(\Delta x_j). + // The workaround is to compute the square of `cost[j]'. + challenger_num = (*itr) * (*itr); + // Initialization during the first loop. + if (entering_index == 0) { + std::swap(current_num, challenger_num); + std::swap(current_den, k->second); + entering_index = k->first; + continue; + } + challenger_value = challenger_num * current_den; + current_value = current_num * k->second; + // Update the values, if the challenger wins. + if (challenger_value > current_value) { + std::swap(current_num, challenger_num); + std::swap(current_den, k->second); + entering_index = k->first; + } + } else { + PPL_ASSERT(working_cost.get(k->first) == 0); + // Initialization during the first loop. + if (entering_index == 0) { + current_num = 0; + std::swap(current_den, k->second); + entering_index = k->first; + continue; + } + // Update the values, if the challenger wins. + if (0 > sgn(current_num) * sgn(k->second)) { + current_num = 0; + std::swap(current_den, k->second); + entering_index = k->first; + } } }

1 0