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

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

[Marcin Borkowski]

Hi all,

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?  If so, is it documented anywhere?  (It would be fine
with me if it weren't, this is not to say that the docs are buggy
without mentioning it, I'm just curious.)

TIA,

-- 
Marcin Borkowski
http://mbork.pl

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

[Stefan Monnier]

> 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.

Maybe you're confusing it with `looking-back` which is much slower than
`looking-at`?


        Stefan

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

[Marcin Borkowski]

On 2021-04-12, at 17:13, 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)?

> Maybe you're confusing it with `looking-back` which is much slower than
> `looking-at`?

Yes, that was it!  Thanks!

Best,

-- 
Marcin Borkowski
http://mbork.pl

RE: [External] : Re: Performance of `re-search-backward' vs `re-search-forward'

[Drew Adams]

> So both basically move character by character and check if the regex
> matches there (more or less)?

They don't move character by character.
They use the Boyer-Moore search algorithm.

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

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

[Stefan Monnier]

>>> 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`.


        Stefan

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

[Stefan Monnier]

>> So both basically move character by character and check if the regex
>> matches there (more or less)?
> They don't move character by character.
> They use the Boyer-Moore search algorithm.
> https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

While this is true in the special case where your regexp only matches
a constant string (i.e. you could have used the non-re
`search-(for|back)ward` instead), it's a rare exception.  In the vast
majority of cases it does move character by character.


        Stefan

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