* Performance of `re-search-backward' vs `re-search-forward'
@ 2021-04-12 5:38 Marcin Borkowski
2021-04-12 15:13 ` Stefan Monnier
0 siblings, 1 reply; 7+ messages in thread
From: Marcin Borkowski @ 2021-04-12 5:38 UTC (permalink / raw
To: Help Gnu Emacs mailing list
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Performance of `re-search-backward' vs `re-search-forward'
2021-04-12 5:38 Performance of `re-search-backward' vs `re-search-forward' Marcin Borkowski
@ 2021-04-12 15:13 ` Stefan Monnier
2021-04-12 19:39 ` Marcin Borkowski
0 siblings, 1 reply; 7+ messages in thread
From: Stefan Monnier @ 2021-04-12 15:13 UTC (permalink / raw
To: help-gnu-emacs
> 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Performance of `re-search-backward' vs `re-search-forward'
2021-04-12 15:13 ` Stefan Monnier
@ 2021-04-12 19:39 ` Marcin Borkowski
2021-04-12 20:40 ` [External] : " Drew Adams
2021-04-12 20:59 ` Stefan Monnier
0 siblings, 2 replies; 7+ messages in thread
From: Marcin Borkowski @ 2021-04-12 19:39 UTC (permalink / raw
To: Stefan Monnier; +Cc: help-gnu-emacs
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
^ permalink raw reply [flat|nested] 7+ messages in thread
* RE: [External] : Re: Performance of `re-search-backward' vs `re-search-forward'
2021-04-12 19:39 ` Marcin Borkowski
@ 2021-04-12 20:40 ` Drew Adams
2021-04-12 21:03 ` Stefan Monnier
2021-04-12 20:59 ` Stefan Monnier
1 sibling, 1 reply; 7+ messages in thread
From: Drew Adams @ 2021-04-12 20:40 UTC (permalink / raw
To: Marcin Borkowski, Stefan Monnier; +Cc: help-gnu-emacs@gnu.org
> 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Performance of `re-search-backward' vs `re-search-forward'
2021-04-12 19:39 ` Marcin Borkowski
2021-04-12 20:40 ` [External] : " Drew Adams
@ 2021-04-12 20:59 ` Stefan Monnier
2021-04-13 6:07 ` Marcin Borkowski
1 sibling, 1 reply; 7+ messages in thread
From: Stefan Monnier @ 2021-04-12 20:59 UTC (permalink / raw
To: Marcin Borkowski; +Cc: help-gnu-emacs
>>> 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [External] : Re: Performance of `re-search-backward' vs `re-search-forward'
2021-04-12 20:40 ` [External] : " Drew Adams
@ 2021-04-12 21:03 ` Stefan Monnier
0 siblings, 0 replies; 7+ messages in thread
From: Stefan Monnier @ 2021-04-12 21:03 UTC (permalink / raw
To: Drew Adams; +Cc: help-gnu-emacs@gnu.org
>> 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
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: Performance of `re-search-backward' vs `re-search-forward'
2021-04-12 20:59 ` Stefan Monnier
@ 2021-04-13 6:07 ` Marcin Borkowski
0 siblings, 0 replies; 7+ messages in thread
From: Marcin Borkowski @ 2021-04-13 6:07 UTC (permalink / raw
To: Stefan Monnier; +Cc: help-gnu-emacs
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
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-04-13 6:07 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-04-12 5:38 Performance of `re-search-backward' vs `re-search-forward' Marcin Borkowski
2021-04-12 15:13 ` Stefan Monnier
2021-04-12 19:39 ` Marcin Borkowski
2021-04-12 20:40 ` [External] : " Drew Adams
2021-04-12 21:03 ` Stefan Monnier
2021-04-12 20:59 ` Stefan Monnier
2021-04-13 6:07 ` Marcin Borkowski
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.