byte-code optimizations

byte-code optimizations

[Paul Pogonyshev]

Hi.

Are you interested in byte-code optimizations?  I think I found
a rather good one, specifically targeted at `c[ad][ad]r' substs.
It can be generalized further, though.

Consider this hypothetical function:

	(lambda (x)
	  (cons (caar x) (cddr x)))

With current Emacs byte-compiler we get

	M-: (disassemble (lambda (x) (cons (caar x) (cddr x))))

byte code:
  args: (x)
0	varref	  x
1	dup	  
2	varbind	  x
3	car	  
4	car	  
5	unbind	  1
6	varref	  x
7	dup	  
8	varbind	  x
9	cdr	  
10	cdr	  
11	unbind	  1
12	cons	  
13	return	  

With the patch (see the very end of this message), this, however,
reduces simply to

byte code:
  args: (x)
0	varref	  x
1	car	  
2	car	  
3	varref	  x
4	cdr	  
5	cdr	  
6	cons	  
7	return	  

In other words, it squeezes the unnecessary binding out of each
`c[ad][ad]r'.  Three commands per each substitution.  This is a
lightweight (and special-cases-only) implementation of a TODO
item in `byte-opt.el'.

If you are interested, I can polish the patch and generalize it
a bit.

Currently, there is one unresolved problem with the patch.  In
`byte-opt.el' top comment it is mentioned that ``However certain
variables should never have their bindings optimized away,
because they affect everything.'' (i.e. `debug-on-error').

I doubt this is particularly important for bindings followed
by car/cdr sequences, but it is certainly better not to left
open pits.

There is also an obvious way to improve: in addition to
`byte-c[ad]r' certain other byte commands can be allowed in
sequences, i.e. `byte-not'.

Comments and suggestions are welcome.

Paul



--- byte-opt.el	22 Mar 2004 13:21:08 -0200	1.75
+++ byte-opt.el	18 Sep 2004 11:04:59 -0200	
@@ -1993,6 +1993,22 @@ If FOR-EFFECT is non-nil, the return val
 		 (byte-compile-log-lap
 		  "  %s [dup/%s]...\t-->\t%s dup..." lap0 lap0 lap0)))
 	    ;;
+	    ;; dup varbind-X [car/cdr ...] unbind-1 --> [car/cdr ...]
+	    ;;
+	    ((and (eq 'byte-dup     (car lap0))
+		  (eq 'byte-varbind (car lap1)))
+	     (setq tmp (cdr rest))
+	     (while (memq (caar (setq tmp (cdr tmp))) '(byte-car byte-cdr)))
+	     (when (and (eq 'byte-unbind (caar tmp)) (= 1 (cdar tmp)))
+	       ;; Throw away  dup varbind-X
+	       (setcar rest (nth 2 rest))
+	       (setcdr rest (nthcdr 3 rest))
+	       ;; Throw away unbind-1
+	       (setcar tmp (nth 1 tmp))
+	       (setcdr tmp (nthcdr 2 tmp))
+	       (byte-compile-log-lap
+		"  dup %s [car/cdr ...] unbind-1\t-->\t[car/cdr...]" lap1)))
+	    ;;
 	    ;; unbind-N unbind-M  -->  unbind-(N+M)
 	    ;;
 	    ((and (eq 'byte-unbind (car lap0))

Re: byte-code optimizations

[Stefan]

> +	    ;; dup varbind-X [car/cdr ...] unbind-1 --> [car/cdr ...]

I get the same optimization result by adding

        car/cdr/equal/nth unbind --> unbind car/cdr/equal/nth

Problem is that such an optimization is only safe if car/cdr/... is not
affected by the bound thing.  If the `unbind' unbinds a variable, then
I think it's always safe.  So I've added to the lapcode optimizer some logic
to keep track of the specpdl stack so that I can distinguish an unbind that
terminates a varbind from one that terminates an unwind-protect.

Better yet: you also get the exact same result code (without any lapcode
optimization) if you use

   (defsubst* cddr (x) (cdr (cdr x)))

I.e. using the `defubst*' (from CL).


        Stefan

Re: byte-code optimizations

[Richard Stallman]

    In other words, it squeezes the unnecessary binding out of each
    `c[ad][ad]r'.  Three commands per each substitution.

I see, those wasteful operations come from defsubst expansion.  Can
you generalize your optimization so it is not limited to car and cdr
operations in the middle?  It ought to be simple to handle many other
cases, as long as there are no jumps inside.

Re: byte-code optimizations

[Richard Stallman]

    Better yet: you also get the exact same result code (without any lapcode
    optimization) if you use

       (defsubst* cddr (x) (cdr (cdr x)))

    I.e. using the `defubst*' (from CL).

What aspect of that definition leads to better results?
Can we change the standard defsubst in a simple way
to achieve the same thing?

Re: byte-code optimizations

[Paul Pogonyshev]

Stefan wrote:

> > +	    ;; dup varbind-X [car/cdr ...] unbind-1 --> [car/cdr ...]
>
> I get the same optimization result by adding
>
>         car/cdr/equal/nth unbind --> unbind car/cdr/equal/nth
>
> Problem is that such an optimization is only safe if car/cdr/... is not
> affected by the bound thing.  If the `unbind' unbinds a variable, then
> I think it's always safe.  So I've added to the lapcode optimizer some
> logic to keep track of the specpdl stack so that I can distinguish an
> unbind that terminates a varbind from one that terminates an
> unwind-protect.

Seems like you are trying to solve this problem (in comment):

(defconst byte-after-unbind-ops
   '(byte-constant byte-dup
     byte-symbolp byte-consp byte-stringp byte-listp byte-numberp byte-integerp
     byte-eq byte-not
     byte-cons byte-list1 byte-list2	; byte-list3 byte-list4
     byte-interactive-p)
   ;; How about other side-effect-free-ops?  Is it safe to move an
   ;; error invocation (such as from nth) out of an unwind-protect?
   ;; No, it is not, because the unwind-protect forms can alter
   ;; the inside of the object to which nth would apply.
   ;; For the same reason, byte-equal was deleted from this list.
   "Byte-codes that can be moved past an unbind.")

