From 838140fb82e696fb131f5c62c51c7b6dea56f3ad Mon Sep 17 00:00:00 2001
From: Marcos Casagrande <marcoscvp90@gmail.com>
Date: Wed, 16 Aug 2023 12:58:03 +0200
Subject: perf(ext/urlpattern): optimize URLPattern.exec (#20170)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This PR optimizes `URLPattern.exec`

- Use component keys from constructor instead of calling it on every
`.exec`. AFAIK keys should always be
`protocol`,`username`,`password`,`hostname`,`port`,`pathname`,`search`,`hash`.
Haven't looked much into it but I think it's safe to define these
outside the constructor as well.
- Add a fast path for `/^$/u` (default regexp) and empty input
- Replaced `ArrayPrototypeMap` & `ObjectFromEntries` with a `for` loop.


**this PR**
```
cpu: 13th Gen Intel(R) Core(TM) i9-13900H
runtime: deno 1.36.1 (x86_64-unknown-linux-gnu)

benchmark      time (avg)        iter/s             (min … max)       p75       p99      p995
--------------------------------------------------------------- -----------------------------
exec 1          2.17 µs/iter     461,022.8     (2.14 µs … 2.27 µs)   2.18 µs   2.27 µs   2.27 µs
exec 2          4.13 µs/iter     242,173.4     (4.08 µs … 4.27 µs)   4.15 µs   4.27 µs   4.27 µs
exec 3          2.55 µs/iter     391,508.1     (2.53 µs … 2.68 µs)   2.56 µs   2.68 µs   2.68 µs
```

**main**
```
cpu: 13th Gen Intel(R) Core(TM) i9-13900H
runtime: deno 1.36.1 (x86_64-unknown-linux-gnu)

benchmark      time (avg)        iter/s             (min … max)       p75       p99      p995
--------------------------------------------------------------- -----------------------------
exec 1          2.45 µs/iter     408,092.4     (2.41 µs … 2.55 µs)   2.46 µs   2.55 µs   2.55 µs
exec 2          4.41 µs/iter     226,706.0   (3.49 µs … 399.56 µs)   4.39 µs   5.49 µs   6.07 µs
exec 3          2.99 µs/iter     334,833.4     (2.94 µs … 3.21 µs)   2.99 µs   3.21 µs   3.21 µs
```
---
 ext/url/01_urlpattern.js | 51 ++++++++++++++++++++++++++++++------------------
 1 file changed, 32 insertions(+), 19 deletions(-)

(limited to 'ext')

diff --git a/ext/url/01_urlpattern.js b/ext/url/01_urlpattern.js
index 04bb50fd7..e6d21e49d 100644
--- a/ext/url/01_urlpattern.js
+++ b/ext/url/01_urlpattern.js
@@ -12,10 +12,7 @@ const ops = core.ops;
 import * as webidl from "ext:deno_webidl/00_webidl.js";
 const primordials = globalThis.__bootstrap.primordials;
 const {
-  ArrayPrototypeMap,
   ArrayPrototypePop,
-  ObjectFromEntries,
-  ObjectKeys,
   RegExpPrototypeExec,
   RegExpPrototypeTest,
   SafeRegExp,
@@ -24,6 +21,7 @@ const {
   TypeError,
 } = primordials;
 
+const EMPTY_MATCH = [""];
 const _components = Symbol("components");
 
 /**
@@ -37,6 +35,16 @@ const _components = Symbol("components");
  * @property {Component} search
  * @property {Component} hash
  */
+const COMPONENTS_KEYS = [
+  "protocol",
+  "username",
+  "password",
+  "hostname",
+  "port",
+  "pathname",
+  "search",
+  "hash",
+];
 
 /**
  * @typedef Component
@@ -64,19 +72,20 @@ class URLPattern {
 
     const components = ops.op_urlpattern_parse(input, baseURL);
 
-    const keys = ObjectKeys(components);
-    for (let i = 0; i < keys.length; ++i) {
-      const key = keys[i];
+    for (let i = 0; i < COMPONENTS_KEYS.length; ++i) {
+      const key = COMPONENTS_KEYS[i];
       try {
         components[key].regexp = new SafeRegExp(
           components[key].regexpString,
           "u",
         );
+        // used for fast path
+        components[key].matchOnEmptyInput =
+          components[key].regexpString === "^$";
       } catch (e) {
         throw new TypeError(`${prefix}: ${key} is invalid; ${e.message}`);
       }
     }
-
     this[_components] = components;
   }
 
@@ -144,9 +153,8 @@ class URLPattern {
 
     const values = res[0];
 
-    const keys = ObjectKeys(values);
-    for (let i = 0; i < keys.length; ++i) {
-      const key = keys[i];
+    for (let i = 0; i < COMPONENTS_KEYS.length; ++i) {
+      const key = COMPONENTS_KEYS[i];
       if (!RegExpPrototypeTest(this[_components][key].regexp, values[key])) {
         return false;
       }
@@ -185,21 +193,26 @@ class URLPattern {
     /** @type {URLPatternResult} */
     const result = { inputs };
 
-    const keys = ObjectKeys(values);
-    for (let i = 0; i < keys.length; ++i) {
-      const key = keys[i];
+    for (let i = 0; i < COMPONENTS_KEYS.length; ++i) {
+      const key = COMPONENTS_KEYS[i];
       /** @type {Component} */
       const component = this[_components][key];
       const input = values[key];
-      const match = RegExpPrototypeExec(component.regexp, input);
+
+      const match = component.matchOnEmptyInput && input === ""
+        ? EMPTY_MATCH // fast path
+        : RegExpPrototypeExec(component.regexp, input);
+
       if (match === null) {
         return null;
       }
-      const groupEntries = ArrayPrototypeMap(
-        component.groupNameList,
-        (name, i) => [name, match[i + 1] ?? ""],
-      );
-      const groups = ObjectFromEntries(groupEntries);
+
+      const groups = {};
+      const groupList = component.groupNameList;
+      for (let i = 0; i < groupList.length; ++i) {
+        groups[groupList[i]] = match[i + 1] ?? "";
+      }
+
       result[key] = {
         input,
         groups,
-- 
cgit v1.2.3