bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Mattias Engdegård]

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

Minor improvement to avoid duplication of some numbers in bytecode.

No significant degradation in compilation speed observed. The savings aren't huge either: 1382 bytes in all .elc files, but the in-memory savings are probably higher, since an extra small flonum (1.0, say) only costs 4 bytes in the .elc file, but something like 16-24 bytes in memory (pointer + boxed flonum).


[-- Attachment #2: 0001-Deduplicate-non-fixnum-numeric-constants-in-byte-com.patch --]
[-- Type: application/octet-stream, Size: 1058 bytes --]

From 9c2b6e940d9fd6db189c52b92c60ed3a3fb7dfd4 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Sun, 22 Dec 2019 12:09:06 +0100
Subject: [PATCH] Deduplicate non-fixnum numeric constants in byte-compilation

* lisp/emacs-lisp/bytecomp.el (byte-compile-get-constant):
Use eql for looking up constants instead of eq, allowing
for bignum and flonum deduplication.
---
 lisp/emacs-lisp/bytecomp.el | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lisp/emacs-lisp/bytecomp.el b/lisp/emacs-lisp/bytecomp.el
index 118356ec26..60dbae1d4b 100644
--- a/lisp/emacs-lisp/bytecomp.el
+++ b/lisp/emacs-lisp/bytecomp.el
@@ -3462,7 +3462,7 @@ byte-compile-get-constant
 	       (if (equal-including-properties (car elt) ,const)
 		   (setq result elt)))
 	     result)
-	 (assq ,const byte-compile-constants))
+	 (assoc ,const byte-compile-constants #'eql))
        (car (setq byte-compile-constants
 		  (cons (list ,const) byte-compile-constants)))))
 
-- 
2.21.0 (Apple Git-122.2)

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Mattias Engdegård]

Pushed to master.

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Pip Cet]

On Sun, Dec 22, 2019 at 5:11 PM Mattias Engdegård <mattiase@acm.org> wrote:
> Minor improvement to avoid duplication of some numbers in bytecode.

I don't have a strong opinion about this (well, I do, actually: 'eq
and 'eql should be equal), but my impression from the last time this
was discussed is that the problems this causes (different code
behavior for byte-compiled code versus evaluated code) outweighed the
benefits (very tiny code size reduction). I don't think different
floating point representations are still an issue.

Most importantly, I think that we should be able to be define

(defun f () (eq 18446744073709551616 18446744073709551616))

That function should always return t on sane systems that have eq =
eql, and always return nil on systems that have <64 bits in a fixnum
and the old-style eq.

With your patch, f will return t if it is byte-compiled without
optimizations, but nil if it isn't byte-compiled or is byte-compiled
with optimizations.

> No significant degradation in compilation speed observed.

That's good, that was another concern, IIRC.

> The savings aren't huge either: 1382 bytes in all .elc files, but the in-memory savings are probably higher, since an extra small flonum (1.0, say) only costs 4 bytes in the .elc file, but something like 16-24 bytes in memory (pointer + boxed flonum).

I don't see how you end up with 24 bytes in that case, though, unless
you over-align floats (which we should, it gives us an extra tag bit).

Anyway, I still think the right course of action here is to fix (or
deprecate) eq rather than changing minor details of the byte compiler
in incompatible ways. However, if we decide the gain is significant
for floating point numbers, let's restrict this to floating point
numbers and leave bignums alone?

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Mattias Engdegård]

27 dec. 2019 kl. 18.07 skrev Pip Cet <pipcet@gmail.com>:

> I don't have a strong opinion about this (well, I do, actually: 'eq
> and 'eql should be equal), but my impression from the last time this
> was discussed is that the problems this causes (different code
> behavior for byte-compiled code versus evaluated code) outweighed the
> benefits (very tiny code size reduction).

Thank you for inspecting my change! And sorry, I didn't know this had been debated before. Is there a record of that discussion anywhere?

> Most importantly, I think that we should be able to be define
> 
> (defun f () (eq 18446744073709551616 18446744073709551616))
> 
> That function should always return t on sane systems that have eq =
> eql, and always return nil on systems that have <64 bits in a fixnum
> and the old-style eq.

I'm not sure I understand. Surely such a criterion imposes a rather low limit on permissible optimisations? For example, shouldn't

(eq (ash 1 x) (ash 1 x))

