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: more byte-code optimizations Date: Sun, 19 Sep 2004 22:52:49 -0200 Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Message-ID: <200409192252.49200.pogonyshev@gmx.net> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable X-Trace: sea.gmane.org 1095623561 11734 80.91.229.6 (19 Sep 2004 19:52:41 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sun, 19 Sep 2004 19:52:41 +0000 (UTC) Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Sep 19 21:52:34 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 1C97jd-0003GC-00 for ; Sun, 19 Sep 2004 21:52:33 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1C97pT-0000Av-JU for ged-emacs-devel@m.gmane.org; Sun, 19 Sep 2004 15:58:35 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.33) id 1C97pK-0000Aa-P6 for emacs-devel@gnu.org; Sun, 19 Sep 2004 15:58:26 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.33) id 1C97pI-0000AI-A9 for emacs-devel@gnu.org; Sun, 19 Sep 2004 15:58:26 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.33) id 1C97pI-0000AF-6u for emacs-devel@gnu.org; Sun, 19 Sep 2004 15:58:24 -0400 Original-Received: from [213.165.64.20] (helo=mail.gmx.net) by monty-python.gnu.org with smtp (Exim 4.34) id 1C97ix-0001PJ-Qw for emacs-devel@gnu.org; Sun, 19 Sep 2004 15:51:52 -0400 Original-Received: (qmail 24420 invoked by uid 65534); 19 Sep 2004 19:51:46 -0000 Original-Received: from unknown (EHLO localhost.localdomain) (195.50.12.120) by mail.gmx.net (mp002) with SMTP; 19 Sep 2004 21:51:46 +0200 X-Authenticated: #16844820 Original-To: emacs-devel@gnu.org User-Agent: KMail/1.4.3 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:27284 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:27284 This patch reduces the number of duplicate command sequences in generated byte-code. For instance, for function =09(lambda (x) =09 (if x =09 (foo) =09 (bar)) =09 x) current byte-compiler generates 0=09varref=09 x 1=09goto-if-nil 1 4=09constant foo 5=09call=09 0 6=09discard=09 =20 7=09goto=09 2 10:1=09constant bar 11=09call=09 0 12=09discard=09 =20 13:2=09varref=09 x 14=09return=09 =20 After the patch, two commands are squeezed out: 0=09varref=09 x 1=09goto-if-nil 1 4=09constant foo 5=09goto=09 2 8:1=09constant bar 9:2=09call=09 0 10=09discard=09 =20 11=09varref=09 x 12=09return=09 =20 This patch looks much less controversial and safer than the one about binding elimination. However, this optimization is size-only, commands executed in all code branches remain the same, only some `goto's are executed earlier. Here is some statistic for a few long functions (length is measured in lapcode commands): byte-optimize-form-code-walker=09 641 --> 619=09-3.4% c-forward-<>-arglist-recur=09 484 --> 469=09-3.1% c-guess-basic-syntax=09=093334 --> 3272=09-1.9% c-guess-fill-prefix=09=09 691 --> 679=09-1.7% edebug-display=09=09=09 424 --> 408=09-3.8% Info-fontify-node=09=091039 --> 1025=09-1.3% Paul --- byte-opt.el=0922 Mar 2004 13:21:08 -0200=091.75 +++ byte-opt.el=0919 Sep 2004 17:40:02 -0200=09 @@ -2005,6 +2005,68 @@ If FOR-EFFECT is non-nil, the return val =09 (setcdr lap1 (+ (cdr lap1) (cdr lap0)))) =09 ) (setq rest (cdr rest))) + + ;; Optimize certain duplicated sequences: + ;; command-N ... command-1 goto-X ... command-N ... command-1 = X: + ;; --> goto-Y ... Y: command-N ... command-1 X: + ;; + ;; Commands before the X tag can be spiced with other tags, but + ;; commands before goto-X cannot be. + ;; + (let* ((double-linked (cons (car lap) (cons nil nil))) +=09 (link=09 double-linked)) + ;; Build double-linked list. The structure of each list link is + ;; like this: (value . (previous . next)) + (while (setq lap (cdr lap)) +=09(setq link (setcdr (cdr link) (cons (car lap) (cons link nil))))) + ;; + ;; Search for duplicated sequences. + (setq link double-linked) + (while link +=09(when (eq (caar link) 'byte-goto) +=09 ;; This is somewhat hackish, but `memq' will work on +=09 ;; double-linked list as well (searching forward). +=09 (let ((pre-goto link) +=09=09(pre-tag (memq (cdar link) double-linked))) +=09 (while (and (setq pre-goto (cadr pre-goto)) +=09=09=09(progn ;; Skip tags (they don't hurt). +=09=09=09 (while (eq (caar (setq pre-tag (cadr pre-tag))) +=09=09=09=09 'TAG)) +=09=09=09 pre-tag) +=09=09=09(eq (caar pre-goto) (caar pre-tag)) +=09=09=09(eq (cdar pre-goto) (cdar pre-tag)))) +=09 (when (not (eq pre-goto (cadr link))) +=09 ;; At least one command is duplicated. +=09 ;; +=09 ;; First, change the goto tag (insert new if needed). +=09 (setq pre-tag (if pre-tag (cddr pre-tag) double-linked)) +=09 (if (eq (caar pre-tag) 'TAG) +=09=09 ;; We don't need a new tag as there's already one. +=09=09 (setcdr (car link) (car pre-tag)) +=09=09;; Else insert a new tag into the double-linked list. +=09=09(let ((new-tag (cons (byte-compile-make-tag) +=09=09=09=09 (cons (cadr pre-tag) pre-tag)))) +=09=09 (setcar (cdr pre-tag) new-tag) +=09=09 (if (cadr new-tag) +=09=09 (setcdr (cdr (cadr new-tag)) new-tag) +=09=09 (setq double-linked new-tag)) +=09=09 (setcdr (car link) (car new-tag)))) +=09 ;; Now, remove the duplicated commands before goto. +=09 (setcar (cdr link) pre-goto) +=09 (if pre-goto +=09=09 (setcdr (cdr pre-goto) link) +=09=09(setq double-linked link)) +=09 (byte-compile-log-lap +=09 " [command ...] goto-X ... [command ...] X: + --> goto-Y ... Y: [command ...] X:")))) +=09(setq link (cddr link))) + ;; + ;; Reconstruct normal list from double-linked list. + (while double-linked +=09(setq lap=09 (cons (car double-linked) lap) +=09 double-linked (cddr double-linked))) + (setq lap (nreverse lap))) + (setq byte-compile-maxdepth (+ byte-compile-maxdepth add-depth))) lap) =20