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

[Stefan Monnier <monnier@iro.umontreal.ca>]

> 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