shithub: libmujs

Download patch

ref: a2b628c9cbb85d2b6fbffe91b1f66e9b915e29f0
parent: dd0a0972b4428771e6a3887da2210c7c9dd40f9c
author: Avi Halachmi (:avih) <avihpit@yahoo.com>
date: Wed Feb 16 06:35:09 EST 2022

array join: avoid strcat, speedup from O(N^2) to O(N)

Previously, each iteration (except the 1st) did this amount of calls:
  2x strlen(result-so-far) + 2x strlen(element) + strlen(sep)
Where except one strlen(element) they're implicit inside strcat, and
of sizes which we already know.

Now each iteration does one strlen(element), and no strcat.

The big speedup is avoiding strlen of the result so far (twice) on
each iteration - O(N^2), but the other extra 2x strlen can add up too.

Join of an array of 2000 strings of 80 chars each:
  Windows: before: 80ms, after: 2ms
  Linux:   before: 20ms, after: 2ms
Measured using Date.now()

--- a/jsarray.c

+++ b/jsarray.c

@@ -91,7 +91,7 @@

 	const char *sep;

 	const char *r;

 	int seplen;

-	int k, n, len;

+	int k, n, len, outlen, rlen;

 	len = js_getlength(J, 0);

@@ -120,20 +120,22 @@

 			r = "";

 		else

 			r = js_tostring(J, -1);

-		n += strlen(r);

+		outlen = n - 1;

+		rlen = strlen(r);

+		n += rlen;

 		if (k == 0) {

 			if (n > JS_STRLIMIT)

 				js_rangeerror(J, "invalid string length");

 			out = js_malloc(J, (int)n);

-			strcpy(out, r);

+			memcpy(out, r, rlen + 1);

 		} else {

 			n += seplen;

 			if (n > JS_STRLIMIT)

 				js_rangeerror(J, "invalid string length");

 			out = js_realloc(J, out, (int)n);

-			strcat(out, sep);

-			strcat(out, r);

+			memcpy(out + outlen, sep, seplen);

+			memcpy(out + outlen + seplen, r, rlen + 1);

 		}

 		js_pop(J, 1);