GMP bignum results using double cells.

GMP bignum results using double cells.

[Rob Browning]

OK.  I'd say that's a bit better -- guile-gmp-old is the smob based
implementation with the extra indirection.  guile-gmp has bignums that
store the mpz_t inside the 3 words of a double cell.

  $ ./run-benchmark guile-1.6 ./guile-1.7 ./guile-gmp-old ./guile-gmp foo.scm
  starting trials
  ("bench-random-op +" "guile-1.6" ((user . 206) (sys . 0) (gc . 91)))
  ("bench-random-op -" "guile-1.6" ((user . 186) (sys . 1) (gc . 59)))
  ("bench-random-op *" "guile-1.6" ((user . 226) (sys . 0) (gc . 101)))
  ("bench-random-op /" "guile-1.6" ((user . 267) (sys . 0) (gc . 116)))
  ("bench-random-op gcd" "guile-1.6" ((user . 126) (sys . 0) (gc . 46)))
  ("bench-random-op lcm" "guile-1.6" ((user . 288) (sys . 0) (gc . 121)))
  starting trials
  ("bench-random-op +" "./guile-1.7" ((user . 353) (sys . 1) (gc . 62)))
  ("bench-random-op -" "./guile-1.7" ((user . 327) (sys . 0) (gc . 62)))
  ("bench-random-op *" "./guile-1.7" ((user . 364) (sys . 0) (gc . 56)))
  ("bench-random-op /" "./guile-1.7" ((user . 392) (sys . 0) (gc . 56)))
  ("bench-random-op gcd" "./guile-1.7" ((user . 276) (sys . 0) (gc . 59)))
  ("bench-random-op lcm" "./guile-1.7" ((user . 392) (sys . 0) (gc . 57)))
  starting trials
  ("bench-random-op +" "./guile-gmp-old" ((user . 414) (sys . 0) (gc . 66)))
  ("bench-random-op -" "./guile-gmp-old" ((user . 399) (sys . 0) (gc . 65)))
  ("bench-random-op *" "./guile-gmp-old" ((user . 438) (sys . 0) (gc . 68)))
  ("bench-random-op /" "./guile-gmp-old" ((user . 434) (sys . 0) (gc . 65)))
  ("bench-random-op gcd" "./guile-gmp-old" ((user . 407) (sys . 0) (gc . 66)))
  ("bench-random-op lcm" "./guile-gmp-old" ((user . 466) (sys . 0) (gc . 67)))
  starting trials
  ("bench-random-op +" "./guile-gmp" ((user . 349) (sys . 1) (gc . 67)))
  ("bench-random-op -" "./guile-gmp" ((user . 302) (sys . 0) (gc . 32)))
  ("bench-random-op *" "./guile-gmp" ((user . 321) (sys . 0) (gc . 33)))
  ("bench-random-op /" "./guile-gmp" ((user . 334) (sys . 0) (gc . 32)))
  ("bench-random-op gcd" "./guile-gmp" ((user . 312) (sys . 0) (gc . 33)))
  ("bench-random-op lcm" "./guile-gmp" ((user . 366) (sys . 0) (gc . 32)))

It looks like the new code is substantially better than 1.7, though if
I understand correctly, and gc time is included in user time, then it
appears the improvement was on the gc side, not the computation side.

Marius, for now, rather than use SCM_CELL_ADDR_1, I mirrored the
handling of real values like this:

  #define SCM_I_BIG_MPZ(x) (((scm_t_big_mpz *) SCM2PTR (x))->mpz)
  #define SCM_BIGP(x) (!SCM_IMP (x) && SCM_TYP16 (x) == scm_tc16_big)

  typedef struct scm_t_big_mpz
  {
    SCM type;
    mpz_t mpz;
  } scm_t_big_mpz;

However, this means that numbers.h now has to include gmp.h, and with
the SCM_CELL_ADDR_1 approach, it wouldn't.  I'd be happy to arrange
things whichever way you prefer.

