Merging bignum to master

Merging bignum to master

[Tom Tromey]

I'm merging bignum to master now, then I'm going to delete the
now-obsolete feature branch.  Please report any problems you find.

thanks,
Tom

Re: Merging bignum to master

[Basil L. Contovounesios]

[-- Attachment #1: Type: text/plain, Size: 366 bytes --]

Tom Tromey <tom@tromey.com> writes:

> I'm merging bignum to master now

Thank you and everyone who helped!

>  [...] Please report any problems you find.

It'd be nice if expt could be updated to handle bignums:

  (let ((googol (expt 10 100)))
    (= googol (apply #'* (make-list 100 10)))) ; => nil

There's also a missing full stop in `(elisp) Integer Basics':


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: bignum.diff --]
[-- Type: text/x-diff, Size: 617 bytes --]

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 89205f9df3..d5600e0806 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -37,7 +37,7 @@ Integer Basics
   Integers in Emacs Lisp can have arbitrary precision.
 
   Under the hood, though, there are two kinds of integers: smaller
-ones, called @dfn{fixnums}, and larger ones, called @dfn{bignums}
+ones, called @dfn{fixnums}, and larger ones, called @dfn{bignums}.
 Some functions in Emacs only accept fixnums.  Also, while fixnums can
 always be compared for equality with @code{eq}, bignums require the
 use of @code{eql}.

[-- Attachment #3: Type: text/plain, Size: 11 bytes --]


-- 
Basil

Re: Merging bignum to master

[Ulrich Mueller]

>>>>> On Sat, 11 Aug 2018, Tom Tromey wrote:

> I'm merging bignum to master now, then I'm going to delete the
> now-obsolete feature branch.  Please report any problems you find.

I noticed that there is no --with-gmp configure option to control
linking against libgmp. It this as it is supposed to be?

Re: Merging bignum to master

[John Wiegley]

[-- Attachment #1: Type: text/plain, Size: 380 bytes --]

>>>>> "TT" == Tom Tromey <tom@tromey.com> writes:

TT> I'm merging bignum to master now, then I'm going to delete the
TT> now-obsolete feature branch. Please report any problems you find.

Thank you for your work, Tom.

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 658 bytes --]

Re: Merging bignum to master

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 507 bytes --]

Ulrich Mueller wrote:
> I noticed that there is no --with-gmp configure option to control
> linking against libgmp. It this as it is supposed to be?

We should have an option, for the same reason we have an option for building 
versus linking to the regex library. I installed the attached to try to do that. 
I didn't call the option --with-gmp, since the idea is that Emacs always uses 
GMP in some form or another. I called it --with-mini-gmp, as it controls whether 
Emacs uses mini-gmp or regular GMP.

[-- Attachment #2: 0001-New-configure-arg-with-mini-gmp.patch --]
[-- Type: text/x-patch, Size: 2524 bytes --]

From 3fc948a36c0f70f73d2e8eb688b1599fa6b73036 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 12 Aug 2018 01:06:15 -0700
Subject: [PATCH] New 'configure' arg --with-mini-gmp

* configure.ac: It lets the builder override default of whther
mini-gmp is used.  Use AC_SEARCH_LIBS as per Autoconf manual.
---
 configure.ac | 35 ++++++++++++++++++++++++-----------
 etc/NEWS     |  7 +++++--
 2 files changed, 29 insertions(+), 13 deletions(-)

diff --git a/configure.ac b/configure.ac
index 690b999125..58bdefab6d 100644
--- a/configure.ac
+++ b/configure.ac
@@ -4302,19 +4302,32 @@ AC_DEFUN
 AC_SUBST(DESLIB)
 AC_SUBST(KRB4LIB)
 
+AC_ARG_WITH([mini-gmp],
+  [AS_HELP_STRING([--without-mini-gmp],
+		  [don't compile and use mini-gmp, a substitute for the
+		   GNU Multiple Precision (GMP) library; this is the
+		   default on systems with recent-enough GMP.])])
 GMP_LIB=
-GMP_OBJ=
+GMP_OBJ=mini-gmp.o
 HAVE_GMP=no
-AC_CHECK_LIB(gmp, __gmpz_roinit_n, [
-  AC_CHECK_HEADERS(gmp.h, [
-    GMP_LIB=-lgmp
-    HAVE_GMP=yes
-    AC_DEFINE(HAVE_GMP, 1, [Define to 1 if you have gmp.h and -lgmp])])])
-if test $HAVE_GMP = no; then
-   GMP_OBJ=mini-gmp.o
-fi
-AC_SUBST(GMP_LIB)
-AC_SUBST(GMP_OBJ)
+case $with_mini_gmp in
+  yes) ;;
+  no) HAVE_GMP=yes;;
+  *) AC_CHECK_HEADERS([gmp.h],
+       [OLIBS=$LIBS
+	AC_SEARCH_LIBS([__gmpz_roinit_n], [gmp])
+	LIBS=$OLIBS
+	case $ac_cv_search___gmpz_roinit_n in
+	  'none needed') HAVE_GMP=yes;;
+	  -*) HAVE_GMP=yes GMP_LIB=$ac_cv_search___gmpz_roinit_n;;
+	esac]);;
+esac
+if test "$HAVE_GMP" = yes; then
+  GMP_OBJ=
+  AC_DEFINE([HAVE_GMP], 1, [Define to 1 if you have recent-enough GMP.])
+fi
+AC_SUBST([GMP_LIB])
+AC_SUBST([GMP_OBJ])
 
 AC_CHECK_HEADERS(valgrind/valgrind.h)
 
diff --git a/etc/NEWS b/etc/NEWS
index d684e35524..decc5e3954 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -24,8 +24,11 @@ When you add a new item, use the appropriate mark if you are sure it applies,
 \f
 * Installation Changes in Emacs 27.1
 
-** configure now checks for the GMP library.  If not found, the
-included "mini-gmp" library is used instead.
+** Emacs now uses GMP, the GNU Multiple Precision library.
+By default, if 'configure' does not find a suitable libgmp, it
+arranges for the included mini-gmp library to be built and used.
+The new 'configure' option --with-mini-gmp uses mini-gmp even if a
+suitable libgmp is available.
 
 ** The new configure option '--with-json' adds support for JSON using
 the Jansson library.  It is on by default; use 'configure
-- 
2.17.1

Re: Merging bignum to master

[Pip Cet]

On Sat, Aug 11, 2018 at 7:48 PM Tom Tromey <tom@tromey.com> wrote:
> I'm merging bignum to master now, then I'm going to delete the
> now-obsolete feature branch.  Please report any problems you find.

Thank you for all your work!

I notice that there are a few places where you use XFIXNUMPTR
directly, rather than make_mint_ptr. Is that intentional? I think now
would be a good time to fix it and make XFIXNUMPTR internal to lisp.h.

Also, the doc comments for most_negative_fixnum and
most_positive_fixnum in data.c still need updating.

Re: Merging bignum to master

[Tom Tromey]

>>>>> "Pip" == Pip Cet <pipcet@gmail.com> writes:

Pip> I notice that there are a few places where you use XFIXNUMPTR
Pip> directly, rather than make_mint_ptr. Is that intentional? I think now
Pip> would be a good time to fix it and make XFIXNUMPTR internal to lisp.h.

I don't think this is something I touched; or if I did, it was just in
one of the mass renamings.  I don't really have an opinion on what
should be done here.

Tom

Re: Merging bignum to master

[Tom Tromey]

>>>>> "Basil" == Basil L Contovounesios <contovob@tcd.ie> writes:

Basil> It'd be nice if expt could be updated to handle bignums:

What do you think of this?

Tom

