Bignum speedup patch causes crash at startup

Bignum speedup patch causes crash at startup

[Andy Moreton]

Hi,

The recent changes in commit fe042e9d ("Speed up (+ 2 2) by a factor of
10") cause an immediate crash in 64bit emacs on Windows.

A patch that is this invasive should have been posted for comment and
review before it was committed. The patch contains both refactorings to
move code around and new code changes. It would have been better to
split this into more than one patch, to enable easier bisection of
problems.

Running master under GDB shows:

(gdb) run -Q
Starting program: C:\emacs\git\emacs\master\build\mingw64-x86_64\src\emacs.exe -Q
[New Thread 13388.0x29bc]
[New Thread 13388.0x24b4]
[New Thread 13388.0x2cd0]
[New Thread 13388.0x12e8]
[New Thread 13388.0x8f8]
[Thread 13388.0x2cd0 exited with code 0]
[New Thread 13388.0x36cc]

Thread 1 received signal SIGSEGV, Segmentation fault.
0x000000006acd4efb in ?? () from C:\msys64\mingw64\bin\libgmp-10.dll
(gdb) bt
#0  0x000000006acd4efb in ?? () from C:\msys64\mingw64\bin\libgmp-10.dll
#1  0x000000040018bcca in mpz_set_intmax (v=<optimized out>, result=<optimized out>) at C:/emacs/git/emacs/master/src/bignum.h:66
#2  bignum_integer (i=<optimized out>, tmp=<optimized out>) at C:/emacs/git/emacs/master/src/bignum.h:79
#3  rounding_driver (arg=make_number(2), divisor=<optimized out>, double_round=<optimized out>, int_divide=0x6acc9560, name=name@entry=0x40067f71f <callint_argfuns+3359> "ceiling") at C:/emacs/git/emacs/master/src/floatfns.c:362
#4  0x000000040018be79 in Fceiling (arg=<optimized out>, divisor=<optimized out>) at C:/emacs/git/emacs/master/src/floatfns.c:446
#5  0x0000000400186a35 in funcall_subr (subr=0x400653d20 <Sceiling>, numargs=numargs@entry=0x2, args=args@entry=0xbfcc00) at C:/emacs/git/emacs/master/src/eval.c:2899
#6  0x000000040018485e in Ffuncall (nargs=0x3, args=args@entry=0xbfcbf8) at C:/emacs/git/emacs/master/src/eval.c:2822
#7  0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(1028), nargs=nargs@entry=0x4, args=<optimized out>, args@entry=0xbfcfc0) at C:/emacs/git/emacs/master/src/bytecode.c:632
#8  0x00000004001882ce in funcall_lambda (fun=XIL(0x4002dd295), nargs=nargs@entry=0x4, arg_vector=arg_vector@entry=0xbfcfc0) at C:/emacs/git/emacs/master/src/lisp.h:1707
#9  0x000000040018495f in Ffuncall (nargs=0x5, args=args@entry=0xbfcfb8) at C:/emacs/git/emacs/master/src/eval.c:2824
#10 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(1024), nargs=nargs@entry=0x4, args=<optimized out>, args@entry=0xbfd200) at C:/emacs/git/emacs/master/src/bytecode.c:632
#11 0x00000004001882ce in funcall_lambda (fun=XIL(0x4002dd195), nargs=nargs@entry=0x4, arg_vector=arg_vector@entry=0xbfd200) at C:/emacs/git/emacs/master/src/lisp.h:1707
#12 0x000000040018495f in Ffuncall (nargs=0x5, args=args@entry=0xbfd1f8) at C:/emacs/git/emacs/master/src/eval.c:2824
#13 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(1024), nargs=nargs@entry=0x4, args=<optimized out>, args@entry=0xbfd438) at C:/emacs/git/emacs/master/src/bytecode.c:632
#14 0x00000004001882ce in funcall_lambda (fun=XIL(0x4002dd7c5), nargs=nargs@entry=0x4, arg_vector=arg_vector@entry=0xbfd438) at C:/emacs/git/emacs/master/src/lisp.h:1707
#15 0x000000040018495f in Ffuncall (nargs=nargs@entry=0x5, args=args@entry=0xbfd430) at C:/emacs/git/emacs/master/src/eval.c:2824
#16 0x00000004001895d5 in call4 (fn=<optimized out>, arg1=arg1@entry=XIL(0x4007800c5), arg2=arg2@entry=XIL(0xf228), arg3=arg3@entry=XIL(0xf228), arg4=arg4@entry=XIL(0xf228)) at C:/emacs/git/emacs/master/src/eval.c:2698
#17 0x000000040001031b in frame_windows_min_size (frame=frame@entry=XIL(0x4007800c5), horizontal=horizontal@entry=XIL(0xf228), ignore=XIL(0xf228), pixelwise=pixelwise@entry=XIL(0xf228)) at C:/emacs/git/emacs/master/src/lisp.h:932
#18 0x0000000400011373 in adjust_frame_size (f=0x4007800c0 <dumped_data+207104>, new_width=<optimized out>, new_height=<optimized out>, inhibit=inhibit@entry=0x5, pretend=0x0, parameter=parameter@entry=XIL(0x3f00)) at C:/emacs/git/emacs/master/src/lisp.h:932
#19 0x0000000400004b19 in change_frame_size_1 (f=<optimized out>, new_width=<optimized out>, new_height=<optimized out>, pretend=<optimized out>, delay=<optimized out>, safe=<optimized out>, pixelwise=<optimized out>) at C:/emacs/git/emacs/master/src/lisp.h:932
#20 0x000000040000ce6b in change_frame_size (f=0x400714c50 <mpz+16>, new_width=0x1, new_height=0x27ee60, pretend=0x60, pretend@entry=0x0, delay=delay@entry=0x0, safe=safe@entry=0x0, pixelwise=0x0) at C:/emacs/git/emacs/master/src/dispnew.c:5583
#21 0x000000040000cf83 in do_pending_window_change (safe=safe@entry=0x0) at C:/emacs/git/emacs/master/src/dispnew.c:5509
#22 0x0000000400017eb0 in x_set_font (f=0x400baea20 <dumped_data+4592224>, arg=XIL(0x518bea4), oldval=<optimized out>) at C:/emacs/git/emacs/master/src/frame.c:4341
#23 0x00000004000166b4 in x_set_frame_parameters (f=<optimized out>, f@entry=0x400baea20 <dumped_data+4592224>, alist=<optimized out>, alist@entry=XIL(0xbfd813)) at C:/emacs/git/emacs/master/src/lisp.h:1035
#24 0x00000004000199d5 in x_default_parameter (f=0x400baea20 <dumped_data+4592224>, alist=<optimized out>, prop=XIL(0x6ee8), deflt=XIL(0x400bb2a25), xprop=0x4006933d3 <illuminant_d65+5507> "font", xclass=0x4006933d8 <illuminant_d65+5512> "Font", type=RES_TYPE_STRING) at C:/emacs/git/emacs/master/src/frame.c:5090
#25 0x000000040020c412 in x_default_font_parameter (f=f@entry=0x400baea20 <dumped_data+4592224>, parms=parms@entry=XIL(0x400808873)) at C:/emacs/git/emacs/master/src/lisp.h:932
#26 0x0000000400216c6f in Fx_create_frame (parameters=XIL(0x400808873)) at C:/emacs/git/emacs/master/src/w32fns.c:5845
#27 0x0000000400186a29 in funcall_subr (subr=0x400659d40 <Sx_create_frame>, numargs=numargs@entry=0x1, args=args@entry=0xbfdb18) at C:/emacs/git/emacs/master/src/eval.c:2897
#28 0x000000040018485e in Ffuncall (nargs=0x2, args=args@entry=0xbfdb10) at C:/emacs/git/emacs/master/src/eval.c:2822
#29 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(256), nargs=nargs@entry=0x1, args=<optimized out>, args@entry=0xbfdda8) at C:/emacs/git/emacs/master/src/bytecode.c:632
#30 0x00000004001882ce in funcall_lambda (fun=XIL(0x40030acd5), nargs=nargs@entry=0x1, arg_vector=arg_vector@entry=0xbfdda8) at C:/emacs/git/emacs/master/src/lisp.h:1707
#31 0x000000040018495f in Ffuncall (nargs=0x2, args=args@entry=0xbfdda0) at C:/emacs/git/emacs/master/src/eval.c:2824
#32 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(257), nargs=nargs@entry=0x1, args=<optimized out>, args@entry=0xbfe148) at C:/emacs/git/emacs/master/src/bytecode.c:632
#33 0x00000004001882ce in funcall_lambda (fun=XIL(0x4009af115), nargs=nargs@entry=0x1, arg_vector=arg_vector@entry=0xbfe148) at C:/emacs/git/emacs/master/src/lisp.h:1707
#34 0x000000040018495f in Ffuncall (nargs=nargs@entry=0x2, args=args@entry=0xbfe140) at C:/emacs/git/emacs/master/src/eval.c:2824
#35 0x0000000400184cce in Fapply (nargs=0x2, args=0xbfe140) at C:/emacs/git/emacs/master/src/eval.c:2399
#36 0x00000004001869e0 in funcall_subr (subr=0x4006533e0 <Sapply>, numargs=numargs@entry=0x2, args=args@entry=0xbfe140) at C:/emacs/git/emacs/master/src/eval.c:2877
#37 0x000000040018485e in Ffuncall (nargs=0x3, args=args@entry=0xbfe138) at C:/emacs/git/emacs/master/src/eval.c:2822
#38 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(128), nargs=nargs@entry=0x1, args=<optimized out>, args@entry=0xbfe3e0) at C:/emacs/git/emacs/master/src/bytecode.c:632
#39 0x00000004001882ce in funcall_lambda (fun=XIL(0x400a3dc65), nargs=nargs@entry=0x1, arg_vector=arg_vector@entry=0xbfe3e0) at C:/emacs/git/emacs/master/src/lisp.h:1707
#40 0x000000040018495f in Ffuncall (nargs=0x2, args=args@entry=0xbfe3d8) at C:/emacs/git/emacs/master/src/eval.c:2824
#41 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(256), nargs=nargs@entry=0x1, args=<optimized out>, args@entry=0xbfe6e0) at C:/emacs/git/emacs/master/src/bytecode.c:632
#42 0x00000004001882ce in funcall_lambda (fun=XIL(0x400399b25), nargs=nargs@entry=0x1, arg_vector=arg_vector@entry=0xbfe6e0) at C:/emacs/git/emacs/master/src/lisp.h:1707
#43 0x000000040018495f in Ffuncall (nargs=0x2, args=args@entry=0xbfe6d8) at C:/emacs/git/emacs/master/src/eval.c:2824
#44 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(0), nargs=nargs@entry=0x0, args=<optimized out>, args@entry=0xbfe930) at C:/emacs/git/emacs/master/src/bytecode.c:632
#45 0x00000004001882ce in funcall_lambda (fun=XIL(0x400398f55), nargs=nargs@entry=0x0, arg_vector=arg_vector@entry=0xbfe930) at C:/emacs/git/emacs/master/src/lisp.h:1707
#46 0x000000040018495f in Ffuncall (nargs=0x1, args=args@entry=0xbfe928) at C:/emacs/git/emacs/master/src/eval.c:2824
#47 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(0), nargs=nargs@entry=0x0, args=<optimized out>, args@entry=0xbff1c8) at C:/emacs/git/emacs/master/src/bytecode.c:632
#48 0x00000004001882ce in funcall_lambda (fun=XIL(0x4003a21f5), nargs=nargs@entry=0x0, arg_vector=arg_vector@entry=0xbff1c8) at C:/emacs/git/emacs/master/src/lisp.h:1707
#49 0x000000040018495f in Ffuncall (nargs=0x1, args=args@entry=0xbff1c0) at C:/emacs/git/emacs/master/src/eval.c:2824
#50 0x00000004001ce74e in exec_byte_code (bytestr=<optimized out>, vector=<optimized out>, maxdepth=<optimized out>, args_template=args_template@entry=make_number(0), nargs=nargs@entry=0x0, args=<optimized out>, args@entry=0xbff550) at C:/emacs/git/emacs/master/src/bytecode.c:632
#51 0x00000004001882ce in funcall_lambda (fun=XIL(0x4003a11a5), fun@entry=XIL(0), nargs=nargs@entry=0x0, arg_vector=arg_vector@entry=0xbff550) at C:/emacs/git/emacs/master/src/lisp.h:1707
#52 0x000000040018756c in apply_lambda (fun=XIL(0), fun@entry=XIL(0x4003a11a5), args=<optimized out>, count=count@entry=0x4) at C:/emacs/git/emacs/master/src/eval.c:2959
#53 0x0000000400187dbf in eval_sub (form=form@entry=XIL(0x400909363)) at C:/emacs/git/emacs/master/src/eval.c:2332
#54 0x000000040018a4ed in Feval (form=XIL(0x400909363), lexical=lexical@entry=XIL(0)) at C:/emacs/git/emacs/master/src/eval.c:2107
#55 0x00000004000f01d8 in top_level_2 () at C:/emacs/git/emacs/master/src/lisp.h:932
#56 0x00000004001836b6 in internal_condition_case (bfun=bfun@entry=0x4000f01bc <top_level_2>, handlers=handlers@entry=XIL(0x5ef0), hfun=hfun@entry=0x4000f59e0 <cmd_error>) at C:/emacs/git/emacs/master/src/eval.c:1349
#57 0x00000004000f2814 in top_level_1 (ignore=<optimized out>) at C:/emacs/git/emacs/master/src/lisp.h:932
#58 0x00000004001835ee in internal_catch (tag=<optimized out>, func=func@entry=0x4000f27c8 <top_level_1>, arg=arg@entry=XIL(0)) at C:/emacs/git/emacs/master/src/eval.c:1114
#59 0x00000004000f4e55 in command_loop () at C:/emacs/git/emacs/master/src/lisp.h:932
#60 0x0000000000000000 in ?? ()
Backtrace stopped: previous frame inner to this frame (corrupt stack?)

Lisp Backtrace:
"ceiling" (0xbfcc00)
"window--min-size-1" (0xbfcfc0)
"window-min-size" (0xbfd200)
"frame-windows-min-size" (0xbfd438)
"x-create-frame" (0xbfdb18)
"x-create-frame-with-faces" (0xbfdda8)
0x9af110 PVEC_COMPILED
"apply" (0xbfe140)
"frame-creation-function" (0xbfe3e0)
"make-frame" (0xbfe6e0)
"frame-initialize" (0xbfe930)
"command-line" (0xbff1c8)
"normal-top-level" (0xbff550)

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Tue, 04 Sep 2018 15:21:11 +0100
> 
> The recent changes in commit fe042e9d ("Speed up (+ 2 2) by a factor of
> 10") cause an immediate crash in 64bit emacs on Windows.

Based on the backtrace I see here, crystal ball says that the new
function init_bignum_once is the problem: it is called during dumping,
before the call to mp_set_memory_functions, which tells GMP to use our
memory-allocation functions.  So GMP uses the "normal" malloc/free to
allocate the data, and then Emacs crashes when it tries to realloc
that after dumping.

I wonder how this was supposed to work on other platforms, since you
cannot generally assume that memory allocated by a function from some
malloc family can be safely freed/reallocated using a function from
another family.  One must use the same family.

Paul, why do we need to call init_bignum_once at dump time?

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> Date: Tue, 04 Sep 2018 18:10:30 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: emacs-devel@gnu.org
> 
> Paul, why do we need to call init_bignum_once at dump time?

And btw, why on earth this call:

  0x01231e45 in Fround (arg=make_number(9), divisor=make_number(1))

would need to use GMP??  It's due to this code:

      if (!FLOATP (arg) && !FLOATP (divisor))
	{
	  if (EQ (divisor, make_fixnum (0)))
	    xsignal0 (Qarith_error);
	  int_divide (mpz[0],
		      *bignum_integer (&mpz[0], arg),
		      *bignum_integer (&mpz[1], divisor));
	  return make_integer_mpz ();
	}

I don't understand why it prefers GMP calls to a simple double
division, when both arguments are fixnums.  What am I missing?

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

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

Andy Moreton wrote:

> The recent changes in commit fe042e9d ("Speed up (+ 2 2) by a factor of
> 10") cause an immediate crash in 64bit emacs on Windows.

Thanks for reporting it. Please try the attached patch, which I installed on master.

> A patch that is this invasive should have been posted for comment and
> review before it was committed.

My feeling was that it was limited to bignum calculations, a reasonably compact 
area conceptually where we don't have many reviewers, unfortunately. Also, my 
judgment was that the effort to split this patch into pieces would have been 
more trouble overall than it would have been worth. Obviously this is a judgment 
call.

I do regularly post for comment patches that I think might run into trouble on 
the MS-Windows side. I didn't think this one would cause trouble. Evidently I 
was wrong, sorry; these things happen.

[-- Attachment #2: 0001-Fix-bignum-initialization.patch --]
[-- Type: text/x-patch, Size: 3215 bytes --]

From 1d84e6523250ab6d14f40fba3922c56d7a40416f Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 4 Sep 2018 09:30:57 -0700
Subject: [PATCH] Fix bignum initialization

Problem reported by Andy Moreton in:
https://lists.gnu.org/r/emacs-devel/2018-09/msg00072.html
and crystal-ball diagnosis by Eli Zaretskii in:
https://lists.gnu.org/r/emacs-devel/2018-09/msg00075.html
* src/alloc.c (xrealloc_for_gmp, xfree_for_gmp): Move to bignum.c.
(init_alloc): Move bignum initialization to init_bignum.
* src/bignum.c (init_bignum): Rename from init_bignum_once.
All users changed.
* src/emacs.c (main): Call init_bignum after init_alloc,
instead of calling init_bignum_once after init_bignum.
---
 src/alloc.c  | 16 ----------------
 src/bignum.c | 18 +++++++++++++++++-
 src/bignum.h |  2 +-
 src/emacs.c  |  2 +-
 4 files changed, 19 insertions(+), 19 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 1eab82d1c2..28ca7804ee 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -7126,18 +7126,6 @@ range_error (void)
   xsignal0 (Qrange_error);
 }
 
-static void *
-xrealloc_for_gmp (void *ptr, size_t ignore, size_t size)
-{
-  return xrealloc (ptr, size);
-}
-
-static void
-xfree_for_gmp (void *ptr, size_t ignore)
-{
-  xfree (ptr);
-}
-
 /* Initialization.  */
 
 void
@@ -7171,10 +7159,6 @@ init_alloc_once (void)
 void
 init_alloc (void)
 {
-  eassert (mp_bits_per_limb == GMP_NUMB_BITS);
-  integer_width = 1 << 16;
-  mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
-
   Vgc_elapsed = make_float (0.0);
   gcs_done = 0;
 
diff --git a/src/bignum.c b/src/bignum.c
index 2ce7412d06..35894f5647 100644
--- a/src/bignum.c
+++ b/src/bignum.c
@@ -34,9 +34,25 @@ along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
 
 mpz_t mpz[4];
 
+static void *
+xrealloc_for_gmp (void *ptr, size_t ignore, size_t size)
+{
+  return xrealloc (ptr, size);
+}
+
+static void
+xfree_for_gmp (void *ptr, size_t ignore)
+{
+  xfree (ptr);
+}
+
 void
-init_bignum_once (void)
+init_bignum (void)
 {
+  eassert (mp_bits_per_limb == GMP_NUMB_BITS);
+  integer_width = 1 << 16;
+  mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
+
   for (int i = 0; i < ARRAYELTS (mpz); i++)
     mpz_init (mpz[i]);
 }
diff --git a/src/bignum.h b/src/bignum.h
index 07622a37af..0e38c615ee 100644
--- a/src/bignum.h
+++ b/src/bignum.h
@@ -43,7 +43,7 @@ struct Lisp_Bignum
 
 extern mpz_t mpz[4];
 
-extern void init_bignum_once (void);
+extern void init_bignum (void);
 extern Lisp_Object make_integer_mpz (void);
 extern void mpz_set_intmax_slow (mpz_t, intmax_t) ARG_NONNULL ((1));
 
diff --git a/src/emacs.c b/src/emacs.c
index 5b399eca64..b1c96d1828 100644
--- a/src/emacs.c
+++ b/src/emacs.c
@@ -1209,7 +1209,6 @@ Using an Emacs configured with --with-x-toolkit=lucid does not have this problem
   if (!initialized)
     {
       init_alloc_once ();
-      init_bignum_once ();
       init_threads_once ();
       init_obarray ();
       init_eval_once ();
@@ -1257,6 +1256,7 @@ Using an Emacs configured with --with-x-toolkit=lucid does not have this problem
     }
 
   init_alloc ();
+  init_bignum ();
   init_threads ();
 
   if (do_initial_setlocale)
-- 
2.17.1

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 4 Sep 2018 09:40:47 -0700
> 
> Andy Moreton wrote:
> 
> > The recent changes in commit fe042e9d ("Speed up (+ 2 2) by a factor of
> > 10") cause an immediate crash in 64bit emacs on Windows.
> 
> Thanks for reporting it. Please try the attached patch, which I installed on master.

It fixes the crash here, thanks.

Re: Bignum speedup patch causes crash at startup

[Andy Moreton]

On Tue 04 Sep 2018, Paul Eggert wrote:

> Andy Moreton wrote:
>
>> The recent changes in commit fe042e9d ("Speed up (+ 2 2) by a factor of
>> 10") cause an immediate crash in 64bit emacs on Windows.
>
> Thanks for reporting it. Please try the attached patch, which I installed on master.

Thanks - that fixes the crash, so Eli's crystal ball is working well.

As this patch moves init of bignum allocators later in startup, will
this cause future problems if bignums are used early in emacs before
dumping ?

    AndyM

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Tue, 04 Sep 2018 18:37:39 +0100
> 
> As this patch moves init of bignum allocators later in startup, will
> this cause future problems if bignums are used early in emacs before
> dumping ?

Yes.  Ideally, bignums shouldn't be used at dump time at all, but if
we must, they should be used only after the call to init_bignum.

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

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

Eli Zaretskii wrote:
> I don't understand why it prefers GMP calls to a simple double
> division, when both arguments are fixnums.  What am I missing?

First, converting a fixnum to a double can lose info. Second, the double 
division could round, which would mean the result would be double-rounded. We're 
already suffering from double-rounding when either argument is floating-point, 
and we don't want that bug to also infect integer division. So even the Emacs 26 
code (which doesn't have bignums) must use integer division here, not double 
division.

This is worth commenting so I installed the attached. While writing the comment 
I noticed there's a bug when one argument is a bignum and the other is a float, 
so I fixed that in the attached too.

[-- Attachment #2: 0001-Fix-round-FLOAT-BIGNUM-bug.patch --]
[-- Type: text/x-patch, Size: 2091 bytes --]

From 21637d5e5b29d5ec8fb966c0ddfbfba3eb33da38 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 4 Sep 2018 11:49:41 -0700
Subject: [PATCH] Fix (round FLOAT BIGNUM) bug

* src/floatfns.c (rounding_driver): Fix bug when one
argument is a float and the other is a bignum.
* test/src/floatfns-tests.el (bignum-round): Test for the bug.
---
 src/floatfns.c             | 7 +++++--
 test/src/floatfns-tests.el | 5 +++++
 2 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/src/floatfns.c b/src/floatfns.c
index 2f33b8652b..13ab7b0359 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -355,6 +355,8 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
       CHECK_NUMBER (divisor);
       if (!FLOATP (arg) && !FLOATP (divisor))
 	{
+	  /* Divide as integers.  Converting to double might lose
+	     info, even for fixnums; also see the FIXME below.  */
 	  if (EQ (divisor, make_fixnum (0)))
 	    xsignal0 (Qarith_error);
 	  int_divide (mpz[0],
@@ -363,10 +365,11 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
 	  return make_integer_mpz ();
 	}
 
-      double f1 = FLOATP (arg) ? XFLOAT_DATA (arg) : XFIXNUM (arg);
-      double f2 = FLOATP (divisor) ? XFLOAT_DATA (divisor) : XFIXNUM (divisor);
+      double f1 = XFLOATINT (arg);
+      double f2 = XFLOATINT (divisor);
       if (! IEEE_FLOATING_POINT && f2 == 0)
 	xsignal0 (Qarith_error);
+      /* FIXME: This division rounds, so the result is double-rounded.  */
       d = f1 / f2;
     }
 
diff --git a/test/src/floatfns-tests.el b/test/src/floatfns-tests.el
index d41b08f796..9a382058b4 100644
--- a/test/src/floatfns-tests.el
+++ b/test/src/floatfns-tests.el
@@ -70,6 +70,11 @@
       (should (= n (floor n)))
       (should (= n (round n)))
       (should (= n (truncate n)))
+      (let ((-n (- n))
+	    (f (float n))
+	    (-f (- (float n))))
+	(should (= 1 (round n f) (round -n -f) (round f n) (round -f -n)))
+	(should (= -1 (round -n f) (round n -f) (round f -n) (round -f n))))
       (dolist (d ns)
         (let ((q (/ n d))
               (r (% n d))
-- 
2.17.1

Re: Bignum speedup patch causes crash at startup

[Andy Moreton]

On Tue 04 Sep 2018, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Tue, 04 Sep 2018 18:37:39 +0100
>> 
>> As this patch moves init of bignum allocators later in startup, will
>> this cause future problems if bignums are used early in emacs before
>> dumping ?
>
> Yes.  Ideally, bignums shouldn't be used at dump time at all, but if
> we must, they should be used only after the call to init_bignum.

Tom added support in commit fb26c9fd69 ("Make purecopy work for
bignums"), so if that causes problems then it may need to be revisited.

    AndyM

Re: Bignum speedup patch causes crash at startup

[Andy Moreton]

On Tue 04 Sep 2018, Andy Moreton wrote:

> On Tue 04 Sep 2018, Paul Eggert wrote:
>
>> Andy Moreton wrote:
>>
>>> The recent changes in commit fe042e9d ("Speed up (+ 2 2) by a factor of
>>> 10") cause an immediate crash in 64bit emacs on Windows.
>>
>> Thanks for reporting it. Please try the attached patch, which I installed on master.
>
> Thanks - that fixes the crash, so Eli's crystal ball is working well.

I now see a strange warning on 64bit Windows (building with gcc 8.2.0
for target x86_64-w64-mingw32):

  CC       data.o
In file included from C:/emacs/git/emacs/master/src/data.c:31:
C:/emacs/git/emacs/master/src/data.c: In function 'arith_driver':
C:/emacs/git/emacs/master/src/lisp.h:2479:34: warning: 'accum' may be used uninitialized in this function [-Wmaybe-uninitialized]
   return FIXNUM_OVERFLOW_P (n) ? make_bigint (n) : make_fixnum (n);
                                  ^~~~~~~~~~~~~~~
C:/emacs/git/emacs/master/src/data.c:2962:12: note: 'accum' was declared here
   intmax_t accum = XFIXNUM (val);
            ^~~~~

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

Andy Moreton wrote:
> I now see a strange warning on 64bit Windows (building with gcc 8.2.0
> for target x86_64-w64-mingw32):
> 
>    CC       data.o
> In file included from C:/emacs/git/emacs/master/src/data.c:31:
> C:/emacs/git/emacs/master/src/data.c: In function 'arith_driver':
> C:/emacs/git/emacs/master/src/lisp.h:2479:34: warning: 'accum' may be used uninitialized in this function [-Wmaybe-uninitialized]
>     return FIXNUM_OVERFLOW_P (n) ? make_bigint (n) : make_fixnum (n);
>                                    ^~~~~~~~~~~~~~~
> C:/emacs/git/emacs/master/src/data.c:2962:12: note: 'accum' was declared here
>     intmax_t accum = XFIXNUM (val);

GCC complains that 'accum' might be used uninitialized even though 'accum's 
declaration has an initializer? Looks like a clear GCC bug, and might be worth 
reporting there.

For what it's worth I don't observe the problem on RHEL 7 x86-64, building with 
GCC 8.2.0 (which I built myself for x86_64-pc-linux-gnu) and configuring Emacs 
with './configure --enable-gcc-warnings --with-gif=no'.

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

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

Andy Moreton wrote:
> Tom added support in commit fb26c9fd69 ("Make purecopy work for
> bignums"), so if that causes problems then it may need to be revisited.

That code is never used and it wouldn't hurt to remove it as per the attached. 
I'll CC: Tom to see if he has an opinion.

[-- Attachment #2: emacs-bignum.diff --]
[-- Type: text/x-patch, Size: 1281 bytes --]

diff --git a/src/alloc.c b/src/alloc.c
index 28ca7804ee..a20991e4b9 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -5325,33 +5325,6 @@ make_pure_float (double num)
   return new;
 }
 
-/* Value is a bignum object with value VALUE allocated from pure
-   space.  */
-
-static Lisp_Object
-make_pure_bignum (struct Lisp_Bignum *value)
-{
-  size_t i, nlimbs = mpz_size (value->value);
-  size_t nbytes = nlimbs * sizeof (mp_limb_t);
-  mp_limb_t *pure_limbs;
-  mp_size_t new_size;
-
-  struct Lisp_Bignum *b = pure_alloc (sizeof *b, Lisp_Vectorlike);
-  XSETPVECTYPESIZE (b, PVEC_BIGNUM, 0, VECSIZE (struct Lisp_Bignum));
-
-  pure_limbs = pure_alloc (nbytes, -1);
-  for (i = 0; i < nlimbs; ++i)
-    pure_limbs[i] = mpz_getlimbn (value->value, i);
-
-  new_size = nlimbs;
-  if (mpz_sgn (value->value) < 0)
-    new_size = -new_size;
-
-  mpz_roinit_n (b->value, pure_limbs, new_size);
-
-  return make_lisp_ptr (b, Lisp_Vectorlike);
-}
-
 /* Return a vector with room for LEN Lisp_Objects allocated from
    pure space.  */
 
@@ -5492,8 +5465,6 @@ purecopy (Lisp_Object obj)
       /* Don't hash-cons it.  */
       return obj;
     }
-  else if (BIGNUMP (obj))
-    obj = make_pure_bignum (XBIGNUM (obj));
   else
     {
       AUTO_STRING (fmt, "Don't know how to purify: %S");

Re: Bignum speedup patch causes crash at startup

[Tom Tromey]

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

Paul> Andy Moreton wrote:
>> Tom added support in commit fb26c9fd69 ("Make purecopy work for
>> bignums"), so if that causes problems then it may need to be revisited.

Paul> That code is never used and it wouldn't hurt to remove it as per the
Paul> attached. I'll CC: Tom to see if he has an opinion.

I added it because someone (Andy I think but this illness is affecting
my memory somewhat) asked for it.  It seemed not impossible for
something to try to dump a bignum.  But, if it isn't needed, then IMO
that's fine.

Tom

Re: Bignum speedup patch causes crash at startup

[Andy Moreton]

On Tue 04 Sep 2018, Tom Tromey wrote:

>>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:
>
> Paul> Andy Moreton wrote:
>>> Tom added support in commit fb26c9fd69 ("Make purecopy work for
>>> bignums"), so if that causes problems then it may need to be revisited.
>
> Paul> That code is never used and it wouldn't hurt to remove it as per the
> Paul> attached. I'll CC: Tom to see if he has an opinion.
>
> I added it because someone (Andy I think but this illness is affecting
> my memory somewhat) asked for it.  It seemed not impossible for
> something to try to dump a bignum.  But, if it isn't needed, then IMO
> that's fine.

I mentioned that support for dumping bignums would seems to be a useful
feature, in the sense of not having arbitrary restrictions. Tom added
code to support that (the commit mentioned above).

Dumping of bignums is not currently required by any emacs code, but it
should be supported unless there is some unreasonable difficulty in
doing so.

    AndyM

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

Andy Moreton wrote:
> Dumping of bignums is not currently required by any emacs code, but it
> should be supported unless there is some unreasonable difficulty in
> doing so.

The difficulty seems to be that memory allocation doesn't work for it, at least 
on MS-Windows. Fixing this is low priority, admittedly.

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> Cc: andrewjmoreton@gmail.com, emacs-devel@gnu.org
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 4 Sep 2018 11:59:53 -0700
> 
> First, converting a fixnum to a double can lose info.

Whether that is a possibility could be established by a simple
magnitude test.

> Second, the double 
> division could round, which would mean the result would be double-rounded. We're 
> already suffering from double-rounding when either argument is floating-point, 
> and we don't want that bug to also infect integer division.

I don't understand what bug you are alluding to.  Can you elaborate?

> So even the Emacs 26 code (which doesn't have bignums) must use
> integer division here, not double division.

Fine, but don't you agree that calling libgmp, when the second
argument is 1 and the 1st is a fixnum, is a little bit ridiculous?
Could we at least special-case that?

Thanks.

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

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

Eli Zaretskii wrote:
>> First, converting a fixnum to a double can lose info.
> Whether that is a possibility could be established by a simple
> magnitude test.

Yes, that could be done, though a simple test like that would not be perfect as 
it would mistakenly reject some valid integers. It would still suffer from 
double-rounding, though.

>> Second, the double
>> division could round, which would mean the result would be double-rounded. We're
>> already suffering from double-rounding when either argument is floating-point,
>> and we don't want that bug to also infect integer division.
> I don't understand what bug you are alluding to.  Can you elaborate?

Double rounding occurs when you are attempting to compute (say) the floor of 
A/B, and do that by first computing A/B as a double (which rounds to the nearest 
double), and then taking the floor of the result. The rounding can cause you to 
lose information, and when you take the floor of the rounded result you get the 
wrong answer. For example, on a 64-bit Emacs, (floor (1+ most-negative-fixnum) 
(1- most-positive-fixnum)) should yield -2 because the the numerator is negative 
and has absolute value slightly greater than that of the positive denominator, 
but with the method you're suggesting the expression would yield -1 (assuming 
IEEE double) because double-precision floating-point division rounds the 
mathematically exact quotient to -1.0.

> don't you agree that calling libgmp, when the second
> argument is 1 and the 1st is a fixnum, is a little bit ridiculous?

Although I wouldn't go that far, we can improve the runtime performance in the 
special case of fixnum / fixnum, at the cost of some complexity in the code and 
very minor slowdown elsewhere. I installed the attached to do that.

[-- Attachment #2: 0001-Improve-round-FIXNUM-FIXNUM-performance.patch --]
[-- Type: text/x-patch, Size: 5097 bytes --]

From baa6ae8724fd4cd7631164a89bf8eed4ff79cfc0 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Wed, 5 Sep 2018 00:21:02 -0700
Subject: [PATCH] Improve (round FIXNUM FIXNUM) performance

* src/floatfns.c (rounding_driver):
New arg fixnum_divide.  All callers changed.
(ceiling2, floor2, truncate2, round2): New functions.
Not that new, actually; these are essentially taken from Emacs 26.
(Fceiling, Ffloor, Fround, Ftruncate): Use them.
---
 src/floatfns.c | 74 +++++++++++++++++++++++++++++++++++---------------
 1 file changed, 52 insertions(+), 22 deletions(-)

diff --git a/src/floatfns.c b/src/floatfns.c
index 13ab7b0359..dc7236353c 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -339,6 +339,7 @@ static Lisp_Object
 rounding_driver (Lisp_Object arg, Lisp_Object divisor,
 		 double (*double_round) (double),
 		 void (*int_divide) (mpz_t, mpz_t const, mpz_t const),
+		 EMACS_INT (*fixnum_divide) (EMACS_INT, EMACS_INT),
 		 const char *name)
 {
   CHECK_NUMBER (arg);
@@ -357,8 +358,14 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
 	{
 	  /* Divide as integers.  Converting to double might lose
 	     info, even for fixnums; also see the FIXME below.  */
-	  if (EQ (divisor, make_fixnum (0)))
-	    xsignal0 (Qarith_error);
+	  if (FIXNUMP (divisor))
+	    {
+	      if (XFIXNUM (divisor) == 0)
+		xsignal0 (Qarith_error);
+	      if (FIXNUMP (arg))
+		return make_int (fixnum_divide (XFIXNUM (arg),
+						XFIXNUM (divisor)));
+	    }
 	  int_divide (mpz[0],
 		      *bignum_integer (&mpz[0], arg),
 		      *bignum_integer (&mpz[1], divisor));
@@ -387,26 +394,47 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
   return double_to_bignum (dr);
 }
 
-static void
-rounddiv_q (mpz_t q, mpz_t const n, mpz_t const d)
+static EMACS_INT
+ceiling2 (EMACS_INT n, EMACS_INT d)
 {
-  /* mpz_tdiv_qr gives us one remainder R, but we want the remainder
-     R1 on the other side of 0 if R1 is closer to 0 than R is; because
-     we want to round to even, we also want R1 if R and R1 are the
-     same distance from 0 and if the quotient is odd.
+  return n / d + ((n % d != 0) & ((n < 0) == (d < 0)));
+}
 
-     If we were using EMACS_INT arithmetic instead of bignums,
-     the following code could look something like this:
+static EMACS_INT
+floor2 (EMACS_INT n, EMACS_INT d)
+{
+  return n / d - ((n % d != 0) & ((n < 0) != (d < 0)));
+}
 
-     q = n / d;
-     r = n % d;
-     neg_d = d < 0;
-     neg_r = r < 0;
-     abs_r = eabs (r);
-     abs_r1 = eabs (d) - abs_r;
-     if (abs_r1 < abs_r + (q & 1))
-       q += neg_d == neg_r ? 1 : -1;  */
+static EMACS_INT
+truncate2 (EMACS_INT n, EMACS_INT d)
+{
+  return n / d;
+}
 
+static EMACS_INT
+round2 (EMACS_INT n, EMACS_INT d)
+{
+  /* The C language's division operator gives us the remainder R
+     corresponding to truncated division, but we want the remainder R1
+     on the other side of 0 if R1 is closer to 0 than R is; because we
+     want to round to even, we also want R1 if R and R1 are the same
+     distance from 0 and if the truncated quotient is odd.  */
+  EMACS_INT q = n / d;
+  EMACS_INT r = n % d;
+  bool neg_d = d < 0;
+  bool neg_r = r < 0;
+  EMACS_INT abs_r = eabs (r);
+  EMACS_INT abs_r1 = eabs (d) - abs_r;
+  if (abs_r1 < abs_r + (q & 1))
+    q += neg_d == neg_r ? 1 : -1;
+  return q;
+}
+
+static void
+rounddiv_q (mpz_t q, mpz_t const n, mpz_t const d)
+{
+  /* Mimic the source code of round2, using mpz_t instead of EMACS_INT.  */
   mpz_t *r = &mpz[2], *abs_r = r, *abs_r1 = &mpz[3];
   mpz_tdiv_qr (q, *r, n, d);
   bool neg_d = mpz_sgn (d) < 0;
@@ -446,7 +474,7 @@ This rounds the value towards +inf.
 With optional DIVISOR, return the smallest integer no less than ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, ceil, mpz_cdiv_q, "ceiling");
+  return rounding_driver (arg, divisor, ceil, mpz_cdiv_q, ceiling2, "ceiling");
 }
 
 DEFUN ("floor", Ffloor, Sfloor, 1, 2, 0,
@@ -455,7 +483,7 @@ This rounds the value towards -inf.
 With optional DIVISOR, return the largest integer no greater than ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, floor, mpz_fdiv_q, "floor");
+  return rounding_driver (arg, divisor, floor, mpz_fdiv_q, floor2, "floor");
 }
 
 DEFUN ("round", Fround, Sround, 1, 2, 0,
@@ -468,7 +496,8 @@ your machine.  For example, (round 2.5) can return 3 on some
 systems, but 2 on others.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, emacs_rint, rounddiv_q, "round");
+  return rounding_driver (arg, divisor, emacs_rint, rounddiv_q, round2,
+			  "round");
 }
 
 /* Since rounding_driver truncates anyway, no need to call 'trunc'.  */
@@ -484,7 +513,8 @@ Rounds ARG toward zero.
 With optional DIVISOR, truncate ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, identity, mpz_tdiv_q, "truncate");
+  return rounding_driver (arg, divisor, identity, mpz_tdiv_q, truncate2,
+			  "truncate");
 }
 
 
-- 
2.17.1

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 4 Sep 2018 13:48:10 -0700
> 
> >    CC       data.o
> > In file included from C:/emacs/git/emacs/master/src/data.c:31:
> > C:/emacs/git/emacs/master/src/data.c: In function 'arith_driver':
> > C:/emacs/git/emacs/master/src/lisp.h:2479:34: warning: 'accum' may be used uninitialized in this function [-Wmaybe-uninitialized]
> >     return FIXNUM_OVERFLOW_P (n) ? make_bigint (n) : make_fixnum (n);
> >                                    ^~~~~~~~~~~~~~~
> > C:/emacs/git/emacs/master/src/data.c:2962:12: note: 'accum' was declared here
> >     intmax_t accum = XFIXNUM (val);
> 
> GCC complains that 'accum' might be used uninitialized even though 'accum's 
> declaration has an initializer? Looks like a clear GCC bug, and might be worth 
> reporting there.

Maybe it's because eassert can abort?

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Tue, 04 Sep 2018 20:50:49 +0100
> 
> Tom added support in commit fb26c9fd69 ("Make purecopy work for
> bignums"), so if that causes problems then it may need to be revisited.

It shouldn't cause any problems because any code that uses that
function should run after init_bignum was already called.

Re: Bignum speedup patch causes crash at startup

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 4 Sep 2018 17:56:03 -0700
> 
> Andy Moreton wrote:
> > Dumping of bignums is not currently required by any emacs code, but it
> > should be supported unless there is some unreasonable difficulty in
> > doing so.
> 
> The difficulty seems to be that memory allocation doesn't work for it, at least 
> on MS-Windows. Fixing this is low priority, admittedly.

I don't think there's anything that needs to be fixed here.  Dumping
pure bignums should not cause any trouble any more than dumping pure
strings.  The only issue is that mp_set_memory_functions must be
called before we call any GMP functions that might allocate memory.

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

Eli Zaretskii wrote:
>>> C:/emacs/git/emacs/master/src/data.c:2962:12: note: 'accum' was declared here
>>>      intmax_t accum = XFIXNUM (val);
>> GCC complains that 'accum' might be used uninitialized even though 'accum's
>> declaration has an initializer? Looks like a clear GCC bug, and might be worth
>> reporting there.
> Maybe it's because eassert can abort?

Possibly, if GCC is buggy. But if GCC is working properly, it can easily tell 
that the preceding eassume (or the eassert buried inside XFIXNUM) cannot 
possibly cause control flow to jump over the initialization and into a use of 
'accum', because any signal must jump out of that block and therefore cannot use 
'accum'.

Re: Bignum speedup patch causes crash at startup

[Pip Cet]

On Wed, Sep 5, 2018 at 3:41 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
> or the eassert buried inside XFIXNUM

There is no eassert inside XFIXNUM, which makes it different from
XSYMBOL etc. I think there should be; that would break the code we're
talking about here, but IMHO it's much cleaner not to call XFIXNUM on
a non-fixnum, knowing that the clever way the code is written will
prevent the meaningless integer thus achieved from ever being used. I
doubt there is a performance gain to be had from that way of writing
code, and it's very hard to read. And there might even be a
performance win to assuming XFIXNUM's argument has the right tag
value.

Re: Bignum speedup patch causes crash at startup

[Paul Eggert]

Pip Cet wrote:
> There is no eassert inside XFIXNUM, which makes it different from
> XSYMBOL etc. I think there should be

Yes, and that's on my list of things to do. Sorry, I got ahead of myself there.