GNU bug report logs - #7089
23.2; slow ansi-color-apply

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 7089 in the body.
You can then email your comments to 7089 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: Leo <sdl.web <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Cc: Alex Schroeder <alex <at> gnu.org>
Subject: 23.2; slow ansi-color-apply
Date: Thu, 23 Sep 2010 10:15:41 +0100

I have found ansi-color-apply very expensive and slow.

To test this, do the following

  (remove-hook 'eshell-output-filter-functions 'eshell-handle-ansi-color)
  (add-hook 'eshell-preoutput-filter-functions 'ansi-color-apply)

and do something in eshell that can output a large coloured text such
as:

  cd /usr/include; ack time

where ack is a single file perl script from http://betterthangrep.com/.
The CPU usage should shoot up to very high.

The following version (after brief testing) seems to be noticeably
faster.

(defun ansi-color-apply* (string)
  "A more efficient implementation of `ansi-color-apply' (which see)."
  (let ((face (car ansi-color-context))
        start end fragment escape-sequence)
    ;; If context was saved and is a string, prepend it.
    (if (cadr ansi-color-context)
        (setq string (concat (cadr ansi-color-context) string)
              ansi-color-context nil))
    (with-temp-buffer
      (insert string)
      (setq start (point-min-marker))
      (goto-char start)
      (while (re-search-forward ansi-color-drop-regexp nil t)
        (replace-match ""))
      (goto-char start)
      ;; Find the next escape sequence.
      (while (re-search-forward ansi-color-regexp nil t)
        (setq end (match-beginning 0))
        (when face
          (put-text-property start end 'ansi-color t)
          (put-text-property start end 'face face))
        (setq start (copy-marker (match-end 0)))
        (setq escape-sequence (match-string 1))
        (replace-match "")
        (setq face (ansi-color-apply-sequence escape-sequence face)))
      ;; search for the possible start of a new escape sequence
      (if (re-search-forward "\033" nil t)
          (setq end (match-beginning 0)
                fragment (buffer-substring end (point-max)))
        (setq end (point-max)))
      ;; if the rest of the string should have a face, put it there
      (when face
        (put-text-property start end 'ansi-color t)
        (put-text-property start end 'face face))
      ;; save context
      (if (or face fragment)
          (setq ansi-color-context (list face fragment))
        (setq ansi-color-context nil))
      (buffer-string))))

Leo

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

From: Leo <sdl.web <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Thu, 23 Sep 2010 11:38:05 +0100

The following version fixed some glitches in setting ansi-color-context.
Also I have received an email from Alex that welcomes the improvement.
Let me know if I should send a patch in.

(defun ansi-color-apply* (string)
  "A more efficient implementation of `ansi-color-apply' (which see)."
  (let ((face (car ansi-color-context))
        start end fragment escape-sequence)
    ;; If context was saved and is a string, prepend it.
    (if (cadr ansi-color-context)
        (setq string (concat (cadr ansi-color-context) string)
              ansi-color-context nil))
    (prog1
        (with-temp-buffer
          (insert string)
          (setq start (point-min-marker))
          (goto-char start)
          (while (re-search-forward ansi-color-drop-regexp nil t)
            (replace-match ""))
          (goto-char start)
          ;; Find the next escape sequence.
          (while (re-search-forward ansi-color-regexp nil t)
            (setq end (match-beginning 0))
            (when face
              (put-text-property start end 'ansi-color t)
              (put-text-property start end 'face face))
            (setq start (copy-marker (match-end 0)))
            (setq escape-sequence (match-string 1))
            (replace-match "")
            (setq face (ansi-color-apply-sequence escape-sequence face)))
          ;; search for the possible start of a new escape sequence
          (if (re-search-forward "\033" nil t)
              (setq fragment
                    (delete-and-extract-region (match-beginning 0)
                                               (point-max))))
          ;; if the rest of the string should have a face, put it there
          (when face
            (put-text-property start (point-max) 'ansi-color t)
            (put-text-property start (point-max) 'face face))
          ;; return the string
          (buffer-string))
      ;; save context; NB: ansi-color-context is buffer-local so set it after
      ;; return to the original buffer
      (if (or face fragment)
          (setq ansi-color-context (list face fragment))
        (setq ansi-color-context nil)))))

Leo

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Leo <sdl.web <at> gmail.com>
Cc: 7089 <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Wed, 27 Oct 2010 22:38:17 -0400

> The following version fixed some glitches in setting ansi-color-context.
> Also I have received an email from Alex that welcomes the improvement.
> Let me know if I should send a patch in.

Yes, a patch would be nice.  Also a ChangeLog explaining the change
(which should hopefully explain why the new code is faster) would
be welcome.


        Stefan

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

From: Leo <sdl.web <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 7089 <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Thu, 28 Oct 2010 12:03:18 +0800

On 2010-10-28 10:38 +0800, Stefan Monnier wrote:
>> The following version fixed some glitches in setting ansi-color-context.
>> Also I have received an email from Alex that welcomes the improvement.
>> Let me know if I should send a patch in.
>
> Yes, a patch would be nice.  Also a ChangeLog explaining the change
> (which should hopefully explain why the new code is faster) would
> be welcome.
>
>
>         Stefan

Attached to the end of this message. I basically rewrite
ansi-color-apply using re-search-forward (as in
ansi-color-apply-on-region) which seems to be an order more efficient
than string-match.

I have been using the new version in eshell and it is almost as
efficient as ansi-color-apply-on-region. It is very painful to use the
original ansi-color-apply.

Do you know for sure string-match is slower (more CPU intensive) than
re-search-forward?

Thanks.
Leo

--------------------------------

From 724a620dd2d5301c32ecf4fbe6ce539db0c9bc8d Mon Sep 17 00:00:00 2001
Date: Thu, 28 Oct 2010 11:48:13 +0800
Subject: [PATCH] Rewrite ansi-color-apply using re-search-forward

to improve efficiency. `string-match' uses a lot of CPU.
---
 lisp/ChangeLog     |    5 ++++
 lisp/ansi-color.el |   66 ++++++++++++++++++++++++++-------------------------
 2 files changed, 39 insertions(+), 32 deletions(-)

diff --git a/lisp/ChangeLog b/lisp/ChangeLog
index 146c6c9..7088f28 100644
--- a/lisp/ChangeLog
+++ b/lisp/ChangeLog
@@ -1,3 +1,8 @@
+2010-10-28  Leo <sdl.web <at> gmail.com>
+
+	* ansi-color.el (ansi-color-apply): Rewrite using
+	re-search-forward for speed.
+
 2010-10-03  Chong Yidong  <cyd <at> stupidchicken.com>
 
 	* minibuffer.el (completion--some, completion--do-completion)
diff --git a/lisp/ansi-color.el b/lisp/ansi-color.el
index 00162c9..6ef55e1 100644
--- a/lisp/ansi-color.el
+++ b/lisp/ansi-color.el
@@ -314,43 +314,45 @@ This function can be added to `comint-preoutput-filter-functions'.
 You cannot insert the strings returned into buffers using font-lock.
 See `ansi-color-unfontify-region' for a way around this."
   (let ((face (car ansi-color-context))
-	(start 0) end escape-sequence result
-	colorized-substring)
+        start end fragment escape-sequence)
     ;; If context was saved and is a string, prepend it.
     (if (cadr ansi-color-context)
         (setq string (concat (cadr ansi-color-context) string)
               ansi-color-context nil))
-    ;; Find the next escape sequence.
-    (while (setq end (string-match ansi-color-regexp string start))
-      (setq escape-sequence (match-string 1 string))
-      ;; Colorize the old block from start to end using old face.
-      (when face
-	(put-text-property start end 'ansi-color t string)
-	(put-text-property start end 'face face string))
-      (setq colorized-substring (substring string start end)
-	    start (match-end 0))
-      ;; Eliminate unrecognized ANSI sequences.
-      (while (string-match ansi-color-drop-regexp colorized-substring)
-	(setq colorized-substring
-	      (replace-match "" nil nil colorized-substring)))
-      (push colorized-substring result)
-      ;; Create new face, by applying escape sequence parameters.
-      (setq face (ansi-color-apply-sequence escape-sequence face)))
-    ;; if the rest of the string should have a face, put it there
-    (when face
-      (put-text-property start (length string) 'ansi-color t string)
-      (put-text-property start (length string) 'face face string))
-    ;; save context, add the remainder of the string to the result
-    (let (fragment)
-      (if (string-match "\033" string start)
-	  (let ((pos (match-beginning 0)))
-	    (setq fragment (substring string pos))
-	    (push (substring string start pos) result))
-	(push (substring string start) result))
+    (prog1
+        (with-temp-buffer
+          (insert string)
+          (setq start (point-min-marker))
+          (goto-char start)
+          (while (re-search-forward ansi-color-drop-regexp nil t)
+            (replace-match ""))
+          (goto-char start)
+          ;; Find the next escape sequence.
+          (while (re-search-forward ansi-color-regexp nil t)
+            (setq end (match-beginning 0))
+            (when face
+              (put-text-property start end 'ansi-color t)
+              (put-text-property start end 'face face))
+            (setq start (copy-marker (match-end 0)))
+            (setq escape-sequence (match-string 1))
+            (replace-match "")
+            (setq face (ansi-color-apply-sequence escape-sequence face)))
+          ;; Search for the possible start of a new escape sequence
+          (if (re-search-forward "\033" nil t)
+              (setq fragment
+                    (delete-and-extract-region (match-beginning 0)
+                                               (point-max))))
+          ;; If the rest of the string should have a face, put it there
+          (when face
+            (put-text-property start (point-max) 'ansi-color t)
+            (put-text-property start (point-max) 'face face))
+          ;; Return the string
+          (buffer-string))
+      ;; Save context; NB: ansi-color-context is buffer-local so set it after
+      ;; exit the temp buffer.
       (if (or face fragment)
-	  (setq ansi-color-context (list face fragment))
-	(setq ansi-color-context nil)))
-    (apply 'concat (nreverse result))))
+          (setq ansi-color-context (list face fragment))
+        (setq ansi-color-context nil)))))
 
 ;; Working with regions
 
-- 
1.7.3

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

From: Stefan Monnier <monnier <at> iro.umontreal.ca>
To: Leo <sdl.web <at> gmail.com>
Cc: 7089 <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Sun, 31 Oct 2010 15:10:32 -0400

>>> The following version fixed some glitches in setting ansi-color-context.
>>> Also I have received an email from Alex that welcomes the improvement.
>>> Let me know if I should send a patch in.
>> Yes, a patch would be nice.  Also a ChangeLog explaining the change
>> (which should hopefully explain why the new code is faster) would
>> be welcome.

> Attached to the end of this message. I basically rewrite
> ansi-color-apply using re-search-forward (as in
> ansi-color-apply-on-region) which seems to be an order more efficient
> than string-match.

> I have been using the new version in eshell and it is almost as
> efficient as ansi-color-apply-on-region.  It is very painful to use the
> original ansi-color-apply.

Any reason why your new code does something similar to
ansi-color-apply-on-region rather than calling
ansi-color-apply-on-region?

> Do you know for sure string-match is slower (more CPU intensive) than
> re-search-forward?

They should be largely equivalent.  The difference between the two codes
might be due to replace-match and substring.  I.e. the original
ansi-color-apply should be at least as efficient as your code (if not
more) in the case where there are no SGR escape sequences.


        Stefan

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

From: Leo <sdl.web <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 7089 <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Tue, 02 Nov 2010 00:23:06 +0800

On 2010-11-01 03:10 +0800, Stefan Monnier wrote:
>>>> The following version fixed some glitches in setting ansi-color-context.
>>>> Also I have received an email from Alex that welcomes the improvement.
>>>> Let me know if I should send a patch in.
>>> Yes, a patch would be nice.  Also a ChangeLog explaining the change
>>> (which should hopefully explain why the new code is faster) would
>>> be welcome.
>
>> Attached to the end of this message. I basically rewrite
>> ansi-color-apply using re-search-forward (as in
>> ansi-color-apply-on-region) which seems to be an order more efficient
>> than string-match.
>
>> I have been using the new version in eshell and it is almost as
>> efficient as ansi-color-apply-on-region.  It is very painful to use the
>> original ansi-color-apply.
>
> Any reason why your new code does something similar to
> ansi-color-apply-on-region rather than calling
> ansi-color-apply-on-region?

`ansi-color-apply-on-region' uses overlays while `ansi-color-apply' uses
text properties.

>> Do you know for sure string-match is slower (more CPU intensive) than
>> re-search-forward?
>
> They should be largely equivalent. The difference between the two
> codes might be due to replace-match and substring. I.e. the original
> ansi-color-apply should be at least as efficient as your code (if not
> more) in the case where there are no SGR escape sequences.
>
>
>         Stefan

Thanks for that info.

Leo

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

From: Leo <sdl.web <at> gmail.com>
To: Stefan Monnier <monnier <at> iro.umontreal.ca>
Cc: 7089-done <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Thu, 25 Nov 2010 14:30:54 +0000

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

On 2010-10-31 19:10 +0000, Stefan Monnier wrote:
>> Do you know for sure string-match is slower (more CPU intensive) than
>> re-search-forward?
>
> They should be largely equivalent.  The difference between the two codes
> might be due to replace-match and substring.  I.e. the original
> ansi-color-apply should be at least as efficient as your code (if not
> more) in the case where there are no SGR escape sequences.
>
>
>         Stefan

I was setting out to profile the two versions of the function and
unfortunately I was not able to see the CPU shootup mentioned in the
first message. My result shows my version of ansi-color-apply is almost
twice as slow as the original one. (The code and data used for profiling
are attached.)

So please ignore this bug report.

Leo

[ansi-color-test.el (application/emacs-lisp, attachment)]

[ansi-test.txt (text/plain, attachment)]

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

From: Stefan Monnier <monnier <at> IRO.UMontreal.CA>
To: Leo <sdl.web <at> gmail.com>
Cc: 7089-done <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Thu, 25 Nov 2010 11:31:01 -0500

>>> Do you know for sure string-match is slower (more CPU intensive) than
>>> re-search-forward?
>> They should be largely equivalent.  The difference between the two codes
>> might be due to replace-match and substring.  I.e. the original
>> ansi-color-apply should be at least as efficient as your code (if not
>> more) in the case where there are no SGR escape sequences.
> I was setting out to profile the two versions of the function and
> unfortunately I was not able to see the CPU shootup mentioned in the
> first message. My result shows my version of ansi-color-apply is almost
> twice as slow as the original one. (The code and data used for profiling
> are attached.)

OK, thanks.  As mentioned, it might depend on the density of SGR escape
sequences (and on the size of the text chunks processed, which can
depend on the machine load).


        Stefan

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

From: Leo <sdl.web <at> gmail.com>
To: Stefan Monnier <monnier <at> IRO.UMontreal.CA>
Cc: 7089-done <at> debbugs.gnu.org
Subject: Re: bug#7089: 23.2; slow ansi-color-apply
Date: Fri, 26 Nov 2010 14:35:26 +0000

On 2010-11-25 16:31 +0000, Stefan Monnier wrote:
>> I was setting out to profile the two versions of the function and
>> unfortunately I was not able to see the CPU shootup mentioned in the
>> first message. My result shows my version of ansi-color-apply is almost
>> twice as slow as the original one. (The code and data used for profiling
>> are attached.)
>
> OK, thanks.  As mentioned, it might depend on the density of SGR escape
> sequences (and on the size of the text chunks processed, which can
> depend on the machine load).

For the record, there's a bug in my version due to the use of
copy-marker, which will create many markers in the temp buffer. Should
use set-marker instead. But even after fixing this, mine is still
slower. So the conclusion holds.

While doing this I have found a bug in the original ansi-color-apply.
I'll put it in a separate report.

Leo

Previous Next

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