GNU bug report logs - #14769
24.3.50; [PATCH] optimize `concat's literals

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 14769 in the body.
You can then email your comments to 14769 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Shigeru Fukaya <shigeru.fukaya <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 24.3.50; [PATCH] optimize `concat's literals
Date: Wed, 03 Jul 2013 02:04:28 +0900

[Message part 1 (text/plain, inline)]

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

[byte-opt.patch (application/octet-stream, attachment)]

Message #8 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Lars Ingebrigtsen <larsi <at> gnus.org>
To: Shigeru Fukaya <shigeru.fukaya <at> gmail.com>
Cc: 14769 <at> debbugs.gnu.org
Subject: Re: bug#14769: 24.3.50; [PATCH] optimize `concat's literals
Date: Wed, 24 Feb 2016 15:51:00 +1100

Shigeru Fukaya <shigeru.fukaya <at> 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

Message #11 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: 14769 <at> debbugs.gnu.org, shigeru.fukaya <at> gmail.com,
 Lars Ingebrigtsen <larsi <at> gnus.org>, Noam Postavsky <npostavs <at> gmail.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>
Subject: [PATCH] optimize `concat's literals
Date: Sun, 16 Jun 2019 13:57:44 +0200

[Message part 1 (text/plain, inline)]

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.

[0001-Merge-consecutive-constant-concat-args-bug-14769.patch (application/octet-stream, attachment)]

Message #14 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Noam Postavsky <npostavs <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 14769 <at> debbugs.gnu.org,
 shigeru.fukaya <at> gmail.com
Subject: Re: bug#14769: [PATCH] optimize `concat's literals
Date: Tue, 18 Jun 2019 21:43:32 -0400

Mattias Engdegård <mattiase <at> 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.

Message #17 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Noam Postavsky <npostavs <at> gmail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 14769 <at> debbugs.gnu.org,
 shigeru.fukaya <at> gmail.com
Subject: Re: bug#14769: [PATCH] optimize `concat's literals
Date: Wed, 19 Jun 2019 14:54:16 +0200

[Message part 1 (text/plain, inline)]

19 juni 2019 kl. 03.43 skrev Noam Postavsky <npostavs <at> gmail.com>:
> 
> Mattias Engdegård <mattiase <at> 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.

[0001-Merge-consecutive-constant-concat-args-bug-14769.patch (application/octet-stream, attachment)]

Message #20 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Noam Postavsky <npostavs <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 14769 <at> debbugs.gnu.org,
 shigeru.fukaya <at> gmail.com
Subject: Re: bug#14769: [PATCH] optimize `concat's literals
Date: Wed, 19 Jun 2019 20:38:12 -0400

Mattias Engdegård <mattiase <at> 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'.

Message #23 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Noam Postavsky <npostavs <at> gmail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 14769 <at> debbugs.gnu.org,
 shigeru.fukaya <at> gmail.com
Subject: Re: bug#14769: [PATCH] optimize `concat's literals
Date: Fri, 21 Jun 2019 11:07:13 +0200

20 juni 2019 kl. 02.38 skrev Noam Postavsky <npostavs <at> 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.

Message #26 received at 14769 <at> debbugs.gnu.org (full text, mbox):

From: Noam Postavsky <npostavs <at> gmail.com>
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 14769 <at> debbugs.gnu.org,
 shigeru.fukaya <at> gmail.com
Subject: Re: bug#14769: [PATCH] optimize `concat's literals
Date: Sat, 22 Jun 2019 18:17:25 -0400

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

> 20 juni 2019 kl. 02.38 skrev Noam Postavsky <npostavs <at> 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.

Message #31 received at 14769-done <at> debbugs.gnu.org (full text, mbox):

From: Mattias Engdegård <mattiase <at> acm.org>
To: Noam Postavsky <npostavs <at> gmail.com>
Cc: Lars Ingebrigtsen <larsi <at> gnus.org>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 14769-done <at> debbugs.gnu.org,
 shigeru.fukaya <at> gmail.com
Subject: Re: bug#14769: [PATCH] optimize `concat's literals
Date: Wed, 26 Jun 2019 11:44:21 +0200

23 juni 2019 kl. 00.17 skrev Noam Postavsky <npostavs <at> 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.