bug#14769: 24.3.50; [PATCH] optimize `concat's literals

bug#14769: 24.3.50; [PATCH] optimize `concat's literals

[Shigeru Fukaya]

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


Current bytecode optimizer works only when all arguments are
constants.

With the attached small patch, adjacent successive literal arguments
of `concat' will become optimized to a string respectively.

	Make successive literals of `concat' optimized to a string.
	* byte-opt.el (byte-optimize-form-code-walker): call
	byte-optimize-concat-args for `concat'.
	(byte-optimize-concat-args): New function.

Regards,
Shigeru

[-- Attachment #2: byte-opt.patch --]
[-- Type: application/octet-stream, Size: 1704 bytes --]

*** byte-opt.el	Fri Jun 14 19:32:39 2013
--- byte-opt.new.el	Wed Jul  3 01:48:29 2013
***************
*** 562,568 ****
  	     (if (and (get fn 'pure)
  		      (byte-optimize-all-constp args))
  		   (list 'quote (apply fn (mapcar #'eval args)))
! 	       (cons fn args)))))))
  
  (defun byte-optimize-all-constp (list)
    "Non-nil if all elements of LIST satisfy `macroexp-const-p"
--- 562,572 ----
  	     (if (and (get fn 'pure)
  		      (byte-optimize-all-constp args))
  		   (list 'quote (apply fn (mapcar #'eval args)))
! 	       (if (eq fn 'concat)
! 		   ;; Not all arguments are literals.
! 		   (cons fn (byte-optimize-concat-args args))
! 		 ;; Other than `concat'.
! 		 (cons fn args))))))))
  
  (defun byte-optimize-all-constp (list)
    "Non-nil if all elements of LIST satisfy `macroexp-const-p"
***************
*** 573,578 ****
--- 577,605 ----
        (setq list (cdr list)))
      constant))
  
