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

[Noam Postavsky <npostavs@users.sourceforge.net>]

[-- 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"