"simplifications"

"simplifications"

[David Kastrup]

Hi, I've seen the following:

Author: Juanma Barranquero <lekktu@gmail.com>  2007-11-17 03:50:37
Committer: Juanma Barranquero <lekktu@gmail.com>  2007-11-17 03:50:37
Parent: 1797ed583c1d6224dbe93db681b112a9b0278358 ((backquote): Improve argument/docstring consistency.)
Child:  034e6631c9aab6db046645510214df80e67c29d4 (*** empty log message ***)
Branches: master, remotes/origin/master, remotes/origin/origin
Follows: merge-multi-tty-to-trunk
Precedes: 

    (ring-size, ring-p, ring-insert, ring-length, ring-empty-p): Use c[ad]dr.
    (ring-plus1): Use `1+'.
    (ring-minus1): Use `zerop'.
    (ring-remove): Use c[ad]dr.  Use `when'.
    (ring-copy): Use c[ad]dr.  Use `let', not `let*'.
    (ring-ref): Use `let', not `let*'.
    (ring-insert-at-beginning): Use c[ad]dr.  Doc fix.
    (ring-insert+extend): Use c[ad]dr.  Fix typo in docstring.
    (ring-member): Simplify.  Doc fix.
    (ring-convert-sequence-to-ring): Simplify.


Could people, before introducing such "optimizations", check the
bytecode?

(defun xxx (x) (cadr x))
generates
byte code for xxx:
  args: (x)
0	varref	  x
1	dup	  
2	varbind	  x
3	cdr	  
4	car	  
5	unbind	  1
6	return	  

while
(defun xxx (x) (car (cdr x)))
generates
byte code for xxx:
  args: (x)
0	varref	  x
1	cdr	  
2	car	  
3	return	  

The former is _quite_ less efficient, so it is not a hot idea to use
it for data access primitives like the ring functions.

Personally, I think that we should make the byte compiler optimize the
unnecessary binding away.  But until that is the case, please don't
gratuitously replace (car (cdr ...)) with (cadr ...).

-- 
David Kastrup

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 11:46 AM, David Kastrup <dak@gnu.org> wrote:

> Could people, before introducing such "optimizations", check the
> bytecode?

Some functions of ring.el already used c??r before my change. etc.

> The former is _quite_ less efficient, so it is not a hot idea to use
> it for data access primitives like the ring functions.

Out of idle curiosity, I'd be really interested in knowing about uses
of ring.el where that difference is going to be significant (i.e.,
we're speaking perhaps of thousands of ring function calls per
second?).

> Personally, I think that we should make the byte compiler optimize the
> unnecessary binding away.  But until that is the case, please don't
> gratuitously replace (car (cdr ...)) with (cadr ...).