Also, I was trying to figure out how to add the test for 

  sizeof (mpz_t) <= 3 * (sizeof (scm_t_bits))

In order to put it in configure.in, we have to have access to the
definition of scm_t_bits (or at least SIZEOF_SCM_T_BITS) at configure
time.  Any thoughts?

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
>   ("bench-random-op gcd" "./guile-1.7" ((user . 276) (sys . 0) (gc . 59)))
>   ("bench-random-op gcd" "./guile-gmp" ((user . 312) (sys . 0) (gc . 33)))

Is that with mpz_gcd?  From nosing around the existing scm_gcd I might
have thought mpz_gcd would be faster.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Rob Browning]

Kevin Ryde <user42@zip.com.au> writes:

> Rob Browning <rlb@defaultvalue.org> writes:
>>
>>   ("bench-random-op gcd" "./guile-1.7" ((user . 276) (sys . 0) (gc . 59)))
>>   ("bench-random-op gcd" "./guile-gmp" ((user . 312) (sys . 0) (gc . 33)))
>
> Is that with mpz_gcd?  From nosing around the existing scm_gcd I might
> have thought mpz_gcd would be faster.

Here's what I get currently:

  starting trials
  ("bench-random-op +" "./guile-gmp" ((user . 294) (sys . 0) (gc . 30)))
  ("bench-random-op -" "./guile-gmp" ((user . 289) (sys . 0) (gc . 31)))
  ("bench-random-op *" "./guile-gmp" ((user . 307) (sys . 1) (gc . 29)))
  ("bench-random-op /" "./guile-gmp" ((user . 316) (sys . 0) (gc . 30)))
  ("bench-random-op gcd" "./guile-gmp" ((user . 302) (sys . 0) (gc . 31)))
  ("bench-random-op lcm" "./guile-gmp" ((user . 345) (sys . 0) (gc . 31)))

To compare gcd in current 1.7 still looks like this:

  ("bench-random-op gcd" "./guile-1.7" ((user . 253) (sys . 0) (gc . 55)))

The fact that all the values are so close makes me wonder if much of
the cost is just interpreter related.

FWIW below is the current gcd_implementation -- I believe the only
clause being executed in the test above is the 2 bigs clause that I
just marked with /* big big clause */ below -- feel free to critique.
Note that I left the same algorithm as before for the inum case.

SCM_GPROC1 (s_gcd, "gcd", scm_tc7_asubr, scm_gcd, g_gcd);
/* "Return the greatest common divisor of all arguments.\n"
 * "If called without arguments, 0 is returned."
 */
SCM
scm_gcd (SCM x, SCM y)
{
  if (SCM_UNBNDP (y)) {
    if (SCM_UNBNDP (x)) {
      return SCM_INUM0;
    } else {
      return x;
    }
  }
  if (SCM_INUMP (x)) {
    if (SCM_INUMP (y)) {
      long xx = SCM_INUM (x);
      long yy = SCM_INUM (y);
      long u = xx < 0 ? -xx : xx;
      long v = yy < 0 ? -yy : yy;
      long result;
      if (xx == 0) {
	result = v;
      } else if (yy == 0) {
	result = u;
      } else {
	long k = 1;
	long t;
	/* Determine a common factor 2^k */
	while (!(1 & (u | v))) {
	  k <<= 1;
	  u >>= 1;
	  v >>= 1;
        }
        /* Now, any factor 2^n can be eliminated */
	if (u & 1) {
	  t = -v;
	} else {
	  t = u;
	b3:
	  t = SCM_SRS (t, 1);
        }
        if (!(1 & t))
	  goto b3;
	if (t > 0)
	  u = t;
	else
	  v = -t;
	t = u - v;
	if (t != 0)
	  goto b3;
	result = u * k;
      }
      if (SCM_POSFIXABLE (result)) {
	return SCM_MAKINUM (result);
      } else {
	return scm_i_long2big (result);
      }
    } else if (SCM_BIGP (y)) {
      SCM result = scm_i_mkbig ();
      SCM mx = scm_i_mkbig ();
      mpz_set_si(SCM_I_BIG_MPZ (mx), SCM_INUM (x));
      scm_remember_upto_here_1 (x);
      mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (mx), SCM_I_BIG_MPZ (y));
      scm_remember_upto_here_2(mx, y);
      return scm_i_normbig (result);
    } else {
      SCM_WTA_DISPATCH_2 (g_gcd, x, y, SCM_ARG2, s_gcd);
    }
  } else if (SCM_BIGP (x)) {
    SCM result = scm_i_mkbig ();
    if (SCM_INUMP (y)) {
      SCM my = scm_i_mkbig ();
      mpz_set_si (SCM_I_BIG_MPZ (my), SCM_INUM (y));
      mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (x), SCM_I_BIG_MPZ (my));
      scm_remember_upto_here_1 (my);
    } else if (SCM_BIGP (y)) {
      /* big big clause */
      mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (x), SCM_I_BIG_MPZ (y));
    } else {
      SCM_WTA_DISPATCH_2 (g_gcd, x, y, SCM_ARG2, s_gcd);
    }
    scm_remember_upto_here_2(x, y);
    return scm_i_normbig (result);
  } else {
    SCM_WTA_DISPATCH_2 (g_gcd, x, y, SCM_ARG1, s_gcd);
  }
}

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Kevin Ryde]

