[Gmp-commit] /var/hg/gmp: Break out and optimise powtab computation from mpn/...
mercurial at gmplib.org
mercurial at gmplib.org
Tue Jan 24 21:41:40 UTC 2017
details: /var/hg/gmp/rev/3424fde4ebc2
changeset: 17214:3424fde4ebc2
user: Torbjorn Granlund <tg at gmplib.org>
date: Tue Jan 24 22:41:36 2017 +0100
description:
Break out and optimise powtab computation from mpn/generic/get_str.c and mpn/generic/set_str.c.
diffstat:
ChangeLog | 20 ++
configure.ac | 2 +-
gmp-impl.h | 9 +-
mpn/generic/compute_powtab.c | 360 +++++++++++++++++++++++++++++++++++++++++++
mpn/generic/get_str.c | 139 ++--------------
mpn/generic/set_str.c | 109 +-----------
tune/set_strb.c | 1 -
tune/set_strs.c | 1 -
tune/tuneup.c | 5 +-
9 files changed, 420 insertions(+), 226 deletions(-)
diffs (truncated from 865 to 300 lines):
diff -r 3d8eeb21ac74 -r 3424fde4ebc2 ChangeLog
--- a/ChangeLog Tue Jan 24 21:08:36 2017 +0100
+++ b/ChangeLog Tue Jan 24 22:41:36 2017 +0100
@@ -1,5 +1,25 @@
2017-01-24 Torbjörn Granlund <tg at gmplib.org>
+ * mpn/generic/compute_powtab.c: New file, providing mpn_compute_powtab
+ for both get_str and set_str.
+
+ * gmp-impl.h (mpn_str_powtab_alloc): New macro.
+ (mpn_dc_set_str_powtab_alloc, mpn_dc_get_str_powtab_alloc): Remove.
+ (mpn_compute_powtab): Declare.
+
+ * mpn/generic/set_str.c: Use mpn_compute_powtab.
+ (mpn_set_str_compute_powtab): Remove.
+
+ * mpn/generic/get_str.c: Use mpn_compute_powtab.
+ (mpn_get_str_compute_powtab): Remove.
+ (mpn_bc_get_str): New name for mpn_sb_get_str.
+
+ * configure.ac (gmp_mpn_functions): Add compute_powtab.
+
+ * tune/tuneup.c (speed_mpn_pre_set_str): Call mpn_compute_powtab.
+ * tune/set_strb.c: Remove mpn_set_str_compute_powtab name mangling.
+ * tune/set_strs.c: Likewise.
+
* configure.ac: Invoke AC_PROG_CC_C99 instead of AC_PROG_CC_STDC.
2017-01-03 Torbjörn Granlund <tg at gmplib.org>
diff -r 3d8eeb21ac74 -r 3424fde4ebc2 configure.ac
--- a/configure.ac Tue Jan 24 21:08:36 2017 +0100
+++ b/configure.ac Tue Jan 24 22:41:36 2017 +0100
@@ -2927,7 +2927,7 @@
mul mul_fft mul_n sqr mul_basecase sqr_basecase nussbaumer_mul \
mulmid_basecase toom42_mulmid mulmid_n mulmid \
random random2 pow_1 \
- rootrem sqrtrem sizeinbase get_str set_str \
+ rootrem sqrtrem sizeinbase get_str set_str compute_powtab \
scan0 scan1 popcount hamdist cmp zero_p \
perfsqr perfpow \
gcd_1 gcd gcdext_1 gcdext gcd_subdiv_step \
diff -r 3d8eeb21ac74 -r 3424fde4ebc2 gmp-impl.h
--- a/gmp-impl.h Tue Jan 24 21:08:36 2017 +0100
+++ b/gmp-impl.h Tue Jan 24 22:41:36 2017 +0100
@@ -3,7 +3,7 @@
THE CONTENTS OF THIS FILE ARE FOR INTERNAL USE AND ARE ALMOST CERTAIN TO
BE SUBJECT TO INCOMPATIBLE CHANGES IN FUTURE GNU MP RELEASES.
-Copyright 1991, 1993-1997, 1999-2015 Free Software Foundation, Inc.
+Copyright 1991-2017 Free Software Foundation, Inc.
This file is part of the GNU MP Library.
@@ -4298,17 +4298,16 @@
int base;
};
typedef struct powers powers_t;
-#define mpn_dc_set_str_powtab_alloc(n) ((n) + GMP_LIMB_BITS)
+#define mpn_str_powtab_alloc(n) ((n) + 2 * GMP_LIMB_BITS) /* FIXME: This can perhaps be trimmed */
#define mpn_dc_set_str_itch(n) ((n) + GMP_LIMB_BITS)
-#define mpn_dc_get_str_powtab_alloc(n) ((n) + 2 * GMP_LIMB_BITS)
#define mpn_dc_get_str_itch(n) ((n) + GMP_LIMB_BITS)
+#define mpn_compute_powtab __MPN(compute_powtab)
+__GMP_DECLSPEC size_t mpn_compute_powtab (powers_t *, mp_ptr, mp_size_t, int);
#define mpn_dc_set_str __MPN(dc_set_str)
__GMP_DECLSPEC mp_size_t mpn_dc_set_str (mp_ptr, const unsigned char *, size_t, const powers_t *, mp_ptr);
#define mpn_bc_set_str __MPN(bc_set_str)
__GMP_DECLSPEC mp_size_t mpn_bc_set_str (mp_ptr, const unsigned char *, size_t, int);
-#define mpn_set_str_compute_powtab __MPN(set_str_compute_powtab)
-__GMP_DECLSPEC void mpn_set_str_compute_powtab (powers_t *, mp_ptr, mp_size_t, int);
/* __GMPF_BITS_TO_PREC applies a minimum 53 bits, rounds upwards to a whole
diff -r 3d8eeb21ac74 -r 3424fde4ebc2 mpn/generic/compute_powtab.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/mpn/generic/compute_powtab.c Tue Jan 24 22:41:36 2017 +0100
@@ -0,0 +1,360 @@
+/* mpn_compute_powtab.
+
+ Contributed to the GNU project by Torbjorn Granlund.
+
+ THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES. IT IS ONLY
+ SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES. IN FACT, IT IS ALMOST
+ GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
+
+Copyright 1991-2017 Free Software Foundation, Inc.
+
+This file is part of the GNU MP Library.
+
+The GNU MP Library is free software; you can redistribute it and/or modify
+it under the terms of either:
+
+ * the GNU Lesser General Public License as published by the Free
+ Software Foundation; either version 3 of the License, or (at your
+ option) any later version.
+
+or
+
+ * the GNU General Public License as published by the Free Software
+ Foundation; either version 2 of the License, or (at your option) any
+ later version.
+
+or both in parallel, as here.
+
+The GNU MP Library is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+for more details.
+
+You should have received copies of the GNU General Public License and the
+GNU Lesser General Public License along with the GNU MP Library. If not,
+see https://www.gnu.org/licenses/. */
+
+/*
+ CAVEATS:
+ * The exptab and powtab vectors are in opposite orders. Probably OK.
+ * Consider getting rid of exptab, doing bit ops on the un argument instead.
+ * Consider rounding greatest power slightly upwards to save adjustments.
+ * In powtab_decide, consider computing cost from just the 2-3 largest
+ operands, since smaller operand contribute little. This makes most sense
+ if exptab is suppressed.
+*/
+
+#include "gmp-impl.h"
+
+#ifndef DIV_1_VS_MUL_1_PERCENT
+#define DIV_1_VS_MUL_1_PERCENT 150
+#endif
+
+#define SET_powers_t(dest, ptr, size, dib, b, sh) \
+ do { \
+ dest.p = ptr; \
+ dest.n = size; \
+ dest.digits_in_base = dib; \
+ dest.base = b; \
+ dest.shift = sh; \
+ } while (0)
+
+#if DIV_1_VS_MUL_1_PERCENT > 120
+#define HAVE_mpn_compute_powtab_mul 1
+static void
+mpn_compute_powtab_mul (powers_t *powtab, mp_ptr powtab_mem, mp_size_t un,
+ int base, const size_t *exptab, size_t n_pows)
+{
+ mp_size_t n;
+ mp_ptr p, t;
+ mp_limb_t cy;
+ long start_idx;
+ int c;
+
+ mp_limb_t big_base = mp_bases[base].big_base;
+ int chars_per_limb = mp_bases[base].chars_per_limb;
+
+ mp_ptr powtab_mem_ptr = powtab_mem;
+
+ size_t digits_in_base = chars_per_limb;
+
+ powers_t *pt = powtab;
+
+ p = powtab_mem_ptr;
+ powtab_mem_ptr += 1;
+ p[0] = big_base;
+
+ SET_powers_t (pt[0], p, 1, digits_in_base, base, 0);
+ pt++;
+
+ t = powtab_mem_ptr;
+ powtab_mem_ptr += 2;
+ t[1] = mpn_mul_1 (t, p, 1, big_base);
+ n = 2;
+
+ digits_in_base *= 2;
+
+ c = t[0] == 0;
+ t += c;
+ n -= c;
+ mp_size_t shift = c;
+
+ SET_powers_t (pt[0], t, n, digits_in_base, base, shift);
+ p = t;
+ pt++;
+
+ if (exptab[0] == ((size_t) chars_per_limb << n_pows))
+ {
+ start_idx = n_pows - 2;
+ }
+ else
+ {
+ if (((digits_in_base + chars_per_limb) << (n_pows-2)) <= exptab[0])
+ {
+ /* 3, sometimes adjusted to 4. */
+ t = powtab_mem_ptr;
+ powtab_mem_ptr += 4;
+ t[n] = cy = mpn_mul_1 (t, p, n, big_base);
+ n += cy != 0;;
+
+ digits_in_base += chars_per_limb;
+
+ c = t[0] == 0;
+ t += c;
+ n -= c;
+ shift += c;
+ }
+ else
+ {
+ /* 2 copy, will always become 3 with back-multiplication. */
+ t = powtab_mem_ptr;
+ powtab_mem_ptr += 3;
+ t[0] = p[0];
+ t[1] = p[1];
+ }
+
+ SET_powers_t (pt[0], t, n, digits_in_base, base, shift);
+ p = t;
+ pt++;
+ start_idx = n_pows - 3;
+ }
+
+ for (long pi = start_idx; pi >= 0; pi--)
+ {
+ t = powtab_mem_ptr;
+ powtab_mem_ptr += 2 * n + 2;
+
+ ASSERT (powtab_mem_ptr < powtab_mem + mpn_str_powtab_alloc (un));
+
+ mpn_sqr (t, p, n);
+
+ digits_in_base *= 2;
+ n *= 2;
+ n -= t[n - 1] == 0;
+ shift *= 2;
+
+ c = t[0] == 0;
+ t += c;
+ n -= c;
+ shift += c;
+
+ /* Adjust new value if it is too small as input to the next squaring. */
+ if (((digits_in_base + chars_per_limb) << pi) <= exptab[0])
+ {
+ t[n] = cy = mpn_mul_1 (t, t, n, big_base);
+ n += cy != 0;
+
+ digits_in_base += chars_per_limb;
+
+ c = t[0] == 0;
+ t += c;
+ n -= c;
+ shift += c;
+ }
+
+ SET_powers_t (pt[0], t, n, digits_in_base, base, shift);
+
+ /* Adjust previous value if it is not at its target power. */
+ if (pt[-1].digits_in_base < exptab[pi + 1])
+ {
+ mp_size_t n = pt[-1].n;
+ mp_ptr p = pt[-1].p;
+ p[n] = cy = mpn_mul_1 (p, p, n, big_base);
+ n += cy != 0;
+
+ ASSERT (pt[-1].digits_in_base + chars_per_limb == exptab[pi + 1]);
+ pt[-1].digits_in_base = exptab[pi + 1];
+
+ c = p[0] == 0;
+ pt[-1].p = p + c;
+ pt[-1].n = n - c;
+ pt[-1].shift += c;
+ }
+
+ p = t;
+ pt++;
+ }
+}
+#endif
+
+#if DIV_1_VS_MUL_1_PERCENT < 275
+#define HAVE_mpn_compute_powtab_div 1
+static void
+mpn_compute_powtab_div (powers_t *powtab, mp_ptr powtab_mem, mp_size_t un,
+ int base, const size_t *exptab, size_t n_pows)
+{
+ mp_ptr p, t;
+
+ mp_limb_t big_base = mp_bases[base].big_base;
+ int chars_per_limb = mp_bases[base].chars_per_limb;
+
+ mp_ptr powtab_mem_ptr = powtab_mem;
+
+ size_t digits_in_base = chars_per_limb;
+
+ powers_t *pt = powtab;
+
+ p = powtab_mem_ptr;
+ powtab_mem_ptr += 1;
+ p[0] = big_base;
+
+ SET_powers_t (pt[0], p, 1, digits_in_base, base, 0);
+ pt++;
More information about the gmp-commit
mailing list