diff --git a/src/floatfns.c b/src/floatfns.c
index bbf7df4db3..c55418a35c 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -206,25 +206,28 @@ DEFUN ("expt", Fexpt, Sexpt, 2, 2, 0,
 {
   CHECK_FIXNUM_OR_FLOAT (arg1);
   CHECK_FIXNUM_OR_FLOAT (arg2);
-  if (FIXNUMP (arg1)     /* common lisp spec */
+  if (INTEGERP (arg1)     /* common lisp spec */
       && FIXNUMP (arg2)   /* don't promote, if both are ints, and */
       && XFIXNUM (arg2) >= 0) /* we are sure the result is not fractional */
     {				/* this can be improved by pre-calculating */
-      EMACS_INT y;		/* some binary powers of x then accumulating */
-      EMACS_UINT acc, x;  /* Unsigned so that overflow is well defined.  */
       Lisp_Object val;
+      mpz_t x, *xp, r;
 
-      x = XFIXNUM (arg1);
-      y = XFIXNUM (arg2);
-      acc = (y & 1 ? x : 1);
-
-      while ((y >>= 1) != 0)
+      if (BIGNUMP (arg1))
+	xp = &XBIGNUM (arg1)->value;
+      else
 	{
-	  x *= x;
-	  if (y & 1)
-	    acc *= x;
+	  mpz_init_set_si (x, XFIXNUM (arg1));
+	  xp = &x;
 	}
-      XSETINT (val, acc);
+
+      mpz_init (r);
+      mpz_pow_ui (r, *xp, XFIXNUM (arg2));
+
+      val = make_number (r);
+      mpz_clear (r);
+      if (xp == &x)
+	mpz_clear (x);
       return val;
     }
   return make_float (pow (XFLOATINT (arg1), XFLOATINT (arg2)));
diff --git a/test/src/floatfns-tests.el b/test/src/floatfns-tests.el
index 7714c05d60..4fab032ecb 100644
--- a/test/src/floatfns-tests.el
+++ b/test/src/floatfns-tests.el
@@ -46,4 +46,8 @@
   (should (= (+ (logb most-positive-fixnum) 1)
              (logb (+ most-positive-fixnum 1)))))
 
+(ert-deftest bignum-expt ()
+  (should (= (expt 10 100)
+             (apply #'* (make-list 100 10)))))
+
 (provide 'floatfns-tests)

Re: Merging bignum to master

[Ulrich Mueller]

>>>>> On Sun, 12 Aug 2018, Paul Eggert wrote:

>> I noticed that there is no --with-gmp configure option to control
>> linking against libgmp. It this as it is supposed to be?

> We should have an option, for the same reason we have an option for
> building versus linking to the regex library. I installed the attached
> to try to do that. I didn't call the option --with-gmp, since the idea
> is that Emacs always uses GMP in some form or another. I called it
> --with-mini-gmp, as it controls whether Emacs uses mini-gmp or regular
> GMP.

Thanks. There's still a problem, with an explicit --without-mini-gmp
option both GMP_LIB and GMP_OBJ end up being empty, and linking of
temacs fails.

Re: Merging bignum to master

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Sun, 12 Aug 2018 01:09:26 -0700
> 
> I didn't call the option --with-gmp, since the idea is that Emacs always uses 
> GMP in some form or another. I called it --with-mini-gmp, as it controls whether 
> Emacs uses mini-gmp or regular GMP.

I think other packages use --enable-mini-gmp, so maybe we should name
the option the same, for consistency.

Thanks.

Re: Merging bignum to master

[Eli Zaretskii]

> From: Ulrich Mueller <ulm@gentoo.org>
> Date: Sun, 12 Aug 2018 19:21:08 +0200
> Cc: emacs-devel@gnu.org
> 
> Thanks. There's still a problem, with an explicit --without-mini-gmp
> option both GMP_LIB and GMP_OBJ end up being empty, and linking of
> temacs fails.

What did you expect --without-mini-gmp to produce?  Emacs _needs_ some
GMP library and cannot be built without one anymore, GMP is not an
optional feature.

Re: Merging bignum to master

[Eli Zaretskii]

> From: "John Wiegley" <johnw@gnu.org>
> Date: Sun, 12 Aug 2018 00:37:25 -0700
> Cc: emacs-devel@gnu.org
> 
> Thank you for your work, Tom.

Seconded.

Re: Merging bignum to master

[Ulrich Mueller]

>>>>> On Sun, 12 Aug 2018, Eli Zaretskii wrote:

>> Thanks. There's still a problem, with an explicit --without-mini-gmp
>> option both GMP_LIB and GMP_OBJ end up being empty, and linking of
>> temacs fails.

> What did you expect --without-mini-gmp to produce?

That it will link against -lgmp, i.e. GMP_LIB should not be empty with
that option.

> Emacs _needs_ some GMP library and cannot be built without one
> anymore, GMP is not an optional feature.

Re: Merging bignum to master

[Paul Eggert]

Eli Zaretskii wrote:
> I think other packages use --enable-mini-gmp, so maybe we should name
> the option the same, for consistency.

The GNU coding standards say that --enable is supposed to be for adding 
user-level facilities, which this is not: the user-level behavior does not 
change. Conversely, the coding standards say that --with is appropriate for 
choosing to use a library like GMP. So --with-SOMETHING seems more appropriate 
here than --enable-SOMETHING.

That being said, the distinction between --with-FOO and --enable-FOO has long 
been a confusing area of the GNU coding standards -- as witnessed by the other 
packages you're thinking about.

Re: Merging bignum to master

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 167 bytes --]

Ulrich Mueller wrote:
> That it will link against -lgmp, i.e. GMP_LIB should not be empty with
> that option.

That's easy enough to change; I installed the attached.

[-- Attachment #2: 0001-configure.ac-GMP_LIB-Set-to-lgmp-if-without-mini-gmp.patch --]
[-- Type: text/x-patch, Size: 661 bytes --]

From ca10011898e2ceeded4027413a1488837199ad7a Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 12 Aug 2018 17:14:43 -0700
Subject: [PATCH] * configure.ac (GMP_LIB): Set to -lgmp if --without-mini-gmp.

---
 configure.ac | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/configure.ac b/configure.ac
index c40b3bd290..0b8849eea2 100644
--- a/configure.ac
+++ b/configure.ac
@@ -4312,7 +4312,7 @@ AC_DEFUN
 HAVE_GMP=no
 case $with_mini_gmp in
   yes) ;;
-  no) HAVE_GMP=yes;;
+  no) HAVE_GMP=yes GMP_LIB=-lgmp;;
   *) AC_CHECK_HEADERS([gmp.h],
        [OLIBS=$LIBS
 	AC_SEARCH_LIBS([__gmpz_roinit_n], [gmp])
-- 
2.17.1

Re: Merging bignum to master

[Tom Tromey]

>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:

Paul> That being said, the distinction between --with-FOO and --enable-FOO
Paul> has long been a confusing area of the GNU coding standards -- as
Paul> witnessed by the other packages you're thinking about.

I find it pretty hard to guess if a given option is --with or --enable,
and normally if I do guess, I pick the wrong one.  So I've thought for a
while now that autoconf should simply treat them identically and this
subtle distinction be erased.

Tom

Re: Merging bignum to master

[Andreas Schwab]

On Aug 12 2018, Paul Eggert <eggert@cs.ucla.edu> wrote:

> Eli Zaretskii wrote:
>> I think other packages use --enable-mini-gmp, so maybe we should name
>> the option the same, for consistency.
>
> The GNU coding standards say that --enable is supposed to be for adding
> user-level facilities, which this is not: the user-level behavior does not
> change. Conversely, the coding standards say that --with is appropriate
> for choosing to use a library like GMP. So --with-SOMETHING seems more
> appropriate here than --enable-SOMETHING.

The autoconf manual says about --enable: "They should only cause parts
of the program to be built rather than left out."  The mini-gmp source
is a part of the sources, and --enable-mini-gmp enables the use of it.
--with is for external dependencies.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Merging bignum to master

[Ulrich Mueller]

>>>>> On Mon, 13 Aug 2018, Andreas Schwab wrote:

> On Aug 12 2018, Paul Eggert <eggert@cs.ucla.edu> wrote:
>> The GNU coding standards say that --enable is supposed to be for adding
>> user-level facilities, which this is not: the user-level behavior does not
>> change. Conversely, the coding standards say that --with is appropriate
>> for choosing to use a library like GMP. So --with-SOMETHING seems more
>> appropriate here than --enable-SOMETHING.

> The autoconf manual says about --enable: "They should only cause parts
> of the program to be built rather than left out."  The mini-gmp source
> is a part of the sources, and --enable-mini-gmp enables the use of it.
> --with is for external dependencies.

The option also controls linking against the external libgmp, so it is
not entirely about internal sources.

Maybe it would be cleaner to call the option --with-gmp (and invert its
logic), after all? It could still be enabled by default.

Re: Merging bignum to master

[Paul Eggert]

Ulrich Mueller wrote:
> Maybe it would be cleaner to call the option --with-gmp (and invert its
> logic), after all? It could still be enabled by default.

Works for me.

Re: Merging bignum to master

[Basil L. Contovounesios]

Tom Tromey <tom@tromey.com> writes:

>>>>>> "Basil" == Basil L Contovounesios <contovob@tcd.ie> writes:
>
> Basil> It'd be nice if expt could be updated to handle bignums:
>
> What do you think of this?

Looks fine to uninitiated me, thanks!

-- 
Basil

Re: Merging bignum to master

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 800 bytes --]

Pip Cet wrote:

> I notice that there are a few places where you use XFIXNUMPTR
> directly, rather than make_mint_ptr. Is that intentional? I think now
> would be a good time to fix it and make XFIXNUMPTR internal to lisp.h.

It's intentional since those few places don't need the full power of 
make_mint_ptr (often the pointers are already aligned) and there might be 
trouble if storage allocation fails if the pointer is not aligned. Perhaps 
you're right and this is overkill; it is confusing at any rate. In the meantime 
I installed the attached first patch to fix a glitch I saw in this area while 
looking at the current XFIXNUMPTR uses.

> Also, the doc comments for most_negative_fixnum and
> most_positive_fixnum in data.c still need updating.

Thanks, done in the second attached patch.

[-- Attachment #2: 0001-Fix-check-for-unsafe-watch-descriptor.patch --]
[-- Type: text/x-patch, Size: 2168 bytes --]

From 76101698a770d389f22b547c331ec78473040c47 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 13 Aug 2018 15:45:17 -0700
Subject: [PATCH 1/2] Fix check for unsafe watch descriptor

* src/lisp.h (make_pointer_integer_unsafe): New function.
(make_pointer_integer): Use it.
* src/gfilenotify.c (dir_monitor_callback): Omit redundant eassert.
(Fgfile_add_watch): Signal an error instead of failing an
assertion if the pointer does not work.
---
 src/gfilenotify.c | 7 +++----
 src/lisp.h        | 8 +++++++-
 2 files changed, 10 insertions(+), 5 deletions(-)

diff --git a/src/gfilenotify.c b/src/gfilenotify.c
index 7eea2cfac1..798f308b31 100644
--- a/src/gfilenotify.c
+++ b/src/gfilenotify.c
@@ -77,7 +77,6 @@ dir_monitor_callback (GFileMonitor *monitor,
 
   /* Determine callback function.  */
   monitor_object = make_pointer_integer (monitor);
-  eassert (FIXNUMP (monitor_object));
   watch_object = assq_no_quit (monitor_object, watch_list);
 
   if (CONSP (watch_object))
@@ -203,10 +202,10 @@ will be reported only in case of the `moved' event.  */)
   if (! monitor)
     xsignal2 (Qfile_notify_error, build_string ("Cannot watch file"), file);
 
-  Lisp_Object watch_descriptor = make_pointer_integer (monitor);
+  Lisp_Object watch_descriptor = make_pointer_integer_unsafe (monitor);
 
-  /* Check the dicey assumption that make_pointer_integer is safe.  */
-  if (! FIXNUMP (watch_descriptor))
+  if (! (FIXNUMP (watch_descriptor)
+	 && XFIXNUMPTR (watch_descriptor) == monitor))
     {
       g_object_unref (monitor);
       xsignal2 (Qfile_notify_error, build_string ("Unsupported file watcher"),
diff --git a/src/lisp.h b/src/lisp.h
index b7ef8dc63a..18d53537cc 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -1188,10 +1188,16 @@ XFIXNUMPTR (Lisp_Object a)
   return XUNTAG (a, Lisp_Int0, char);
 }
 
+INLINE Lisp_Object
+make_pointer_integer_unsafe (void *p)
+{
+  return TAG_PTR (Lisp_Int0, p);
+}
+
 INLINE Lisp_Object
 make_pointer_integer (void *p)
 {
-  Lisp_Object a = TAG_PTR (Lisp_Int0, p);
+  Lisp_Object a = make_pointer_integer_unsafe (p);
   eassert (FIXNUMP (a) && XFIXNUMPTR (a) == p);
   return a;
 }
-- 
2.17.1


[-- Attachment #3: 0002-Update-doc-strings-for-fixnum-constants.patch --]
[-- Type: text/x-patch, Size: 1454 bytes --]

From dc18a0917a5531ef3e1c9b4921bb4d8f317bc7a4 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 13 Aug 2018 15:55:06 -0700
Subject: [PATCH 2/2] Update doc strings for fixnum constants

* src/data.c (most-positive-fixnum, most-negative-fixnum):
Update doc strings in the light of fixnums.
---
 src/data.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/src/data.c b/src/data.c
index 7b8dd45c94..a1215b9d6b 100644
--- a/src/data.c
+++ b/src/data.c
@@ -4260,13 +4260,13 @@ syms_of_data (void)
   set_symbol_function (Qwholenump, XSYMBOL (Qnatnump)->u.s.function);
 
   DEFVAR_LISP ("most-positive-fixnum", Vmost_positive_fixnum,
-	       doc: /* The largest value that is representable in a Lisp integer.
+	       doc: /* The greatest integer that is represented efficiently.
 This variable cannot be set; trying to do so will signal an error.  */);
   Vmost_positive_fixnum = make_fixnum (MOST_POSITIVE_FIXNUM);
   make_symbol_constant (intern_c_string ("most-positive-fixnum"));
 
   DEFVAR_LISP ("most-negative-fixnum", Vmost_negative_fixnum,
-	       doc: /* The smallest value that is representable in a Lisp integer.
+	       doc: /* The least integer that is represented efficiently.
 This variable cannot be set; trying to do so will signal an error.  */);
   Vmost_negative_fixnum = make_fixnum (MOST_NEGATIVE_FIXNUM);
   make_symbol_constant (intern_c_string ("most-negative-fixnum"));
-- 
2.17.1

Re: Merging bignum to master

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

Eli said:

  > The autoconf manual says about --enable: "They should only cause parts
  > of the program to be built rather than left out."

Yes, but that is a superficial way to look at it.  The real intended
meaning of --enable is to include a feature, or support for some
feature.  So --enable option ought to be named after the feature it
enables, NOT after some piece of code.

If we stick to that, the substantial difference between --enable and
--with will be clear, so people will not confuse them.

  > That being said, the distinction between --with-FOO and --enable-FOO has long 
  > been a confusing area of the GNU coding standards -- as witnessed by the other 
  > packages you're thinking about.

Is that because some cases have been handled erroneously?  Or is it
because some cases don't really fit into either --with or --enable?

If the latter, I think we need to take the bull by the horns
and work out a good way to handle those cases, rather than forcing them
into one of two slots which they do not fit.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Merging bignum to master

[Andy Moreton]

On Sun 12 Aug 2018, Tom Tromey wrote:

>>>>>> "Basil" == Basil L Contovounesios <contovob@tcd.ie> writes:
>
> Basil> It'd be nice if expt could be updated to handle bignums:
>
> What do you think of this?
>
> Tom
>
> diff --git a/src/floatfns.c b/src/floatfns.c
> index bbf7df4db3..c55418a35c 100644
> --- a/src/floatfns.c
> +++ b/src/floatfns.c
> @@ -206,25 +206,28 @@ DEFUN ("expt", Fexpt, Sexpt, 2, 2, 0,
>  {
>    CHECK_FIXNUM_OR_FLOAT (arg1);
>    CHECK_FIXNUM_OR_FLOAT (arg2);
> -  if (FIXNUMP (arg1)     /* common lisp spec */
> +  if (INTEGERP (arg1)     /* common lisp spec */
>        && FIXNUMP (arg2)   /* don't promote, if both are ints, and */
>        && XFIXNUM (arg2) >= 0) /* we are sure the result is not fractional */
>      {				/* this can be improved by pre-calculating */
> -      EMACS_INT y;		/* some binary powers of x then accumulating */
> -      EMACS_UINT acc, x;  /* Unsigned so that overflow is well defined.  */

You have dropped some of the commentary that explains how it is trying
to give similar behaviour to Common Lisp. See the description at:
<http://www.lispworks.com/documentation/lw50/CLHS/Body/f_exp_e.htm>

>        Lisp_Object val;
> +      mpz_t x, *xp, r;
>  
> -      x = XFIXNUM (arg1);
> -      y = XFIXNUM (arg2);
> -      acc = (y & 1 ? x : 1);
> -
> -      while ((y >>= 1) != 0)
> +      if (BIGNUMP (arg1))
> +	xp = &XBIGNUM (arg1)->value;
> +      else
>  	{
> -	  x *= x;
> -	  if (y & 1)
> -	    acc *= x;
> +	  mpz_init_set_si (x, XFIXNUM (arg1));

This doesn't work for systems where sizeof (EMACS_INT) > sizeof (long).
> +	  xp = &x;
>  	}
> -      XSETINT (val, acc);
> +
> +      mpz_init (r);
> +      mpz_pow_ui (r, *xp, XFIXNUM (arg2));
Likewise.

> +
> +      val = make_number (r);
> +      mpz_clear (r);
> +      if (xp == &x)
> +	mpz_clear (x);
>        return val;
>      }
>    return make_float (pow (XFLOATINT (arg1), XFLOATINT (arg2)));
> diff --git a/test/src/floatfns-tests.el b/test/src/floatfns-tests.el
> index 7714c05d60..4fab032ecb 100644
> --- a/test/src/floatfns-tests.el
> +++ b/test/src/floatfns-tests.el
> @@ -46,4 +46,8 @@
>    (should (= (+ (logb most-positive-fixnum) 1)
>               (logb (+ most-positive-fixnum 1)))))
>  
> +(ert-deftest bignum-expt ()
> +  (should (= (expt 10 100)
> +             (apply #'* (make-list 100 10)))))
> +
>  (provide 'floatfns-tests)

Re: Merging bignum to master

[Andy Moreton]

On Sat 11 Aug 2018, Tom Tromey wrote:

> I'm merging bignum to master now, then I'm going to delete the
> now-obsolete feature branch.  Please report any problems you find.

ELISP> (mod (+ most-positive-fixnum 0) 2)
1 (#o1, #x1, ?\C-a)
ELISP> (mod (+ most-positive-fixnum 1) 2)
0 (#o0, #x0, ?\C-@)
ELISP> (mod (+ most-positive-fixnum 1) 2.0)
1.0                          <<<<<<<<< expected 0.0
ELISP> (mod (+ most-positive-fixnum 1.0) 2)
0.0

So (mod bignum float) appears to misbehave. It looks like the problem is
that fmod_float does not handle bignums.

    AndyM

Re: Merging bignum to master

[Noam Postavsky]

On 13 August 2018 at 18:58, Paul Eggert <eggert@cs.ucla.edu> wrote:

> meantime I installed the attached first patch to fix a glitch I saw in this
> area while looking at the current XFIXNUMPTR uses.

> --- a/src/lisp.h
> +++ b/src/lisp.h
> @@ -1189,9 +1189,15 @@ XFIXNUMPTR (Lisp_Object a)
>  }
>
>  INLINE Lisp_Object
> +make_pointer_integer_unsafe (void *p)
> +{
> +  return TAG_PTR (Lisp_Int0, p);
> +}
> +
> +INLINE Lisp_Object
>  make_pointer_integer (void *p)
>  {
> -  Lisp_Object a = TAG_PTR (Lisp_Int0, p);
> +  Lisp_Object a = make_pointer_integer_unsafe (p);

I use ./configure --enable-check-lisp-object-type, and this gives me

  CC       dispnew.o
In file included from dispnew.c:27:0:
lisp.h: In function ‘make_pointer_integer_unsafe’:
lisp.h:568:28: error: expected expression before ‘{’ token
 # define LISP_INITIALLY(w) {w}
                            ^
lisp.h:790:3: note: in expansion of macro ‘LISP_INITIALLY’
   LISP_INITIALLY ((Lisp_Word) ((untagged_ptr) (ptr) + LISP_WORD_TAG (tag)))
   ^~~~~~~~~~~~~~
lisp.h:1194:10: note: in expansion of macro ‘TAG_PTR’
   return TAG_PTR (Lisp_Int0, p);
          ^~~~~~~

Re: Merging bignum to master

[Paul Eggert]

Richard Stallman wrote:
>    > That being said, the distinction between --with-FOO and --enable-FOO has long
>    > been a confusing area of the GNU coding standards -- as witnessed by the other
>    > packages you're thinking about.
> 
> Is that because some cases have been handled erroneously?  Or is it
> because some cases don't really fit into either --with or --enable?

In some cases it's erroneous coding. But more often, I think, it's because the 
two names are both plausible and developers and users are easily confused about 
which names to use.

For example, coreutils ./configure has a --with-gmp option, which causes two 
things to happen: first, 'expr' and 'factor' link to the GMP library (which is 
appropriate for --with-FOO) and second, these two programs support the feature 
of arbitrary-length integers (which is appropriate for --enable-FOO).

Strictly speaking, I supose the GNU Coding Standards require Coreutils to have 
both a --with-gmp option (to control whether the GMP library is used) and an 
--enable-bignum option (to control whether bignums are supported). But that 
would be more confusing than what Coreutils has now, which is a single option 
that controls both things, and which is more natural since the only reason you'd 
want to link to GMP is to have bignums, and if you want bignums with Coreutils 
the only way to get them is to link to GMP.

> If the latter, I think we need to take the bull by the horns
> and work out a good way to handle those cases, rather than forcing them
> into one of two slots which they do not fit.

I hope that we needn't make the coding standards even more complicated than they 
already are in this area. When complexity causes confusion, adding more 
complexity is likely to cause more confusion.

I'd be more inclined to go in the direction Tom Tromey suggested, which is to no 
longer require a sharp distinction between --with-FOO and --enable-FOO since the 
distinction's confusion is more trouble than it's worth.

Re: Merging bignum to master

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 158 bytes --]

Is it intentional that int-forwarded variables are still limited to
the fixnum range? In any case, we probably didn't want to rename
XINTFWD to XFIXNUMFWD...

[-- Attachment #2: 0001-fix-minor-oversights-in-the-bignum-patch.patch --]
[-- Type: text/x-patch, Size: 2045 bytes --]

From 546cc94a830ac971ac72700deac908fd8e41d356 Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@gmail.com>
Date: Tue, 14 Aug 2018 12:36:04 +0000
Subject: [PATCH] fix minor oversights in the bignum patch

---
 src/data.c  | 6 +++---
 src/lread.c | 7 +++----
 2 files changed, 6 insertions(+), 7 deletions(-)

diff --git a/src/data.c b/src/data.c
index a1215b9d6bf..4cd93f0ac7f 100644
--- a/src/data.c
+++ b/src/data.c
@@ -74,7 +74,7 @@ XKBOARD_OBJFWD (union Lisp_Fwd *a)
   return &a->u_kboard_objfwd;
 }
 static struct Lisp_Intfwd *
-XFIXNUMFWD (union Lisp_Fwd *a)
+XINTFWD (union Lisp_Fwd *a)
 {
   eassert (INTFWDP (a));
   return &a->u_intfwd;
@@ -1002,7 +1002,7 @@ do_symval_forwarding (register union Lisp_Fwd *valcontents)
   switch (XFWDTYPE (valcontents))
     {
     case Lisp_Fwd_Int:
-      XSETINT (val, *XFIXNUMFWD (valcontents)->intvar);
+      XSETINT (val, *XINTFWD (valcontents)->intvar);
       return val;
 
     case Lisp_Fwd_Bool:
@@ -1095,7 +1095,7 @@ store_symval_forwarding (union Lisp_Fwd *valcontents, register Lisp_Object newva
     {
     case Lisp_Fwd_Int:
       CHECK_FIXNUM (newval);
-      *XFIXNUMFWD (valcontents)->intvar = XFIXNUM (newval);
+      *XINTFWD (valcontents)->intvar = XFIXNUM (newval);
       break;
 
     case Lisp_Fwd_Bool:
diff --git a/src/lread.c b/src/lread.c
index df2fe581203..7411f1c7354 100644
--- a/src/lread.c
+++ b/src/lread.c
@@ -3813,10 +3813,9 @@ string_to_number (char const *string, int base, int flags)
       return make_bignum_str (string, base);
     }
 
-  /* Either the number uses float syntax, or it does not fit into a fixnum.
-     Convert it from string to floating point, unless the value is already
-     known because it is an infinity, a NAN, or its absolute value fits in
-     uintmax_t.  */
+  /* The number uses float syntax.  Convert it from string to floating
+     point, unless the value is already known because it is an
+     infinity, a NAN, or its absolute value fits in uintmax_t.  */
   if (! value)
     value = atof (string + signedp);
 
-- 
2.18.0

Re: Merging bignum to master

[Paul Eggert]

Pip Cet wrote:
> Is it intentional that int-forwarded variables are still limited to
> the fixnum range? In any case, we probably didn't want to rename
> XINTFWD to XFIXNUMFWD...

I think some C code does assume fixnum ranges for these variables, and would 
have to be inspected. Presumably we'd go to either intmax_t range or Emacs 
integers (fixnums or bignums), and that might need to be thought through in a 
case-by-case basis. In the meantime XFIXNUMFWD is probably a good name since 
that's effectively what the code does now.

Re: Merging bignum to master

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 399 bytes --]

On 08/13/2018 02:14 AM, Paul Eggert wrote:
> Ulrich Mueller wrote:
>> Maybe it would be cleaner to call the option --with-gmp (and invert its
>> logic), after all? It could still be enabled by default.
>
> Works for me.
>
On further thought it's probably a bit clearer to call it --with-libgmp 
rather than --with-gmp since GMP code is always used one way or another, 
so I installed the attached.


[-- Attachment #2: 0001-Rename-without-mini-gmp-to-with-libgmp.txt --]
[-- Type: text/plain, Size: 2938 bytes --]

From fafbe1c3a2e3174afa1d4bf6aeb8502fac7b5933 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 14 Aug 2018 16:06:05 -0700
Subject: [PATCH] Rename --without-mini-gmp to --with-libgmp
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* configure.ac (HAVE_GMP): Rename ‘configure’ option from
--without-mini-gmp to --with-libgmp.  All uses changed.
* doc/lispref/numbers.texi (Predicates on Numbers): Large
integers are always available.  Clarify how eq works on them.
---
 configure.ac             | 15 +++++++--------
 doc/lispref/numbers.texi |  6 ++----
 etc/NEWS                 |  2 +-
 3 files changed, 10 insertions(+), 13 deletions(-)

diff --git a/configure.ac b/configure.ac
index 7b9448e13b..e5d094cf9e 100644
--- a/configure.ac
+++ b/configure.ac
@@ -4303,17 +4303,16 @@ AC_DEFUN
 AC_SUBST(DESLIB)
 AC_SUBST(KRB4LIB)
 
-AC_ARG_WITH([mini-gmp],
-  [AS_HELP_STRING([--without-mini-gmp],
-		  [don't compile and use mini-gmp, a substitute for the
-		   GNU Multiple Precision (GMP) library; this is the
-		   default on systems with recent-enough GMP.])])
+AC_ARG_WITH([libgmp],
+  [AS_HELP_STRING([--without-libgmp],
+		  [don't use the GNU Multiple Precision (GMP) library;
+		   this is the default on systems lacking libgmp.])])
 GMP_LIB=
 GMP_OBJ=mini-gmp-emacs.o
 HAVE_GMP=no
-case $with_mini_gmp in
-  yes) ;;
-  no) HAVE_GMP=yes GMP_LIB=-lgmp;;
+case $with_libgmp in
+  no) ;;
+  yes) HAVE_GMP=yes GMP_LIB=-lgmp;;
   *) AC_CHECK_HEADERS([gmp.h],
        [OLIBS=$LIBS
 	AC_SEARCH_LIBS([__gmpz_roinit_n], [gmp])
diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 89205f9df3..bd633b77c3 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -319,10 +319,8 @@ Predicates on Numbers
 
 @defun bignump object
 This predicate tests whether its argument is a large integer, and
-returns @code{t} if so, @code{nil} otherwise.  Large integers cannot
-be compared with @code{eq}, only with @code{=} or @code{eql}.  Also,
-large integers are only available if Emacs was compiled with the GMP
-library.
+returns @code{t} if so, @code{nil} otherwise.  Unlike small integers,
+large integers can be @code{=} or @code{eql} even if they are not @code{eq}.
 @end defun
 
 @defun fixnump object
diff --git a/etc/NEWS b/etc/NEWS
index f1d09a2b63..3ae956c788 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -27,7 +27,7 @@ When you add a new item, use the appropriate mark if you are sure it applies,
 ** Emacs now uses GMP, the GNU Multiple Precision library.
 By default, if 'configure' does not find a suitable libgmp, it
 arranges for the included mini-gmp library to be built and used.
-The new 'configure' option --with-mini-gmp uses mini-gmp even if a
+The new 'configure' option --without-libgmp uses mini-gmp even if a
 suitable libgmp is available.
 
 ** The new configure option '--with-json' adds support for JSON using
-- 
2.17.1

Re: Merging bignum to master

[Pip Cet]

If you really think XFIXNUMFWD is a good name, don't you at least
agree that it should go with renaming other references to intfwds to
fixnumfwds? Right now we have:

static struct Lisp_Intfwd *
XFIXNUMFWD (union Lisp_Fwd *a)
{
  eassert (INTFWDP (a));
  return &a->u_intfwd;
}

I still think that's clearly a case of over-eager replacement (XINT ->
XFIXNUM). To have XFIXNUMFWD but INTFWDP seems obviously wrong to me.

On Tue, Aug 14, 2018 at 6:01 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
>
> Pip Cet wrote:
> > Is it intentional that int-forwarded variables are still limited to
> > the fixnum range? In any case, we probably didn't want to rename
> > XINTFWD to XFIXNUMFWD...
>
> I think some C code does assume fixnum ranges for these variables, and would
> have to be inspected. Presumably we'd go to either intmax_t range or Emacs
> integers (fixnums or bignums), and that might need to be thought through in a
> case-by-case basis. In the meantime XFIXNUMFWD is probably a good name since
> that's effectively what the code does now.

Re: Merging bignum to master

[Andy Moreton]

On Sat 11 Aug 2018, Tom Tromey wrote:

> I'm merging bignum to master now, then I'm going to delete the
> now-obsolete feature branch.  Please report any problems you find.

I've noticed a bug in bignumcompare for 64bit Windows: it handles large
positive fixnums correctly, but not large negative fixnums. A patch liek
this should fix it:

    AndyM


diff --git a/src/data.c b/src/data.c
index a1215b9d6b..c89fa3cf51 100644
--- a/src/data.c
+++ b/src/data.c
@@ -2409,7 +2409,7 @@ bignumcompare (Lisp_Object num1, Lisp_Object num2,
 	}
       else if (FIXNUMP (num2))
         {
-          if (sizeof (EMACS_INT) > sizeof (long) && XFIXNUM (num2) > LONG_MAX)
+          if (sizeof (EMACS_INT) > sizeof (long))
             {
               mpz_t tem;
               mpz_init (tem);
@@ -2440,7 +2440,7 @@ bignumcompare (Lisp_Object num1, Lisp_Object num2,
       else
         {
 	  eassume (FIXNUMP (num1));
-          if (sizeof (EMACS_INT) > sizeof (long) && XFIXNUM (num1) > LONG_MAX)
+          if (sizeof (EMACS_INT) > sizeof (long))
             {
               mpz_t tem;
               mpz_init (tem);

Re: Merging bignum to master

[Paul Eggert]

Pip Cet wrote:
> If you really think XFIXNUMFWD is a good name

I don't. But this area should be improved soon enough, and in the meantime I 
wouldn't fiddle with the name since any fiddly replacement is likely to be 
changed anyway.

Re: Merging bignum to master

[Andy Moreton]

On Tue 14 Aug 2018, Andy Moreton wrote:

> On Sun 12 Aug 2018, Tom Tromey wrote:
>
>>>>>>> "Basil" == Basil L Contovounesios <contovob@tcd.ie> writes:
>>
>> Basil> It'd be nice if expt could be updated to handle bignums:
>>
>> What do you think of this?

Tom and Basil, please try the following patch for expt.
I have given it some light sanity testing on Windows 64bit.

    AndyM


diff --git a/src/floatfns.c b/src/floatfns.c
index bbf7df4db3..0e7e3090e8 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -204,29 +204,38 @@ DEFUN ("expt", Fexpt, Sexpt, 2, 2, 0,
        doc: /* Return the exponential ARG1 ** ARG2.  */)
   (Lisp_Object arg1, Lisp_Object arg2)
 {
-  CHECK_FIXNUM_OR_FLOAT (arg1);
+  CHECK_NUMBER (arg1);
   CHECK_FIXNUM_OR_FLOAT (arg2);
-  if (FIXNUMP (arg1)     /* common lisp spec */
-      && FIXNUMP (arg2)   /* don't promote, if both are ints, and */
-      && XFIXNUM (arg2) >= 0) /* we are sure the result is not fractional */
-    {				/* this can be improved by pre-calculating */
-      EMACS_INT y;		/* some binary powers of x then accumulating */
-      EMACS_UINT acc, x;  /* Unsigned so that overflow is well defined.  */
-      Lisp_Object val;
-
-      x = XFIXNUM (arg1);
-      y = XFIXNUM (arg2);
-      acc = (y & 1 ? x : 1);
-
-      while ((y >>= 1) != 0)
-	{
-	  x *= x;
-	  if (y & 1)
-	    acc *= x;
-	}
-      XSETINT (val, acc);
-      return val;
+
+  if (INTEGERP (arg1)           /* common lisp spec */
+      && FIXNUMP (arg2)         /* don't promote, if both are ints, and */
+      && XFIXNUM (arg2) >= 0    /* we are sure the result is not fractional */
+      && (sizeof (EMACS_INT) <= sizeof (long)
+          || (long) XFIXNUM (arg2) == XFIXNUM (arg2)))
+    {
+      Lisp_Object res;
+      mpz_t val;
+
+      mpz_init (val);
+      if (BIGNUMP (arg1))
+        {
+          mpz_pow_ui (val, XBIGNUM (arg1)->value, XFIXNUM (arg2));
+        }
+      else if (XFIXNUM (arg1) >= 0)
+        {
+          mpz_ui_pow_ui (val, XFIXNUM (arg1), XFIXNUM (arg2));
+        }
+      else
+        {
+          mpz_ui_pow_ui (val, -XFIXNUM (arg1), XFIXNUM (arg2));
+          if (XFIXNUM (arg2) & 1)
+            mpz_neg (val, val);
+        }
+      res = make_number (val);
+      mpz_clear (val);
+      return res;
     }
+
   return make_float (pow (XFLOATINT (arg1), XFLOATINT (arg2)));
 }
 

Re: Merging bignum to master

[Andy Moreton]

On Wed 15 Aug 2018, Pip Cet wrote:

> If you really think XFIXNUMFWD is a good name, don't you at least
> agree that it should go with renaming other references to intfwds to
> fixnumfwds? Right now we have:
>
> static struct Lisp_Intfwd *
> XFIXNUMFWD (union Lisp_Fwd *a)
> {
>   eassert (INTFWDP (a));
>   return &a->u_intfwd;
> }

Please don't top-post on technical mailing lists.

XFIXNUMFWD might not be pretty, but it does convey the idea that this is
code that only understands fixnums (the same as pre-bignum emacs), and
will need careful inspection before modifying it to support bignums.

> I still think that's clearly a case of over-eager replacement (XINT ->
> XFIXNUM). To have XFIXNUMFWD but INTFWDP seems obviously wrong to me.

The XINT -> XFIXNUM renaming preserved the meaning from pre-bignum
emacs i.e. only fixnums are supported.

It would seem sensible to rename INTFWDP -> FIXNUMFWDP to keep the
naming consistent, and then extend the code to support bignums later.

One thing to be careful of here is that on 64bit Windows builds of
emacs, sizeof (EMACS_INT) is 64bit but sizeof (long) is 32bit. This
requires careful use of the GMP library API, which does not accept long
long inputs (see mpz_set_intmax and mpz_set_uintmax in lisp.h).

    AndyM

Re: Merging bignum to master

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > Strictly speaking, I supose the GNU Coding Standards require Coreutils to have 
  > both a --with-gmp option (to control whether the GMP library is used) and an 
  > --enable-bignum option (to control whether bignums are supported).

Why would we need both?  Given --enable-bignums, which seems
fundametally to fit the purpose, is there really a reason for
--with-gmp?  Do we support bignums other than using gmp?

  > I'd be more inclined to go in the direction Tom Tromey suggested,
  > which is to no longer require a sharp distinction between
  > --with-FOO and --enable-FOO since the distinction's confusion is
  > more trouble than it's worth.

To me that sounds like surrendering to confusion without trying to
clear it up.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Merging bignum to master

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > On further thought it's probably a bit clearer to call it --with-libgmp 
  > rather than --with-gmp since GMP code is always used one way or another, 
  > so I installed the attached.

If it is a question of how the feature is implemented, then --with is
the right kind of option for it.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Merging bignum to master

[Basil L. Contovounesios]

Andy Moreton <andrewjmoreton@gmail.com> writes:

> On Tue 14 Aug 2018, Andy Moreton wrote:
>
>> On Sun 12 Aug 2018, Tom Tromey wrote:
>>
>>>>>>>> "Basil" == Basil L Contovounesios <contovob@tcd.ie> writes:
>>>
>>> Basil> It'd be nice if expt could be updated to handle bignums:
>>>
>>> What do you think of this?
>
> Tom and Basil, please try the following patch for expt.
> I have given it some light sanity testing on Windows 64bit.

Light sanity testing passing on x86_64-pc-linux-gnu, too.

Thanks,

-- 
Basil

Re: Merging bignum to master

[Paul Eggert]

Richard Stallman wrote:

> Why would we need both?  Given --enable-bignums, which seems
> fundametally to fit the purpose, is there really a reason for
> --with-gmp?  Do we support bignums other than using gmp?

Yes and no. If by "using gmp" you mean linking to libgmp, some GNU packages do 
support bignums other than by linking to libgmp. However, every GNU package that 
I know of supports bignums either by linking to libgmp or by compiling code 
copied from some subset of the GMP sources.

Here are some 'configure' options that GNU packages use to control this. As far 
as I can see, only Emacs master 'configure' follows the GNU coding standards. 
This suggests that in this area the standards are either too ambitious or are 
not clear enough; in either case they could use examples to cover some of the 
issues mentioned below.

* Emacs (master branch) always supports bignums, and by default it uses libgmp 
if available and otherwise substitutes its own portable and slower 
implementation copied from the GMP source code. The default can be overridden 
with --with-libgmp / --without-libgmp. This follows the GNU coding standards, 
and it wouldn't make sense to for Emacs 'configure' to have an --enable-bignum 
option since bignums are always supported.

* MPFR and Nettle always use bignums and by default always uses libgmp. Their 
'configure' scripts have an --enable-mini-gmp option to cause their builds to 
use the portable and slower substitute. This doesn't follow the GNU coding 
standards, since --enable-mini-gmp doesn't affect user-visible features.

* Coreutils supports bignums only as a build-time option that affects 
user-visible behavior. The Coreutils implementation always uses libgmp to 
support bignums if bignums are requested. Its 'configure' has a --with-gmp / 
--without-gmp option that works much like Emacs's --with-libgmp / 
--without-libgmp option, and that enables the bignum feature. It sounds like 
you're saying that Coreutils should rename its --with-gmp / --without-gmp option 
to --enable-bignums / --disable-bignums or something like that, since the option 
enables user-visible behavior. (Better yet, I suppose Coreutils should do what 
Emacs does and substitute its own portable implementation and use a 
--with-libgmp / --without-libgmp 'configure' option, though that'd be more work.)

* GNU Common Lisp always supports bignums and requires libgmp, and has an 
--enable-oldgmp option that links to an older version of libgmp rather than a 
newer one. This usage doesn't follow the GNU coding standards, which say this 
should be a --with option.

* GCC always uses bignums and requires libgmp, and if the platform lacks libgmp 
the GCC build process documents a procedure for you to download the GMP sources, 
build a libgmp of your own, and link to that. GCC's 'configure' program has a 
--with-gmp=DIR option that lets you tell the build procedure where libgmp is 
installed if it is neither supplied by your system nor built from sources in the 
way that GCC recommends. This --with-gmp=DIR option doesn't follow the GNU 
coding standards, which say "Do not use a @samp{--with} option to specify the 
file name to use to find certain files."

I doubt whether this is an exhaustive survey, but it should give you a feel for 
some of the confusion in this area.

Re: Merging bignum to master

[Stefan Monnier]

> XFIXNUMFWD might not be pretty, but it does convey the idea that this is
> code that only understands fixnums (the same as pre-bignum emacs), and
> will need careful inspection before modifying it to support bignums.

IIRC, the forwarding names are based on the C names (BOOLFWD, INTFWD,
OBJFWD), so I don't think "bignum" would make much sense.


        Stefan

Re: Merging bignum to master

[Stefan Monnier]

> Why would we need both?  Given --enable-bignums, which seems

We don't have (and don't want to have) "--enable-bignums".
Bignums are simply always enabled; the only question is whether they're
provided by libgmp or by our copy of the fallback mini-gmp.


        Stefan

Re: Merging bignum to master

[Eli Zaretskii]

> From: "Basil L. Contovounesios" <contovob@tcd.ie>
> Date: Sun, 12 Aug 2018 00:28:02 +0300
> Cc: emacs-devel@gnu.org
> 
> There's also a missing full stop in `(elisp) Integer Basics':

Thanks, fixed.

Re: Merging bignum to master

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 344 bytes --]

Andy Moreton wrote:

> Tom and Basil, please try the following patch for expt.
> I have given it some light sanity testing on Windows 64bit.

Thanks, I wrote up some test cases for that and found by inspection a few 
problems having to do with XFIXNUM returning a value greater than ULONG_MAX, 
that sort of thing, and installed the attached.


[-- Attachment #2: 0001-Add-bignum-support-to-expt.patch --]
[-- Type: text/x-patch, Size: 4035 bytes --]

From 47b7a5bd492e92dda928843e28a707b9682cb32f Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sun, 19 Aug 2018 01:22:08 -0700
Subject: [PATCH] Add bignum support to expt

Problem and initial solution reported by Andy Moreton in:
https://lists.gnu.org/r/emacs-devel/2018-08/msg00503.html
* doc/lispref/numbers.texi (Math Functions): expt integer
overflow no longer causes truncation; it now signals an error
since bignum overflow is a big deal.
* src/floatfns.c (Fexpt): Support bignum arguments.
* test/src/floatfns-tests.el (bignum-expt): New test.
---
 doc/lispref/numbers.texi   |  2 +-
 src/floatfns.c             | 47 ++++++++++++++++++++++----------------
 test/src/floatfns-tests.el |  9 ++++++++
 3 files changed, 37 insertions(+), 21 deletions(-)

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 74a313e2e1..209e9f139a 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -1185,7 +1185,7 @@ Math Functions
 @defun expt x y
 This function returns @var{x} raised to power @var{y}.  If both
 arguments are integers and @var{y} is nonnegative, the result is an
-integer; in this case, overflow causes truncation, so watch out.
+integer; in this case, overflow signals an error, so watch out.
 If @var{x} is a finite negative number and @var{y} is a finite
 non-integer, @code{expt} returns a NaN.
 @end defun
diff --git a/src/floatfns.c b/src/floatfns.c
index 713d42694f..54d068c29e 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -204,29 +204,36 @@ DEFUN ("expt", Fexpt, Sexpt, 2, 2, 0,
        doc: /* Return the exponential ARG1 ** ARG2.  */)
   (Lisp_Object arg1, Lisp_Object arg2)
 {
-  CHECK_FIXNUM_OR_FLOAT (arg1);
-  CHECK_FIXNUM_OR_FLOAT (arg2);
-  if (FIXNUMP (arg1)     /* common lisp spec */
-      && FIXNUMP (arg2)   /* don't promote, if both are ints, and */
-      && XFIXNUM (arg2) >= 0) /* we are sure the result is not fractional */
-    {				/* this can be improved by pre-calculating */
-      EMACS_INT y;		/* some binary powers of x then accumulating */
-      EMACS_UINT acc, x;  /* Unsigned so that overflow is well defined.  */
-      Lisp_Object val;
-
-      x = XFIXNUM (arg1);
-      y = XFIXNUM (arg2);
-      acc = (y & 1 ? x : 1);
-
-      while ((y >>= 1) != 0)
+  CHECK_NUMBER (arg1);
+  CHECK_NUMBER (arg2);
+
+  /* Common Lisp spec: don't promote if both are integers, and if the
+     result is not fractional.  */
+  if (INTEGERP (arg1) && NATNUMP (arg2))
+    {
+      unsigned long exp;
+      if (RANGED_FIXNUMP (0, arg2, ULONG_MAX))
+	exp = XFIXNUM (arg2);
+      else if (MOST_POSITIVE_FIXNUM < ULONG_MAX && BIGNUMP (arg2)
+	       && mpz_fits_ulong_p (XBIGNUM (arg2)->value))
+	exp = mpz_get_ui (XBIGNUM (arg2)->value);
+      else
+	xsignal3 (Qrange_error, build_string ("expt"), arg1, arg2);
+
+      mpz_t val;
+      mpz_init (val);
+      if (FIXNUMP (arg1))
 	{
-	  x *= x;
-	  if (y & 1)
-	    acc *= x;
+	  mpz_set_intmax (val, XFIXNUM (arg1));
+	  mpz_pow_ui (val, val, exp);
 	}
-      XSETINT (val, acc);
-      return val;
+      else
+	mpz_pow_ui (val, XBIGNUM (arg1)->value, exp);
+      Lisp_Object res = make_number (val);
+      mpz_clear (val);
+      return res;
     }
+
   return make_float (pow (XFLOATINT (arg1), XFLOATINT (arg2)));
 }
 
diff --git a/test/src/floatfns-tests.el b/test/src/floatfns-tests.el
index 43a2e27829..e4caaa1e49 100644
--- a/test/src/floatfns-tests.el
+++ b/test/src/floatfns-tests.el
@@ -42,6 +42,15 @@
   (should (= most-positive-fixnum
              (- (abs most-negative-fixnum) 1))))
 
+(ert-deftest bignum-expt ()
+  (dolist (n (list most-positive-fixnum (1+ most-positive-fixnum)
+                   most-negative-fixnum (1- most-negative-fixnum)
+                   -2 -1 0 1 2))
+    (should (= (expt n 0) 1))
+    (should (= (expt n 1) n))
+    (should (= (expt n 2) (* n n)))
+    (should (= (expt n 3) (* n n n)))))
+
 (ert-deftest bignum-logb ()
   (should (= (+ (logb most-positive-fixnum) 1)
              (logb (+ most-positive-fixnum 1)))))
-- 
2.17.1

Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Karl Fogel]

On 'master' as of commit ecd7a94077, if you do this:

  (setq mark-ring-max (1+ most-positive-fixnum))

then any command that calls `push-mark' will raise an error:

  Wrong type argument: fixnump, 2305843009213693952

(Lots of common commands do, obviously: `beginning-of-buffer', `yank', etc.)

The root cause is in `nthcdr', which now requires a fixnum for its first argument, although this requirement is not documented:

  DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
         doc: /* Take cdr N times on LIST, return the result.  */)
    (Lisp_Object n, Lisp_Object list)
  {
    CHECK_FIXNUM (n);
    [...]
  }

Should we document this?  I haven't followed the fixnum thread(s) carefully -- has the issue of documenting fixnum requirements has already been raised and settled?

My proposal would be to at least document it for `nthcdr', so that anyone who traces down the documentation stack down from this backtrace can see what happened without having to look at the C source code itself.  I don't know how many other primitives are affected, but `nthcdr' seems like a major one.  However, if this has already been discussed, and we've decided that fixnum is a reasonable requirement for many functions, and does not need to be documented specially, then that's fine.  (As to why I was setting `mark-ring-max' so high as to run into this issue, that's a long story and not relevant here :-) .)

Best regards,
-Karl

Paul Eggert <eggert@cs.ucla.edu> writes:
>Pip Cet wrote:
>> Is it intentional that int-forwarded variables are still limited to
>> the fixnum range? In any case, we probably didn't want to rename
>> XINTFWD to XFIXNUMFWD...
>
>I think some C code does assume fixnum ranges for these variables, and
>would have to be inspected. Presumably we'd go to either intmax_t
>range or Emacs integers (fixnums or bignums), and that might need to
>be thought through in a case-by-case basis. In the meantime XFIXNUMFWD
>is probably a good name since that's effectively what the code does
>now.

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Paul Eggert]

Karl Fogel wrote:
> My proposal would be to at least document it for `nthcdr'

It would be better to fix nthcdr so that it works on bignums, and similarly for 
other functions that are currently limited to fixnums. I'd rather work on this 
than on going through all the doc strings and carefully consider whether they 
should say "fixnum" rather than "integer".

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Eli Zaretskii]

> From: Karl Fogel <kfogel@red-bean.com>
> Date: Mon, 20 Aug 2018 11:28:45 -0500
> Cc: tom@tromey.com, Pip Cet <pipcet@gmail.com>, emacs-devel@gnu.org
> 
> On 'master' as of commit ecd7a94077, if you do this:
> 
>   (setq mark-ring-max (1+ most-positive-fixnum))
> 
> then any command that calls `push-mark' will raise an error:
> 
>   Wrong type argument: fixnump, 2305843009213693952
> 
> (Lots of common commands do, obviously: `beginning-of-buffer', `yank', etc.)
> 
> The root cause is in `nthcdr', which now requires a fixnum for its first argument, although this requirement is not documented:
> 
>   DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
>          doc: /* Take cdr N times on LIST, return the result.  */)
>     (Lisp_Object n, Lisp_Object list)
>   {
>     CHECK_FIXNUM (n);
>     [...]
>   }
> 
> Should we document this?

Yes, I think so.

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Mon, 20 Aug 2018 09:54:21 -0700
> Cc: tom@tromey.com, Pip Cet <pipcet@gmail.com>, emacs-devel@gnu.org
> 
> Karl Fogel wrote:
> > My proposal would be to at least document it for `nthcdr'
> 
> It would be better to fix nthcdr so that it works on bignums

??? How can you make it "work" on bignums, when the size of data
structures is fundamentally limited by the architectural constants
like SIZE_T_MAX and PTRDIFF_MAX?

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 433 bytes --]

Paul Eggert wrote:
> Karl Fogel wrote:
>> My proposal would be to at least document it for `nthcdr'
> 
> It would be better to fix nthcdr so that it works on bignums

... and I did that by installing the attached patch.

Thanks for reporting the problem. It's helpful to see which functions should 
have higher priority for fixing these sorts of glitches. If you're bitten by 
similar glitches in other functions please let us know.

[-- Attachment #2: 0001-nthcdr-now-works-with-bignums.patch --]
[-- Type: text/x-patch, Size: 1115 bytes --]

From 21397837eaf0801e7b1cd4155a811a939a7667de Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 20 Aug 2018 10:24:19 -0700
Subject: [PATCH] nthcdr now works with bignums

Problem reported by Karl Fogel in:
https://lists.gnu.org/r/emacs-devel/2018-08/msg00671.html
* src/fns.c (Fnthcdr): Support bignum counts.
---
 src/fns.c | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index a11de1b082..aeb9308d22 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1402,9 +1402,20 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
        doc: /* Take cdr N times on LIST, return the result.  */)
   (Lisp_Object n, Lisp_Object list)
 {
-  CHECK_FIXNUM (n);
+  CHECK_INTEGER (n);
   Lisp_Object tail = list;
-  for (EMACS_INT num = XFIXNUM (n); 0 < num; num--)
+
+  EMACS_INT num;
+  if (FIXNUMP (n))
+    num = XFIXNUM (n);
+  else
+    {
+      num = mpz_sgn (XBIGNUM (n)->value);
+      if (0 < num)
+	num = EMACS_INT_MAX;  /* LIST cannot possibly be this long.  */
+    }
+
+  for (; 0 < num; num--)
     {
       if (! CONSP (tail))
 	{
-- 
2.17.1

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Mon, 20 Aug 2018 10:27:34 -0700
> Cc: tom@tromey.com, Pip Cet <pipcet@gmail.com>, emacs-devel@gnu.org
> 
> +  if (FIXNUMP (n))
> +    num = XFIXNUM (n);
> +  else
> +    {
> +      num = mpz_sgn (XBIGNUM (n)->value);
> +      if (0 < num)
> +	num = EMACS_INT_MAX;  /* LIST cannot possibly be this long.  */

So we now silently replace the argument with another, smaller value,
and then go ahead as if business as usual?  Is that a good,
user-friendly behavior?

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Pip Cet]

On Mon, Aug 20, 2018 at 6:01 PM Eli Zaretskii <eliz@gnu.org> wrote:
> > From: Paul Eggert <eggert@cs.ucla.edu>
> > Date: Mon, 20 Aug 2018 10:27:34 -0700
> > Cc: tom@tromey.com, Pip Cet <pipcet@gmail.com>, emacs-devel@gnu.org
> >
> > +  if (FIXNUMP (n))
> > +    num = XFIXNUM (n);
> > +  else
> > +    {
> > +      num = mpz_sgn (XBIGNUM (n)->value);
> > +      if (0 < num)
> > +     num = EMACS_INT_MAX;  /* LIST cannot possibly be this long.  */
>
> So we now silently replace the argument with another, smaller value,
> and then go ahead as if business as usual?  Is that a good,
> user-friendly behavior?

It's certainly incorrect for circular lists.

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 958 bytes --]

Pip Cet wrote:
>> So we now silently replace the argument with another, smaller value,
>> and then go ahead as if business as usual?  Is that a good,
>> user-friendly behavior?
> It's certainly incorrect for circular lists.

Yes, sorry, I forgot the circular case. Fixed by installing the attached patch.

This patch improves circular-list nthcdr performance for fixnums too. For 
example, on my Fedora 28 x86-64 platform (AMD Phenom II X4 910e, circa 2010) the 
third line of the following benchmark runs about 8 million times faster:

(setq bench-circular (list 1 2 3 4 5 6))
(setcdr (nthcdr 5 bench-circular) bench-circular)
(nthcdr 536870911 bench-circular)

Normally I wouldn't bother with this sort of performance improvement (I mean, 
how often to people write code that deliberately goes around in circles? :-), 
but nthcdr is used so often that it seemed worth doing. Plus it was fun to fix 
this mostly by using machine arithmetic rather than GMP.

[-- Attachment #2: 0001-Speed-up-nthcdr-N-L-when-L-is-circular.patch --]
[-- Type: text/x-patch, Size: 4225 bytes --]

From eb83344fc7c08ec08b51e7700f1ac2632afa462c Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Mon, 20 Aug 2018 15:52:29 -0700
Subject: [PATCH] Speed up (nthcdr N L) when L is circular

Also, fix bug when N is a positive bignum, a problem reported
by Eli Zaretskii and Pip Cet in:
https://lists.gnu.org/r/emacs-devel/2018-08/msg00690.html
* src/fns.c (Fnthcdr): If a cycle is found, reduce the count
modulo the cycle length before continuing.  This reduces the
worst-case cost of (nthcdr N L) from N to min(N, C) where C is
the number of distinct cdrs of L.  Reducing modulo the cycle
length also allows us to do arithmetic with machine words
instead of with GMP.
* test/src/fns-tests.el (test-nthcdr-circular): New test.
---
 src/fns.c             | 58 ++++++++++++++++++++++++++++++++++++++-----
 test/src/fns-tests.el | 16 ++++++++++++
 2 files changed, 68 insertions(+), 6 deletions(-)

diff --git a/src/fns.c b/src/fns.c
index aeb9308d22..8cff6b1b6c 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1403,7 +1403,12 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
   (Lisp_Object n, Lisp_Object list)
 {
   CHECK_INTEGER (n);
-  Lisp_Object tail = list;
+
+  /* A huge but in-range EMACS_INT that can be substituted for a
+     positive bignum while counting down.  It does not introduce
+     miscounts because a list or cycle cannot possibly be this long,
+     and any counting error is fixed up later.  */
+  EMACS_INT large_num = EMACS_INT_MAX;
 
   EMACS_INT num;
   if (FIXNUMP (n))
@@ -1412,16 +1417,57 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
     {
       num = mpz_sgn (XBIGNUM (n)->value);
       if (0 < num)
-	num = EMACS_INT_MAX;  /* LIST cannot possibly be this long.  */
+	num = large_num;
     }
 
-  for (; 0 < num; num--)
+  EMACS_INT tortoise_num = num;
+  Lisp_Object tail = list, saved_tail = tail;
+  FOR_EACH_TAIL_SAFE (tail)
     {
-      if (! CONSP (tail))
+      if (num <= 0)
+	return tail;
+      if (tail == li.tortoise)
+	tortoise_num = num;
+      saved_tail = XCDR (tail);
+      num--;
+      rarely_quit (num);
+    }
+
+  tail = saved_tail;
+  if (! CONSP (tail))
+    {
+      CHECK_LIST_END (tail, list);
+      return Qnil;
+    }
+
+  /* TAIL is part of a cycle.  Reduce NUM modulo the cycle length to
+     avoid going around this cycle repeatedly.  */
+  intptr_t cycle_length = tortoise_num - num;
+  if (! FIXNUMP (n))
+    {
+      /* Undo any error introduced when LARGE_NUM was substituted for
+	 N, by adding N - LARGE_NUM to NUM, using arithmetic modulo
+	 CYCLE_LENGTH.  */
+      mpz_t z; /* N mod CYCLE_LENGTH.  */
+      mpz_init (z);
+      if (cycle_length <= ULONG_MAX)
+	num += mpz_mod_ui (z, XBIGNUM (n)->value, cycle_length);
+      else
 	{
-	  CHECK_LIST_END (tail, list);
-	  return Qnil;
+	  mpz_set_intmax (z, cycle_length);
+	  mpz_mod (z, XBIGNUM (n)->value, z);
+	  intptr_t iz;
+	  mpz_export (&iz, NULL, -1, sizeof iz, 0, 0, z);
+	  num += iz;
 	}
+      mpz_clear (z);
+      num += cycle_length - large_num % cycle_length;
+    }
+  num %= cycle_length;
+
+  /* One last time through the cycle.  */
+  for (; 0 < num; num--)
+    {
       tail = XCDR (tail);
       rarely_quit (num);
     }
diff --git a/test/src/fns-tests.el b/test/src/fns-tests.el
index f722ed6333..92dc18fa03 100644
--- a/test/src/fns-tests.el
+++ b/test/src/fns-tests.el
@@ -624,4 +624,20 @@ dot2
         (should (eq (gethash b2 hash)
                     (funcall test b1 b2)))))))
 
+(ert-deftest test-nthcdr-circular ()
+  (dolist (len '(1 2 5 37 120 997 1024))
+    (let ((cycle (make-list len nil)))
+      (setcdr (last cycle) cycle)
+      (dolist (n (list (1- most-negative-fixnum) most-negative-fixnum
+                       -1 0 1
+                       (1- len) len (1+ len)
+                       most-positive-fixnum (1+ most-positive-fixnum)
+                       (* 2 most-positive-fixnum)
+                       (* most-positive-fixnum most-positive-fixnum)
+                       (ash 1 12345)))
+        (let ((a (nthcdr n cycle))
+              (b (if (<= n 0) cycle (nthcdr (mod n len) cycle))))
+          (should (equal (list (eq a b) n len)
+                         (list t n len))))))))
+
 (provide 'fns-tests)
-- 
2.17.1

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > It would be better to fix nthcdr so that it works on bignums, and similarly for

I think that is wasted effort.  If n is a bignum, how many years would
it take for nthcdr to return?

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Paul Eggert]

Richard Stallman wrote:
> If n is a bignum, how many years would it take for nthcdr to return?

It'd be a tiny fraction of a year. Nanoseconds would be a better unit of 
measure. I just timed the following test case with n == 2**61 (a bignum) on a 
2-element circular list:

(setq circular (list 1 2))
(setcdr (last circular) circular)
(setq n (ash 1 61))
(nthcdr n bench-circular)

On my circa-2010 64-bit desktop with Emacs master, the nthcdr call consumes 160 
nanoseconds. (You asked "how many years": it's about 5 femtoyears. :-)

Re: Some vars now limited to fixnum size.

[Tom Tromey]

>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:

Paul> Paul Eggert wrote:
>> Karl Fogel wrote:
>>> My proposal would be to at least document it for `nthcdr'
>> 
>> It would be better to fix nthcdr so that it works on bignums

Paul> ... and I did that by installing the attached patch.

I think the bytecode interpreter needs a similar update.

Tom

Re: Some vars now limited to fixnum size.

[Andy Moreton]

On Tue 21 Aug 2018, Tom Tromey wrote:

>>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:
>
> Paul> Paul Eggert wrote:
>>> Karl Fogel wrote:
>>>> My proposal would be to at least document it for `nthcdr'
>>> 
>>> It would be better to fix nthcdr so that it works on bignums
>
> Paul> ... and I did that by installing the attached patch.
>
> I think the bytecode interpreter needs a similar update.

Yes - see bugs 32476, 32477, 32485 and 32486.

    AndyM

Re: Some vars now limited to fixnum size.

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 545 bytes --]

Tom Tromey wrote:
>>> It would be better to fix nthcdr so that it works on bignums
> Paul> ... and I did that by installing the attached patch.
> 
> I think the bytecode interpreter needs a similar update.

I don't see any problems with the Bnthcdr implementation in the bytecode 
interpreter, as it simply calls Fnthcdr.

Perhaps you are thinking of some other bignum problems in the bytecode 
interpreter? I just now took a quick look and found some problems, and fixed the 
ones that I found by installing the attached patch. Did I miss any?

[-- Attachment #2: 0001-Fix-bignum-bugs-with-nth-elt.patch --]
[-- Type: text/x-patch, Size: 3898 bytes --]

From 1244713462569240bd25f0e4bbb3a2af9ac3c52d Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 21 Aug 2018 11:40:23 -0700
Subject: [PATCH] Fix bignum bugs with nth, elt, =

* src/bytecode.c (exec_byte_code): Support bignums
when implementing nth, elt, and =.
* src/lisp.h (SMALL_LIST_LEN_MAX): New constant.
* src/fns.c (Fnthcdr): Use it.
(Felt): Do not reject bignum indexes.
---
 src/bytecode.c | 39 +++++++++++++--------------------------
 src/fns.c      |  5 ++---
 src/lisp.h     |  5 +++++
 3 files changed, 20 insertions(+), 29 deletions(-)

diff --git a/src/bytecode.c b/src/bytecode.c
index b27fa7c5c6..17457fc574 100644
--- a/src/bytecode.c
+++ b/src/bytecode.c
@@ -832,13 +832,14 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object vector, Lisp_Object maxdepth,
 	CASE (Bnth):
 	  {
 	    Lisp_Object v2 = POP, v1 = TOP;
-	    CHECK_FIXNUM (v1);
-	    for (EMACS_INT n = XFIXNUM (v1); 0 < n && CONSP (v2); n--)
+	    if (RANGED_FIXNUMP (0, v1, SMALL_LIST_LEN_MAX))
 	      {
-		v2 = XCDR (v2);
-		rarely_quit (n);
+		for (EMACS_INT n = XFIXNUM (v1); 0 < n && CONSP (v2); n--)
+		  v2 = XCDR (v2);
+		TOP = CAR (v2);
 	      }
-	    TOP = CAR (v2);
+	    else
+	      TOP = Fnth (v1, v2);
 	    NEXT;
 	  }
 
@@ -985,15 +986,8 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object vector, Lisp_Object maxdepth,
 
 	CASE (Beqlsign):
 	  {
-	    Lisp_Object v2 = POP, v1 = TOP;
-	    if (FLOATP (v1) || FLOATP (v2))
-	      TOP = arithcompare (v1, v2, ARITH_EQUAL);
-	    else
-	      {
-		CHECK_FIXNUM_OR_FLOAT_COERCE_MARKER (v1);
-		CHECK_FIXNUM_OR_FLOAT_COERCE_MARKER (v2);
-		TOP = EQ (v1, v2) ? Qt : Qnil;
-	      }
+	    Lisp_Object v1 = POP;
+	    TOP = arithcompare (TOP, v1, ARITH_EQUAL);
 	    NEXT;
 	  }
 
@@ -1264,23 +1258,16 @@ exec_byte_code (Lisp_Object bytestr, Lisp_Object vector, Lisp_Object maxdepth,
 
 	CASE (Belt):
 	  {
-	    if (CONSP (TOP))
+	    Lisp_Object v2 = POP, v1 = TOP;
+	    if (CONSP (v1) && RANGED_FIXNUMP (0, v2, SMALL_LIST_LEN_MAX))
 	      {
-		/* Exchange args and then do nth.  */
-		Lisp_Object v2 = POP, v1 = TOP;
-		CHECK_FIXNUM (v2);
+		/* Like the fast case for Bnth, but with args reversed.  */
 		for (EMACS_INT n = XFIXNUM (v2); 0 < n && CONSP (v1); n--)
-		  {
-		    v1 = XCDR (v1);
-		    rarely_quit (n);
-		  }
+		  v1 = XCDR (v1);
 		TOP = CAR (v1);
 	      }
 	    else
-	      {
-		Lisp_Object v1 = POP;
-		TOP = Felt (TOP, v1);
-	      }
+	      TOP = Felt (v1, v2);
 	    NEXT;
 	  }
 
diff --git a/src/fns.c b/src/fns.c
index 9d681017c1..b368ffd58f 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -1418,7 +1418,7 @@ DEFUN ("nthcdr", Fnthcdr, Snthcdr, 2, 2, 0,
       num = XFIXNUM (n);
 
       /* Speed up small lists by omitting circularity and quit checking.  */
-      if (num < 128)
+      if (num <= SMALL_LIST_LEN_MAX)
 	{
 	  for (; 0 < num; num--, tail = XCDR (tail))
 	    if (! CONSP (tail))
@@ -1503,9 +1503,8 @@ N counts from zero.  If LIST is not that long, nil is returned.  */)
 
 DEFUN ("elt", Felt, Selt, 2, 2, 0,
        doc: /* Return element of SEQUENCE at index N.  */)
-  (register Lisp_Object sequence, Lisp_Object n)
+  (Lisp_Object sequence, Lisp_Object n)
 {
-  CHECK_FIXNUM (n);
   if (CONSP (sequence) || NILP (sequence))
     return Fcar (Fnthcdr (n, sequence));
 
diff --git a/src/lisp.h b/src/lisp.h
index 8f48a33484..c5593b2100 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4694,6 +4694,11 @@ enum
 	 Lisp_String))							\
      : make_unibyte_string (str, len))
 
+/* The maximum length of "small" lists, as a heuristic.  These lists
+   are so short that code need not check for cycles or quits while
+   traversing.  */
+enum { SMALL_LIST_LEN_MAX = 127 };
+
 /* Loop over conses of the list TAIL, signaling if a cycle is found,
    and possibly quitting after each loop iteration.  In the loop body,
    set TAIL to the current cons.  If the loop exits normally,
-- 
2.17.1

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

  > (setq circular (list 1 2))
  > (setcdr (last circular) circular)
  > (setq n (ash 1 61))
  > (nthcdr n bench-circular)

  > On my circa-2010 64-bit desktop with Emacs master, the nthcdr call consumes 160

How does it do the job so fast?  Does it calculate the length of the
list, then divide?

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Some vars now limited to fixnum size. (Was: Merging bignum to master)

[Paul Eggert]

Richard Stallman wrote:
> How does it do the job so fast?  Does it calculate the length of the
> list, then divide?

Yes, it computes modulo the list cycle length.

Re: Some vars now limited to fixnum size.

[Tom Tromey]

>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:

>> I think the bytecode interpreter needs a similar update.

Paul> I don't see any problems with the Bnthcdr implementation in the
Paul> bytecode interpreter, as it simply calls Fnthcdr.

Paul> Perhaps you are thinking of some other bignum problems in the bytecode
Paul> interpreter? I just now took a quick look and found some problems, and
Paul> fixed the ones that I found by installing the attached patch. Did I
Paul> miss any?

Sorry, I thought you were looking at nth, not nthcdr.  I'm not thinking
super clearly lately, one fun effect of my illness.

The Bnth case in the bytecode interpreter only worked on fixnums but I
see you fixed that in your patch -- thanks.  I'd noticed Beqlsign being
wrong yesterday, too, but I see you fixed that as well :)

Tom