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