April 2010 - PPL-devel - BUGSENG Mailman

Problems with test suite on alpha
by Michael Tautschnig 09 Sep '10

09 Sep '10

Hi PPL developers, I've reported problems with some test cases because of suspected gcc bugs on alpha earlier already. Now it seems that even more test cases are broken, most probably because of the very same bug (I suspect it to be http://gcc.gnu.org/bugzilla/show_bug.cgi?id=8966). My question now is: How to proceed? Shall I specifically disable the failing test cases by surrounding them with an #ifndef __alpha__ or disable the entire test suite on alpha? Thanks, Michael

2 6

[GIT] ppl/w3ppl(master): BagnaraHZ10CGTA has been published.
by Roberto Bagnara 30 Apr '10

30 Apr '10

Module: ppl/w3ppl Branch: master Commit: 82fc74d0e00c6d7815ad123c2a7fdcbb136a54de URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/w3ppl.git;a=commit;h=82fc74d0e0… Author: Roberto Bagnara <bagnara(a)cs.unipr.it> Date: Fri Apr 30 07:52:39 2010 +0200 BagnaraHZ10CGTA has been published. --- htdocs/Documentation/ppl.bib | 2 -- 1 files changed, 0 insertions(+), 2 deletions(-) diff --git a/htdocs/Documentation/ppl.bib b/htdocs/Documentation/ppl.bib index fe8ae8c..ccafdd8 100644 --- a/htdocs/Documentation/ppl.bib +++ b/htdocs/Documentation/ppl.bib @@ -913,8 +913,6 @@ Pages = "453--473", Publisher = "Elsevier", Year = 2010, - Note = "To appear in print. Available online at - \url{http://dx.doi.org/10.1016/j.comgeo.2009.09.002}", Abstract = "Deciding whether the union of two convex polyhedra is itself a convex polyhedron is a basic problem in polyhedral computations; having important applications

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row_Over_CO_Tree: fix and add assertions in lower_bound_hint_assign() methods.
by Marco Poletti 29 Apr '10

29 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: 2cf56c434df271eaa572391c61ad9e8b184a7f78 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2cf56c434df2… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Thu Apr 29 20:37:22 2010 +0200 Unlimited_Sparse_Row_Over_CO_Tree: fix and add assertions in lower_bound_hint_assign() methods. --- src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh | 16 ++++++++++++++-- 1 files changed, 14 insertions(+), 2 deletions(-) diff --git a/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh b/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh index 8d3614a..ad737d0 100644 --- a/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh +++ b/src/Unlimited_Sparse_Row_Over_CO_Tree.inlines.hh @@ -510,8 +510,14 @@ Unlimited_Sparse_Row_Over_CO_Tree tree.lower_bound(itr, i); +#ifndef NDEBUG + CO_Tree::inorder_iterator itr2(&tree); + tree.lower_bound(itr2, i); + PPL_ASSERT(itr == itr2); +#endif + if (itr->first < i) - ++itr; + itr.get_next_value(); #ifndef NDEBUG itr.get_previous_value(); @@ -535,8 +541,14 @@ Unlimited_Sparse_Row_Over_CO_Tree tree.lower_bound(itr, i); +#ifndef NDEBUG + CO_Tree::inorder_const_iterator itr2(&tree); + tree.lower_bound(itr2, i); + PPL_ASSERT(itr == itr2); +#endif + if (itr->first < i) - ++itr; + itr.get_next_value(); #ifndef NDEBUG itr.get_previous_value();

1 0

PPL in windows
by saber mirzaei 28 Apr '10

28 Apr '10

To whom it may concern. I'm a MS univeristy student and i'm going to use parma library tool for my goal which is generating and model checking and i need a polyhedra operation tool, so i choosed your tool, but i want to use is with a windows based model checking tool, as i have seen so far your tools only use with GNU/linux OSes, so how i can use PPL, is there any win based version? or i should change it as my need? thanks for your consideration in advanced. sincerely yours. Saber Mirzaei.

2 1

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: fix performance regression in steepest_edge_exact_entering_index(), introduced in commit 8194fc.
by Marco Poletti 26 Apr '10

26 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: dfeb453411a7ae94212f433d73bb16f7e20d366b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=dfeb453411a7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Apr 26 21:06:57 2010 +0200 MIP_Problem: fix performance regression in steepest_edge_exact_entering_index(), introduced in commit 8194fc. --- src/MIP_Problem.cc | 10 +- src/MIP_Problem.cc.orig | 2623 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 2628 insertions(+), 5 deletions(-) Diff: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commitdiff;h=dfeb4534…

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem: fix performance regression in steepest_edge_float_entering_index(), introduced in commit 6DA127.
by Marco Poletti 26 Apr '10