Rob Browning <rlb@defaultvalue.org> writes:
>
> The fact that all the values are so close makes me wonder if much of
> the cost is just interpreter related.

Perhaps bigger numbers would show up better.  The advantages of gmp
normally increase with increasing size.

> Note that I left the same algorithm as before for the inum case.

mpn_gcd_1 would be a possibility for that, to save some code.
Probably no great difference in speed normally, though gmp does have
some nice assembler versions for K6 and Athlon.

>     } else if (SCM_BIGP (y)) {
>       SCM result = scm_i_mkbig ();
>       SCM mx = scm_i_mkbig ();
>       mpz_set_si(SCM_I_BIG_MPZ (mx), SCM_INUM (x));
>       scm_remember_upto_here_1 (x);
>       mpz_gcd(SCM_I_BIG_MPZ (result), SCM_I_BIG_MPZ (mx), SCM_I_BIG_MPZ (y));

Could probably use mpz_gcd_ui instead of converting x to an mpz.

Unless I've missed something basic and a conversion should be done.
In which case maybe the result variable could be pressed into service,
convert into that and call mpz_gcd(result,result,y).


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> It looks like the new code is substantially better than 1.7, though if
> I understand correctly, and gc time is included in user time, then it
> appears the improvement was on the gc side, not the computation side.

That looks very good to me.  Certainly good enough to integrate it
into the 1.7 branch.

> Marius, for now, rather than use SCM_CELL_ADDR_1, I mirrored the
> handling of real values like this:
> 
>   #define SCM_I_BIG_MPZ(x) (((scm_t_big_mpz *) SCM2PTR (x))->mpz)
>   #define SCM_BIGP(x) (!SCM_IMP (x) && SCM_TYP16 (x) == scm_tc16_big)
> 
>   typedef struct scm_t_big_mpz
>   {
>     SCM type;
>     mpz_t mpz;
>   } scm_t_big_mpz;
> 
> However, this means that numbers.h now has to include gmp.h, and with
> the SCM_CELL_ADDR_1 approach, it wouldn't.  I'd be happy to arrange
> things whichever way you prefer.

Do we need to define scm_t_big_mpz in numbers.h?  Couldn't it just be
an declared-but-undefined struct there?  Like

  #define SCM_I_BIG_MPZ(x) (((scm_t_big_mpz *) SCM2PTR (x))->mpz)
  #define SCM_BIGP(x) (!SCM_IMP (x) && SCM_TYP16 (x) == scm_tc16_big)

  typedef struct scm_t_big_mpz scm_t_big_mpz;

and later in numbers.c

  struct scm_t_big_mpz
  {
    SCM type;
    mpz_t mpz;
  };

> Also, I was trying to figure out how to add the test for 
> 
>   sizeof (mpz_t) <= 3 * (sizeof (scm_t_bits))
> 
> In order to put it in configure.in, we have to have access to the
> definition of scm_t_bits (or at least SIZEOF_SCM_T_BITS) at configure
> time.  Any thoughts?

We can also put the test somewhere in init.c and have Guile abort
noisily when it fails.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Rob Browning]