be allowed to be optimised to t (after CSE, say), even if x can be 64, despite the fact that interpreted or low-optimised compiled code would yield nil in that case?

Perhaps the change should really be done on the emacs-27 branch, to avoid changing bignum behaviour, but that is just a slightly weaker version of the same restriction. Unless we decide to turn eq into a synonym for eql, eq is a one-sided conservative approximation of eql for bignums and flonums.

> Anyway, I still think the right course of action here is to fix (or
> deprecate) eq rather than changing minor details of the byte compiler
> in incompatible ways. However, if we decide the gain is significant
> for floating point numbers, let's restrict this to floating point
> numbers and leave bignums alone?

What would anyone gain from such a restriction? And the change is minor because it's a small thing to do; what I thought looked like an obvious oversight, or one that made more sense back when Elisp didn't have bignums.

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Pip Cet]

On Sat, Dec 28, 2019 at 3:49 PM Mattias Engdegård <mattiase@acm.org> wrote:
> 27 dec. 2019 kl. 18.07 skrev Pip Cet <pipcet@gmail.com>:
> > I don't have a strong opinion about this (well, I do, actually: 'eq
> > and 'eql should be equal), but my impression from the last time this
> > was discussed is that the problems this causes (different code
> > behavior for byte-compiled code versus evaluated code) outweighed the
> > benefits (very tiny code size reduction).
>
> Thank you for inspecting my change! And sorry, I didn't know this had been debated before. Is there a record of that discussion anywhere?

It was part of the rather extensive eq-vs-eql debate, I'm afraid.

I'll try to be clear about this: I think anything but making eq and
eql synonymous is likely to cause problems that drive programmers away
from Elisp. But there are axioms that programmers can rely on that are
stronger than what eq actually promises. For example, two objects
might be thought either to be eq to each other or not, but code such
as this:

(defun my-not-eq (x y) (not (eq x y)))

(defun always-t ()
  (or (eq 18446744073709551616 18446744073709551616)
      (my-not-eq 18446744073709551616 18446744073709551616)))

(byte-compile 'always-t)
(always-t)

will yield unexpected results.

> > Most importantly, I think that we should be able to be define
> >
> > (defun f () (eq 18446744073709551616 18446744073709551616))
> >
> > That function should always return t on sane systems that have eq =
> > eql, and always return nil on systems that have <64 bits in a fixnum
> > and the old-style eq.
>
> I'm not sure I understand. Surely such a criterion imposes a rather low limit on permissible optimisations?

Yes, it does. I think any change in the behavior of eq, except for
making it equal to eql, is likely to break code that's out there
somewhere (and that doesn't mean we hear about it; more likely, people
end up abandoning Elisp and using JavaScript instead). So the second
best option is to keep the current (pre-patch) behavior in which (eq
1.0 1.0) is reliably nil, IMHO.

Technically, I think code such as

(cond ((eq a b) 1) ((not (eq a b)) 2) (t 3))

is allowed to return 3. We should attempt not to make changes that
make this more likely, though.

(Again, is this really what we want? If you can't modify an eq-based
hash table reliably, because keys might have become eq (and thus
overwrite each other) that weren't eq when you checked the hash table,
what can you use such hash tables for?)

> For example, shouldn't
>
> (eq (ash 1 x) (ash 1 x))
>
> be allowed to be optimised to t (after CSE, say), even if x can be 64, despite the fact that interpreted or low-optimised compiled code would yield nil in that case?
>
> Perhaps the change should really be done on the emacs-27 branch, to avoid changing bignum behaviour, but that is just a slightly weaker version of the same restriction. Unless we decide to turn eq into a synonym for eql, eq is a one-sided conservative approximation of eql for bignums and flonums.

You're right, that is eq's contract. But people do misuse it, and one
of the things they wouldn't expect is that optimization results in
things becoming non-eq that were eq before optimization; I think the
other direction is much less problematic.

> > Anyway, I still think the right course of action here is to fix (or
> > deprecate) eq rather than changing minor details of the byte compiler
> > in incompatible ways. However, if we decide the gain is significant
> > for floating point numbers, let's restrict this to floating point
> > numbers and leave bignums alone?
>
> What would anyone gain from such a restriction? And the change is minor because it's a small thing to do; what I thought looked like an obvious oversight, or one that made more sense back when Elisp didn't have bignums.

Well, Elisp has had floats for a while, and bignum constants appear to
be nonexistent, so far.

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Mattias Engdegård]

