ruby-changes:30664
From: akr <ko1@a...>
Date: Sat, 31 Aug 2013 21:17:26 +0900 (JST)
Subject: [ruby-changes:30664] akr:r42743 (trunk): * bignum.c: Use GMP to accelerate big Bignum multiplication.
akr 2013-08-31 21:17:18 +0900 (Sat, 31 Aug 2013) New Revision: 42743 http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42743 Log: * bignum.c: Use GMP to accelerate big Bignum multiplication. (bary_mul_gmp): New function. (bary_mul): Use bary_mul_gmp. (bigsq): Use different threshold with GMP. * configure.in: Detect GMP. Modified files: trunk/ChangeLog trunk/bignum.c trunk/configure.in trunk/ext/-test-/bignum/mul.c trunk/internal.h Index: configure.in =================================================================== --- configure.in (revision 42742) +++ configure.in (revision 42743) @@ -1049,6 +1049,16 @@ AC_CHECK_HEADERS( \ https://github.com/ruby/ruby/blob/trunk/configure.in#L1049 setjmpex.h ) +AC_ARG_WITH([gmp], + [AS_HELP_STRING([--without-gmp], + [disable GNU GMP to accelerate Bignum operations])], + [], + [with_gmp=yes]) +AS_IF([test "x$with_gmp" != xno], + [AC_CHECK_HEADERS(gmp.h) + AS_IF([test "x$ac_cv_header_gmp_h" != xno], + AC_CHECK_LIB([gmp], [__gmpz_init]))]) + dnl check for large file stuff mv confdefs.h confdefs1.h : > confdefs.h Index: ChangeLog =================================================================== --- ChangeLog (revision 42742) +++ ChangeLog (revision 42743) @@ -1,3 +1,14 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1 +Sat Aug 31 21:02:07 2013 Tanaka Akira <akr@f...> + + * bignum.c: Use GMP to accelerate big Bignum multiplication. + (bary_mul_gmp): New function. + (bary_mul): Use bary_mul_gmp. + (bigsq): Use different threshold with GMP. + + * configure.in: Detect GMP. + + [ruby-core:56658] [Feature #8796] + Sat Aug 31 15:03:00 2013 Charlie Somerville <charliesome@r...> * compile.c (NODE_MATCH3): pass CALL_INFO to opt_regexpmatch2 Index: ext/-test-/bignum/mul.c =================================================================== --- ext/-test-/bignum/mul.c (revision 42742) +++ ext/-test-/bignum/mul.c (revision 42743) @@ -42,6 +42,16 @@ mul_toom3(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/mul.c#L42 return rb_big_norm(rb_big_mul_toom3(big(x), big(y))); } +#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) +static VALUE +mul_gmp(VALUE x, VALUE y) +{ + return rb_big_norm(rb_big_mul_gmp(big(x), big(y))); +} +#else +#define mul_gmp rb_f_notimplement +#endif + void Init_mul(VALUE klass) { @@ -52,4 +62,5 @@ Init_mul(VALUE klass) https://github.com/ruby/ruby/blob/trunk/ext/-test-/bignum/mul.c#L62 rb_define_method(rb_cInteger, "big_mul_balance", mul_balance, 1); rb_define_method(rb_cInteger, "big_mul_karatsuba", mul_karatsuba, 1); rb_define_method(rb_cInteger, "big_mul_toom3", mul_toom3, 1); + rb_define_method(rb_cInteger, "big_mul_gmp", mul_gmp, 1); } Index: internal.h =================================================================== --- internal.h (revision 42742) +++ internal.h (revision 42743) @@ -518,6 +518,9 @@ VALUE rb_big_mul_normal(VALUE x, VALUE y https://github.com/ruby/ruby/blob/trunk/internal.h#L518 VALUE rb_big_mul_balance(VALUE x, VALUE y); VALUE rb_big_mul_karatsuba(VALUE x, VALUE y); VALUE rb_big_mul_toom3(VALUE x, VALUE y); +#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) +VALUE rb_big_mul_gmp(VALUE x, VALUE y); +#endif VALUE rb_big_sq_fast(VALUE x); /* file.c */ Index: bignum.c =================================================================== --- bignum.c (revision 42742) +++ bignum.c (revision 42743) @@ -25,6 +25,11 @@ https://github.com/ruby/ruby/blob/trunk/bignum.c#L25 #endif #include <assert.h> +#if defined(HAVE_LIBGMP) && defined(HAVE_GMP_H) +#define USE_GMP +#include <gmp.h> +#endif + VALUE rb_cBignum; const char ruby_digitmap[] = "0123456789abcdefghijklmnopqrstuvwxyz"; @@ -129,6 +134,7 @@ STATIC_ASSERT(sizeof_long_and_sizeof_bdi https://github.com/ruby/ruby/blob/trunk/bignum.c#L134 #define KARATSUBA_BALANCED(xn, yn) ((yn)/2 < (xn)) #define TOOM3_BALANCED(xn, yn) (((yn)+2)/3 * 2 < (xn)) +#define GMP_MUL_DIGITS 20 #define KARATSUBA_MUL_DIGITS 70 #define TOOM3_MUL_DIGITS 150 @@ -2409,6 +2415,42 @@ rb_big_mul_toom3(VALUE x, VALUE y) https://github.com/ruby/ruby/blob/trunk/bignum.c#L2415 return z; } +#ifdef USE_GMP +static void +bary_mul_gmp(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) +{ + const size_t nails = (sizeof(BDIGIT)-SIZEOF_BDIGITS)*CHAR_BIT; + mpz_t x, y, z; + size_t count; + + assert(xn + yn <= zn); + + mpz_inits(x, y, z, 0); + mpz_import(x, xn, -1, sizeof(BDIGIT), 0, nails, xds); + if (xds == yds && xn == yn) { + mpz_mul(z, x, x); + } + else { + mpz_import(y, yn, -1, sizeof(BDIGIT), 0, nails, yds); + mpz_mul(z, x, y); + } + mpz_export (zds, &count, -1, sizeof(BDIGIT), 0, nails, z); + BDIGITS_ZERO(zds+count, zn-count); + mpz_clears(x, y, z, 0); +} + +VALUE +rb_big_mul_gmp(VALUE x, VALUE y) +{ + size_t xn = RBIGNUM_LEN(x), yn = RBIGNUM_LEN(y), zn = xn + yn; + VALUE z = bignew(zn, RBIGNUM_SIGN(x)==RBIGNUM_SIGN(y)); + bary_mul_gmp(BDIGITS(z), zn, BDIGITS(x), xn, BDIGITS(y), yn); + RB_GC_GUARD(x); + RB_GC_GUARD(y); + return z; +} +#endif + static void bary_short_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { @@ -2601,8 +2643,13 @@ bary_mul_toom3_start(BDIGIT *zds, size_t https://github.com/ruby/ruby/blob/trunk/bignum.c#L2643 static void bary_mul(BDIGIT *zds, size_t zn, const BDIGIT *xds, size_t xn, const BDIGIT *yds, size_t yn) { +#ifdef USE_GMP + const size_t naive_threshold = GMP_MUL_DIGITS; +#else + const size_t naive_threshold = KARATSUBA_MUL_DIGITS; +#endif if (xn <= yn) { - if (xn < KARATSUBA_MUL_DIGITS) { + if (xn < naive_threshold) { if (xds == yds && xn == yn) bary_sq_fast(zds, zn, xds, xn); else @@ -2611,13 +2658,17 @@ bary_mul(BDIGIT *zds, size_t zn, const B https://github.com/ruby/ruby/blob/trunk/bignum.c#L2658 } } else { - if (yn < KARATSUBA_MUL_DIGITS) { + if (yn < naive_threshold) { bary_short_mul(zds, zn, yds, yn, xds, xn); return; } } +#ifdef USE_GMP + bary_mul_gmp(zds, zn, xds, xn, yds, yn); +#else bary_mul_toom3_start(zds, zn, xds, xn, yds, yn, NULL, 0); +#endif } struct big_div_struct { @@ -5566,10 +5617,17 @@ bigsq(VALUE x) https://github.com/ruby/ruby/blob/trunk/bignum.c#L5617 xds = BDIGITS(x); zds = BDIGITS(z); +#ifdef USE_GMP + if (xn < GMP_MUL_DIGITS) + bary_sq_fast(zds, zn, xds, xn); + else + bary_mul(zds, zn, xds, xn, xds, xn); +#else if (xn < KARATSUBA_MUL_DIGITS) bary_sq_fast(zds, zn, xds, xn); else bary_mul(zds, zn, xds, xn, xds, xn); +#endif RB_GC_GUARD(x); return z; -- ML: ruby-changes@q... Info: http://www.atdot.net/~ko1/quickml/