Repository: blitz-js/superjson
Pull request #94 (2021-01-21 18:30:43)

Fix Performance Regression
@simonedelmann [reported performance issues](https://blitzjs.slack.com/archives/C011EQ0J75M/p1611216056009200) with SuperJSON. This PR tries to solve them.


Patch:
diff --git a/.gitignore b/.gitignore
index 5a19e8a..0e75fe5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,3 @@
 node_modules
 dist
-coverage
\ No newline at end of file
+coverage
diff --git a/package.json b/package.json
index ebd117f..8271010 100644
--- a/package.json
+++ b/package.json
@@ -58,7 +58,7 @@
     "url": "https://github.com/blitz-js/superjson"
   },
   "devDependencies": {
-    "@types/lodash": "^4.14.161",
+    "@types/lodash": "^4.14.168",
     "@types/mongodb": "^3.5.27",
     "benchmark": "^2.1.4",
     "eslint-plugin-es5": "^1.5.0",
diff --git a/src/annotator.ts b/src/annotator.ts
index b1ab5ee..aadaeec 100644
--- a/src/annotator.ts
+++ b/src/annotator.ts
@@ -44,10 +44,11 @@ class ValueAnnotationFactory {
   private tree = PathTree.create<TypeAnnotation | null>(null);
 
   add(path: any[], annotation: TypeAnnotation) {
-    this.tree = PathTree.append(this.tree, path.map(String), annotation);
+    PathTree.append(this.tree, path, annotation);
   }
 
   create() {
+    PathTree.compress(this.tree);
     return PathTree.collapseRoot(this.tree);
   }
 }
@@ -75,7 +76,7 @@ class ReferentialEqualityAnnotationFactory {
 
       let identities = PathTree.create<string | null>(null);
       identicalPaths.forEach(identicalPath => {
-        identities = PathTree.appendPath(identities, identicalPath);
+        PathTree.appendPath(identities, identicalPath);
       });
 
       const minimizedIdentities = PathTree.collapseRoot(identities);
@@ -83,7 +84,7 @@ class ReferentialEqualityAnnotationFactory {
         throw new Error('Illegal State');
       }
 
-      tree = PathTree.append(tree, shortestPath, minimizedIdentities);
+      PathTree.append(tree, shortestPath, minimizedIdentities);
     });
 
     return PathTree.collapseRoot(tree);
diff --git a/src/pathtree.ts b/src/pathtree.ts
index 2edbe7f..a042d88 100644
--- a/src/pathtree.ts
+++ b/src/pathtree.ts
@@ -1,6 +1,6 @@
 import { stringifyPath, parsePath } from './pathstringifier';
 import { isUndefined, isNull, isArray, isPlainObject } from './is';
-import { forEach, every, find } from 'lodash';
+import { forEach, every } from 'lodash';
 
 export type Tree<T> = InnerNode<T> | Leaf<T>;
 type Leaf<T> = [T];
@@ -23,14 +23,6 @@ export function isTree<T>(
   return false;
 }
 
