[comp.emacs] Speed of replace-match vs. replace-string

hugh@ear.mit.edu (Hugh Secker-Walker) (02/14/91)

I was trying to speed up some code we use here.  I know it's dangerous
to assume anything about the speed with which forms evaluate based on
their "complexity", but here's my (counter-intuitive) finding using
"GNU Emacs 18.55.5 of Wed Oct 10 1990 on ear (berkeley-unix)", an
Ultrix 4.0 DECstation 3100.

The test case boils down to two functions, byte-compiled, which get
rid of occurrences of "ab".

(defun kill-ab-1 ()
  "The simple ab killer."
  (save-excursion
    (goto-char (point-min))
    (replace-string "ab" "")))

(defun kill-ab-2 ()
  "The complex ab killer."
  (save-excursion
    (goto-char (point-min))
    (while (search-forward "ab" nil t)
      (replace-match ""))))

Which runs faster on a buffer, freshly reverted from its file, which
contains 684,000 characters and 7,200 occurrences of "ab"?  Essentially
we're comparing (replace-string "ab" "") with
(while (search-forward "ab" nil t) (replace-match "")).

Surprise (you must have guessed) it turns out that kill-ab-2 runs in
about half the time of kill-ab-1.

This factor of two is just about my threshold for wondering if the
optimization is worth porting to existing code (some users are running
on VAXstation IIs).  Explanations?  Comments?

--
Hugh Secker-Walker                    INTERNET:  hugh@ear-ache.mit.edu
MIT, Research Lab of Electronics      UUCP:      mit-eddie!mit-athena!hugh

acevedo@athena.mit.edu (Gabriel) (02/17/91)

The reason is that kill-ab-1 is not as simple as it seems.
`replace-string' is NOT an elisp primitive function; it is defined in
`loaddefs.el', and it actually calls a rather complex function
`perform-replace', which is written in elisp. On the other hand,
`replace-match' is an elisp primitive. And, as always, the rule of thumb
is that elisp primitives run much faster than any substitute written in
elisp. 

To find out if a function is a lisp primitive or not, use `subrp':

subrp:
T if OBJECT is a built-in function.

--
Raul Acevedo
acevedo@athena.mit.edu

"Remember, Information is not knowledge; Knowledge is not Wisdom;
Wisdom is not truth; Truth is not beauty; Beauty is not love;
Love is not music; Music is the best."
	 - Frank Zappa