Re: Performance of `re-search-backward' vs `re-search-forward'

[Marcin Borkowski]

On 2021-04-12, at 22:59, Stefan Monnier <monnier@iro.umontreal.ca> wrote:

>>>> I seem to (very vaguely) remember reading that `re-search-backward' is
>>>> significantly slower than `re-search-forward'.  However, I can't find
>>>> anything about it in the docstring (nor in the Elisp reference) now.  Am
>>>> I even correct?
>>> I haven't looked at the code recently so my memory might be off, but
>>> I can't think of any reason why it should be noticeably slower, no.
>> So both basically move character by character and check if the regex
>> matches there (more or less)?
>
> Yes, they're more or less loops that move char-by-char and call
> `looking-at` each time.  The `looking-at` is always doing a "forward
> match" even if the outer loop is search backward, which is why the
> performance difference should be negligible even if there might be
> a difference in the performance of the outer loop.
>
>
>>> Maybe you're confusing it with `looking-back` which is much slower than
>>> `looking-at`?
>> Yes, that was it!  Thanks!
>
> Right: `looking-back` is actually doing a `re-search-backward` so it has
> an outer loop which calls `looking-at` each time, hence it's O(n) times
> slower than `looking-at`.

Thanks for the explanation!

-- 
Marcin Borkowski
http://mbork.pl