Marius Vollmer <mvo@zagadka.de> writes:

>> However, this means that numbers.h now has to include gmp.h, and with
>> the SCM_CELL_ADDR_1 approach, it wouldn't.  I'd be happy to arrange
>> things whichever way you prefer.
>
> Do we need to define scm_t_big_mpz in numbers.h?  Couldn't it just be
> an declared-but-undefined struct there?  Like

Possibly.  In the first pass, I was just matching what the other types
did, but this will probably work.  I'll try it.

>> In order to put it in configure.in, we have to have access to the
>> definition of scm_t_bits (or at least SIZEOF_SCM_T_BITS) at configure
>> time.  Any thoughts?
>
> We can also put the test somewhere in init.c and have Guile abort
> noisily when it fails.

True.  It'd be nice to have the test at configure, time, but perhaps
that can wait for later, if ever...

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Rob Browning]

Rob Browning <rlb@defaultvalue.org> writes:

>> Do we need to define scm_t_big_mpz in numbers.h?  Couldn't it just be
>> an declared-but-undefined struct there?  Like
>
> Possibly.  In the first pass, I was just matching what the other types
> did, but this will probably work.  I'll try it.

Ahh, that's why -- in gc-card.c, we have to call mpz_clear
(SCM_I_BIG_MPZ (x)).  I'd put the direct call in there just for
efficiency, and I also used direct manipulations in a few other places
(dealing with the ipv6 addresses and random number generation I
think).

So would you prefer: SCM_CELL_ADDR_1, putting the scm_t_big_mpz in
numbers.h, or just adding functions to the scm_i_big interface for any
non-numbers.c usages of bignums, even libguile internal ones.  The
latter would of course have more overhead, but it might not be
enough to be significant.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> So would you prefer: SCM_CELL_ADDR_1, putting the scm_t_big_mpz in
> numbers.h, or just adding functions to the scm_i_big interface for any
> non-numbers.c usages of bignums, even libguile internal ones.

Could we put it into an 'internal' header file that is not being
installed?

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Rob Browning]

Marius Vollmer <mvo@zagadka.de> writes:

> Could we put it into an 'internal' header file that is not being
> installed?

Sure.  I'm favorably disposed toward 'private' C headers.  I'd just
thought that the general consensus was against them.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> Marius Vollmer <mvo@zagadka.de> writes:
> 
> > Could we put it into an 'internal' header file that is not being
> > installed?
> 
> Sure.  I'm favorably disposed toward 'private' C headers.  I'd just
> thought that the general consensus was against them.

Yep, you are right, I think.  Is it a big problem to include gmp.h in
numbers.h, anyway?  I'd say we can just do it.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Rob Browning]

Marius Vollmer <mvo@zagadka.de> writes:

> Yep, you are right, I think.  Is it a big problem to include gmp.h in
> numbers.h, anyway?  I'd say we can just do it.

Sure.  That'll work.  Though we could also use the SCM_CELL_ADDR_1
approach if you'd rather.  I don't feel strongly about it either way.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG starting 2002-11-03 = 14DD 432F AE39 534D B592  F9A0 25C8 D377 8C7E 73A4


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: GMP bignum results using double cells.

[Marius Vollmer]

Rob Browning <rlb@defaultvalue.org> writes:

> Sure.  That'll work.  Though we could also use the SCM_CELL_ADDR_1
> approach if you'd rather.  I don't feel strongly about it either way.

I don't, either.  Please do what you think is best.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel