bug#1334: 23.0.60; bug of bytecomp arithmetic operations

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Shigeru Fukaya]

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

Hello,

Current byte compiler has potential problems in arithmetic operations.
Examples are all on Intel 32-bit. Result may occur in other
environments.

1. Operations are all compiled to binary operations. It may cause
overflows or truncations in floating point data operations.

   Examples.
      (upper result is by interpreter, lower is by code after compile)

    (let ((a most-positive-fixnum) (b 1) (c 1.0))  (+ a b c))
         --> 268435457.0
         --> -268435455.0

    (let ((a most-positive-fixnum) (b -2) (c 1.0)) (- a b c))
         --> 268435456.0
         --> -268435456.0

    (let ((a most-positive-fixnum) (b 2) (c 1.0))  (* a b c))
         --> 536870910.0
         --> -2.0

    (let ((a 3) (b 2) (c 1.0)) (/ a b c))
         --> 1.5
         --> 1.0


2. Most integer constants are moved to the end of expressions and
pre-calculated at compile time. Changing of order may cause different
result from original expressions.
(In other words, `byte-optimize-delay-constants-math' should not be called)

   Examples.

      (let ((a (+ 1 (expt 2 -52))) (b (expt 2 -53))) (+ a -1 b))
         --> 3.3306690738754696e-016
         --> 4.440892098500626e-016

      (let ((a (expt 2 -1074)) (b 0.25)) (* a 4 b))
         --> 5e-324
         --> 0.0


3. Mulitiplication/Division optimization sometimes don't consider
floating point operators.

   Examples.

      (let ((a 1.0)) (* a 0))
         --> 0.0
         --> 0

      (let ((a 1.0)) (* a 2.0 0))
         --> 0.0
         --> 0

      (let ((a 1.0)) (/ 0 a))
         --> 0.0
         --> 0

      (let ((a 1.0)) (/ 3 a 2))
         --> 1.5
         --> 1.0


4. In division, optimizing -1 twice and cause erroneous results.

   Examples.

      (/ 3 -1)
         --> -3
         --> 3


Attached files are rewrittren version and too much changed, so it is
possibly just for references (At least, alias functions are not
treated well, and not comprehensively tested).

   bytecomp-patch.el -- contain only new and modified symbols/functions.
   byte-opt-test.el  -- test function that shows interpreter/original/revised
                        results.
   test.log          -- test result using above files.
   byte-opt.el bytecomp.el -- changed files to replace.

Regards,
Shigeru

[-- Attachment #2: bc.tgz --]
[-- Type: application/x-gzip, Size: 75456 bytes --]

bug#1334: marked as done (23.0.60; bug of bytecomp arithmetic operations)

[Emacs bug Tracking System]

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


Your message dated Fri, 21 Nov 2008 13:56:15 -0500
with message-id <871vx4aoxc.fsf@cyd.mit.edu>
and subject line Re: 23.0.60; bug of bytecomp arithmetic operations
has caused the Emacs bug report #1334,
regarding 23.0.60; bug of bytecomp arithmetic operations
to be marked as done.

This means that you claim that the problem has been dealt with.
If this is not the case it is now your responsibility to reopen the
bug report if necessary, and/or fix the problem forthwith.

(NB: If you are a system administrator and have no idea what this
message is talking about, this may indicate a serious mail system
misconfiguration somewhere. Please contact don@donarmstrong.com
immediately.)


-- 
1334: http://emacsbugs.donarmstrong.com/cgi-bin/bugreport.cgi?bug=1334
Emacs Bug Tracking System
Contact don@donarmstrong.com with problems

[-- Attachment #2: Type: message/rfc822, Size: 107435 bytes --]

[-- Attachment #2.1.1: Type: text/plain, Size: 2259 bytes --]

Hello,

Current byte compiler has potential problems in arithmetic operations.
Examples are all on Intel 32-bit. Result may occur in other
environments.

1. Operations are all compiled to binary operations. It may cause
overflows or truncations in floating point data operations.

   Examples.
      (upper result is by interpreter, lower is by code after compile)

    (let ((a most-positive-fixnum) (b 1) (c 1.0))  (+ a b c))
         --> 268435457.0
         --> -268435455.0

    (let ((a most-positive-fixnum) (b -2) (c 1.0)) (- a b c))
         --> 268435456.0
         --> -268435456.0

    (let ((a most-positive-fixnum) (b 2) (c 1.0))  (* a b c))
         --> 536870910.0
         --> -2.0

    (let ((a 3) (b 2) (c 1.0)) (/ a b c))
         --> 1.5
         --> 1.0


2. Most integer constants are moved to the end of expressions and
pre-calculated at compile time. Changing of order may cause different
result from original expressions.
(In other words, `byte-optimize-delay-constants-math' should not be called)

   Examples.

      (let ((a (+ 1 (expt 2 -52))) (b (expt 2 -53))) (+ a -1 b))
         --> 3.3306690738754696e-016
         --> 4.440892098500626e-016

      (let ((a (expt 2 -1074)) (b 0.25)) (* a 4 b))
         --> 5e-324
         --> 0.0


3. Mulitiplication/Division optimization sometimes don't consider
floating point operators.

   Examples.

      (let ((a 1.0)) (* a 0))
         --> 0.0
         --> 0

      (let ((a 1.0)) (* a 2.0 0))
         --> 0.0
         --> 0

      (let ((a 1.0)) (/ 0 a))
         --> 0.0
         --> 0

      (let ((a 1.0)) (/ 3 a 2))
         --> 1.5
         --> 1.0


4. In division, optimizing -1 twice and cause erroneous results.

   Examples.

      (/ 3 -1)
         --> -3
         --> 3


Attached files are rewrittren version and too much changed, so it is
possibly just for references (At least, alias functions are not
treated well, and not comprehensively tested).

   bytecomp-patch.el -- contain only new and modified symbols/functions.
   byte-opt-test.el  -- test function that shows interpreter/original/revised
                        results.
   test.log          -- test result using above files.
   byte-opt.el bytecomp.el -- changed files to replace.

Regards,
Shigeru

[-- Attachment #2.1.2: bc.tgz --]
[-- Type: application/x-gzip, Size: 75456 bytes --]

[-- Attachment #3: Type: message/rfc822, Size: 1907 bytes --]

From: Chong Yidong <cyd@stupidchicken.com>
To: "Shigeru Fukaya" <shigeru.fukaya@gmail.com>
Cc: 1334-done@emacsbugs.donarmstrong.com
Subject: Re: 23.0.60; bug of bytecomp arithmetic operations
Date: Fri, 21 Nov 2008 13:56:15 -0500
Message-ID: <871vx4aoxc.fsf@cyd.mit.edu>

I've reviewed your patch, and checked most of it into CVS (I took the
liberty of rewording some comments, plus some minor edits).

> *** Optimize addtion/subtraction where their last operand is 1 or
> -1 to use `1+', `1-' funcitons. This pattern often appears and
> more effective at least in size (byte-add1 vs constant 1).

Let's leave this till after the release.  It's not clear to me that
there is a significant speed increase from it, and we should try to
restrict the changes to bug fixes for the moment.

Thanks very much for working on this.

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Chong Yidong]

> Hello,
>
> Current byte compiler has potential problems in arithmetic operations.
> Examples are all on Intel 32-bit. Result may occur in other
> environments.

Good work catching these problems.  I've committed your bytecomp.el
changes into CVS.  I'm double-checking your changes to byte-opt.el, and
will commit them in later if no problems occur.

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Chong Yidong]