I don't usually do it gratuitously, or I would've done it in a lot of
places. I stumbled upon it, and certainly having code chock-full of

 (let ((hd (car (car ...)))
        (ln (car ...))
        (vec (cdr (cdr ...))))

is not my idea of fun, or legible, or maintainable, or... you pick the
word. Not that c??r is much of an improvement; we should be able to
define accesor functions in the package

 (defsubst ring--vec (ring)
    (cdr (cdr ring)))

and have the byte-compiler optimize them away.

So, IMO, instead of bringing back the pain, let's enhance the byte-optimizer.

But of course, you can revert the change if you dislike it that much.

             Juanma

Re: "simplifications"

[Stefan Monnier]

> is not my idea of fun, or legible, or maintainable, or... you pick the
> word. Not that c??r is much of an improvement; we should be able to
> define accesor functions in the package

>  (defsubst ring--vec (ring)
>     (cdr (cdr ring)))

> and have the byte-compiler optimize them away.

1 - if you use defsubst* the byte-code will look good.
2 - you can use defstruct to get all that and more.
3 - I don't think it's worth the trouble to make the byte-optimizer more
    complex for such little benefit.  If you want to improve it, use the
    lexbind branch: it's a much saner starting point.


        Stefan "whose local Emacs hacks include some byte-optimizer
                improvement which does manage to optimize `cadr' but it's too
                much work works with too many limitations and on top of
                that, it's not even clear that the optimization is
                always correct: it doesn't account for the case where
                you do
                (defsubst cadr (debug-on-error) (car (cdr debug-on-error)))
                in which case the optimization is not semantics preserving"

Re: "simplifications"

[David Kastrup]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> is not my idea of fun, or legible, or maintainable, or... you pick the
>> word. Not that c??r is much of an improvement; we should be able to
>> define accesor functions in the package
>
>>  (defsubst ring--vec (ring)
>>     (cdr (cdr ring)))
>
>> and have the byte-compiler optimize them away.
>
> 1 - if you use defsubst* the byte-code will look good.
> 2 - you can use defstruct to get all that and more.
> 3 - I don't think it's worth the trouble to make the byte-optimizer more
>     complex for such little benefit.  If you want to improve it, use the
>     lexbind branch: it's a much saner starting point.
>
>
>         Stefan "whose local Emacs hacks include some byte-optimizer
>                 improvement which does manage to optimize `cadr' but it's too
>                 much work works with too many limitations and on top of
>                 that, it's not even clear that the optimization is
>                 always correct: it doesn't account for the case where
>                 you do
>                 (defsubst cadr (debug-on-error) (car (cdr debug-on-error)))
>                 in which case the optimization is not semantics preserving"

defsubst is an advanced construct.  I think it is reasonable to give
fewer guarantees about its operation than we do for defun.

-- 
David Kastrup

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 4:11 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> 1 - if you use defsubst* the byte-code will look good.

Nice. Thanks!

> 2 - you can use defstruct to get all that and more.

Yes. It's not my code; it it were, I would be using defstruct. I'm a
big Common Lisp fan.

> 3 - I don't think it's worth the trouble to make the byte-optimizer more
>     complex for such little benefit.  If you want to improve it, use the
>     lexbind branch: it's a much saner starting point.

Isn't that branch supposed to be merged back someday?

> it doesn't account for the case where
> you do
> (defsubst cadr (debug-on-error) (car (cdr debug-on-error)))
> in which case the optimization is not semantics preserving"

And I'n not sure it should... I think I agree with David here: if
you're using defsubst to optimize, you should expect some gotchas.

             Juanma

Re: "simplifications"

[Stefan Monnier]

>> it doesn't account for the case where
>> you do
>> (defsubst cadr (debug-on-error) (car (cdr debug-on-error)))
>> in which case the optimization is not semantics preserving"

> And I'n not sure it should... I think I agree with David here: if
> you're using defsubst to optimize, you should expect some gotchas.

Well, my optimization is not specific to defsubst, so it will also
remove the let-binding in:

   (let ((debug-on-error t))
     (car (car (cdr x))))


In any case, if you want a "fast and loose" defsubst, it's there already
under the name defsubst*.


        Stefan

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 4:44 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> Well, my optimization is not specific to defsubst, so it will also
> remove the let-binding in:
>
>    (let ((debug-on-error t))
>      (car (car (cdr x))))

Why? There can be no dynamic bindings under that optimization?

> In any case, if you want a "fast and loose" defsubst, it's there already
> under the name defsubst*.

I'll remember it. Thanks again.

             Juanma

Re: "simplifications"

[Stefan Monnier]

>> Well, my optimization is not specific to defsubst, so it will also
>> remove the let-binding in:
>> 
>> (let ((debug-on-error t))
>> (car (car (cdr x))))

> Why? There can be no dynamic bindings under that optimization?

Of course, there can, but it knows about primitives that don't use any
dynamically bound variables.  Oh well... except for those funny ones
like debug-on-error which are used virtually everywhere.


        Stefan

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 4:58 PM, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

> Of course, there can, but it knows about primitives that don't use any
> dynamically bound variables.  Oh well... except for those funny ones
> like debug-on-error which are used virtually everywhere.

I'm absolutely sure I'm asking something really obvious, but, why
wouldn't simply work to have a list of dynamic variables whose
bindings Just Can Not be optimized away?

             Juanma

Re: "simplifications"

[Stefan Monnier]

>> Of course, there can, but it knows about primitives that don't use any
>> dynamically bound variables.  Oh well... except for those funny ones
>> like debug-on-error which are used virtually everywhere.

> I'm absolutely sure I'm asking something really obvious, but, why
> wouldn't simply work to have a list of dynamic variables whose
> bindings Just Can Not be optimized away?

It would probably work.  I just haven't done it, and given my experience
with this optimization, I'm unlikely to ever do it.


        Stefan

Re: "simplifications"

[David Kastrup]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>> it doesn't account for the case where
>>> you do
>>> (defsubst cadr (debug-on-error) (car (cdr debug-on-error)))
>>> in which case the optimization is not semantics preserving"
>
>> And I'n not sure it should... I think I agree with David here: if
>> you're using defsubst to optimize, you should expect some gotchas.
>
> Well, my optimization is not specific to defsubst, so it will also
> remove the let-binding in:
>
>    (let ((debug-on-error t))
>      (car (car (cdr x))))
>
>
> In any case, if you want a "fast and loose" defsubst, it's there already
> under the name defsubst*.

For a suitable value of "there":

(describe-function 'defsubst*)
Debugger entered--Lisp error: (void-function defsubst*)
  describe-function-1(defsubst*)
  describe-function(defsubst*)
  eval((describe-function (quote defsubst*)))
  eval-last-sexp-1(nil)
  eval-last-sexp(nil)
  call-interactively(eval-last-sexp)

-- 
David Kastrup

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 5:02 PM, David Kastrup <dak@gnu.org> wrote:

> For a suitable value of "there":

It's an (eval-when-compile (require 'cl)) away, of which there are
186+ in the lisp/* tree.

             Juanma

Re: "simplifications"

[Richard Stallman]

    >> it doesn't account for the case where
    >> you do
    >> (defsubst cadr (debug-on-error) (car (cdr debug-on-error)))
    >> in which case the optimization is not semantics preserving"

I think it is fine to treat the args of a defsubst function
in a special way, as long as we document that.  However,
it would be easy enough to turn off the optimization for variables
that are defvar'd.

    Well, my optimization is not specific to defsubst, so it will also
    remove the let-binding in:

       (let ((debug-on-error t))
	 (car (car (cdr x))))

Which optimization is that one?  It too needs something to prevent it
from removing that binding, such as don't remove bindings for
variables that have been defvar'd.

The optimization I suggested would apply to the expansion of defsubst
calls.  So it would not apply to `let' expressions that originate
in other ways.

Re: "simplifications"

[Stefan Monnier]

>     Well, my optimization is not specific to defsubst, so it will also
>     remove the let-binding in:

>        (let ((debug-on-error t))
> 	 (car (car (cdr x))))

> Which optimization is that one?

Some optimization with which I played locally.  I still have it in my
tree, but all I got from it is an understanding that it's not the right
way to approach the problem :-)


        Stefan

Re: "simplifications"

[Stephen J. Turnbull]

Stefan Monnier writes:

 > Some optimization with which I played locally.  I still have it in my
 > tree, but all I got from it is an understanding that it's not the right
 > way to approach the problem :-)

What, not even a "stupid T-shirt"?

Re: "simplifications"

[David Kastrup]

"Stephen J. Turnbull" <stephen@xemacs.org> writes:

> Stefan Monnier writes:
>
>  > Some optimization with which I played locally.  I still have it in my
>  > tree, but all I got from it is an understanding that it's not the right
>  > way to approach the problem :-)
>
> What, not even a "stupid T-shirt"?

Without so much as a binding, it essentially becomes a single thread.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: "simplifications"

[Stephen J. Turnbull]

David Kastrup writes:
 > "Stephen J. Turnbull" <stephen@xemacs.org> writes:
 > 
 > > Stefan Monnier writes:
 > >
 > >  > Some optimization with which I played locally.  I still have it in my
 > >  > tree, but all I got from it is an understanding that it's not the right
 > >  > way to approach the problem :-)
 > >
 > > What, not even a "stupid T-shirt"?
 > 
 > Without so much as a binding, it essentially becomes a single thread.

*splutter*

David, you owe me *three* monitor wipes ... 

Re: "simplifications"

[Juanma Barranquero]

Two additional comments, BTW:

> Could people, before introducing such "optimizations", check the
> bytecode?

I didn't write "optimization" anywhere in the ChangeLog, because I was
not worried about optimization.

If you're gonna revert the change, perhaps you'll want also revert the
one to ring-member. My version, with catch, is a lot cleaner IMO, but
in my extremely informal tests (which I did before commiting) it was
about 1,5% slower. I had to go to the hundreds of thousands of
ring-member invocations to see the difference, but perhaps that's very
significant for you.

             Juanma

Re: "simplifications"

[Miles Bader]

David Kastrup <dak@gnu.org> writes:
> Personally, I think that we should make the byte compiler optimize the
> unnecessary binding away.

It'd be nice if it did, though you need to analyze the function to make
sure there are no hidden uses of that binding; in particular, you need
to know if any functions called inside the defsubst might use the
dynamic binding of the defsubst's args.

[I personally think that's a bit silly, and that it would be enough to
just define defsubst as not guaranteeing dynamic bindings of its args,
but as a recall, this has been discussed before, and the current
behavior declared necessary...]

This is one area where lexical binding makes things cheaper:

   ;; -*- lexical-binding: t -*-
   (defsubst lcadr (arg) (car (cdr arg)))
   (defun xxx (x) (lcadr x))

=>

   byte code for xxx:
     args: (x)
    interactive: nil
   0	dup	  
   1	cdr	  
   2	car	  
   3	return	  

The "dup" is because stack slot 0 is where argument "x" is kept.
[Since x is only used once, the dup is unnecessary here, but it's
certainly cheaper than varref+varbind.]

-Miles
-- 
80% of success is just showing up.  --Woody Allen

Re: "simplifications"

[David Kastrup]

Miles Bader <miles.bader@necel.com> writes:

> David Kastrup <dak@gnu.org> writes:
>> Personally, I think that we should make the byte compiler optimize the
>> unnecessary binding away.
>
> It'd be nice if it did, though you need to analyze the function to make
> sure there are no hidden uses of that binding; in particular, you need
> to know if any functions called inside the defsubst might use the
> dynamic binding of the defsubst's args.
>
> [I personally think that's a bit silly, and that it would be enough to
> just define defsubst as not guaranteeing dynamic bindings of its args,
> but as a recall, this has been discussed before, and the current
> behavior declared necessary...]

My recollection was rather that optimizing such cases (for a suitable
definition of "such") was deemed a good idea, but too invasive for the
Emacs 22 release schedule.

-- 
David Kastrup

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 12:57 PM, David Kastrup <dak@gnu.org> wrote:

> My recollection was rather that optimizing such cases (for a suitable
> definition of "such") was deemed a good idea, but too invasive for the
> Emacs 22 release schedule.

FWIW, my c??r changes to ring.el were commited only to the trunk.

             Juanma

Re: "simplifications"

[David Kastrup]

"Juanma Barranquero" <lekktu@gmail.com> writes:

> On Nov 19, 2007 12:57 PM, David Kastrup <dak@gnu.org> wrote:
>
>> My recollection was rather that optimizing such cases (for a suitable
>> definition of "such") was deemed a good idea, but too invasive for the
>> Emacs 22 release schedule.
>
> FWIW, my c??r changes to ring.el were commited only to the trunk.

I was not suggesting reverting the changes.  It is not important
enough for that sort of back-and-forth changing.  On the other hand,
as long as it degrades code quality, I'd prefer people to refrain from
doing large-scale "cleanups" or "simplifications" of that kind.
Before we are starting a trend here, it would be nice if the
optimizations making such changes not have an impact on efficiency
would be in place.

-- 
David Kastrup

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 1:21 PM, David Kastrup <dak@gnu.org> wrote:

> On the other hand,
> as long as it degrades code quality

"Code quality" is an ambiguous metric, unless you define it. I suppose
you're using some variant of the "code quality = efficiency"
equivalence. Obviously I wasn't. That does not mean that I didn't
think of efficiency (I did, or I wouldn't have done measurements of
ring-member's speed). Though I agree that currently (car (cdr x)) is
faster than (cadr x), I still don't see how that will affect much to
clients of ring.el unless they're doing a quite performance-oriented
use of it. OTOH, code is a bit more readable now IMHO.

> I'd prefer people to refrain from
> doing large-scale "cleanups" or "simplifications" of that kind.

That's about a dozen trivial changes in a package with 165 non-empty,
non-comment lines. Perhaps we should previously agree also in the
definition of "large scale".

> Before we are starting a trend here, it would be nice if the
> optimizations making such changes not have an impact on efficiency
> would be in place.

With this, I agree. You see, I was sure we would find some common
ground after all...

             Juanma

Re: "simplifications"

[David Kastrup]

"Juanma Barranquero" <lekktu@gmail.com> writes:

> On Nov 19, 2007 1:21 PM, David Kastrup <dak@gnu.org> wrote:
>
>> On the other hand,
>> as long as it degrades code quality
>
> "Code quality" is an ambiguous metric, unless you define it. I suppose
> you're using some variant of the "code quality = efficiency"
> equivalence. Obviously I wasn't. That does not mean that I didn't
> think of efficiency (I did, or I wouldn't have done measurements of
> ring-member's speed). Though I agree that currently (car (cdr x)) is
> faster than (cadr x), I still don't see how that will affect much to
> clients of ring.el unless they're doing a quite performance-oriented
> use of it. OTOH, code is a bit more readable now IMHO.
>
>> I'd prefer people to refrain from
>> doing large-scale "cleanups" or "simplifications" of that kind.
>
> That's about a dozen trivial changes in a package with 165 non-empty,
> non-comment lines. Perhaps we should previously agree also in the
> definition of "large scale".

I am afraid that you are really too eager to interpret my mails as a
personal critique of you and this particular change.  Again: I don't
think this particular case nearly important or relevant enough to
warrant reverting those changes.  But it is not the first such change
I see, and I would prefer to see changes in the byte compiler that
would make such changes a no-brainer, where one does not have to weigh
code efficiency vs. readability.

-- 
David Kastrup

Re: "simplifications"

[Juanma Barranquero]

On Nov 19, 2007 1:49 PM, David Kastrup <dak@gnu.org> wrote:

> I am afraid that you are really too eager to interpret my mails as a
> personal critique of you and this particular change.

I ask you about definitions, and suddenly I'm "eager to interpret
[...] emails as a personal critique". Curious.

> But it is not the first such change
> I see, and I would prefer to see changes in the byte compiler that
> would make such changes a no-brainer, where one does not have to weigh
> code efficiency vs. readability.

Then perhaps these kinds of changes, in the trunk, will be useful by
furthering the relevance of the issue.

             Juanma

Re: "simplifications"

[Richard Stallman]

    Personally, I think that we should make the byte compiler optimize the
    unnecessary binding away.  But until that is the case, please don't
    gratuitously replace (car (cdr ...)) with (cadr ...).

Maybe we could improve the handling of defsubst
to recognize that that binding is unnecessary.
To handle simple cases like this, it is enough to scan
the bytecode instructions and see that they don't call
any functions or refer to that variable.

I think the place to do this is in `byte-compile-unfold-lambda'.

Is someone interested?