skip-chars-forward v. re-search-forward

skip-chars-forward v. re-search-forward

[Dave Love]

I've tended to use skip-chars-forward instead of re-search-forward
since it's byte-coded and I assumed it's more efficient.  However, I
made a measurement and found that skip-chars-forward was actually
slower than re-search-forward.

Is there a good reason for maintaining the two implementations?
Implementing skip-chars-forward using re-search-forward would have the
advantage that character classes would work with it, which they
currently don't.

Re: skip-chars-forward v. re-search-forward

[Andreas Schwab]

Dave Love <d.love@dl.ac.uk> writes:

|> I've tended to use skip-chars-forward instead of re-search-forward
|> since it's byte-coded and I assumed it's more efficient.  However, I
|> made a measurement and found that skip-chars-forward was actually
|> slower than re-search-forward.

Both skip-chars-forward and re-search-forward are builtin functions.  But
re-search-forward uses a cache for recently used regexps to avoid the
overhead of compiling it, whereas skip-chars-forward always sets up the
search map anew.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: skip-chars-forward v. re-search-forward

[Richard Stallman]

    I've tended to use skip-chars-forward instead of re-search-forward
    since it's byte-coded and I assumed it's more efficient.  However, I
    made a measurement and found that skip-chars-forward was actually
    slower than re-search-forward.

That is really surprising.  Can you figure out what makes
skip-chars-forward so slow?  We ought to be able to make it faster
than re-search-forward without much effort, so we may as well try.

Re: skip-chars-forward v. re-search-forward

[Richard Stallman]

    Both skip-chars-forward and re-search-forward are builtin functions.  But
    re-search-forward uses a cache for recently used regexps to avoid the
    overhead of compiling it, whereas skip-chars-forward always sets up the
    search map anew.

If skip-chars-forward had a cache, it would probably run faster
than regexp searching.

Re: skip-chars-forward v. re-search-forward

[Dave Love]

Andreas Schwab <schwab@suse.de> writes:

> But re-search-forward uses a cache for recently used regexps to
> avoid the overhead of compiling it, whereas skip-chars-forward
> always sets up the search map anew.

Yes, but that doesn't address the question.

Anyhow, caching doesn't account for the experimental data, at least
when searching a big buffer for a missing pattern.  re-search-forward
is faster in one-off use.

Re: skip-chars-forward v. re-search-forward

[Dave Love]

Richard Stallman <rms@gnu.org> writes:

> That is really surprising.  Can you figure out what makes
> skip-chars-forward so slow?

It would be best for a regexp expert to look at it.

> We ought to be able to make it faster than re-search-forward without
> much effort, so we may as well try.

I don't know enough for that to be clear to me, though it's suggested
by the separate implementation for the special case and
skip-chars-forward being byte-coded.  [Why not re-search-forward,
which must be more common?]

I could believe that the introduction of multibyte changed factors
which are relevant, but that's just a guess.

Re: skip-chars-forward v. re-search-forward

[Kenichi Handa]

In article <E19126X-0005aH-00@fencepost.gnu.org>, Richard Stallman <rms@gnu.org> writes:
>     I've tended to use skip-chars-forward instead of re-search-forward
>     since it's byte-coded and I assumed it's more efficient.  However, I
>     made a measurement and found that skip-chars-forward was actually
>     slower than re-search-forward.

> That is really surprising.  Can you figure out what makes
> skip-chars-forward so slow?  We ought to be able to make it faster
> than re-search-forward without much effort, so we may as well try.

I've just installed a fix for skip-chars-forward.  I think
the reason of the slowness was that it uses FETCH_CHAR
naively.  I changed the code to use the common technique of
*p, *stop, *endp.

The attached benchmark code (using a 25M-byte file that
doesn't contain "%" nor syntax `"') shows that now
skip-chars-forward/backward is slightly faster than
re-search-forward/backward.

(search-forward "%")           0.561530
(skip-chars-forward "^%")      1.174494
(re-search-forward "[%]")      1.239955
(skip-syntax-forward "^\"")    2.712070
(re-search-forward "\\s\"")    26.080168
(search-backward "%")          0.992879
(skip-chars-backward "^%")     3.079179
(re-search-backward "[%]")     10.005354

It's still surprising that search-forward/backward is more
than twice faster.  I have no idea what kind of magic the
boyer-moore search is using.