Hi Shigeru,

I've been looking through your changes to byte-opt.el.  They look good,
but some of the changes are a little too agressive for my tastes, so
close to pretest.

Could you separate out the byte-optimize-*-functions part of the patch?
A mistake in any of these lists could lead to some hard-to-track errors.
If in doubt, let's simply not perform the optimization for now.  We can
apply these changes after the release.

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Shigeru Fukaya]

Hi, Chong,

I agree it's too aggressive. I'd just sought for the best.

> Could you separate out the byte-optimize-*-functions part of the patch?
They are mutually affected. So I'll make and send a patch of
byte-opt.el that includes minimal changes to the latest CVS. It is
necessary because the current byte-opt.el still has problems I
pointed. It will take a few days. 

Is it ok?

Regards,
Shigeru

----- Original Message ----- 
From: "Chong Yidong" <cyd@stupidchicken.com>
To: "Shigeru Fukaya" <shigeru.fukaya@gmail.com>
Cc: <1334@emacsbugs.donarmstrong.com>
Sent: Saturday, November 15, 2008 8:10 AM
Subject: Re: 23.0.60; bug of bytecomp arithmetic operations


> Hi Shigeru,
> 
> I've been looking through your changes to byte-opt.el.  They look good,
> but some of the changes are a little too agressive for my tastes, so
> close to pretest.
> 
> Could you separate out the byte-optimize-*-functions part of the patch?
> A mistake in any of these lists could lead to some hard-to-track errors.
> If in doubt, let's simply not perform the optimization for now.  We can
> apply these changes after the release.