If you can properly track `unwind-protect' unbinds, then your
optimization is probably better.

> Better yet: you also get the exact same result code (without any lapcode
> optimization) if you use
>
>    (defsubst* cddr (x) (cdr (cdr x)))
>
> I.e. using the `defubst*' (from CL).

Is there a reason to use `defsubst' then?  Do `defsubst' and
`defsubst*' differ in result?  (Frankly speaking, I cannot read
it.)

RMS wrote:

>     In other words, it squeezes the unnecessary binding out of each
>     `c[ad][ad]r'.  Three commands per each substitution.
> 
> I see, those wasteful operations come from defsubst expansion.  Can
> you generalize your optimization so it is not limited to car and cdr
> operations in the middle?  It ought to be simple to handle many other
> cases, as long as there are no jumps inside.

My latest version is below.  I generalized it (skips all byte-codes
in `byte-compile-side-effect-free-dynamically-safe-ops' plus
`byte-varref' which reference another variable.  I also implemented
the `binding-is-magic' property suggested in TODO section and a few
other generalizations.

However, we (actually Stefan) need to decide whether we want to try
optimizing unbinds without visible bindings.  I.e. I'm optimizing

	varbind-X ... unbind-N --> discard ... unbind-(N-1)

while Stefan suggests a more general

	... unbind-1 --> unbind-1 ...

which is then followuped by other (existing) optimizations.

Paul



--- byte-opt.el	22 Mar 2004 13:21:08 -0200	1.75
+++ byte-opt.el	19 Sep 2004 14:00:27 -0200	
@@ -1467,6 +1467,33 @@ of FORM by signalling the error at compi
      byte-member byte-assq byte-quo byte-rem)
    byte-compile-side-effect-and-error-free-ops))
 
+(defconst byte-compile-side-effect-free-dynamically-safe-ops
+  '(;; Same as `byte-compile-side-effect-free-ops' but without
+    ;; `byte-varref', `byte-symbol-value' and certain editing
+    ;; primitives.
+    byte-constant byte-dup byte-symbolp byte-consp byte-stringp byte-listp
+    byte-integerp byte-numberp byte-eq byte-equal byte-not byte-car-safe
+    byte-cdr-safe byte-cons byte-list1 byte-list2 byte-point byte-point-max
+    byte-point-min byte-following-char byte-preceding-char
+    byte-eolp byte-eobp byte-bolp byte-bobp
+    ;;
+    byte-nth byte-memq byte-car byte-cdr byte-length byte-aref
+    byte-get byte-concat2 byte-concat3 byte-sub1 byte-add1
+    byte-eqlsign byte-gtr byte-lss byte-leq byte-geq byte-diff byte-negate
+    byte-plus byte-max byte-min byte-mult byte-char-after
+    byte-string= byte-string< byte-nthcdr byte-elt
+    byte-member byte-assq byte-quo byte-rem))
+
+(put 'debug-on-error 'binding-is-magic t)
+(put 'debug-on-abort 'binding-is-magic t)
+(put 'debug-on-next-call 'binding-is-magic t)
+(put 'inhibit-quit 'binding-is-magic t)
+(put 'quit-flag 'binding-is-magic t)
+(put 't 'binding-is-magic t)
+(put 'nil 'binding-is-magic t)
+(put 'gc-cons-threshold 'binding-is-magic t)
+(put 'track-mouse 'binding-is-magic t)
+
 ;; This crock is because of the way DEFVAR_BOOL variables work.
 ;; Consider the code
 ;;
