Making `replace-match' more efficient

Making `replace-match' more efficient

[Lars Ingebrigtsen]

We use `replace-match' a lot in our code (either directly or
indirectly), and I was poking at it to see whether there's any obvious
opportunities to make it faster, and immediately found a way to make
`replace-regexp-in-string' 10% faster in the by just checking whether
the replacement contains any backslashes or not.  (It's f2bd2386a79.)

So I poked at it some more, and thought that the exploratory patch below
seemed like an obvious way to make it generate less garbage, but the
performance impact was exactly zero, so I ditched that.

But it still seems like there's still opportunities for making it faster
in many common cases.  For instance, the most popular REPLACE string is
"", which should be exploitable...

Anyway, I'm just posting this here in case it inspires somebody to
explore.

diff --git a/src/search.c b/src/search.c
index 08f1e9474f..5471e05c0f 100644
--- a/src/search.c
+++ b/src/search.c
@@ -2501,9 +2501,6 @@ DEFUN ("replace-match", Freplace_match, Sreplace_match, 1, 5, 0,
     {
       Lisp_Object before, after;
 
-      before = Fsubstring (string, make_fixnum (0), make_fixnum (sub_start));
-      after = Fsubstring (string, make_fixnum (sub_end), Qnil);
-
       /* Substitute parts of the match into NEWTEXT
 	 if desired.  */
       if (NILP (literal))
@@ -2598,6 +2595,30 @@ DEFUN ("replace-match", Freplace_match, Sreplace_match, 1, 5, 0,
       else if (case_action == cap_initial)
 	newtext = Fupcase_initials (newtext);
 
+      if (SBYTES (string) == SCHARS (string)
+	  && SBYTES (newtext) == SCHARS (newtext)
+	  && !string_intervals (string)
+	  && !string_intervals (newtext))
+	{
+	  char *conc;
+	  ptrdiff_t len = sub_start + SBYTES (newtext) +
+	    SBYTES (string) - sub_end;
+
+	  conc = xmalloc (len);
+	  memcpy (conc, SSDATA (string), sub_start);
+	  memcpy (conc + sub_start, SSDATA (newtext), SBYTES (newtext));
+	  memcpy (conc + sub_start + SBYTES (newtext),
+		  SSDATA (string) + sub_end,
+		  SBYTES (string) - sub_end);
+	  Lisp_Object result = make_unibyte_string (conc, len);
+
+	  xfree (conc);
+	  return result;
+	}
+      
+      before = Fsubstring (string, make_fixnum (0), make_fixnum (sub_start));
+      after = Fsubstring (string, make_fixnum (sub_end), Qnil);
+
       return concat3 (before, newtext, after);
     }
 

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: Making `replace-match' more efficient

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Date: Thu, 07 Oct 2021 20:33:00 +0200
> 
> +      if (SBYTES (string) == SCHARS (string)
> +	  && SBYTES (newtext) == SCHARS (newtext)

This is not enough to detect pure-ASCII strings, because such strings
are many times unibyte.  Perhaps this is one reason why you didn't see
any significant performance gains.

Re: Making `replace-match' more efficient

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

>> +      if (SBYTES (string) == SCHARS (string)
>> +	  && SBYTES (newtext) == SCHARS (newtext)
>
> This is not enough to detect pure-ASCII strings, because such strings
> are many times unibyte.  Perhaps this is one reason why you didn't see
> any significant performance gains.

It was just an exploratory patch.  I confirmed that this branch was
taken in my tests.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no