Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Stefan Monnier]

>     Recomplexify ‘delete-trailing-whitespace’ by treating \n as
>     whitespace again
>
>     Mostly reverts "Simplify ‘delete-trailing-whitespace’ by not treating
>     \n as whitespace" from 2016-07-04.  Setting \n to non-whitespace
>     causes the regex engine to backtrack a lot when searching for
>     "\\s-+$" (Bug#26079).

Why do we use syntax-tables?
IOW why do we use \s- rather than something like [\s\t]?


        Stefan

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Noam Postavsky]

On Wed, Mar 15, 2017 at 7:28 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>>     Recomplexify ‘delete-trailing-whitespace’ by treating \n as
>>     whitespace again
>>
>>     Mostly reverts "Simplify ‘delete-trailing-whitespace’ by not treating
>>     \n as whitespace" from 2016-07-04.  Setting \n to non-whitespace
>>     causes the regex engine to backtrack a lot when searching for
>>     "\\s-+$" (Bug#26079).
>
> Why do we use syntax-tables?
> IOW why do we use \s- rather than something like [\s\t]?

No clue. But (re-search-forward "[\s\t]+$" nil t) is also slow.

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Stefan Monnier]

>>> Recomplexify ‘delete-trailing-whitespace’ by treating \n as
>>> whitespace again
>>> Mostly reverts "Simplify ‘delete-trailing-whitespace’ by not treating
>>> \n as whitespace" from 2016-07-04.  Setting \n to non-whitespace
>>> causes the regex engine to backtrack a lot when searching for
>>> "\\s-+$" (Bug#26079).
>> Why do we use syntax-tables?
>> IOW why do we use \s- rather than something like [\s\t]?
> No clue. But (re-search-forward "[\s\t]+$" nil t) is also slow.

Slower than "\\s-+$"?


        Stefan

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Noam Postavsky]

On Wed, Mar 15, 2017 at 10:50 AM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
>>>> Recomplexify ‘delete-trailing-whitespace’ by treating \n as
>>>> whitespace again
>>>> Mostly reverts "Simplify ‘delete-trailing-whitespace’ by not treating
>>>> \n as whitespace" from 2016-07-04.  Setting \n to non-whitespace
>>>> causes the regex engine to backtrack a lot when searching for
>>>> "\\s-+$" (Bug#26079).
>>> Why do we use syntax-tables?
>>> IOW why do we use \s- rather than something like [\s\t]?
>> No clue. But (re-search-forward "[\s\t]+$" nil t) is also slow.
>
> Slower than "\\s-+$"?

No, seems to be twice as fast actually (this is still horribly slow).
On the test file given in Bug#26079[1]

(benchmark 1 '(re-search-forward "[\s\t]+$" nil t)) ;=> Elapsed time: 9.944000s
(benchmark 1 '(save-excursion
        (let ((end-marker nil))
          (goto-char (point-min))
          (with-syntax-table (make-syntax-table (syntax-table))
            (modify-syntax-entry ?\f "_")
            (modify-syntax-entry ?\n "_")
            (re-search-forward "\\s-+$" end-marker t))))) ;=> Elapsed
time: 20.496000s

[1]: https://raw.githubusercontent.com/stakemori/e8theta_degree3/master/results/wt18_17_5/wt18_17_5.org

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Stefan Monnier]

>>>>> Recomplexify ‘delete-trailing-whitespace’ by treating \n as
>>>>> whitespace again
>>>>> Mostly reverts "Simplify ‘delete-trailing-whitespace’ by not treating
>>>>> \n as whitespace" from 2016-07-04.  Setting \n to non-whitespace
>>>>> causes the regex engine to backtrack a lot when searching for
>>>>> "\\s-+$" (Bug#26079).
>>>> Why do we use syntax-tables?
>>>> IOW why do we use \s- rather than something like [\s\t]?
>>> No clue. But (re-search-forward "[\s\t]+$" nil t) is also slow.
>> Slower than "\\s-+$"?
> No, seems to be twice as fast actually (this is still horribly slow).

I meant

   slower than the best performance of "\\s-+$"?

because "[\s\t]+$" shouldn't backtrack.  Using "\\s-+$" with
a syntax-table that puts \n in the whitespace syntax is indeed asking
for trouble, but I'm surprised "[\s\t]+$" is only twice as fast as this
pathological case (and hence presumably much slower than "\\s-+$" when
\n is not whitespace).



        Stefan

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Noam Postavsky]

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

On Wed, Mar 15, 2017 at 4:26 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> because "[\s\t]+$" shouldn't backtrack.  Using "\\s-+$" with
> a syntax-table that puts \n in the whitespace syntax is indeed asking
> for trouble, but I'm surprised "[\s\t]+$" is only twice as fast as this
> pathological case (and hence presumably much slower than "\\s-+$" when
> \n is not whitespace).

Why should one backtrack and not the other? The *2 ratio seems to hold
for both pathologically slow and normal case. Matching against a
sequence of non-trailing whitespace seens to have quadradic complexity
(see attached, timings are from an elisp buffer), does that give you
any hints?

