From: Noam Postavsky <npostavs@users.sourceforge.net>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: Emacs developers <emacs-devel@gnu.org>
Subject: Re: [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again
Date: Wed, 15 Mar 2017 20:18:24 -0400 [thread overview]
Message-ID: <CAM-tV-9SZNuq0L9D5OEVSArL85og4jvDXU60MeyXZ0U_PHut+A@mail.gmail.com> (raw)
In-Reply-To: <jwvinnap9vc.fsf-monnier+gmane.emacs.devel@gnu.org>
[-- 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"
next prev parent reply other threads:[~2017-03-16 0:18 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20170315023157.29463.36647@vcs0.savannah.gnu.org>
[not found] ` <20170315023159.30AA520CAB@vcs0.savannah.gnu.org>
2017-03-15 11:28 ` [Emacs-diffs] master c66aaa6: Recomplexify ‘delete-trailing-whitespace’ by treating \n as whitespace again Stefan Monnier
2017-03-15 12:09 ` Noam Postavsky
2017-03-15 14:50 ` Stefan Monnier
2017-03-15 17:05 ` Noam Postavsky
2017-03-15 20:26 ` Stefan Monnier
2017-03-16 0:18 ` Noam Postavsky [this message]
2017-03-16 2:52 ` Stefan Monnier
2017-03-16 3:04 ` Noam Postavsky
2017-03-16 3:08 ` Stefan Monnier
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAM-tV-9SZNuq0L9D5OEVSArL85og4jvDXU60MeyXZ0U_PHut+A@mail.gmail.com \
--to=npostavs@users.sourceforge.net \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.