----- Original Message ----- 
From: "Chong Yidong" <cyd@stupidchicken.com>
To: "Shigeru Fukaya" <shigeru.fukaya@gmail.com>
Cc: <1334@emacsbugs.donarmstrong.com>
Sent: Saturday, November 15, 2008 8:10 AM
Subject: Re: 23.0.60; bug of bytecomp arithmetic operations


> Hi Shigeru,
> 
> I've been looking through your changes to byte-opt.el.  They look good,
> but some of the changes are a little too agressive for my tastes, so
> close to pretest.
> 
> Could you separate out the byte-optimize-*-functions part of the patch?
> A mistake in any of these lists could lead to some hard-to-track errors.
> If in doubt, let's simply not perform the optimization for now.  We can
> apply these changes after the release.

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Chong Yidong]

"Shigeru Fukaya" <shigeru.fukaya@gmail.com> writes:

>> Could you separate out the byte-optimize-*-functions part of the patch?
>
> They are mutually affected. So I'll make and send a patch of
> byte-opt.el that includes minimal changes to the latest CVS. It is
> necessary because the current byte-opt.el still has problems I
> pointed. It will take a few days. 
>
> Is it ok?

That would be great.  Thanks!

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Shigeru Fukaya]

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

Hello, Chong and everybody,


After bytecomp.el is revised, problems remains as follows;


1. Operations are all compiled to binary operations. It may cause
overflows or truncations in floating point data operations.

   ==> solved.