-function isPrefixOf<T>(potentialPrefix: T[], of: T[]): boolean {
-  if (potentialPrefix.length > of.length) {
-    return false;
-  }
-
-  return potentialPrefix.every((value, index) => value === of[index]);
-}
-
 export module PathTree {
   export function create<T>(value: T): Tree<T> {
     return [value];
@@ -56,52 +48,23 @@ export module PathTree {
   /**
    * @description Optimised for adding new leaves. Does not support adding inner nodes.
    */
-  export function append<T>(tree: Tree<T>, path: string[], value: T): Tree<T> {
+  export function append<T>(tree: Tree<T>, path: string[], value: T) {
     if (path.length === 0) {
-      if (tree.length === 1) {
-        return [value];
-      } else {
-        const [, children] = tree;
-        return [value, children];
-      }
+      tree[0] = value;
+      return;
     }
 
     if (tree.length === 1) {
-      const [nodeValue] = tree;
-      return [nodeValue, { [stringifyPath(path)]: [value] }];
+      ((tree as any) as InnerNode<T>)[1] = { [stringifyPath(path)]: [value] };
     } else {
-      const [nodeValue, children] = tree;
-      const availablePaths = Object.keys(children);
-
-      // due to the constraints mentioned in the functions description,
-      // there may be prefixes of `path` already set, but no extensions of it.
-      // If there's such a prefix, we'll find it.
-      const prefix = find(availablePaths, candidate =>
-        isPrefixOf(parsePath(candidate), path)
-      );
-
-      if (isUndefined(prefix)) {
-        return [nodeValue, { ...children, [stringifyPath(path)]: [value] }];
-      } else {
-        const pathWithoutPrefix = path.slice(parsePath(prefix).length);
-        return [
-          nodeValue,
-          {
-            ...children,
-            [prefix]: append(children[prefix], pathWithoutPrefix, value),
-          },
-        ];
-      }
+      tree[1][stringifyPath(path)] = [value];
     }
   }
 
-  export function appendPath(
-    tree: Tree<string | null>,
-    path: string[]
-  ): Tree<string | null> {
+  export function appendPath(tree: Tree<string | null>, path: string[]) {
     const front = path.slice(0, path.length - 1);
     const last = path[path.length - 1];
-    return append(tree, front, last);
+    append(tree, front, last);
   }
 
   /**
@@ -198,4 +161,52 @@ export module PathTree {
 
     return [null, tree];
   }
+
+  /**
+   * @description Compress nested trees for smaller output
+   */
+  export function compress<T>(tree: Tree<T | null>) {
+    if (tree.length === 1) {
+      // tree root is Leaf
+      return;
+    }
+
+    const origin = tree[1];
+    const keys = Object.keys(origin).sort((a, b) => a.length - b.length);
+    const transformed: Record<string, Tree<T | null>> = {};
+
+    for (let i = 0; i < keys.length; i++) {
+      const key = keys[i];
+
+      let parentKey = undefined;
+      let splittedKey = key.split('.');
+      while (splittedKey.length > 0) {
+        splittedKey.pop();
+        const possibleParentKey = splittedKey.join('.');
+        if (transformed.hasOwnProperty(possibleParentKey)) {
+          parentKey = possibleParentKey;
+          break;
+        }
+      }
+      if (parentKey && transformed[parentKey]) {
+        transformed[parentKey][1] = Object.assign(
+          transformed[parentKey][1] || {},
+          {
+            [key.substring(parentKey.length + 1)]: origin[key],
+          }
+        );
+        continue;
+      } else {
+        transformed[key] = origin[key];
+      }
+    }
+
+    // Recursive optimization
+    const transformedKeys = Object.keys(transformed);
+    for (let i = 0; i < transformedKeys.length; i++) {
+      compress(transformed[transformedKeys[i]]);
+    }
+
+    tree[1] = transformed;
+  }
 }
diff --git a/yarn.lock b/yarn.lock
index d3373d6..99f32d7 100644
--- a/yarn.lock
+++ b/yarn.lock
@@ -1116,10 +1116,10 @@
   resolved "https://registry.yarnpkg.com/@types/json5/-/json5-0.0.29.tgz#ee28707ae94e11d2b827bcbe5270bcea7f3e71ee"
   integrity sha1-7ihweulOEdK4J7y+UnC86n8+ce4=
 
-"@types/lodash@^4.14.161":
-  version "4.14.161"
-  resolved "https://registry.yarnpkg.com/@types/lodash/-/lodash-4.14.161.tgz#a21ca0777dabc6e4f44f3d07f37b765f54188b18"
-  integrity sha512-EP6O3Jkr7bXvZZSZYlsgt5DIjiGr0dXP1/jVEwVLTFgg0d+3lWVQkRavYVQszV7dYUwvg0B8R0MBDpcmXg7XIA==
+"@types/lodash@^4.14.168":
+  version "4.14.168"
+  resolved "https://registry.yarnpkg.com/@types/lodash/-/lodash-4.14.168.tgz#fe24632e79b7ade3f132891afff86caa5e5ce008"
+  integrity sha512-oVfRvqHV/V6D1yifJbVRU3TMp8OT6o6BG+U9MkwuJ3U8/CsDHvalRpsxBqivn71ztOFZBTfJMvETbqHiaNSj7Q==
 
 "@types/mongodb@^3.5.27":
   version "3.5.27"


Test patch:
diff --git a/src/index.test.ts b/src/index.test.ts
index e483fcb..2012c6f 100644
--- a/src/index.test.ts
+++ b/src/index.test.ts
@@ -792,6 +792,45 @@ test('regression #83: negative zero', () => {
   expect(1 / parsed).toBe(-Infinity);
 });
 
+test('performance regression', () => {
+  const data: any[] = [];
+  for (let i = 0; i < 100; i++) {
+    let nested1 = [];
+    let nested2 = [];
+    for (let j = 0; j < 10; j++) {
+      nested1[j] = {
+        createdAt: new Date(),
+        updatedAt: new Date(),
+        innerNested: {
+          createdAt: new Date(),
+          updatedAt: new Date(),
+        },
+      };
+      nested2[j] = {
+        createdAt: new Date(),
+        updatedAt: new Date(),
+        innerNested: {
+          createdAt: new Date(),
+          updatedAt: new Date(),
+        },
+      };
+    }
+    const object = {
+      createdAt: new Date(),
+      updatedAt: new Date(),
+      nested1,
+      nested2,
+    };
+    data.push(object);
+  }
+
+  const t1 = Date.now();
+  SuperJSON.serialize(data);
+  const t2 = Date.now();
+  const duration = t2 - t1;
+  expect(duration).toBeLessThan(500);
+});
+
 test('regression #95: no undefined', () => {
   const input: unknown[] = [];
 
diff --git a/src/pathtree.test.ts b/src/pathtree.test.ts
index 56a2f18..cb642c7 100644
--- a/src/pathtree.test.ts
+++ b/src/pathtree.test.ts
@@ -3,19 +3,22 @@ import { PathTree } from './pathtree';
 test('pathtree', () => {
   let tree = PathTree.create<string | null>(null);
 
-  tree = PathTree.append(tree, ['abc'], '1');
+  PathTree.append(tree, ['abc'], '1');
 
   expect(tree).toEqual([null, { abc: ['1'] }]);
 
-  tree = PathTree.append(tree, ['abc', 'd'], '2');
+  PathTree.append(tree, ['abc', 'd'], '2');
+  PathTree.compress(tree);
 
   expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }] }]);
 
-  tree = PathTree.append(tree, ['foo', 'bar'], '3');
+  PathTree.append(tree, ['foo', 'bar'], '3');
+  PathTree.compress(tree);
 
   expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }], 'foo.bar': ['3'] }]);
 
-  tree = PathTree.append(tree, ['foo', 'bar', 'lel', 'lol'], '4');
+  PathTree.append(tree, ['foo', 'bar', 'lel', 'lol'], '4');
+  PathTree.compress(tree);
 
   expect(tree).toEqual([
     null,