From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Paul Pogonyshev Newsgroups: gmane.emacs.devel Subject: Re: byte-code optimizations Date: Sun, 19 Sep 2004 14:15:11 -0200 Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Message-ID: <200409191412.50820.pogonyshev@gmx.net> References: <200409181152.15364.pogonyshev@gmx.net> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-Trace: sea.gmane.org 1095592596 12692 80.91.229.6 (19 Sep 2004 11:16:36 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sun, 19 Sep 2004 11:16:36 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Sep 19 13:16:24 2004 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1C8zg7-0006nX-00 for ; Sun, 19 Sep 2004 13:16:23 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1C8zlw-000328-7O for ged-emacs-devel@m.gmane.org; Sun, 19 Sep 2004 07:22:24 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.33) id 1C8zlm-00031q-8J for emacs-devel@gnu.org; Sun, 19 Sep 2004 07:22:14 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.33) id 1C8zll-00031e-Mr for emacs-devel@gnu.org; Sun, 19 Sep 2004 07:22:14 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1C8zll-00031U-JT for emacs-devel@gnu.org; Sun, 19 Sep 2004 07:22:13 -0400 Original-Received: from [213.165.64.20] (helo=mail.gmx.net) by monty-python.gnu.org with smtp (Exim 4.34) id 1C8zfb-00046t-M5 for emacs-devel@gnu.org; Sun, 19 Sep 2004 07:15:52 -0400 Original-Received: (qmail 406 invoked by uid 65534); 19 Sep 2004 11:15:34 -0000 Original-Received: from unknown (EHLO localhost.localdomain) (195.50.12.116) by mail.gmx.net (mp003) with SMTP; 19 Sep 2004 13:15:34 +0200 X-Authenticated: #16844820 Original-To: Stefan , Richard Stallman User-Agent: KMail/1.4.3 In-Reply-To: X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: main.gmane.org gmane.emacs.devel:27275 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:27275 Stefan wrote: > > +=09 ;; 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-in= tegerp byte-eq byte-not byte-cons byte-list1 byte-list2=09; 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 lapcod= e > 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. >=20 > 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 =09varbind-X ... unbind-N --> discard ... unbind-(N-1) while Stefan suggests a more general =09... unbind-1 --> unbind-1 ... which is then followuped by other (existing) optimizations. Paul --- byte-opt.el=0922 Mar 2004 13:21:08 -0200=091.75 +++ byte-opt.el=0919 Sep 2004 14:00:27 -0200=09 @@ -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)) =20 +(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-lis= tp + 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-nega= te + byte-plus byte-max byte-min byte-mult byte-char-after + byte-string=3D 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 =09=09 (setq lap (delq lap0 lap)))) =09 (setq keep-going t)) =09 ;; +=09 ;; varbind-X [car/cdr/ ...] unbind-1 --> discard [car/cdr/ ...] +=09 ;; varbind-X [car/cdr/ ...] unbind-N +=09 ;; --> discard [car/cdr/ ...] unbind-(N-1) +=09 ;; +=09 ((and (eq 'byte-varbind (car lap1)) +=09=09 (not (get (cadr lap1) 'binding-is-magic))) +=09 (setq tmp (cdr rest)) +=09 (while +=09=09 (or +=09=09 (memq (caar (setq tmp (cdr tmp))) +=09=09=09 byte-compile-side-effect-free-dynamically-safe-ops) +=09=09 (and (eq (caar tmp) 'byte-varref) +=09=09=09 (not (eq (cadr (car tmp)) (cadr lap1)))))) +=09 (when (eq 'byte-unbind (caar tmp)) +=09=09 ;; Avoid evalling this crap when not logging anyway +=09=09 (when (memq byte-optimize-log '(t lap)) +=09=09 (let ((format-string) +=09=09=09 (args)) +=09=09 (if (and (=3D (aref byte-stack+-info (symbol-value (car lap0)= )) +=09=09=09=091) +=09=09=09 (memq (car lap0) side-effect-free)) +=09=09=09 (setq format-string +=09=09=09 " %s %s [car/cdr/ ...] %s\t-->\t[car/cdr/ ...]" +=09=09=09 args (list lap0 lap1 (car tmp))) +=09=09 (setq format-string +=09=09=09 " %s [car/cdr/ ...] %s\t-->\t%s [car/cdr/ ...]" +=09=09=09 args (list lap1 (car tmp) (cons 'byte-discard 0)))) +=09=09 (when (> (cdar tmp) 1) +=09=09 (setq format-string (concat format-string " %s")) +=09=09 (nconc args (list (cons 'byte-unbind (1- (cdar tmp)))))) +=09=09 (apply 'byte-compile-log-lap-1 format-string args))) +=09=09 ;; Do the real work +=09=09 (if (and (=3D (aref byte-stack+-info (symbol-value (car lap0))) +=09=09=09 1) +=09=09=09 (memq (car lap0) side-effect-free)) +=09=09 ;; Optimization: throw const/dup/... varbind right away. +=09=09 (progn +=09=09 (setcar rest (nth 2 rest)) +=09=09 (setcdr rest (nthcdr 3 rest))) +=09=09 (setcar lap1 'byte-discard) +=09=09 (setcdr lap1 0)) +=09=09 (if (=3D (cdar tmp) 1) +=09=09 (progn +=09=09 ;; Throw away unbind-1 +=09=09 (setcar tmp (nth 1 tmp)) +=09=09 (setcdr tmp (nthcdr 2 tmp))) +=09=09 (setcdr (car tmp) (1- (cdar tmp)))) +=09=09 (setq keep-going t))) +=09 ;; =09 ;; X: varref-Y ... varset-Y goto-X --> =09 ;; X: varref-Y Z: ... dup varset-Y goto-Z =09 ;; (varset-X goto-BACK, BACK: varref-X --> copy the varref down= =2E)