+ (defun byte-optimize-concat-args (args)
+   ;;
+   ;; Convert arguments of `concat' such that adjacent successive
+   ;; literal arguments to one string, and remove null strings.
+   ;;
+   (let (newargs)
+     (while args
+       ;; loop for literals
+       (let (l)
+ 	(while (and args (macroexp-const-p (car args)))
+ 	  (push (car args) l)
+ 	  (setq args (cdr args)))
+ 	(when l
+ 	  (let ((s (apply #'concat (mapcar #'eval (nreverse l)))))
+ 	    ;; keep non-null string
+ 	    (unless (equal s "")
+ 	      (push s newargs)))))
+       ;; non-literal argument
+       (when args
+ 	(push (car args) newargs)
+ 	(setq args (cdr args))))
+     (nreverse newargs)))
+ 
  (defun byte-optimize-form (form &optional for-effect)
    "The source-level pass of the optimizer."
    ;;

bug#14769: 24.3.50; [PATCH] optimize `concat's literals

[Lars Ingebrigtsen]

Shigeru Fukaya <shigeru.fukaya@gmail.com> writes:

> Current bytecode optimizer works only when all arguments are
> constants.
>
> With the attached small patch, adjacent successive literal arguments
> of `concat' will become optimized to a string respectively.
>
> 	Make successive literals of `concat' optimized to a string.
> 	* byte-opt.el (byte-optimize-form-code-walker): call
> 	byte-optimize-concat-args for `concat'.
> 	(byte-optimize-concat-args): New function.

I think the patch below looks sensible, but the bytecode optimiser is
not something I'm familiar with.  Does this look OK to all y'all?

>
> Regards,
> Shigeru
>
> *** byte-opt.el	Fri Jun 14 19:32:39 2013
> --- byte-opt.new.el	Wed Jul  3 01:48:29 2013
> ***************
> *** 562,568 ****
>   	     (if (and (get fn 'pure)
>   		      (byte-optimize-all-constp args))
>   		   (list 'quote (apply fn (mapcar #'eval args)))
> ! 	       (cons fn args)))))))
>   
>   (defun byte-optimize-all-constp (list)
>     "Non-nil if all elements of LIST satisfy `macroexp-const-p"
> --- 562,572 ----
>   	     (if (and (get fn 'pure)
>   		      (byte-optimize-all-constp args))
>   		   (list 'quote (apply fn (mapcar #'eval args)))
> ! 	       (if (eq fn 'concat)
> ! 		   ;; Not all arguments are literals.
> ! 		   (cons fn (byte-optimize-concat-args args))
> ! 		 ;; Other than `concat'.
> ! 		 (cons fn args))))))))
>   
>   (defun byte-optimize-all-constp (list)
>     "Non-nil if all elements of LIST satisfy `macroexp-const-p"
> ***************
> *** 573,578 ****
> --- 577,605 ----
>         (setq list (cdr list)))
>       constant))
>   
> + (defun byte-optimize-concat-args (args)
> +   ;;
> +   ;; Convert arguments of `concat' such that adjacent successive
> +   ;; literal arguments to one string, and remove null strings.
> +   ;;
> +   (let (newargs)
> +     (while args
> +       ;; loop for literals
> +       (let (l)
> + 	(while (and args (macroexp-const-p (car args)))
> + 	  (push (car args) l)
> + 	  (setq args (cdr args)))
> + 	(when l
> + 	  (let ((s (apply #'concat (mapcar #'eval (nreverse l)))))
> + 	    ;; keep non-null string
> + 	    (unless (equal s "")
> + 	      (push s newargs)))))
> +       ;; non-literal argument
> +       (when args
> + 	(push (car args) newargs)
> + 	(setq args (cdr args))))
> +     (nreverse newargs)))
> + 
>   (defun byte-optimize-form (form &optional for-effect)
>     "The source-level pass of the optimizer."
>     ;;
>

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#14769: [PATCH] optimize `concat's literals

[Mattias Engdegård]

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

Since this bug was mentioned in  https://debbugs.gnu.org/36237, here is a slightly reworked version that does not special-case `concat' in the general code.


[-- Attachment #2: 0001-Merge-consecutive-constant-concat-args-bug-14769.patch --]
[-- Type: application/octet-stream, Size: 2312 bytes --]

From 4a65b351c5f72a7d53904c57137c69bd6dc4d568 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Sun, 16 Jun 2019 13:13:47 +0200
Subject: [PATCH] Merge consecutive constant `concat' args (bug#14769)

Suggested by Shigeru Fukaya <shigeru.fukaya@gmail.com>

* lisp/emacs-lisp/byte-opt.el (byte-optimize-concat): New.
(concat): Add byte-optimizer.
---
 lisp/emacs-lisp/byte-opt.el | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index 44cca6136c..1ebafec3f2 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -850,6 +850,29 @@ byte-optimize-memq
                           ',list)))))
     (byte-optimize-predicate form)))
 
+(defun byte-optimize-concat (form)
+  "Merge adjacent constant arguments to `concat'."
+  (let ((args nil)
+        (accum nil))
+    (dolist (arg (cdr form))
+      (unless (and (macroexp-const-p arg)
+                   (let ((val (eval arg)))
+                     (and (or (stringp val)
+                              (and (or (listp val) (vectorp val))
+                                   (not (memq nil (mapcar #'characterp val)))))
+                          ;; Constant arg: concat with previous.
+                          (setq accum (concat accum val)))))
+        ;; Non-constant arg.
+        (when (and accum (not (zerop (length accum))))
+          (push accum args))
+        (push arg args)
+        (setq accum nil)))
+    (when (and accum (not (zerop (length accum))))
+      (push accum args))
+    (if (= (length args) (length (cdr form)))
+        form          ; No improvement.
+      (cons 'concat (nreverse args)))))
+
 (put 'identity 'byte-optimizer 'byte-optimize-identity)
 (put 'memq 'byte-optimizer 'byte-optimize-memq)
 
@@ -892,6 +915,8 @@ byte-optimize-memq
 (put 'car-safe 'byte-optimizer 'byte-optimize-predicate)
 (put 'cdr-safe 'byte-optimizer 'byte-optimize-predicate)
 
+(put 'concat 'byte-optimizer 'byte-optimize-concat)
+
 ;; I'm not convinced that this is necessary.  Doesn't the optimizer loop
 ;; take care of this? - Jamie
 ;; I think this may some times be necessary to reduce ie (quote 5) to 5,
-- 
2.20.1 (Apple Git-117)

bug#14769: [PATCH] optimize `concat's literals

[Noam Postavsky]

Mattias Engdegård <mattiase@acm.org> writes:

> +    (dolist (arg (cdr form))

> +                   (let ((val (eval arg)))

> +                          ;; Constant arg: concat with previous.
> +                          (setq accum (concat accum val)))))

Hmm, I think the OP's patch is careful not to concat in a loop like
this: it's O(n^2).  I guess for most human written code n is small
enough that it doesn't matter, but I could imagine this slowing
compilation of a very big rx macro.

bug#14769: [PATCH] optimize `concat's literals

[Mattias Engdegård]

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

19 juni 2019 kl. 03.43 skrev Noam Postavsky <npostavs@gmail.com>:
> 
> Mattias Engdegård <mattiase@acm.org> writes:
> 
>> +    (dolist (arg (cdr form))
> 
>> +                   (let ((val (eval arg)))
> 
>> +                          ;; Constant arg: concat with previous.
>> +                          (setq accum (concat accum val)))))
> 
> Hmm, I think the OP's patch is careful not to concat in a loop like
> this: it's O(n^2).  I guess for most human written code n is small
> enough that it doesn't matter, but I could imagine this slowing
> compilation of a very big rx macro.

Yes, I thought it wouldn't matter but you are right. Updated patch attached.

For that matter, ry performs this optimisation itself, but it's also nice to have it in the compiler, since concat is frequently used to split long string constants in elisp source.

[-- Attachment #2: 0001-Merge-consecutive-constant-concat-args-bug-14769.patch --]
[-- Type: application/octet-stream, Size: 2408 bytes --]

From d4c3bbce9472618b5e762a18af5ba1a2b1b79698 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Mattias=20Engdeg=C3=A5rd?= <mattiase@acm.org>
Date: Sun, 16 Jun 2019 13:13:47 +0200
Subject: [PATCH] Merge consecutive constant `concat' args (bug#14769)

Suggested by Shigeru Fukaya <shigeru.fukaya@gmail.com>

* lisp/emacs-lisp/byte-opt.el (byte-optimize-concat): New.
(concat): Add byte-optimizer.
---
 lisp/emacs-lisp/byte-opt.el | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/lisp/emacs-lisp/byte-opt.el b/lisp/emacs-lisp/byte-opt.el
index b0aa407c8b..2e09601639 100644
--- a/lisp/emacs-lisp/byte-opt.el
+++ b/lisp/emacs-lisp/byte-opt.el
@@ -850,6 +850,33 @@ byte-optimize-memq
                           ',list)))))
     (byte-optimize-predicate form)))
 
+(defun byte-optimize-concat (form)
+  "Merge adjacent constant arguments to `concat'."
+  (let ((args (cdr form))
+        (newargs nil))
+    (while args
+      (let ((strings nil)
+            val)
+        (while (and args (macroexp-const-p (car args))
+                    (progn
+                      (setq val (eval (car args)))
+                      (and (or (stringp val)
+                               (and (or (listp val) (vectorp val))
+                                    (not (memq nil
+                                               (mapcar #'characterp val))))))))
+          (push val strings)
+          (setq args (cdr args)))
+        (when strings
+          (let ((s (apply #'concat (nreverse strings))))
+            (when (not (zerop (length s)))
+              (push s newargs)))))
+      (when args
+        (push (car args) newargs)
+        (setq args (cdr args))))
+    (if (= (length newargs) (length (cdr form)))
+        form          ; No improvement.
+      (cons 'concat (nreverse newargs)))))
+
 (put 'identity 'byte-optimizer 'byte-optimize-identity)
 (put 'memq 'byte-optimizer 'byte-optimize-memq)
 
@@ -892,6 +919,8 @@ byte-optimize-memq
 (put 'car-safe 'byte-optimizer 'byte-optimize-predicate)
 (put 'cdr-safe 'byte-optimizer 'byte-optimize-predicate)
 
+(put 'concat 'byte-optimizer 'byte-optimize-concat)
+
 ;; I'm not convinced that this is necessary.  Doesn't the optimizer loop
 ;; take care of this? - Jamie
 ;; I think this may some times be necessary to reduce ie (quote 5) to 5,
-- 
2.20.1 (Apple Git-117)

bug#14769: [PATCH] optimize `concat's literals

[Noam Postavsky]

Mattias Engdegård <mattiase@acm.org> writes:

> Yes, I thought it wouldn't matter but you are right. Updated patch attached.

Looks good to me.  As a minor aesthetic nitpick, I would suggest using
`pop', since you're already using `push'.

bug#14769: [PATCH] optimize `concat's literals

[Mattias Engdegård]

20 juni 2019 kl. 02.38 skrev Noam Postavsky <npostavs@gmail.com>:
> 
> Looks good to me.

Thanks for looking through the code!

>  As a minor aesthetic nitpick, I would suggest using
> `pop', since you're already using `push'.

Not to the same variable though; it isn't a stack. If it's all the same to you, I'd rather keep that part of the code as it is.

bug#14769: [PATCH] optimize `concat's literals

[Noam Postavsky]

Mattias Engdegård <mattiase@acm.org> writes:

> 20 juni 2019 kl. 02.38 skrev Noam Postavsky <npostavs@gmail.com>:
>
>>  As a minor aesthetic nitpick, I would suggest using
>> `pop', since you're already using `push'.
>
> Not to the same variable though; it isn't a stack.

Okay, interesting.  I never considered making that stylistic
distinction, I tend to use it on lists freely.

> If it's all the same to you, I'd rather keep that part of the code as it is.

Yeah, no problem.

bug#14769: [PATCH] optimize `concat's literals

[Mattias Engdegård]

23 juni 2019 kl. 00.17 skrev Noam Postavsky <npostavs@gmail.com>:
> 
> Yeah, no problem.

I take that as approval for the patch then, which has become somewhat more urgent now that the rx `literal' patch has been pushed.
The alternative would be to add this concat-simplification logic to rx instead (why ry does), but it is of general use.
Pushed to master.