28 dec. 2019 kl. 17.36 skrev Pip Cet <pipcet@gmail.com>:

> It was part of the rather extensive eq-vs-eql debate, I'm afraid.

Thank you, I think I have heard most of the possible arguments in one form or the other over the years...

> I'll try to be clear about this: I think anything but making eq and
> eql synonymous is likely to cause problems that drive programmers away
> from Elisp.

Actually, I can think of a bunch of more pressing issues, both in terms of the language, its implementation, and the framework.

> But there are axioms that programmers can rely on that are
> stronger than what eq actually promises. For example, two objects
> might be thought either to be eq to each other or not, but code such
> as this:
> 
> (defun my-not-eq (x y) (not (eq x y)))
> 
> (defun always-t ()
>  (or (eq 18446744073709551616 18446744073709551616)
>      (my-not-eq 18446744073709551616 18446744073709551616)))
> 
> (byte-compile 'always-t)
> (always-t)
> 
> will yield unexpected results.

Elisp has a few 'boundedly undefined' parts which would be avoided in a greenfield design but that we are more or less stuck with for the time being, and probably should paint in large letters on the first page of the manual. Such as: don't use eq for numbers; don't mutate literals (strings, conses, vectors); etc.

>> I'm not sure I understand. Surely such a criterion imposes a rather low limit on permissible optimisations?
> 
> Yes, it does. I think any change in the behavior of eq, except for
> making it equal to eql, is likely to break code that's out there
> somewhere (and that doesn't mean we hear about it; more likely, people
> end up abandoning Elisp and using JavaScript instead). So the second
> best option is to keep the current (pre-patch) behavior in which (eq
> 1.0 1.0) is reliably nil, IMHO.

(Javascript's notion of equality, I'm told, is not quite a model of elegance and simplicity, but perhaps that was your point.)

In my experience people seem to have little trouble understanding that eq shouldn't be used to compare numbers. If anything, the introduction of bignums helps driving the point home: up to and including Emacs 26, elisp programmers could get away with eq for integers but not floating-point numbers. Now, the rules are simpler. (Characters still get a free pass, I suppose.)

While we could document a safe range of fixnums for which eq applies, it's probably better not to.

I definitely don't think it's worth propping up broken code that somehow relies on the non-identity of float literals (bignums isn't a worry yet). Such code is not only wrong, it's fragile: fragile in the face of changes to elisp, and of innocent-looking changes to the code itself, such as introducing variables for values.

This doesn't mean that I would necessary be opposed to making eq a synonym for eql; just that it would be a rather more momentous decision that I won't bore anyone by discussing here (although I'd be happy to talk about it over a drink if we meet one day). Has any state-of-the-art Scheme or Lisp implementation ever taken that step?

> Technically, I think code such as
> 
> (cond ((eq a b) 1) ((not (eq a b)) 2) (t 3))
> 
> is allowed to return 3. We should attempt not to make changes that
> make this more likely, though.

Given the state of elisp byte-code optimisation, there is plenty of room for improvements before such semantics become unavoidable. In particular, the committed change does not in any way enable such paradoxical behaviour.

> (Again, is this really what we want? If you can't modify an eq-based
> hash table reliably, because keys might have become eq (and thus
> overwrite each other) that weren't eq when you checked the hash table,
> what can you use such hash tables for?)

Are you arguing that this would be a consequence of the constant deduplication? When eq-based hash tables are not for use with numeric keys anyway?

> You're right, that is eq's contract. But people do misuse it, and one
> of the things they wouldn't expect is that optimization results in
> things becoming non-eq that were eq before optimization; I think the
> other direction is much less problematic.

Good thing that the change works in that other direction then!

>> What would anyone gain from such a restriction? And the change is minor because it's a small thing to do; what I thought looked like an obvious oversight, or one that made more sense back when Elisp didn't have bignums.
> 
> Well, Elisp has had floats for a while, and bignum constants appear to
> be nonexistent, so far.

In other words, there is no broken bignum code that can break.

Obviously it's a small change, and one that I'm prepared to revert if required. But I would like to understand the reason and principles behind it. I want elisp to be faster; we have promised exactly nobody that each numeric literal has its own identity, nor is that a reasonable assumption by a programmer to make.

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Sat, 28 Dec 2019 19:50:14 +0100
> Cc: 38708@debbugs.gnu.org
> 
> Obviously it's a small change, and one that I'm prepared to revert if required. But I would like to understand the reason and principles behind it. I want elisp to be faster; we have promised exactly nobody that each numeric literal has its own identity, nor is that a reasonable assumption by a programmer to make.

IMO, this discussion should happen on emacs-devel, not here.  Some
people whose opinions might be important don't read the bug list.

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Pip Cet]

On Sat, Dec 28, 2019 at 6:50 PM Mattias Engdegård <mattiase@acm.org> wrote:
> Elisp has a few 'boundedly undefined' parts which would be avoided in a greenfield design but that we are more or less stuck with for the time being, and probably should paint in large letters on the first page of the manual. Such as: don't use eq for numbers; don't mutate literals (strings, conses, vectors); etc.

I don't think we're stuck with those two, and I don't think we should
be making them worse than they already are (in Emacs 26.3).

Sorry, the rest of this got a bit long. I think your change isn't as
trivial as it seems at first glance, and we shouldn't do it for Emacs
27, but it's fine on the master branch and might help us shake out
some bugs (and, strategically, the paradoxical behavior observed with
your patch is a good argument for making eq and eql synonymous).

> In my experience people seem to have little trouble understanding that eq shouldn't be used to compare numbers.

Not my experience.

In fact, anyone who reads
https://www.gnu.org/software/emacs/manual/html_mono/elisp.html#Equality-Predicates
today would come away with the reassuring knowledge that "If object1
and object2 are integers with the same value, they are considered to
be the same object (i.e., eq returns t)."

And there's plenty of code that uses eq to compare numbers, on the
master branch, today.

So whether you learn by experience or by "stable" documentation,
you'll pick up the habit of comparing integers with eq.

> If anything, the introduction of bignums helps driving the point home: up to and including Emacs 26, elisp programmers could get away with eq for integers but not floating-point numbers. Now, the rules are simpler. (Characters still get a free pass, I suppose.)

What are the rules, then? "Use eql, except if you're comparing against
a small integer, when eq is fine, or a character, which might not be
that small but will be fine, or a number you know from studying the
Emacs internals is a fixnum"?

> While we could document a safe range of fixnums for which eq applies, it's probably better not to.

My impression was people were very careful to use eq and EQ whenever
they could prove the numbers were still in fixnum range.

> > Technically, I think code such as
> >
> > (cond ((eq a b) 1) ((not (eq a b)) 2) (t 3))
> >
> > is allowed to return 3. We should attempt not to make changes that
> > make this more likely, though.
>
> Given the state of elisp byte-code optimisation, there is plenty of room for improvements before such semantics become unavoidable. In particular, the committed change does not in any way enable such paradoxical behaviour.

(defun f ()
  (cond
   ((eq 1.0 1.0) 1)
   ((my-not-eq 1.0 1.0) 2)
   (t 3))))

produces 3 here, with your patch and standard byte compilation. That
seems just as paradoxical to me.

(You're right about hash tables).

> > You're right, that is eq's contract. But people do misuse it, and one
> > of the things they wouldn't expect is that optimization results in
> > things becoming non-eq that were eq before optimization; I think the
> > other direction is much less problematic.
>
> Good thing that the change works in that other direction then!

Sorry, I may have been ambiguous: With your patch, (eq 1.0 1.0) is t
without optimization, nil with optimization. That's the direction I
meant.

> >> What would anyone gain from such a restriction? And the change is minor because it's a small thing to do; what I thought looked like an obvious oversight, or one that made more sense back when Elisp didn't have bignums.
> >
> > Well, Elisp has had floats for a while, and bignum constants appear to
> > be nonexistent, so far.
>
> In other words, there is no broken bignum code that can break.

Sorry, that was a response to the second part: the original code makes
just as much sense now as it did in the pre-bignum age. You're right
that folding floats but not bignums is probably a bad idea.

This probably isn't leading anywhere, but I still think this snippet
of code is somewhat realistic and should never output "1 nil". First
we count the number of eq-distinct elements, then we check whether the
elements are eq-distinct.

(defun count-distinct-elements (&rest args)
  (let ((ht (make-hash-table :test 'eq)))
    (dolist (arg args)
      (puthash arg 1 ht))
    (hash-table-count ht)))

(defmacro f (x y)
  `(format "%S %S" (count-distinct-elements ,x ,y) (eq ,x ,y)))

(defun g ()
  (f 1.0 1.0))

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Mattias Engdegård]

29 dec. 2019 kl. 18.29 skrev Pip Cet <pipcet@gmail.com>:

> On Sat, Dec 28, 2019 at 6:50 PM Mattias Engdegård <mattiase@acm.org> wrote:
>> Elisp has a few 'boundedly undefined' parts which would be avoided in a greenfield design but that we are more or less stuck with for the time being, and probably should paint in large letters on the first page of the manual. Such as: don't use eq for numbers; don't mutate literals (strings, conses, vectors); etc.
> 
> I don't think we're stuck with those two, and I don't think we should
> be making them worse than they already are (in Emacs 26.3).

I have some sympathy for the eq=eql idea but the faster we make elisp, the harder such a change becomes (since the difference in speed becomes more apparent).

> [...] I think your change isn't as
> trivial as it seems at first glance, and we shouldn't do it for Emacs
> 27, but it's fine on the master branch and might help us shake out
> some bugs (and, strategically, the paradoxical behavior observed with
> your patch is a good argument for making eq and eql synonymous).

Thanks for clarifying. I'll try to be brief; we seem to agree on the important points.

>> In my experience people seem to have little trouble understanding that eq shouldn't be used to compare numbers.
> 
> Not my experience.

Sorry, I meant observing and teaching programming in Scheme and (Common) Lisp, both having a similar eq/eql split. Elisp is special in that eq has until now always worked for all integers, so naturally there is a substantial body of code written that way, both inside and outside Emacs.

> In fact, anyone who reads
> https://www.gnu.org/software/emacs/manual/html_mono/elisp.html#Equality-Predicates
> today would come away with the reassuring knowledge that "If object1
> and object2 are integers with the same value, they are considered to
> be the same object (i.e., eq returns t)."

Good point. The revised text (in Emacs 27) still gives fixnums a prominent place; perhaps it should be toned down?

> So whether you learn by experience or by "stable" documentation,
> you'll pick up the habit of comparing integers with eq.

Yet habits will have to change whether the deduplication change stays or not, since we have bignums and eq≠eql. I'm confident that people can learn new rules if properly taught.

> What are the rules, then? "Use eql, except if you're comparing against
> a small integer, when eq is fine, or a character, which might not be
> that small but will be fine, or a number you know from studying the
> Emacs internals is a fixnum"?

If it were up to me, the simple rule should be not to use eq for numbers. Anything else is fine-print.

> My impression was people were very careful to use eq and EQ whenever
> they could prove the numbers were still in fixnum range.

Maybe the manual put excessive emphasis on performance?
Programmers who learn from a too early reading of code hand-tuned by experts tend to pick up some questionable habits no matter the language.

> (defun f ()
>  (cond
>   ((eq 1.0 1.0) 1)
>   ((my-not-eq 1.0 1.0) 2)
>   (t 3))))
> 
> produces 3 here, with your patch and standard byte compilation. That
> seems just as paradoxical to me.

It's not hard to produce a contradiction if starting from a false premise, in this case "eq on numbers yields a useful or at least consistent result".

The same is true for your hash-table example: replace 1.0 with "abc", and you will get the same (contradictory-looking) result, since the compiler deduplicates strings, too. Distinct literals may or may not be eq.

>> Good thing that the change works in that other direction then!
> 
> Sorry, I may have been ambiguous: With your patch, (eq 1.0 1.0) is t
> without optimization, nil with optimization. That's the direction I
> meant.

I understand, and it is I who should apologise for the clever tone in my answer.

bug#38708: [PATCH] Deduplicate flonum and bignum constants in bytecode

[Eli Zaretskii]

> From: Mattias Engdegård <mattiase@acm.org>
> Date: Sun, 29 Dec 2019 23:30:32 +0100
> Cc: 38708@debbugs.gnu.org
> 
> Thanks for clarifying. I'll try to be brief; we seem to agree on the important points.

PLEASE take this discussion to emacs-devel.  These are serious
matters, they shouldn't be discussed on the bug list.

TIA