@@ -1871,6 +1898,55 @@ If FOR-EFFECT is non-nil, the return val
 		      (setq lap (delq lap0 lap))))
 	       (setq keep-going t))
 	      ;;
+	      ;; varbind-X [car/cdr/ ...] unbind-1 --> discard [car/cdr/ ...]
+	      ;; varbind-X [car/cdr/ ...] unbind-N
+	      ;;   --> discard [car/cdr/ ...] unbind-(N-1)
+	      ;;
+	      ((and (eq 'byte-varbind (car lap1))
+		    (not (get (cadr lap1) 'binding-is-magic)))
+	       (setq tmp (cdr rest))
+	       (while
+		   (or
+		    (memq (caar (setq tmp (cdr tmp)))
+			  byte-compile-side-effect-free-dynamically-safe-ops)
+		    (and (eq (caar tmp) 'byte-varref)
+			 (not (eq (cadr (car tmp)) (cadr lap1))))))
+	       (when (eq 'byte-unbind (caar tmp))
+		 ;; Avoid evalling this crap when not logging anyway
+		 (when (memq byte-optimize-log '(t lap))
+		   (let ((format-string)
+			 (args))
+		     (if (and (= (aref byte-stack+-info (symbol-value (car lap0)))
+				1)
+			      (memq (car lap0) side-effect-free))
+			 (setq format-string
+			       "  %s %s [car/cdr/ ...] %s\t-->\t[car/cdr/ ...]"
+			       args (list lap0 lap1 (car tmp)))
+		       (setq format-string
+			     "  %s [car/cdr/ ...] %s\t-->\t%s [car/cdr/ ...]"
+			     args (list lap1 (car tmp) (cons 'byte-discard 0))))
+		     (when (> (cdar tmp) 1)
+		       (setq format-string (concat format-string " %s"))
+		       (nconc args (list (cons 'byte-unbind (1- (cdar tmp))))))
+		     (apply 'byte-compile-log-lap-1 format-string args)))
+		 ;; Do the real work
+		 (if (and (= (aref byte-stack+-info (symbol-value (car lap0)))
+			     1)
+			  (memq (car lap0) side-effect-free))
+		     ;; Optimization: throw const/dup/... varbind right away.
+		     (progn
+		       (setcar rest (nth 2 rest))
+		       (setcdr rest (nthcdr 3 rest)))
+		   (setcar lap1 'byte-discard)
+		   (setcdr lap1 0))
+		 (if (= (cdar tmp) 1)
+		     (progn
+		       ;; Throw away unbind-1
+		       (setcar tmp (nth 1 tmp))
+		       (setcdr tmp (nthcdr 2 tmp)))
+		   (setcdr (car tmp) (1- (cdar tmp))))
+		 (setq keep-going t)))
+	      ;;
 	      ;; X: varref-Y    ...     varset-Y goto-X  -->
 	      ;; X: varref-Y Z: ... dup varset-Y goto-Z
 	      ;; (varset-X goto-BACK, BACK: varref-X --> copy the varref down.)

Re: byte-code optimizations

[Richard Stallman]

    However, we (actually Stefan) need to decide whether we want to try
    optimizing unbinds without visible bindings.  I.e. I'm optimizing

	    varbind-X ... unbind-N --> discard ... unbind-(N-1)

    while Stefan suggests a more general

	    ... unbind-1 --> unbind-1 ...

    which is then followuped by other (existing) optimizations.

The way to decide this is to look at what the results would be in
various cases.  Simply doing the unbind-1 earlier is not a significant
improvement; it does not make the code smaller or faster.  As far as I
can see, the only way it achieves a benefit is if it leads to
eliminating the unbind-1.  That would only happen if Stefan's
optimization moves the unbind-1 back to right after a varbind, right?
If so is optimization is indirectly equivalent to yours.

I can see one other case where Stefan's optimization might make a
difference.  If we install your tail-jumping optimization, Stefan's
optimization might produce more opportunities to do tail-jumping, or
it might ruin some opportunities to do tail-jumping.  But I think
that effect will be too small to matter anyway.

Unless I have missed some point here, I think your version of the
optimization is the better of the two (all else being equal), because
it gets directly to the desired result instead of requiring it to be
done in two steps.

Some comments on details of your code:

    +(put 't 'binding-is-magic t)
    +(put 'nil 'binding-is-magic t)

That is unnecessary; you can't bind nil or t,

    +(put 'debug-on-next-call 'binding-is-magic t)

That is unnecessary, since a function call would never
be safe to do this optimization over,

    +(defconst byte-compile-side-effect-free-dynamically-safe-ops
    +  '(;; Same as `byte-compile-side-effect-free-ops' but without
    +    ;; `byte-varref', `byte-symbol-value' and certain editing
    +    ;; primitives.

Why exclude byte-symbol-value?

After you deal with those little points, I'd like your code to be
installed.  However, there is still the question of whether we should
change the standard defsubst to work the way defsubst* does.

Re: byte-code optimizations

[Stefan Monnier]

>> Unless I have missed some point here, I think your version of the
>> optimization is the better of the two (all else being equal), because
>> it gets directly to the desired result instead of requiring it to be
>> done in two steps.

> It must also be much simpler (though I never saw what Stefan had).

Yes, it's much simpler.  Also my code can break on some bytecode.
More specifically, my code requires that the specpdl stack be unique for any
given point in the byte-code, which is not the case for example if the
bytecode does the equivalent of

        if cond
           varbind X
        endif
        ...blabla...
        if cond
           unbind 1
        endif

AFAIK, my code works for any bytecode coming out of the current bytecode
compiler (barring bugs), but it might break with some other
bytecode compiler.

>> However, there is still the question of whether we should
>> change the standard defsubst to work the way defsubst* does.
> Maybe we can even use `defmacro' for `caar' and friends.  Since
> they evaluate their lone argument only once, there must not be
> any problems, right?

Just think of (mapcar 'caar x)

> If this (or `defsubst*') works, I'll investigate whether this
> byte-code optimization gives any improvement after such a change.

What defsubst* does is treat the argument as a kind of "lexically scoped"
variable, but only in very limited ways.  I.e. the

        (defsubst* caar (x) (car (car x)))

will expand:

        (caar y)  =>  (car (car y))
        (caar (f y)) => (let ((x (f y))) ..cl-gunk.. (car (car x)))

[ The cl-gunk is stuff added by CL for CL such as a `catch' statement. ]
If you ignore the nasty cl-gunk, I think the resulting optimization is
similar to what we get, except it works in a few more cases.
E.g. it'll expand

     (defsubst* foo (x) (symbol-value x))

     (foo y) => (symbol-value y)

whereas our optimization won't be able to do that because it can't assume
a "somewhat lexically scoped" semantics.


        Stefan

Re: byte-code optimizations

[Miles Bader]

On Tue, Sep 21, 2004 at 05:05:30PM -0400, Stefan Monnier wrote:
> What defsubst* does is treat the argument as a kind of "lexically scoped"
> variable, but only in very limited ways.  I.e. the
...
>      (defsubst* foo (x) (symbol-value x))
> 
>      (foo y) => (symbol-value y)
> 
> whereas our optimization won't be able to do that because it can't assume
> a "somewhat lexically scoped" semantics.

I vote for saying "you're not allowed to treat defsubst argument bindings as
normal dynamic bindings, and if you have tons of code that does, well screw
you, you're probably a crappy programmer anyway."

Maybe a bit more diplomatically.

-Miles
-- 
My spirit felt washed.  With blood.  [Eli Shin, on "The Passion of the Christ"]

Re: byte-code optimizations

[Miles Bader]

On Wed, Sep 22, 2004 at 01:31:59AM -0200, Paul Pogonyshev wrote:
> > I vote for saying "you're not allowed to treat defsubst argument bindings
> > as normal dynamic bindings, and if you have tons of code that does, well
> > screw you, you're probably a crappy programmer anyway."
> 
> While I do agree with this, it's generally better to avoid changing
> stabilized behaviour only for optimization reasons.  Otherwise,
> really-difficult-to-debug bugs can jump out of nowhere.

There's also a point where you have to just say "enough is enough".

-Miles
-- 
[|nurgle|]  ddt- demonic? so quake will have an evil kinda setting? one that
            will  make every christian in the world foamm at the mouth?
[iddt]      nurg, that's the goal

Re: byte-code optimizations

[Paul Pogonyshev]

>     However, we (actually Stefan) need to decide whether we want to try
>     optimizing unbinds without visible bindings.  I.e. I'm optimizing
>
> 	    varbind-X ... unbind-N --> discard ... unbind-(N-1)
>
>     while Stefan suggests a more general
>
> 	    ... unbind-1 --> unbind-1 ...
>
>     which is then followuped by other (existing) optimizations.
>
> The way to decide this is to look at what the results would be in
> various cases.  Simply doing the unbind-1 earlier is not a significant
> improvement; it does not make the code smaller or faster.  As far as I
> can see, the only way it achieves a benefit is if it leads to
> eliminating the unbind-1.  That would only happen if Stefan's
> optimization moves the unbind-1 back to right after a varbind, right?
> If so is optimization is indirectly equivalent to yours.

After a `varbind' or `unwind-protect' or similar.  However, I doubt
that those make much difference, so Stefan's optimization must be
_nearly_ equivalent to mine.

> I can see one other case where Stefan's optimization might make a
> difference.  If we install your tail-jumping optimization, Stefan's
> optimization might produce more opportunities to do tail-jumping, or
> it might ruin some opportunities to do tail-jumping.  But I think
> that effect will be too small to matter anyway.

In its current form tail-jumping optimization is executed only once,
after all other optimizations are made.  However, it can give better
results if run interchangeably with other optimizations, i.e. it
sometimes gives opportunities to optimize further.  Such an approach
may be too expensive in terms of optimization speed, so I left it
out at least for now.

> Unless I have missed some point here, I think your version of the
> optimization is the better of the two (all else being equal), because
> it gets directly to the desired result instead of requiring it to be
> done in two steps.

It must also be much simpler (though I never saw what Stefan had).

> Some comments on details of your code:
>
>     +(put 't 'binding-is-magic t)
>     +(put 'nil 'binding-is-magic t)
>
> That is unnecessary; you can't bind nil or t,

Removed (I followed suggestions in the comments to the top of the
file).

>     +(put 'debug-on-next-call 'binding-is-magic t)
>
> That is unnecessary, since a function call would never
> be safe to do this optimization over,

Removed.

>     +(defconst byte-compile-side-effect-free-dynamically-safe-ops
>     +  '(;; Same as `byte-compile-side-effect-free-ops' but without
>     +    ;; `byte-varref', `byte-symbol-value' and certain editing
>     +    ;; primitives.
>
> Why exclude byte-symbol-value?

Because value can change as the result of the binding we are
trying to eliminate.

> After you deal with those little points, I'd like your code to be
> installed.

Modified patch is below.

> However, there is still the question of whether we should
> change the standard defsubst to work the way defsubst* does.

Maybe we can even use `defmacro' for `caar' and friends.  Since
they evaluate their lone argument only once, there must not be
any problems, right?

If this (or `defsubst*') works, I'll investigate whether this
byte-code optimization gives any improvement after such a change.

Paul



--- byte-opt.el	22 Mar 2004 13:21:08 -0200	1.75
+++ byte-opt.el	21 Sep 2004 22:41:30 -0200	
@@ -1467,6 +1467,30 @@ of FORM by signalling the error at compi
      byte-member byte-assq byte-quo byte-rem)
    byte-compile-side-effect-and-error-free-ops))
 
+(defconst byte-compile-side-effect-free-dynamically-safe-ops
+  '(;; Same as `byte-compile-side-effect-free-ops' but without
+    ;; `byte-varref', `byte-symbol-value' and certain editing
+    ;; primitives.
+    byte-constant byte-dup byte-symbolp byte-consp byte-stringp byte-listp
+    byte-integerp byte-numberp byte-eq byte-equal byte-not byte-car-safe
+    byte-cdr-safe byte-cons byte-list1 byte-list2 byte-point byte-point-max
+    byte-point-min byte-following-char byte-preceding-char
+    byte-eolp byte-eobp byte-bolp byte-bobp
+    ;;
+    byte-nth byte-memq byte-car byte-cdr byte-length byte-aref
+    byte-get byte-concat2 byte-concat3 byte-sub1 byte-add1
+    byte-eqlsign byte-gtr byte-lss byte-leq byte-geq byte-diff byte-negate
+    byte-plus byte-max byte-min byte-mult byte-char-after
+    byte-string= byte-string< byte-nthcdr byte-elt
+    byte-member byte-assq byte-quo byte-rem))
+
+(put 'debug-on-error 'binding-is-magic t)
+(put 'debug-on-abort 'binding-is-magic t)
+(put 'inhibit-quit 'binding-is-magic t)
+(put 'quit-flag 'binding-is-magic t)
+(put 'gc-cons-threshold 'binding-is-magic t)
+(put 'track-mouse 'binding-is-magic t)
+
 ;; This crock is because of the way DEFVAR_BOOL variables work.
 ;; Consider the code
 ;;
@@ -1871,6 +1895,55 @@ If FOR-EFFECT is non-nil, the return val
 		      (setq lap (delq lap0 lap))))
 	       (setq keep-going t))
 	      ;;
+	      ;; varbind-X [car/cdr/ ...] unbind-1 --> discard [car/cdr/ ...]
+	      ;; varbind-X [car/cdr/ ...] unbind-N
+	      ;;   --> discard [car/cdr/ ...] unbind-(N-1)
+	      ;;
+	      ((and (eq 'byte-varbind (car lap1))
+		    (not (get (cadr lap1) 'binding-is-magic)))
+	       (setq tmp (cdr rest))
+	       (while
+		   (or
+		    (memq (caar (setq tmp (cdr tmp)))
+			  byte-compile-side-effect-free-dynamically-safe-ops)
+		    (and (eq (caar tmp) 'byte-varref)
+			 (not (eq (cadr (car tmp)) (cadr lap1))))))
+	       (when (eq 'byte-unbind (caar tmp))
+		 ;; Avoid evalling this crap when not logging anyway
+		 (when (memq byte-optimize-log '(t lap))
+		   (let ((format-string)
+			 (args))
+		     (if (and (= (aref byte-stack+-info (symbol-value (car lap0)))
+				 1)
+			      (memq (car lap0) side-effect-free))
+			 (setq format-string
+			       "  %s %s [car/cdr/ ...] %s\t-->\t[car/cdr/ ...]"
+			       args (list lap0 lap1 (car tmp)))
+		       (setq format-string
+			     "  %s [car/cdr/ ...] %s\t-->\t%s [car/cdr/ ...]"
+			     args (list lap1 (car tmp) (cons 'byte-discard 0))))
+		     (when (> (cdar tmp) 1)
+		       (setq format-string (concat format-string " %s"))
+		       (nconc args (list (cons 'byte-unbind (1- (cdar tmp))))))
+		     (apply 'byte-compile-log-lap-1 format-string args)))
+		 ;; Do the real work
+		 (if (and (= (aref byte-stack+-info (symbol-value (car lap0)))
+			     1)
+			  (memq (car lap0) side-effect-free))
+		     ;; Optimization: throw const/dup/... varbind right away.
+		     (progn
+		       (setcar rest (nth 2 rest))
+		       (setcdr rest (nthcdr 3 rest)))
+		   (setcar lap1 'byte-discard)
+		   (setcdr lap1 0))
+		 (if (= (cdar tmp) 1)
+		     (progn
+		       ;; Throw away unbind-1
+		       (setcar tmp (nth 1 tmp))
+		       (setcdr tmp (nthcdr 2 tmp)))
+		   (setcdr (car tmp) (1- (cdar tmp))))
+		 (setq keep-going t)))
+	      ;;
 	      ;; X: varref-Y    ...     varset-Y goto-X  -->
 	      ;; X: varref-Y Z: ... dup varset-Y goto-Z
 	      ;; (varset-X goto-BACK, BACK: varref-X --> copy the varref down.)

Re: byte-code optimizations

[Paul Pogonyshev]

Stefan wrote:

> >> However, there is still the question of whether we should
> >> change the standard defsubst to work the way defsubst* does.
> >
> > Maybe we can even use `defmacro' for `caar' and friends.  Since
> > they evaluate their lone argument only once, there must not be
> > any problems, right?
>
> Just think of (mapcar 'caar x)

Point.

> > If this (or `defsubst*') works, I'll investigate whether this
> > byte-code optimization gives any improvement after such a change.
>
> What defsubst* does is treat the argument as a kind of "lexically scoped"
> variable, but only in very limited ways.  I.e. the
>
>         (defsubst* caar (x) (car (car x)))
>
> will expand:
>
>         (caar y)  =>  (car (car y))
>         (caar (f y)) => (let ((x (f y))) ..cl-gunk.. (car (car x)))
>
> [ The cl-gunk is stuff added by CL for CL such as a `catch' statement. ]
> If you ignore the nasty cl-gunk, I think the resulting optimization is
> similar to what we get, except it works in a few more cases.
> E.g. it'll expand
>
>      (defsubst* foo (x) (symbol-value x))
>
>      (foo y) => (symbol-value y)
>
> whereas our optimization won't be able to do that because it can't assume
> a "somewhat lexically scoped" semantics.

Then byte-code optimization probably has only one advantage: it works
for normal `let' bindings too.  Probably not a particularly strong
advantage, though, as there must not be many so simple `let's around.

Will replacing `defsubst' definition with `defsubst*' or something
similar be visible from ``outside?''  Or, on a smaller scale, will
redefining `caar' and friends with `defsubst*' be?

Paul

Re: byte-code optimizations

[Paul Pogonyshev]

> On Tue, Sep 21, 2004 at 05:05:30PM -0400, Stefan Monnier wrote:
> > What defsubst* does is treat the argument as a kind of "lexically scoped"
> > variable, but only in very limited ways.  I.e. the
>
> ...
>
> >      (defsubst* foo (x) (symbol-value x))
> >
> >      (foo y) => (symbol-value y)
> >
> > whereas our optimization won't be able to do that because it can't assume
> > a "somewhat lexically scoped" semantics.
>
> I vote for saying "you're not allowed to treat defsubst argument bindings
> as normal dynamic bindings, and if you have tons of code that does, well
> screw you, you're probably a crappy programmer anyway."

While I do agree with this, it's generally better to avoid changing
stabilized behaviour only for optimization reasons.  Otherwise,
really-difficult-to-debug bugs can jump out of nowhere.

Paul

Re: byte-code optimizations

[Richard Stallman]

    After a `varbind' or `unwind-protect' or similar.  However, I doubt
    that those make much difference, so Stefan's optimization must be
    _nearly_ equivalent to mine.

It would be an error to move an unbind that matches an unwind-protect.

    >     +(defconst byte-compile-side-effect-free-dynamically-safe-ops
    >     +  '(;; Same as `byte-compile-side-effect-free-ops' but without
    >     +    ;; `byte-varref', `byte-symbol-value' and certain editing
    >     +    ;; primitives.
    >
    > Why exclude byte-symbol-value?

    Because value can change as the result of the binding we are
    trying to eliminate.

Yes, of course.

    > However, there is still the question of whether we should
    > change the standard defsubst to work the way defsubst* does.

    Maybe we can even use `defmacro' for `caar' and friends.  Since
    they evaluate their lone argument only once, there must not be
    any problems, right?

We don't want to replace defsubst with defmacro.
That's not what we're talking about.  The idea is to
to make defsubst work better, to make it do the good things
that defsubst* does.

    I vote for saying "you're not allowed to treat defsubst argument
    bindings as normal dynamic bindings, and if you have tons of code
    that does, well screw you, you're probably a crappy programmer
    anyway."

There is no reason to consider such an unpleasant alternative.
It is clearly not necessary for making an improvement here.

Anyway, please install your updated patch.

Re: byte-code optimizations

[Paul Pogonyshev]

> Anyway, please install your updated patch.

I don't have write access to CVS.  Someone else should do it.

And I would appreciate if someone read through the patch and
said "I understand what it does and I can't see any bugs in
it."

Paul