[-- Attachment #2: trailing-ws-regexp-benchmark.el --]
[-- Type: text/x-emacs-lisp, Size: 1952 bytes --]

;; Pathological case, both seem to be quadratic in the length of a whitespace sequence.
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 1000 ?\s) "X")))"Elapsed time: 0.090000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 2000 ?\s) "X")))"Elapsed time: 0.258000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 4000 ?\s) "X")))"Elapsed time: 0.630000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 8000 ?\s) "X")))"Elapsed time: 2.260000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 16000 ?\s) "X")))"Elapsed time: 9.306000s"

(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 1000 ?\s) "X")))"Elapsed time: 0.395000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 2000 ?\s) "X")))"Elapsed time: 0.347000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 4000 ?\s) "X")))"Elapsed time: 1.282000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 8000 ?\s) "X")))"Elapsed time: 5.051000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 16000 ?\s) "X")))"Elapsed time: 20.144000s"

;; Normal case, linear.
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 8000 ?_) "X")))"Elapsed time: 0.001000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 16000 ?_) "X")))"Elapsed time: 0.002000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 32000 ?_) "X")))"Elapsed time: 0.003000s"
(benchmark 1 `(string-match "[\s\t]+$" ,(concat (make-string 64000 ?_) "X")))"Elapsed time: 0.007000s"

(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 8000 ?_) "X")))"Elapsed time: 0.004000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 16000 ?_) "X")))"Elapsed time: 0.008000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 32000 ?_) "X")))"Elapsed time: 0.016000s"
(benchmark 1 `(string-match "\\s-+$" ,(concat (make-string 64000 ?_) "X")))"Elapsed time: 0.031000s"

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Stefan Monnier]

> Why should one backtrack and not the other? The *2 ratio seems to hold
> for both pathologically slow and normal case. Matching against a
> sequence of non-trailing whitespace seens to have quadradic complexity
> (see attached, timings are from an elisp buffer), does that give you
> any hints?

Yes, it's normal: the "search" attempts a "match" from every whitespace.
So if you have N consecutive whitespace chars in the middle of line,
that gives you N attempts to "match" and every attempt takes O(N) steps
to find that the end of the whitespace is not an LF.

I don't understand how "\\s-+$" can be significantly faster than
"[\s\t]+$" in this respect.


        Stefan

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Noam Postavsky]

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

On Wed, Mar 15, 2017 at 10:52 PM, Stefan Monnier
<monnier@iro.umontreal.ca> wrote:
> Yes, it's normal: the "search" attempts a "match" from every whitespace.
> So if you have N consecutive whitespace chars in the middle of line,
> that gives you N attempts to "match" and every attempt takes O(N) steps
> to find that the end of the whitespace is not an LF.
>
> I don't understand how "\\s-+$" can be significantly faster than
> "[\s\t]+$" in this respect.

What?  I though I said "\\s-+" is *slower* (though only by a factor of 2).

Anyway, how about the attached which removes the syntax table stuff.

[-- Attachment #2: 0001-Simplify-delete-trailing-whitespace-by-dropping-synt.patch --]
[-- Type: text/x-patch, Size: 1669 bytes --]

From 2275487232b96ca782ca671d60be002e3948a764 Mon Sep 17 00:00:00 2001
From: Noam Postavsky <npostavs@gmail.com>
Date: Wed, 15 Mar 2017 23:01:13 -0400
Subject: [PATCH] Simplify delete-trailing-whitespace by dropping syntax tables

* lisp/simple.el (delete-trailing-whitespace): Just match [[:blank:]]
independently of current syntax table.
---
 lisp/simple.el | 15 +++++++--------
 1 file changed, 7 insertions(+), 8 deletions(-)

diff --git a/lisp/simple.el b/lisp/simple.el
index 369fbf7192..2cf8c13225 100644
--- a/lisp/simple.el
+++ b/lisp/simple.el
@@ -630,14 +630,13 @@ delete-trailing-whitespace
     (save-excursion
       (let ((end-marker (and end (copy-marker end))))
         (goto-char (or start (point-min)))
-        (with-syntax-table (make-syntax-table (syntax-table))
-          ;; Don't delete formfeeds, even if they are considered whitespace.
-          (modify-syntax-entry ?\f "_")
-          (while (re-search-forward "\\s-$" end-marker t)
-            (skip-syntax-backward "-" (line-beginning-position))
-            (let ((b (point)) (e (match-end 0)))
-              (when (region-modifiable-p b e)
-                (delete-region b e)))))
+        ;; Note that trying to match all the trailing whitespace with
+        ;; just the regexp can be very slow (Bug#26079).
+        (while (re-search-forward "[[:blank:]]$" end-marker t)
+          (skip-syntax-backward "-" (line-beginning-position))
+          (let ((b (point)) (e (match-end 0)))
+            (when (region-modifiable-p b e)
+              (delete-region b e))))
         (if end
             (set-marker end-marker nil)
           ;; Delete trailing empty lines.
-- 
2.11.1

Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again

[Stefan Monnier]

>> I don't understand how "\\s-+$" can be significantly faster than
>> "[\s\t]+$" in this respect.
> What?  I though I said "\\s-+" is *slower* (though only by a factor of 2).

The bug#26079 seems to indicate that the old Emacs-25 code was a lot faster.

Oh, I see.  It's that the old code used "\\s-$" rather than "\\s-+$".
Yes, that old code does avoid the quadratic effect this way.


        Stefan