I tried it on GNU/Linux (devian).  Could someone please try
it on the different system?

---
Ken'ichi HANDA
handa@m17n.org

(defun benchtest ()
  (require 'benchmark)
  (save-excursion
    (let ((coding-system-for-read 'utf-8))
      (set-buffer
       (find-file-noselect "/project/mule/UNIDATA/Unihan-3.2.0.txt")))
    ;; It is sure that the buffer doesn't contain "%" nor syntax `"'.
    (concat
     (format "%-30S %f\n" '(search-forward "%")
	     (car (benchmark-run
		   10 (progn (goto-char 1)
			     (search-forward "%" nil 'move)))))
     (format "%-30S %f\n" '(skip-chars-forward "^%")
	     (car (benchmark-run
		   10 (progn (goto-char 1)
			     (skip-chars-forward "^%")))))
     (format "%-30S %f\n" '(re-search-forward "[%]")
	     (car (benchmark-run
		   10 (progn (goto-char 1)
			     (re-search-forward "[%]" nil 'move)))))
     (format "%-30S %f\n" '(skip-syntax-forward "^\"")
	     (car (benchmark-run
		   10 (progn (goto-char 1)
			     (skip-syntax-forward "^\"")))))
     (format "%-30S %f\n" '(re-search-forward "\\s\"")
	     (car (benchmark-run
		   10 (progn (goto-char 1)
			     (re-search-forward "\\s\"" nil 'move)))))
     (format "%-30S %f\n" '(search-backward "%")
	     (car (benchmark-run
		   10 (progn (goto-char (point-max))
			     (search-backward "%" nil 'move)))))
     (format "%-30S %f\n" '(skip-chars-backward "^%")
	     (car (benchmark-run
		   10 (progn (goto-char (point-max))
			     (skip-chars-backward "^%")))))
     (format "%-30S %f\n" '(re-search-backward "[%]")
	     (car (benchmark-run
		   10 (progn (goto-char (point-max))
			     (re-search-backward "[%]" nil 'move))))))))

Re: skip-chars-forward v. re-search-forward

[Richard Stallman]

    It's still surprising that search-forward/backward is more
    than twice faster.  I have no idea what kind of magic the
    boyer-moore search is using.

The comparison between search-forward and skip-chars-forward
does not seem meaningful to me, because they do different jobs.
The only case which both of these functions can do is
(search-forward "a") and (skip-chars-forward "^a").

The time taken by search-forward is inversely proportional to the
search string size in favorable cases, so if you tried a longer
string, it was probably faster.

Re: skip-chars-forward v. re-search-forward

[Dave Love]

Richard Stallman <rms@gnu.org> writes:

> The comparison between search-forward and skip-chars-forward
> does not seem meaningful to me, because they do different jobs.
> The only case which both of these functions can do is
> (search-forward "a") and (skip-chars-forward "^a").

That's probably not an uncommon use, and it looks as though the
optimizer might usefully translate one to the other.  I was originally
comparing with re-search-forward, though.  The skip-chars versions
still don't seem to have a big advantage, and they have the
disadvantage of not supporting char classes.

Re: skip-chars-forward v. re-search-forward

[Kenichi Handa]

In article <E199FUs-0003kd-00@fencepost.gnu.org>, Richard Stallman <rms@gnu.org> writes:
>     It's still surprising that search-forward/backward is more
>     than twice faster.  I have no idea what kind of magic the
>     boyer-moore search is using.

> The comparison between search-forward and skip-chars-forward
> does not seem meaningful to me, because they do different jobs.
> The only case which both of these functions can do is
> (search-forward "a") and (skip-chars-forward "^a").

That is what I did in my benchmark test.
  (search-forward "%")
    vs (skip-chars-forward "^%")
    vs (re-search-forward "[%]")

> The time taken by search-forward is inversely proportional to the
> search string size in favorable cases, so if you tried a longer
> string, it was probably faster.

Yes, I know that.  I was surprised because search-forward
was twice faster even if the search string size is one.

---
Ken'ichi HANDA
handa@m17n.org

Re: skip-chars-forward v. re-search-forward

[Richard Stallman]

    Yes, I know that.  I was surprised because search-forward
    was twice faster even if the search string size is one.

This could be a matter of how tightly coded the inner loop is.