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