[PPL-devel] mpz_addmul_ui with ui = 1

[Roberto Bagnara]

Paul Zimmermann wrote:
>> From: Roberto Bagnara <bagnara at 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?rev=1.80;content-type=text%2Fplain;cvsroot=PPL

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/boeing1.mps?cvsroot=PPL)
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 at cs.unipr.it