Paul Zimmermann wrote:
From: Roberto Bagnara <bagnara@cs.unipr.it> In the Parma Polyhedra Library, we found out that, for mpz_mul(), checking the source arguments against 0 gives rise to significant speedups in some algorithms.
this surprises me, since 0 has a special representation in mpz, and thus is early detected in mpz_add and mpz_mul. Please can you give an example?
Hi Paul, sorry for the delay: I was busy and I wanted to check my facts again before replying. The example is in http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/~checkout~/ppl/src/MIP_Problem.cc?... There you will find the two following fragments: // FIXME(0.10.1): the test seems to speed up the GMP computation. if (tableau_ij != 0) { scalar_value = tableau_ij * norm_factor[i]; add_mul_assign(challenger_den, scalar_value, scalar_value); } and #if 1 // CHECKME: the test seems to speed up the GMP computation. const Coefficient& y_i = y[i]; if (y_i != 0) sub_mul_assign(x_i, y_i, normalized_x_k); #else sub_mul_assign(x_i, y[i], normalized_x_k); #endif // 1 This happens in our implementation of the simplex with unbounded arithmetics. As an example, if we leave the code as it is, solving the problem boeing1.mps (http://www.cs.unipr.it/cgi-bin/cvsweb.cgi/ppl/demos/ppl_lpsol/examples/boein...) the CPU time is 7.95 seconds; if we remove the tests against zero, the CPU time increases to 11.88 seconds. Timings have been taken on a machine equipped with an Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz, running Fedora 10, gmp-4.2.2-8.fc10.x86_64, GCC 4.3.2. The code for add_mul_assign() and sub_mul_assign() is below, where GMP_Integer is an alias for mpz_class: inline void add_mul_assign(GMP_Integer& x, const GMP_Integer& y, const GMP_Integer& z) { mpz_addmul(x.get_mpz_t(), y.get_mpz_t(), z.get_mpz_t()); } inline void sub_mul_assign(GMP_Integer& x, const GMP_Integer& y, const GMP_Integer& z) { mpz_submul(x.get_mpz_t(), y.get_mpz_t(), z.get_mpz_t()); } If it can help, I am willing to perform the same test on different platforms, possibly with different versions of GMP and/or GCC. All the best, Roberto -- Prof. Roberto Bagnara Computer Science Group Department of Mathematics, University of Parma, Italy http://www.cs.unipr.it/~bagnara/ mailto:bagnara@cs.unipr.it