2. Most integer constants are moved to the end of expressions and
pre-calculated at compile time. Changing of order may cause different
result from original expressions.
(In other words, `byte-optimize-delay-constants-math' should not be called)

   ==> In multiplication/division, problems become not to occur.
       I suppose it is because difference of precision/scale size in
       elisp, execution level, processor internal (elisp < C < processor)
       take over the issue.

	    (let ((a (expt 2 -1074)) (b 0.125))
	      (list (* a b 8) (* (* a b) 8)))
	    --> (5e-324 0.0)

       I can't find the bad case so far. So, in multiplication and
       division, I suppose, at least now, changing calculation order
       is allowable and leave `byte-optimize-delay-constants-math'.

       Addition/Subtraction still show this problem.


3. Mulitiplication/Division optimization sometimes don't consider
floating point operators.

   ==> Add patterns.

   Examples.

      (let ((a most-positive-fixnum) (b 2.0)) (* a 2 b))
	 --> 1073741820.0
	 --> -4.0

      (let ((a 3) (b 2)) (/ a b 1.0))
	 --> 1.5
	 --> 1


4. In division, optimizing -1 twice and cause erroneous results.

   ==> Easy.


To get all examples at a glance, see the attached
`byte-test-minimal.el' or its log file.


Changing policy / plan

* Change functions byte-optimize-plus, byte-optimize-minus,
byte-optimize-multiply, byte-optimize-divide.

* All modifications are closed to the function itself. Don't add other
functions, symbols.

* Don't call `byte-optimize-delay-constants-math' in plus, minus
operations. Remain to call it in multiplication, division operations.

* Call `byte-optimize-predicate' at the last as in minus operation.
This will optimize expressions that all arguments are constant to
constant values.

* Consider frequency or possibility.

** Remove/Abandon some optimizations.

*** Most optimizations that need floating point data result.

**** Zero in operands of multiplication or division (first
operand). This case seems rare. If you do something, it's like
below,

Multiplication:
   (cond ((or (memql 0.0 (cdr form))
	      (and (eq 0 last) (memq t (mapcar #'floatp (cdr form)))))
	  (setq form (nconc (list 'progn)
			    (delq 0 (mapcar (lambda (x)
					      (if (or (numberp x) (symbolp x))
						  0
						x))
					    (cdr form)))
			    (list 0.0))))

Division:
   (cond ((or (eql (cadr form) 0.0)
	      (and (eq (cadr form) 0) (memq t (mapcar #'floatp (cddr form)))))
	  ;; This optimization may throw out division by zero error.
	  (setq form (nconc (list 'progn)
			    (delq 0 (mapcar (lambda (x)
					      (if (or (numberp x) (symbolp x))
						  0
						x))
					    (cdr form)))
			    (list 0.0))))
	 ((and (eq (cadr form 0) 0) (numberp last) (nthcdr 3 form))
	  (setq form (byte-compile-butlast form))
	  )


** Add some optimizations.

*** Optimize addtion/subtraction where their last operand is 1 or
-1 to use `1+', `1-' funcitons. This pattern often appears and
more effective at least in size (byte-add1 vs constant 1).

*** Other small changes.


Files:
   ChangeLog
   byte-opt.el		   - modified file.
   byte-opt.diff	   - diff by `diff -c OLD NEW >byte-opt.diff'
   byte-test-minimal.el	   - test script to compare original and revised.
   log.summary		   - sammary output by byte-test-minimal
   log.detail		   - detailed (with disassembled code) output by
byte-test-minimal.
   byte-regress-minimal.el - simple coverage test
   log.regress		   - log output of the coverage test

If something is wrong, let me know, please.


Regards,
Shigeru


2008/11/15 Chong Yidong <cyd@stupidchicken.com>:
> "Shigeru Fukaya" <shigeru.fukaya@gmail.com> writes:
>
>>> Could you separate out the byte-optimize-*-functions part of the patch?
>>
>> They are mutually affected. So I'll make and send a patch of
>> byte-opt.el that includes minimal changes to the latest CVS. It is
>> necessary because the current byte-opt.el still has problems I
>> pointed. It will take a few days.
>>
>> Is it ok?
>
> That would be great.  Thanks!
>

[-- Attachment #2: bc2.tgz --]
[-- Type: application/x-gzip, Size: 28631 bytes --]

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Chong Yidong]

Thanks.  I'm looking through your changes.

!      ;; (- 0 x) --> (- x)
!      ((and (eq (nth 1 form) 0) (= (length form) 3))
!       (setq form (list '- (nth 1 form))))

Shouldn't this be (nth 2 form) on the last line?

bug#1334: 23.0.60; bug of bytecomp arithmetic operations

[Shigeru Fukaya]

Hi, Chong,

> Shouldn't this be (nth 2 form) on the last line?
Of course, you are right.

I found  I had tested with my older version.
In `byte-regression-test', I should have remove the following line.
 
    (load "byte-opt-minimal")

After above correction, log output contains three errors.

(let ((a 3) (b 2) (c 1.0)) (- 0 a)) --> -3, NG
 --> 0
(let ((a 3) (b 2) (c 1.0)) (- 0 c)) --> -1.0, NG
 --> 0
(let ((a 3) (b 2) (c 1.0)) (- 0 a)) --> -3, NG
 --> 0

Thank you,

- Shigeru


----- Original Message ----- 
From: "Chong Yidong" <cyd@stupidchicken.com>
To: "Shigeru Fukaya" <shigeru.fukaya@gmail.com>
Cc: <1334@emacsbugs.donarmstrong.com>
Sent: Friday, November 21, 2008 4:40 PM
Subject: Re: 23.0.60; bug of bytecomp arithmetic operations


> Thanks.  I'm looking through your changes.
> 
> !      ;; (- 0 x) --> (- x)
> !      ((and (eq (nth 1 form) 0) (= (length form) 3))
> !       (setq form (list '- (nth 1 form))))
> 
> Shouldn't this be (nth 2 form) on the last line?