26 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: ed8ebcb3b3f7d99523f0e142ba11c5703951a8b3 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ed8ebcb3b3f7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Mon Apr 26 13:39:51 2010 +0200 MIP_Problem: fix performance regression in steepest_edge_float_entering_index(), introduced in commit 6DA127. --- src/MIP_Problem.cc | 10 +++++----- 1 files changed, 5 insertions(+), 5 deletions(-) diff --git a/src/MIP_Problem.cc b/src/MIP_Problem.cc index 984a5a2..88b7d6f 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1070,13 +1070,13 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { } } } - std::vector<std::pair<dimension_type, double> >::const_iterator - k = columns.begin(); - std::vector<std::pair<dimension_type, double> >::const_iterator - k_end = columns.end(); + std::vector<std::pair<dimension_type, double> >::const_reverse_iterator + k = columns.rbegin(); + std::vector<std::pair<dimension_type, double> >::const_reverse_iterator + k_end = columns.rend(); for ( ; k != k_end; ++k) { // challenger_dens[*k] is the square of the challenger value. - if (entering_index == 0 || k->second >= current_value_squared) { + if (entering_index == 0 || k->second > current_value_squared) { current_value_squared = k->second; entering_index = k->first; }

1 0

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

25 Apr '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=45cf54806c18… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:51:46 2010 +0200 PIP_Tree_Node: little optimization in add_constraint(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=765d2c4844b9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:48:49 2010 +0200 PIP_Tree.cc: use *_assign() and *_hint_assign() methods, in compatibility_check_find_pivot_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=f9e21435234b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:45:33 2010 +0200 PIP_Tree.cc: use *_assign() and *_hint_assign() methods, in find_lexico_minimum_column_in_set(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cc44c920ee20… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:37:01 2010 +0200 PIP_Solution_Node: use find_create_assign() and find_create_hint_assign(), in generate_cut(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cebedf4e09b0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:30:35 2010 +0200 PIP_Solution_Node: use find_create_assign() and find_create_hint_assign(), in solve(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=422ed5ad1c0a… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:23:00 2010 +0200 PIP_Solution_Node: use find_create_assign() and find_create_hint_assign(), in update_tableau(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=cd225ad34edf… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:13:27 2010 +0200 PIP_Tree_Node: use find_create_assign() and find_create_hint_assign(), in compatibility_check(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c429d07b5a03… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 22:05:01 2010 +0200 PIP_Tree: use find_create_assign() and find_create_hint_assign(), in merge_assign(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=241a9487fa09… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 21:30:01 2010 +0200 PIP_Problem: use *_assign() and *_hint_assign() methods, in solve(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=29e4e2abc202… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 21:17:07 2010 +0200 MIP_Problem: use lower_bound_hint_assign(), in OK(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=20678655731b… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 21:01:20 2010 +0200 MIP_Problem: use *_assign() and *_hint_assign() methods, in process_pending_constraints(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=703b2d1bb2fd… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 20:48:19 2010 +0200 Dense_Row: add find_create_assign() and find_create_hint_assign() methods. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8409d095a5f9… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 20:47:28 2010 +0200 Dense_Row: add default constructor for iterator and const_iterator.

1 0

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

25 Apr '10

URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=2f7598b23351… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 19:24:07 2010 +0200 CO_Tree: cache level_data arrays and share them among trees with the same height. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8194fcc2cec6… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 18:27:55 2010 +0200 MIP_Problem: reversed loop in steepest_edge_exact_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=6da127293c70… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 18:27:41 2010 +0200 MIP_Problem: reversed loop in steepest_edge_float_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=1676d8e611a7… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 18:03:14 2010 +0200 MIP_Problem: optimize steepest_edge_exact_entering_index(). URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ba8dabf354b0… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 16:50:17 2010 +0200 Unlimited_Sparse_Row_Over_CO_Tree: optimize combine() method. URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=8696af5a29af… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 16:49:34 2010 +0200 MIP_Problem: optimize steepest_edge_float_entering_index().

1 0

[GIT] ppl/ppl(sparse_matrices): Unlimited_Sparse_Row_Over_CO_Tree: optimize combine_needs_second().
by Marco Poletti 25 Apr '10

25 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: c75a75d9eb636efc7facf173d098aebb480d304b URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=c75a75d9eb63… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 12:43:06 2010 +0200 Unlimited_Sparse_Row_Over_CO_Tree: optimize combine_needs_second(). --- src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh | 121 +++++--------------- 1 files changed, 27 insertions(+), 94 deletions(-) diff --git a/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh b/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh index 22b2181..eb5b2d4 100644 --- a/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh +++ b/src/Unlimited_Sparse_Row_Over_CO_Tree.templates.hh @@ -76,74 +76,13 @@ template <typename Func1, typename Func2> void Unlimited_Sparse_Row_Over_CO_Tree ::combine_needs_second(const Unlimited_Sparse_Row_Over_CO_Tree& y, - const Func1& g, const Func2& h) { - iterator i = begin(); - iterator last_i = begin(); - const_iterator j = y.begin(); - if (!i.itr.is_at_end()) { - if (!j.itr.is_at_end()) { - if (i->first == j->first) { - g(i->second, j->second); - last_i = i; - ++i; - ++j; - } else - if (i->first < j->first) { - last_i = i; - ++i; - } else { - last_i = find_create(j->first); - h(last_i->second, j->second); - i = last_i; - ++i; - if (this == &y) - j = last_i; - ++j; - } - } else { - last_i = i; - ++i; - } - } else { - if (!j.itr.is_at_end()) { - last_i = find_create(j->first); - h(last_i->second, j->second); - i = last_i; - ++i; - if (this == &y) - j = last_i; - ++j; - } else { - PPL_ASSERT(i.itr.is_at_end()); - PPL_ASSERT(j.itr.is_at_end()); - - return; - } - } - PPL_ASSERT(!last_i.itr.is_at_end()); - while (!i.itr.is_at_end() && !j.itr.is_at_end()) - if (i->first == j->first) { - g(i->second, j->second); - last_i = i; - ++i; - ++j; - } else - if (i->first < j->first) { - last_i = i; - i = lower_bound(j->first, i); - } else { - last_i = find_create(j->first, last_i); - h(last_i->second, j->second); - i = last_i; - ++i; - if (this == &y) - j = last_i; - ++j; - } - while (!j.itr.is_at_end()) { - last_i = find_create(j->first, last_i); - h(last_i->second, j->second); - ++j; + const Func1& g, const Func2& /* h */) { + iterator i; + unordered_const_iterator j = y.unordered_begin(); + unordered_const_iterator j_end = y.unordered_end(); + for ( ; j != j_end; ++j) { + find_create_assign(j->first, i); + g(i->second, j->second); } } @@ -153,42 +92,36 @@ Unlimited_Sparse_Row_Over_CO_Tree ::combine(const Unlimited_Sparse_Row_Over_CO_Tree& y, const Func1& f, const Func2& g, const Func3& h) { iterator i = begin(); - iterator last_i = begin(); const_iterator j = y.begin(); if (!i.itr.is_at_end()) { if (!j.itr.is_at_end()) { if (i->first == j->first) { g(i->second, j->second); - last_i = i; ++i; ++j; } else if (i->first < j->first) { f(i->second); - last_i = i; ++i; } else { - last_i = find_create(j->first); - h(last_i->second, j->second); - i = last_i; - ++i; + find_create_assign(j->first, i); + h(i->second, j->second); if (this == &y) - j = last_i; + j = i; + ++i; ++j; } } else { f(i->second); - last_i = i; ++i; } } else { if (!j.itr.is_at_end()) { - last_i = find_create(j->first); - h(last_i->second, j->second); - i = last_i; - ++i; + find_create_assign(j->first, i); + h(i->second, j->second); if (this == &y) - j = last_i; + j = i; + ++i; ++j; } else { PPL_ASSERT(i.itr.is_at_end()); @@ -197,35 +130,35 @@ Unlimited_Sparse_Row_Over_CO_Tree return; } } - PPL_ASSERT(!last_i.itr.is_at_end()); while (!i.itr.is_at_end() && !j.itr.is_at_end()) if (i->first == j->first) { g(i->second, j->second); - last_i = i; ++i; ++j; } else if (i->first < j->first) { f(i->second); - last_i = i; ++i; } else { - last_i = find_create(j->first, last_i); - h(last_i->second, j->second); - i = last_i; - ++i; + --i; + find_create_hint_assign(j->first, i); + h(i->second, j->second); if (this == &y) - j = last_i; + j = i; + ++i; ++j; } while (!i.itr.is_at_end()) { f(i->second); ++i; } - while (!j.itr.is_at_end()) { - last_i = find_create(j->first, last_i); - h(last_i->second, j->second); - ++j; + if (!j.itr.is_at_end()) { + --i; + while (!j.itr.is_at_end()) { + find_create_hint_assign(j->first, i); + h(i->second, j->second); + ++j; + } } }

1 0

[GIT] ppl/ppl(sparse_matrices): MIP_Problem:: use lower_bound_hint_assign() in steepest_edge_float_entering_index().
by Marco Poletti 25 Apr '10

25 Apr '10

Module: ppl/ppl Branch: sparse_matrices Commit: ad7ead07cfb5be5f6918629ac9f53cd74e98e264 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=ad7ead07cfb5… Author: Marco Poletti <poletti.marco(a)gmail.com> Date: Sun Apr 25 12:42:40 2010 +0200 MIP_Problem:: use lower_bound_hint_assign() in steepest_edge_float_entering_index(). --- 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 e911745..c9e611d 100644 --- a/src/MIP_Problem.cc +++ b/src/MIP_Problem.cc @@ -1049,7 +1049,7 @@ PPL::MIP_Problem::steepest_edge_float_entering_index() const { break; PPL_ASSERT(j->first <= *k); if (j->first < *k) - j = tableau_i.lower_bound(*k, j); + tableau_i.lower_bound_hint_assign(*k, j); else { const Coefficient& tableau_ij = j->second; WEIGHT_BEGIN();

1 0